Il est temps de commencer à mettre les mains dans le cambouis, ne serait-ce que pour voir si la création d'un RayTracer (même simpliste) en temps réel est vraiment envisageable avec la technologie Flash d'Adobe.
Le but de cette série d'articles n'est pas d'expliquer le fonctionnement d'un RayTracer ou de détailler des formules mathématiques. Je ferai donc l'impasse sur certaines explications, sur lesquelles je pourrai toutefois revenir selon les commentaires reçus.
Première étape : la détection des collisions avec les volumes.
Cet Article fait partie d'une série. Il est fortement recommandé d'avoir lu les articles précédents pour y comprendre quelque chose…
Avant tout, petit résumé du mode de fonctionnement d'un RayTracer :
Le lancer de rayon consiste, pour chaque pixel de l'image générée, à lancer un rayon depuis le point de vue (la caméra) dans la scène 3D. Le premier point d'impact du rayon sur un objet définit l'objet concerné par le pixel correspondant.
Des rayons sont ensuite lancés depuis le point d'impact en direction de chaque source de lumière pour déterminer sa luminosité (est-il éclairé ou à l'ombre d'autres objets ?). Cette luminosité combinée avec la couleur de l'objet ainsi que d'autres informations éventuelles (angles entre la normale à l'objet et les sources de lumières, réflexions, transparence, etc.) déterminent la couleur finale du pixel. (Wikipédia)
Le schéma principal est donc une double boucle (une boucle dans une boucle) parcourant l'écran (pour chaque x de chaque ligne) et déterminant (pixel après pixel) la couleur à dessiner. Pour déterminer cette couleur on détermine d'abord si le point testé "appartient" à un des volumes (sphère, cube, plan, cone, …) de la scène que l'on souhaite calculer. On simule pour cela un "rayon" qui part du pixel de l'écran le long de l'axe des Z; Si ce rayon rentre en collision avec un des volumes présents, il faut calculer la couleur en fonction de la couleur de base de ce volume, mais aussi de la proximité d'une source lumineuse (dans ce cas ce pixel sera très éclairé), d'un autre volume (qui pourrait projeter une ombre sur ce point d'intersection), de la matière du volume, de sa transparence, …
Une fois ce principe "simple" compris, on peut passer au développement de la première étape : la détection de la collision avec les volumes. Dans un RayTracer, les volumes sont – en général - définis par une formule mathématique. Le plus simple et le plus classique est la sphère. Nous allons donc commencer par là…
Dans un espace en 3D, un point noté (x,y,z) appartient à une sphère de centre (xc,yc,zc) et de rayon rc si l'équation suivante est respectée :
(x-xc) 2 +(y-yc) 2 +(z-zc) 2 =rc 2
Dans le cas de notre double boucle, on connaît à chaque instant la valeur de x et de y (puisque c'est le point que l'on est en train de tester); on cherche donc z (qui est la donnée manquante pour déterminer précisément le point d'intersection avec cette sphère). L'équation précédente peut donc être développée de cette façon :
x 2 -2xxc+xc 2 +y 2 -2yyc+yc 2 +z 2 -2zzc+zc 2 -rc 2 =0
Puis
z 2 + (-2zc) z + (x 2 -2xxc+xc 2 +y 2 -2yyc+yc 2 +zc 2 -rc 2 )=0
Ce qui est une "simple" équation du second degré (type ax 2 +bx+c=0, avec z comme inconnue), que l'on apprend à résoudre au lycée (en tous cas de mon temps…). On commence par calculer le "discriminant" puis à tester son signe pour savoir si une solution existe. Si aucune solution n'existe (discriminant négatif) alors aucun point n'est solution de l'équation, donc il n'existe pas de point (avec ce x et ce y) qui entre en collision avec cette sphère. Si il existe une solution, on la trouve facilement (voir Wikipédia sur les équations du second degré…). Il faut pour chaque point tester la collision avec TOUTES les sphères (en tous cas dans un premier temps, on optimisera par la suite) et ne retenir que la sphère la plus proche (les autres etant cachée derrière, aucun intérêt). Ce qui revient en gros à 3 boucles imbriquées :
Pour chaque Y de l'écran
Pour chaque X de l'écran
Pour chaque volume de la scène
Tester si du point en cours, le rayon lancé entre en collision avec ce volume
Une fois ces premiers outils mathématiques assimilés, on peut mettre tout ça en place dans un projet Flash. Je commence par me créer une classe "RayTracer", une classe "Volume" (pour ce qui est commun à tous les types de volumes) et une classe "Sphere". Dans son script, Forrest Briggs (voir article précédent) n'utilise pas la POO (programmation orientée objet); dans l'objectif d'un gain de temps évidemment. Car développer en POO n'est en rien un gage de rapidité (bien au contraire parfois...). Appeler des méthodes ou propriétés d'un objet peut être plus long que de lire une simple variable. Toutefois je souhaite moi conserver l'approche POO, si pratique pour développer. Elle est aussi indispensable pour remplir un de mes objectifs (voir article précédent) : la possibilité d'utiliser ce RayTracer dans d'autres applications Flash.
Je choisis aussi une simplification extrême et sacrilège pour tout créateur en 3D : supprimer la notion de focale ! Cette notion , liée à celle de caméra et de perspective, permet - entre autre - de simuler la "profondeur" de la scène et donc de rendre les objets lointains plus petits que les objets proches. A priori donc une notion indispensable dans ce projet. Toutefois mon objectif n'est pas de créer des scènes complexes, mais plutôt d'afficher des objets simples et proches de l'écran. Supprimer la focale simplifiera aussi un peu les calculs, ce qui est le bienvenue... Les rayons partiront donc perpendiculairement à l'écran; la formule précédente peut donc être appliquée telle quelle pour chaque pixel.
Une fois tout cela mis en place j'obtiens pour une scène simple (3 sphères dont une mobile (la verte)) l'image suivante :
3 images par seconde ! une catastrophe !... Heureusement il y a de très nombreuses pistes d'optimisation à explorer...
Actuellement TOUS les pixels de l'image sont testés, alors qu'une part importante d'entre eux sont "loin" de toutes sphères. On va donc commencer par réduire la zone testée (et donc le nombre d'itérations des boucles imbriquées). Il est facile (puisque les rayons sont perpendiculaires à l'écran) de déterminer le point le plus à gauche (appartenant à une sphère), le point le plus à droite, le plus haut, le plus bas, ... Bref les nouvelles valeurs de départ et d'arrêt de nos boucles. On parle de "Bounding box". Dans notre cas cela accélère déjà énormément le traitement :
11 images par seconde ! La piste est bonne alors je la creuse... En effet en procédant ainsi de nombreux points de notre nouvelle zone de test sont encore loin des sphères (tous ceux ENTRE les sphères pour faire simple). je décide non pas de tester une seule grande zone, mais de créer autant de zones de test qu'il existe de volumes (=Bounding Box). Il s'agit donc d'avoir plusieurs zones, mais au plus près de chaque volume, pour diminuer le nombre de points "vides" testés. Attention, il faut que ces bounding box tiennent compte non seulement de la position actuelle des volumes, mais aussi de leur position précédente, sous peine de laisser des trainées (de points non re-testés) en cas de déplacement. Au passage je m'arrange pour ne pas tester 2 fois un pixel qui appartiendrait à plusieurs de ces zones. Je peux aussi simplifier la boucle sur les volumes testés, en supprimant progressivement des volumes à tester à chaque zone passée. Un pixel déjà déterminé (et appartenant à un volume) n'est plus à retester dans les autres zones (le premier test déterminant forcément l'objet le plus proche). Bref, pas mal de petites optimisations qui boostent les résultats :
En moyenne 20 images par seconde ! Le chiffre dépendant de la position des sphères les unes par rapport aux autres. Plus elles sont proches (voire se chevauchent), plus le chiffre est bon (puisque moins de pixels à tester).
J'envisage de créer des Bounding Box rondes (et non simplement rectangulaires); Toutefois le gain obtenu d'un coté est perdu par les calculs nécessaires à la détermination de ces cercles de test... Je laisse donc tomber.
Il existe de nombreuses autres méthodes d'optimisation à cette étape (comme les arbres binaires) mais qui ne sont pas forcément adaptée à mon cas, alors je décide de ne pas les utiliser.
J'essaie aussi d'optimiser les calculs, en mémorisant des valeurs (plutôt que de les recalculer à chaque itération), mais là surprise ! Accéder à une variable est largement plus long que de refaire certains calculs simples (comme une multiplication par exemple). Je dois donc tester chaque optimisation de ce genre pour être sûr de son intérêt. J'utilise aussi les "trucs" classiques d'optimisation (bon choix du type de données, décalage binaire pour remplacer les multiplications/divisions par les nombres pairs, ...). Les résultats sont mitigés, mais cela devait être fait et testé.
J'écris chaque pixel (dans un bitmapData) au moment où je le calcule, plutôt que de passer par un buffer (ByteArray ou autre) qui après tests se montre plus lent qu'une écriture directe.
J'utilise setPixel et non setPixel32. Tant pis pour la gestion de la transparence, mais le gain est vraiment sensible...
Une animation (pas une vidéo) pour tester en ligne (veillez à mettre à jour votre lecteur Flash pour bénéficier d'une vitesse optimale) :
Il me reste encore quelques pistes d'optimisations pour cette partie, mais j'y reviendrai ultérieurement. En l'état le FrameRate me semble suffisant pour passer à l'étape suivante : l'introduction de la lumière !
A suivre...