Simulation d'éclairage dans des environnements architecturaux complexes : approches séquentielle et parallèle

Computing global illumination for complex environments in moderate time and walking through them is one of the challenges in computer graphics. Indeed, hierarchical radiosity is a very demanding process in terms of computation time and memory ressources even for scenes of moderate complexity. A preprocessing is then necessary. This preprocessing consists in partitioning the environment into regions (called cells) and determining visibility between these regions. We propose a new partitioning method that relies on image analysis and consists in matching cell models with geometric elements within the scene. Compared to the binary space subdivision technique, our method results in a low number of cells fitting at best with the environment topology. Radiosity computation is performed only for a resident subset of cells which changes during the resolution process. The geometric and photometric information is stored on the disk. Lighting simulation is then considered as the composition of elementary tasks consisting in (i) loading in memory the necessary information for the simulation, (ii) performing radiosity computations, (iii) updating the database located on the disk. However, in order to reduce the numerous disk transfers, the computations must be ordered to make the radiosity algorithms tractable. To this end, we propose several strategies making use of the cells resulting from the scene partitioning as well as a graph expressing visibility between these cells. These strategies predict for the short, medium and long range terms the disk transfer costs that determine the choice of the cells that will shoot their energy. This algorithm is the starting point for our SPMD parallel hierarchical radiosity program, based on a public domain software called MPI (Message Passing Interface). In this case, the database is stored on a single disk and accessed by all the processors (through NFS in case of a network of computers). Each processor performs computations for a subset of regions according to the same ordering strategies as our sequential algorithm. Dynamic load balancing relies on a task stealing approach while termination is detected by configuring the processors into a ring and moving a token round this ring.Effectuer des calculs d'illumination globale pour des environnements complexes et les visualiser de manière interactive demeure un problème difficile en synthèse d'images. En effet, la radiosité hiérarchique est un processus très coûteux en termes de temps de calcul et de ressources mémoire, même pour des scènes de complexité moyenne. Par conséquent, dans le cas d'environnements complexes, une étape de précalcul est nécessaire. Ce précalcul consiste à découper la scène en plusieurs régions (appelées cellules) et évaluer les relations de visibilité entre ces régions. La méthode de découpage (ou de structuration) que nous proposons est inspirée de l'analyse d'images et consiste à mettre en correspondance des modèles génériques de cellules avec des éléments géométriques déduits de la scène. Comparée à la technique de subdivision binaire de l'espace, cette méthode fournit des résultats beaucoup plus convaincants car le nombre de cellules obtenues est plus faible et par conséquent les calculs de visibilité et de simulation d'éclairage se trouvent simplifiés. A chaque étape de la simulation d'éclairage, seule une petite partie de la scène réside en mémoire. Les informations géométriques et photométriques nécessaires à la représentation des objets de la scène sont stockées sur disque. La simulation de la propagation de la lumière est alors considérée comme la composition de tâches élémentaires consistant à (i) charger en mémoire les informations nécessaires à la simulation, (ii) effectuer les calculs de radiosité, (iii) remettre à jour la base de données sur le disque. Néanmoins, afin de réduire les nombreux échanges d'information entre le disque et la mémoire, il est nécessaire d'ordonner les calculs de manière efficace. Pour cela, nous proposons plusieurs stratégies d'ordonnancement des calculs reposant sur une prédiction des coûts de ces échanges d'informations à court, moyen ou long terme. Ces stratégies utilisent les connaissances relatives à la structuration de la scène en cellules et les relations de visibilité qui existent entre elles. Nous avons mis en oeuvre une version parallèle de cet algorithme à l'aide de l'environnement de programmation MPI (Message Passing Interface). Dans ce cas, toutes les données sont stockées sur un disque commun à tous les processeurs afin de réduire le nombre de messages et leur taille. Chaque processeur effectue les calculs pour un ensemble de régions selon les mêmes stratégies d'ordonnancement que l'algorithme séquentiel. Un mécanisme d'équilibrage de charge dynamique suivant une technique de vol de tâche (task stealing) permet d'éviter que certains processeurs restent inactifs au cours des calculs. Enfin, la terminaison de l'algorithme est réalisée à l'aide d'une reconfiguration dynamique des processeurs en anneau qui permet également la gestion de la convergence de l'algorithme