Partitioning and ordering large radiosity computations

ABSTRACT

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.

REFERENCES

• 1: Daniel R. Baum , Stephen Mann , Kevin P. Smith , James M. Winget, Making radiosity usable: automatic preprocessing and meshing techniques for the generation of accurate radiosity solutions, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.51-60, July 1991
• 2: Daniel R. Baum , James M. Winget, Real time radiosity through parallel processing and hardware acceleration, Proceedings of the 1990 symposium on Interactive 3D graphics, p.67-75, February 1990, Snowbird, Utah, United States
• 3: Bentley,J.Experiments on Geometric Traveling Salesman Heuristics. Tech. Rep. Computing Science (No. 151), AT&T Bell Laboratories, 1990.
• 4: A. T. Campbell, III , Donald S. Fussell, Adaptive mesh generation for global diffuse illumination, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.155-164, Aug. 1990
• 5: Michael F. Cohen , Shenchang Eric Chen , John R. Wallace , Donald P. Greenberg, A progressive refinement approach to fast radiosity image generation, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.75-84, Aug. 1988
• 6: Michael F. Cohen , Donald P. Greenberg, The hemi-cube: a radiosity solution for complex environments, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.31-40, Jul. 1985
• 7: Feda,M.,and Purgathofer,W.Accelerating radiosity by overshooting. In Proc. 3 rd Eurographics Workshop on Rendering (May 1992), pp. 21-31.
• 8: Henry Fuchs , Zvi M. Kedem , Bruce Naylor, Predetermining visibility priority in 3-D scenes (Preliminary Report), Proceedings of the 6th annual conference on Computer graphics and interactive techniques, p.175-181, August 08-10, 1979, Chicago, Illinois, United States
• 9: Thomas A Funkhouser, Database and Display Algorithms for Interactive Visualization, University of California at Berkeley, Berkeley, CA, 1993
• 10: Thomas A. Funkhouser , Carlo H. Séquin, Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.247-254, September 1993 [doi>10.1145/166117.166149]
• 11: Thomas A. Funkhouser , Carlo H. Séquin , Seth J. Teller, Management of large amounts of data in interactive building walkthroughs, Proceedings of the 1992 symposium on Interactive 3D graphics, p.11-20, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147158]
• 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: Steven J. Gortler , Peter Schröder , Michael F. Cohen , Pat Hanrahan, Wavelet radiosity, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.221-230, September 1993 [doi>10.1145/166117.166146]
• 14: Haines,E.,and Wallace,J.Shaft Culling for Efficient Ray-Traced Radiosity. In Proc. 2 nd Eurographics Workshop on Rendering (May 1991).
• 15: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
• 16: Paul S. Heckbert , James M. Winget, Finite Element Methods for Global Illumination, University of California at Berkeley, Berkeley, CA, 1991
• 17: Dani Lischinski , Filippo Tampieri , Donald P. Greenberg, Combining hierarchical radiosity and discontinuity meshing, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.199-208, September 1993 [doi>10.1145/166117.166143]
• 18: J. Marks , R. Walsh , J. Christensen , M. Friedell, Image and intervisibility coherence in rendering, Proceedings on Graphics interface '90, p.17-30, June 1990, Halifax, Nova Scotia
• 19: Rodney J. Recker , David W. George , Donald P. Greenberg, Acceleration techniques for progressive refinement radiosity, Proceedings of the 1990 symposium on Interactive 3D graphics, p.59-66, February 1990, Snowbird, Utah, United States
• 20: John Peterson , Mark Jones, Implementing type classes, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.227-236, June 21-25, 1993, Albuquerque, New Mexico, United States
• 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: Brian Smits , James Arvo , Donald Greenberg, A clustering algorithm for radiosity in complex environments, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.435-442, July 1994 [doi>10.1145/192161.192277]
• 23: Seth Jared Teller, Visibility computations in densely occluded polyhedral environments, University of California at Berkeley, Berkeley, CA, 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: Seth Teller , Pat Hanrahan, Global visibility algorithms for illumination computations, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.239-246, September 1993 [doi>10.1145/166117.166148]
• 26: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.61-70, July 1991
• 27: Roy Troutman , Nelson L. Max, Radiosity algorithms using higher order finite element methods, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.209-212, September 1993 [doi>10.1145/166117.166144]
• 28: J. R. Wallace , K. A. Elmquist , E. A. Haines, A Ray tracing algorithm for progressive radiosity, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.315-324, July 1989
• 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: Harold R. Zatz, Galerkin radiosity: a higher order solution method for global illumination, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.213-220, September 1993 [doi>10.1145/166117.166145]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Radiosity

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
equilibrium methods, multigridding, spatial subdivision