Le lancer de rayon est un algorithme permettant de représenter des scènes 3D de façon très réaliste. Son principe, simple et puissant, repose sur les lois de l'optique géométrique : l'image que voit un observateur est le fruit des interactions entre des photons 6mis par des sources lumineuses et des objets possédant des propriétés géométriques et optiques. L'utilisation d'un modèle basé sur la physique permet une bonne approche des phénomènes naturels suivants : l'éclairement par des sources lumineuses, la réflexion de la lumière sur des objets et la transmission de la lumière à travers des objets transparents. L'algorithme dérivant de ce modèle possède pourtant un inconvénient majeur : le temps de traitement d'une image est très important. Bien que de nombreuses méthodes d'accélération aient été proposées pour tenter d'améliorer sa vitesse d'exécution, ce problème demeure bien présent. Toutefois, avec le développement actuel des machines parallèles à mémoire distribuée et des réseaux d'ordinateurs, une voie d'accélération très prometteuse se développe : la parallélisation. De plus, la mise en commun des capacités ''mémoire" de chaque composante d'une architecture parallèle rend possible le traitement de scènes comportant un plus grand nombre d'objets aux propriétés de plus en plus complexes. Le chapitre 1 présente l'algorithme de lancer de rayon ainsi que les accélérations séquentielles proposées dans la littérature. D apparaît que les techniques les plus efficaces sont basées soit sur l'utilisation de volumes englobants soit sur des subdivisions de l'espace. Malgré ces optimisations, la parallélisation demeure la source d'accélération au plus fort potentiel. Le chapitre 2 recense les différents types d'architectures parallèles et expose les familles d'algorithmes utilisées pour la parallélisation du lancer de rayon sur des machines parallèles à mémoire distribuée. Deux stratégies permettent une distribution de la base de données : 1' envoi de rayons et l'envoi d'objets. Dans le chapitre 3, après avoir présenté nos contraintes, nous comparons les algorithmes parallèles pouvant y répondre grâce à leur modélisation. Les résultats obtenus vont nous amener à proposer deux nouveaux algorithmes de parallélisation basés sur un nouveau type de flot. Enfin, dans le chapitre 4 nous présentons nos résultats expérimentaux et leur analyse. Nos tests sont réalisés sur des machines massivement parallèles et sur un réseau de stations de travail.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00985973 |
| Date | 01 December 1997 |
| Creators | Nebel, Jean-Christophe |
| Publisher | Ecole Nationale Supérieure des Mines de Saint-Etienne, Université Jean Monnet - Saint-Etienne |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0023 seconds