A Perceptually-Driven Parallel Algorithm for Efficient Radiosity Simulation

Simon Gibson and Roger J. Hubbold.
IEEE Transactions on Visualization and Computer Graphics, 6(3), July-September 2000.

Abstract

We describe a novel algorithm for computing view-independent finite-element radiosity solutions on distributed shared-memory parallel architectures. Our approach is based on the notion of a {\it sub-iteration\/} being the transfer of energy from a single source to a subset of the scene's receiver patches. By using an efficient queue-based scheduling system to process these sub-iterations, we show how radiosity solutions can be generated without the need for processor synchronisation between iterations of the progressive refinement algorithm. The only significant source of inter-processor communication required by our method is for visibility calculations. We also describe a perceptually-driven approach to visibility estimation, which employs an efficient volumetric grid structure, and attempts to reduce the amount of inter-processor communication by approximating visibility queries between distant patches. Our algorithm also eliminates the need for dynamic load-balancing until the end of the solution process, and is shown to achieve a super-linear speedup in many situations.