Optimizing ray-tracing

Méthodes d'optimisation du tracé de rayons

Olivier Devillers (1)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure

Ray tracing is the only image synthesis technique which allows the rendering of specular effects. In this thesis we explore the use of space subdivisions for ray tracing optimization. We propose a new method of subdivision: the macro- regions. This structure is based on a grid where some places, having a low density of information, are enclosed into macro-regions. We present a theoretical and practical study of space subdivision methods: grid, octree, bounding boxes and macro-regions structure. The average cost of a ray is investigated both from a practical point of view using the results of an implementation of the algorithm, and from a theoritical one, using some results from stochastic geometry. This cost is divided into two parts, the average number of objects intersected by a ray and the average number of regions intersected by a ray. The analysis gives some means to compute the same numbers for other subdivision structures. Results exposed in this thesis show the efficiency of the macro-regions struc- ture.

Le tracé de rayons est la seule technique de synthèse d'images permettant le réalisation d'effets lumineux spéculaires. Cet algorithme est très coûteux en temps de calcul. Nous nous intéressons aux diverses méthodes d'optimisation du tracé de rayons basées sur la subdivision de l'espace. Nous proposons une structure de subdivision originale : les macro-régions. Cette structure utilise un grid dans lequel les éléments de grid appartenant à des zones à faible densité d'information sont regroupées en macro-régions. Nous présentons ensuite une étude théorique et pratique du coût de dif- férentes méthodes de subdivision de l'espace : grid, octree, boîtes englobantes et la structure de macro-régions. Le coût moyen d'un rayon est étudié d'un point de vue pratique d'après les résultats d'une implantation de l'algorithme, et théorique en utilisant des résultats de géométrie stochastique. Ce coût est divisé en deux parties, on calculera tout d'abord le nombre moyen d'objets rencontrés par un rayon, puis le nombre moyen de régions rencontrées par un rayon dans les différents cas de subdivision. Cette étude fournit un certain nombre de résultats généraux permettant de mener à bien les mêmes calculs pour d'autres structures. Les résultats exposés établissent l'efficacité de la subdivision par macro- régions.

Mots clés: Computer graphics

Mots clés: synthèse d'images; lancer de rayons; rendu réaliste; radiosité

Domaines: Synthèse d'image et réalité virtuelle [cs.GR]

Olivier Devillers. Méthodes d'optimisation du tracé de rayons. Synthèse d'image et réalité virtuelle [cs.GR]. Université Paris Sud - Paris XI, 1988. Français. ⟨NNT : ⟩. ⟨tel-00772857⟩