Parallélisation
Les algorithmes de rendu par lancé de rayons que nous avons présentés sont fortement parallélisable :
Les données de scène ne varient pas durant le rendu. De plus, elles sont accédées uniquement en lecture, plusieurs threads peuvent donc les lire sans avoir à gérer des problématiques de concurrence.
Le calcul de la couleur d’un pixel est indépendant des autres pixels.
Principe
On doit découper la zone de rendu en sous-zones qui vont être distribuées aux threads disponibles. On pourrait avec n threads découper l’image en n zones. Cependant cette stratégie est mauvaise. En effet, certaines zones de l’image requièrent moins de calcul que d’autres du fait qu’elles contiennent moins d’objets comme par exemple un plafond. Ainsi en créant 1 zone par thread, les threads ayant fini le plus tôt vont attendre les threads traitant les parties les plus complexes de l’image. Par exemple, si 9 threads mettent 1, 2, 3 … 8 et 9 secondes à terminer, le temps global d’attente pour l’utilisateur est de 10 secondes alors que 5 secondes auraient dû suffire. Nous avons donc intérêt à découper l’image finale en de multiples zones. Chaque thread calcule ainsi plusieurs zones de l’image.
La double boucle en largeur et en hauteur du Raycasting peut se transformer facilement pour gérer une zone rectangulaire de l’image :
Chaque thread à son démarrage va lancer une requête pour demander une zone à calculer. Une fois cette zone terminée, il l’envoie à l’affichage et demande une autre zone dans la liste. S’il n’y en a plus, le thread s’arrête. Cette approche permet d’équilibrer la charge de calcul.
L : liste contenant les zones à calculer // structure de données gérant les accès concurrentiels
Tant que L non vide
Si Z = L.DemandeZone() existe
Calcul de l'image correspond à Z
Affichage de l'image sur la zone Z
Traditionnellement, sur un CPU possédant 6 cœurs, il semble judicieux de créer 6x2 threads. Le système deviendra cependant peu réactif car tous les cœurs seront occupés à 100%. Si vous voulez continuer à utiliser votre machine pendant les calculs, laissez un cœur de libre.
Simulation
Nous avons simulé un exemple avec 4 threads, chaque thread dispose de sa propre couleur : noir, gris foncé, gris clair, blanc. Chaque thread remplit sa zone avec une couleur unie, pour différencier leurs performances, le thread noir est 4x plus rapide, le gris foncé 3x, le gris clair 2x et le noir est notre référence. Voici le rendu en cours de simulation :
Les zones sont distribuées de haut en bas et de gauche à droite. Les threads les traitent et les affichent donc dans cet ordre. Dans la colonne la plus à droite, des carrés restent roses. Cela provient du fait que le thread noir est le plus rapide, ainsi lorsque le dernier carré noir est affiché, le thread blanc est encore en train de calculer sa zone qui n’est donc pas encore affichée, d’où la présence d’un carré rose, signe du retard d’un autre thread.
Dans notre exemple, le thread noir était le plus rapide, il a donc calculé le plus de zone de rendu dans notre image finale. Le thread blanc était le plus lent ; les zones blanches sont les moins nombreuses.
Multi-threads en C#
La mise en place du multi-threads peut être fait facilement dans le code à travers un simple appel de fonction. Cela est certes très pratique, mais il ne faut pas oublier que cette fonction va s’exécuter dans un thread tiers et qu’il a quelques concepts à prendre en compte. Voici quelques informations utiles :
Rappel : nous utilisons une application graphique/fenêtrée. Les différents composants (widgets) de la fenêtre appartiennent au thread principal de l’application. Celui-ci gère d’ailleurs tous les évènements que reçoit la fenêtre : déplacement, agrandissement, click bouton… Ce n’est pas parce que la fenêtre ne fait rien que ce thread n’existe pas. Il est juste en attente d’évènements extérieurs.
Les threads fils peuvent librement accéder aux ressources de la scène 3D car ils le font uniquement en lecture. Aucune précaution particulière n’est à prendre dans ce cas.
La liste des zones à dessiner représente une ressource partagée. Elle doit donc se synchroniser entre les différents threads enfants. Pour cela, C# fournit une classe très pratique nommée ConcurrentBag représentant une liste gérant la synchronisation entre threads, nous utiliserons donc cette classe. Merci de consulter sa documentation et ses exemples.
Chaque fois qu’un thread a traité une zone de l’image, il serait judicieux de l’afficher. Cependant, cela sous-entendrait qu’un thread fils modifie en écriture un objet appartenant au thread principal de la fenêtre et là c’est dangereux. Pour résoudre ce problème, nous utilisons une solution simple qui consiste à envoyer un évènement au thread principal qui sera donc exécuté de manière asynchrone mais par le thread propriétaire de la zone d’affichage. Cette approche utilise la méthode Invoke. Le thread fils utilise cette méthode pour « retourner » un bitmap contenant le rendu de la zone traitée. Le système se charge alors de transférer l’objet au thread principal pour affichage. Article : Faire un appel « safe call » vers le thread de la GUI grâce à la méthode Invoke
Exemple
Un exemple complet est disponible pour vous aider. Testez le pour vous familiariser avec cette approche :