Un peu de technique (octree, raycasting)...

Un arbre en informatique est une structure de données fréquemment utilisée car elle permet d’agencer ces données de façon hiérarchique. Tout le monde l’utilise de façon quotidienne sans même s’en rendre compte en manipulant les fichiers de son ordinateur, en effet les systèmes de fichiers emploient une structure arborescente : il y a la racine du disque dur qui contient plusieurs fils (les dossiers), eux même contiennent d’autres fils (des sous dossiers) et ainsi de suite jusqu’aux feuilles (les fichiers). Cet exemple devrait vous donner une idée intuitive d’un des intérêts de l’utilisation d’arbres : accéder aux éléments d’un arbre équilibré est nettement plus rapide que si tous les éléments étaient éparpillés.

Les nœuds d’un arbre peuvent avoir un nombre différents de fils : lorsqu’il y a au plus deux fils on parle d’arbre binaire, zéro ou quatre fils arbre quaternaire et enfin lorsqu’il y a zéro ou huit fils on parle d’arbre octal. Mais quel est l’intérêt de ces arbres dans le cas qui nous intéresse ? Jusqu’à présent nous utilisions les voxels selon une grille régulière ce qui en fait gaspillait énormément de données pour encoder du vide, les octrees permettent d’utiliser plus efficacement l’espace mémoire en utilisant la résolution la plus fine uniquement là où c’est nécessaire. Penser en 3 dimensions n’est pas la chose la plus aisée qui soit et n’est pas facile à représenter dans un article, nous allons donc  commencer par présenter ça de façon bidimensionnelle.

Voici l’approximation du cercle, avec une grille de résolution 12 x 12. L’approximation est grossière faute d’une résolution suffisante et cependant une grosse quantité de cellules sont blanches et donc inutiles. Si nous utilisions un quadtree voilà ce que nous obtiendrions :

La construction du quatree est simple : on part de l’image initiale que l’on subdivise en deux selon les deux directions, nous obtenons quatre quadrants. Lorsqu’un quadrant est soit vide, soit entièrement plein l’algorithme s’arrête là. Si le quadrant n’est que partiellement rempli alors on subdivise de nouveau ce quadrant en quatre et ainsi de suite. L’algorithme s’arrête lorsque tous les quadrants sont homogènes c'est-à-dire uniformément vides ou pleins, ou plus traditionnellement lorsqu’une profondeur donné a été atteinte (dans l’exemple ci-dessus nous nous sommes arrêtés à une profondeur d’arbre de 4 c'est-à-dire une division de 16 dans chaque dimension). Comme vous pouvez le constater même avec notre exemple basique le résultat obtenu est un peu plus fidèle au cercle initial et pourtant nous utilisons moins de données (97 nœuds ou « cases » si vous préférez dans ce cas contre 122 avec la grille régulière). Un octree est une simple extension de cette technique à 3 dimensions. 

En pratique le gain en espace mémoire à définition égale est un peu moins important qu’on pourrait le penser de prime abord, en effet dans le cas d’une grille régulière la position des voxels est implicite. A l’inverse dans le cas d’un octree chaque nœud doit conserver un « lien » vers chacun de ses fils. En pratique il faut donc pour chaque nœud conserver 8 pointeurs en plus de la couleur et de la normale du voxel.

Mais ce n’est qu’un petit inconvénient face aux nombreux autres avantages de l’octree, pour bien comprendre les apports les plus importants de l’octree il faut tout d’abord décrire la façon dont cette structure de donnée est affichée. Il existe plusieurs manières d’afficher des voxels mais la technique choisie par id Software est le raycasting, c’est celle-ci que nous allons décrire.

Raycasting

Tout comme le raytracing, le raycasting repose sur le lancer de rayons pour chacun des pixels de l’image, mais là où il diffère c’est que dès qu’une intersection a été trouvée l’algorithme s’arrête là et ne lance pas de rayons secondaires.

Par conséquent le raycasting est plus rapide que le raytracing car comme nous l’avons vu dans notre précédent article ce sont les rayons secondaires qui posent problèmes du fait de leurs accès mémoires. Autre avantage : calculer l’intersection de rayons avec les voxels est beaucoup plus rapide qu’avec des triangles. De plus il est inutile de construire une structure de données supplémentaires pour accélérer ces calculs d’intersection : l’octree est à la fois l’ensemble des données  (géométrie et textures) et la structure d’accélération.