“Coarse-grained parallelism for hierarchical radiosity using group iterative methods” by Funkhouser

This paper describes algorithms that allow multiple hierarchical radiosity solvers to work on the same radiosity solution in parallel. We have developed a system based on a group iterative approach that repeatedly: 1) partitions patches into groups, 2) distributes a copy of each group to a slave processor which updates radiosities for all patches in that group, and 3) merges the updates back into a master solution. The primary advantage of this approach is that separate instantiations of a hierarchical radiosity solver can gather radiosity to patches in separate groups in parallel with very little contention or communication overhead. This feature, along with automatic partitioning and dynamic load balancing algorithms, enables our implemented system to achieve significant speedups running on moderate numbers of workstations connected by a local area network. This system has been used to compute the radiosity solution for a very large model representing a five floor building with furniture.

1. Baum, D., and Winget, J. Real Time Radiosity Through Parallel Processing and Hardware Acceleration. Computer Graphics (1990 Symposium on Interactive 3D Graphics), 24, 2, 67-75.
2. Bouatouch, K., and Priol, T. Data Management Scheme for Parallel Radiosity. Computer-Aided Design, 26, 12, December, 1994, 876-883.
3. Chalmers, A, and Paddon, D. Parallel Processing of Progressive Refinement Radiosity Methods. Second Eurographics Workshop on Rendering, Barcelona, Spain, May, 1991.
4. Chen, S.E. A Progressive Radiosity Method and its Implementation in a Distributed Processing Environment. Master’s Thesis, Cornell University, 1989.
5. Cohen, M., Greenberg, D., Immel, D., and Brock, E An Efficient Radiosity Approach for Realistic Image Synthesis.IEEE Computer Graphics and Applications, 6, 3 (March, 1986), 25-35.
6. Cohen, M., Chen, S., Wallace, J., and Greenberg, D. A Progressive Refinement Approach to Fast Radiosity Image Generation. Computer Graphics (Proc. SIGGRAPH ’88), 22, 4, 75-84.
7. Drettakis, G., Fiume, E., and Fournier, A. Tightly-Coupled Multi-Processing for a Global Illumination Algorithm. EU- ROGRAPHICS ’90, Montreux, Switzerland, 1990.
8. Drucker, S., and Schroder, E Fast Radiosity Using a Data Parallel Architecture. Third Eurographics Workshop on Rendering, 1992.
9. Feda, M., and Purgathofer, W. Progressive Refinement Radiosity on a Transputer Network. Second Eurographics Workshop on Rendering, 1991, 139-148.
10. Feda, M., and Purgathofer, W. Progressive Ray Refinement for Monte Carlo Radiosity. Fourth Eurographics Workshop on Rendering, 1993, 15-25.
11. Garey, M., and Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.
12. Guattery, S., and Miller, G. On the Performance of Spectral Graph Partitioning Methods. 1995 ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995.
13. Golub, G., and Van Loan, C. Matrix Computations. John Hopkins University Press, Baltimore, MD, 2nd Edition, 1989.
14. Goral, C., Torrance, K., Greenberg, D., and Battaile, B. Modeling the Interaction of Light Between Diffuse Surfaces. Computer Graphics (Proc. SIGGRAPH ’84), 18, 3,213-222.
15. Gortler, S., Schroder, R, Cohen, M., and Hanrahan, R Wavelet Radiosity. Computer Graphics (Proc. SIGGRAPH ’93), 221- 230.
16. Guitton, R, Roman, J., and Subrenat, G. Implementation Results and Analysis of a Parallel Progressive Radiosity. In 1995 Parallel Rendering Symposium, Atlanta, Georgia, October, 1995,31-37.
17. Hanrahan, R, and Salzman, D. A Rapid Hierarchical Radiosity Algorithm. Computer Graphics (Proc. SIGGRAPH ’91), 25, 4, 197-206.
18. Naylor, B. Constructing Good Partitioning Trees. Graphics Interface ’93. Toronto, CA, May, 1993, 181-191.
19. Paddon, D., and Chalmers, A. Parallel Processing of the Radiosity Method. Computer-Aided Design, 26, 12, December, 1994, 917-927.
20. Recker, R., George, D., and Greenberg, D. Acceleration Techniques for Progressive Refinement Radiosity. Computer Graphics (1990 Symposium on Interactive 3D Graphics), 24, 2, 59-66.
21. Rushmeier, H., Patterson, C., and Veerasamy, A. Geometric Simplification for Indirect Illumination Calculations. Graphics Interface ’93, May, 1993,227-236.
22. Sillion, F. A Unified Hierarchical Algorithm for Global Illumination with Scattering Volumes and Object Clusters. IEEE Transactions on Visualization and Computer Graphics, I, 3, September, 1995.
23. Singh, J.R, Gupta, A. and Levoy, M. Parallel Visualization Algorithms: Performance and Architectural Implications. IEEE Compuwr, 27, 7 (July 1994), 45-55.
24. Smits, B., Arvo, J., and Greenberg, D. A Clustering Algorithm for Radiosity in Complex Environments. Computer Graphics (Proc. SIGGRAPH ’94), 435-442.
25. Teller, S., Visibility Computations in Densely Occluded Polyhedral Environments. Ph.D. thesis, Computer Science Division (EECS), University of California, Berkeley, 1992. Also available as UC Berkeley technical report UCB/CSD-92-708.
26. Teller, S., and Hanrahan, R Global Visibility Algorithms for Illumination Computations. Computer Graphics (Proc. SIG- GRAPH ’93), 239-246.
27. Teller, S., Fowler, C., Funkhouser, T., and Hanrahan, R Partitioning and Ordering Large Radiosity Computations. Computer Graphics (Proc. SIGGRAPH ’94), 443-450.
28. Wallace, J., Elmquist, K., Haines, E. A Ray Tracing Algorithm for Progressive Radiosity. Computer Graphics (Proc. SIG- GRAPH ’89), 23, 3, 315-324.
29. Young, D.M. Iterative Solution of Large Linear Systems. Computer Science and Applied Mathematics. Academic Press, New York, 1971.
30. Zareski, D., Wade, B., Hubbard, R and Shirley, R Efficient Parallel Global Illumination using Density Estimation. 1995 Parallel Rendering Symposium. Atlanta, Georgia, October, 1995, 47-54.
31. Zareski, D. Parallel Decomposition of View-Independent Global Illumination Algorithms. Master’s thesis, Cornell University, 1996.