Philippe Ris Dr. Philippe RIS
183 rue du Général de Gaulle
78740 Vaux sur Seine
e-mail : contact.ris@free.fr


Thèse : Parallélisation du lancer de rayon par évaluation dynamique de la topologie de la scène

Cliquez sur le(s) chapitre(s) à charger (format PDF ou postscript zippé).


Mots clés : Rendu réaliste, Lancer de rayon, Parallélisme, Calculs distribués, Analyse des performances, Modélisation statistique, Calcul des variations, Taximonie des optimisations.

Dans cette thèse sur le lancer de rayon parallèle et l'analyse des performances, on distingue trois parties :

1) Nous présentons une formalisation du lancer de rayon à l'aide de quatre graphes : le graphe des objets réels (objets de la scène et boîtes englobantes), graphe des objets virtuels (rayons), graphe des processus (description algorithmique du programme) et le graphe des machines. Ce formalisme permet de décrire les différentes optimisations à travers la structuration des graphes. Une nouvelle taxinomie des méthodes d'optimisations tant séquentielles que parallèles est déduite.

2) Une optimisation parallèle du lancer de rayon basée sur l'exploitation d'informations topologiques déduites des calculs effectués est présentée. Cette méthode utilise un ensemble de règles logiques agissant au niveau des processus, ainsi que des messages échangés entre ceux-ci. Ces règles optimisent principalement les calculs sur les rayons primaires mais permettent aussi d'optimiser ceux concernant les rayons secondaires et d'ombre grâce à l'ajustement des boîtes englobantes. Elles sont accompagnées d'une seconde série de règles simples redéfinissant la notion de cohérence ainsi que d'une troisième applicable à l'animation.

3) La dernière partie est consacrée à l'analyse des performances selon deux approches. Dans un premier temps, le lancer de rayon est analysé pour en extraire un certain nombre de paramètres caractérisant les performances calculatoire. Un protocole de tests est défini ; ces tests sont indépendants de la machine et reproductibles. Dans un second temps, une version simplifiée de notre lancer de rayon est décrite mathématiquement par des moyens statistiques. Il est alors par exemple possible de donner une formule mathématique du gain de cette méthode et de rechercher grâce au calcul des variations le meilleur découpage écran maximisant ce gain. Cette approche encore limitée aux rayons primaires semble ouvrir de nouvelles pistes de recherche.

Les diplômes

Ph. RIS



La soutenance a eu lieu le vendredi 27 Septembre 1996 à l'université de Marne-La-Vallée, IFI, amphi F1
Cette thèse est une thèse de l'université de Franche-Comté




This PhD thesis presents our work in parallel ray-tracing. We can distinguish three parts in this work :

1) A ray-tracing formalisation based upon four graphs is presented : graph of real objects (scene objets and bounding boxes), graph of virtual objects (rays), graph of processes (algorithmical description of ray tracer) and the graph of computers. This formalisation makes the description of optimisation easier and is suitable for a new classification of classical methods, as well as new and parallel methods.

2) A parallel optimisation based upon dynamic acquisition of topological knowledge is presented. The method uses a set of logical rules computed by each process. The processes exchange messages that allow the reduction of ray/object intersection computation. Two other sets of rules about coherence and animation are given too.

3) The last part deals with performance analysis. In a first time, we analyse ray-tracing in order to extract relevant parameters. A test protocol is defined. These tests are not dependant on a computer and are repeatable. In a second time, a simple release of our ray tracer is mathematically described with statistics. It is then possible to give an equation of benefit for instance. The best tilling of screen can be found with a variation calculation of this equation. For the moment, this approach is only suitable for primary rays but it seems to open a new research domain.