Lancer de rayons dans un octree.: Utilisation de la connectivité via les coordonnées de Plücker

Most of the computation time in ray-tracing algorithms is spent traversing the accelerating structure. Usual bottlenecks are memory latency and branching. We present here an octree traversal algorithm which offers the best of both octrees and regular grid. This algorithm mostly uses the connectivity of the tree's leafs. Using the Plücker coordinates, it's possible to implement it in a way which keeps memory accesses coherent, while drastically limiting branching operations.L'essentiel du temps de calcul des systèmes de tracé de rayons est passé dans le parcours de la structure accélératrice. Les facteurs limitants de ce parcours sont la latence mémoire et le branchement. Nous proposons ici un algorithme de traversée d'octree alliant les bénéfices de l'arbre et ceux de la grille régulière. Celui-ci est basé sur l'utilisation de la connectivité entre les feuilles de l'arbre. Via les coordonnées de Plücker, il est possible de l'implémenter d'une façon qui maintienne un certaine cohérence des données, tout en limitant drastiquement le nombre de branchements