Parallel Hierarchical Radiosity for Complex Building Interiors

Daniel Meneveaux 1 Kadi Bouatouch 1
1 SIAMES - Computer generated images, animation, modeling and simulation
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : In this paper we propose a SPMD parallel hierarchical radiosity algorithm relying on a novel partitioning method which may apply to any kind of architectural scene, not necessarly axial. This algorithm is based on a public domain software called MPI (Message Passing Interface) which allows the use of either a heterogeneous set of concurrent computers or a parallel computer or both. The database is stored on a single disk and accessed by all the processors (through NFS in case of a network of computers). As the objective is to handle complex scenes like building interiors, to cope with the problem of memory size, only a subset of the database resides in memory of each processor. This subset is determined with the help of partitioning into 3D cells, clustering and visibility calculations. A graph expressing visibility between the resulting clusters is determined, partitioned (with a new method based on classification of K-means type) and distributed among all the processors. Each processor is responsible for gathering energy (using Gauss Seidel method) only for its subset of clusters. In order to reduce the disk transfers due to downloading these subsets of clusters, we use an ordering strategy based on the traveling salesman 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. The parallel iterative resolution is of group iterative type. Its mathematical convergence is proved in appendix.
Type de document :
[Research Report] RR-3425, INRIA. 1998
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:22:44
Dernière modification le : mercredi 11 avril 2018 - 01:51:07
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:40:21



  • HAL Id : inria-00073265, version 1


Daniel Meneveaux, Kadi Bouatouch. Parallel Hierarchical Radiosity for Complex Building Interiors. [Research Report] RR-3425, INRIA. 1998. 〈inria-00073265〉



Consultations de la notice


Téléchargements de fichiers