“Partitioning and ordering large radiosity computations” by Teller, Fowler, Funkhouser and Hanrahan

We describe a system that computes radiosity solutions for polygonal environments much larger than can be stored in main memory. The solution is stored in and retrieved from a database as the computation proceeds. Our system is based on two ideas: the use of visibility oracles to find source and blocker surfaces potentially visible to a receiving surface; and the use of hierarchical techniques to represent interactions between large surfaces efficiently, and to represent the computed radiosity solution compactly. Visibility information allows the environment to be partitioned into subsets, each containing all the information necessary to transfer light to a cluster of receiving polygons. Since the largest subset needed for any particular cluster is much smaller than the total size of the environment, these subset computations can be performed in much less memory than can classical or hierarchical radiosity. The computation is then ordered for further efficiency. Careful ordering of energy transfers minimizes the number of database reads and writes. We report results from large solutions of unfurnished and furnished buildings, and show that our implementation’s observed running time scales nearly linearly with both local and global model complexity.

1. Baum,D.,Mann,S.,Smith,K.,and Winget,J.Making Radiosity Usable: Automatic Preprocessing and Meshing Techniques for the Generation of Accurate Radiosity Solutions. Computer Graphics (Proc. Siggraph ’91) 4 (1991), 51-60.
2. Baum,D.,and Winget,J.Real Time Radiosity Through Parallel Pro-cessing and Hardware Acceleration. Computer Graphics (1990 Symposium Interactive 3D Graphics) 24, 2 (March 1990), 67-75.
3. Bentley,J.Experiments on Geometric Traveling Salesman Heuristics. Tech. Rep. Computing Science (No. 151), AT&T Bell Laboratories, 1990.
4. Campbell III,A.,and Fussell,D.Adaptive Mesh Generation for Global Diffuse Illumination. Computer Graphics (Proc. Siggraph ’90) 24, 4 (1990), 155-164.
5. Cohen,M.,Chen,S.,Wallace,J.,and Greenberg,D.A Pro-gressive Refinement Approach to Fast Radiosity Image Generation. Computer Graphics (Proc. Siggraph ’88) 22, 4 (1988), 75-84.
6. Cohen,M.,and Greenberg,D.The Hemi-Cube: A Radiosity Solution for Complex Environments. Computer Graphics (Proc. Siggraph ’85) 19,3 (1985), 31-40.
7. Feda,M.,and Purgathofer,W.Accelerating radiosity by overshooting. In Proc. 3 rd Eurographics Workshop on Rendering (May 1992), pp. 21-31.
8. Fuchs,H.,Kedem,Z.,and Naylor,B.Predetermining visibility priority in 3-D scenes. Computer Graphics (Proc. Siggraph ’79) 13, 2 (1979), 175-182.
9. Funkhouser,T.Database and Display Algorithms for Interactive Visual-ization of Architectural Models. PhD thesis, (Also TR UCB/CSD 93/771) CS Dept., UC Berkeley, 1993.
10. Funkhouser,T.,and S ~equin,C.Adaptive display algorithm for in-teractive frame rates during visualization of complex virtual environments. Computer Graphics (Proc. Siggraph ’93) 27 (1993), 247-254.
11. Funkhouser,T.,S ~equin,C.,and Teller,S.Management of Large Amounts of Data in Interactive Building Walkthroughs. In Proc. 1992 Work-shop on Interactive 3D Graphics (1992), pp. 11-20.
12. Gortler,S.,Cohen,M.,and Slusallek,P.Radiosity and relaxation methods – Progressive refinement in Southwell relaxation. Technical Report TR-408-93, Department of Computer Science, Princeton University, 1993.
13. Gortler,S.,Schr ~oder,P.,Cohen,M.,and Hanrahan,P.Wavelet radiosity. Computer Graphics (Proc. Siggraph ’93) (August 1993), 221-230.
14. Haines,E.,and Wallace,J.Shaft Culling for Efficient Ray-Traced Radiosity. In Proc. 2 nd Eurographics Workshop on Rendering (May 1991).
15. Hanrahan,P.,Salzman,D.,and Aupperle,L.A Rapid Hierarchical Radiosity Algorithm. Computer Graphics (Proc. Siggraph ’91) 25, 4 (1991), 197-206.
16. Heckbert,P.,and Winget,J.Finite element methods for global illu-mination. Tech. Rep. UCB/CSD 91/643, CS Department, UC Berkeley, 1991.
17. Lischinski,D.,Tampieri,F.,and Greenberg,D.P.Combining Hier-archical Radiosity and Discontinuity Meshing. Computer Graphics (Proc. Sig-graph ’93) 27 (1993).
18. Marks,J.,Walsh,R.,Christensen,J.,and Friedell,M.Image and Intervisibility Coherence in Rendering. In Proc. of Graphics Interface ’90 (May 1990), pp. 17-30.
19. Recker,R.,George,D.,and Greenberg,D.Acceleration Techniques for Progressive Refinement Radiosity. Computer Graphics (1990 Symp. on Interactive 3D Graphics) 24, 2 (1990), 59-66.
20. Rushmeier,H.,Patterson,C.,and Veerasamy,A.Geometric sim-plification for indirect illumination calculations. In Proc. Graphics Interface ’93 (1993), pp. 227-236.
21. Schr ~oder,P.,Gortler,S.,Cohen,M.,and Hanrahan,P.Wavelet projections for radiosity. In Eurographics Workshop on Rendering (1993), pp. 105-114.
22. Smits,B.,Arvo,J.,and Greenberg,D.A Clustering Algorithm for Radiosity in Complex Environments. Computer Graphics (Proc. Siggraph ’94) 28 (1994).
23. Teller,S.Visibility Computations in Densely Occluded Polyhedral Envi-ronments. PhD thesis, (Also TR UCB/CSD 92/708) CS Dept., UC Berkeley, 1992.
24. Teller,S.A Methodology for Geometric Algorithm Development. In Proc. Computer Graphics International ’93 (1993), N. and D. Thalmann, Eds., pp. 306-317.
25. Teller,S.,and Hanrahan,P.Global Visibility Algorithms for Illu-mination Computations. Computer Graphics (Proc. Siggraph ’93) 27 (1993), 239-246.
26. Teller,S.,and S ~equin,C.H.Visibility Preprocessing for Interactive Walkthroughs. Computer Graphics (Proc. Siggraph ’91) 25, 4 (1991), 61-69.
27. Troutman,R.,and Max,N.Radiosity algorithms using higher order finite element methods. Computer Graphics (Proc. Siggraph ’93) (1993), 209- 212.
28. Wallace,J.,Elmquist,K.,and Haines,E.A Ray Tracing Algorithm for Progressive Radiosity. Computer Graphics (Proc. Siggraph ’89) 23,3 (1989), 315-324.
29. Xu,H.,Peng,Q.-S.,and Liang,Y.-D.Accelerated radiosity method for complex environments. Computers and Graphics 14, 1 (1990), 65-71.
30. Zatz,H.Galerkin radiosity: A higher order solution method for global illumination. Computer Graphics (Proc. Siggraph ’93) 27 (1993), 213-220.