Parallel Hierarchical Radiosity for Complex Building Interiors

Main page for other related papers


D. Meneveaux, K. Bouatouch
Computer Graphics Forum
vol. 18, num. 4. Elsevier Ed.
déc. 1999


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 proven in appendix.