Adaptive mesh generation for global diffuse illumination

ABSTRACT

Rapid developments in the design of algorithms for rendering globally illuminated scenes have taken place in the past five years. Net energy methods such as the hemicube and other radiosity algorithms have become very effective at computing the energy balance for scenes containing diffusely reflecting objects. Such methods first break up a scene description into a relatively large number of elements, or possibly several levels of elements. Energy transfers among these elements are then determined using a variety of means. While much progress has been made in the design of energy transfer algorithms, little or no attention has been paid to the proper generation of the mesh of surface elements. This paper presents a technique for adaptively creating a mesh of surface elements as the energy transfers are computed. The method allows large numbers of small elements to be placed at parts of the scene where the most active energy transfers occur without requiring that other parts of the scene be needlessly subdivided to the same degree. As a result, the computational effort in the energy transfer computations can be concentrated where it has the most effect.

REFERENCES

• 1: D. R. Baum , H. E. Rushmeire , J. M. Winget, Improving radiosity solutions through the use of analytically determined form-factors, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.325-334, July 1989
• 2: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.99-106, July 1989
• 3: 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
• 4: Cohen, Michael F., Donald P. Greenberg, David S. Immel and Philip J. Brock, A Radiosity Solution for Complex Environments, IEEE Computer Graphics and Applications Vol. 6, No. 3, March 1986, pp. 26-35.
• 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: Cook, Robert L., Thomas Porter, Loren Carpenter, Distributed Ray Tracing, Computer Graphics (SIG- GRAPH '85 Proceedings), Vol. 19, No. 3, July 1985, pp. }11-120.
• 7: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 8: Cindy M. Goral , Kenneth E. Torrance , Donald P. Greenberg , Bennett Battaile, Modeling the interaction of light between diffuse surfaces, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.213-222, January 1984
• 9: James T. Kajiya, The rendering equation, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.143-150, Aug. 1986
• 10: Bruce Fountain Naylor, A priori based techniques for determining visibility priority for 3-d scenes, 1981
• 11: Tomoyuki Nishita , Eihachiro Nakamae, Continuous tone representation of three-dimensional objects taking account of shadows and interreflection, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.23-30, Jul. 1985
• 12: Tomoyuki Nishita , Isao Okamura , Eihachiro Nakamae, Shading models for point and linear sources, ACM Transactions on Graphics (TOG), v.4 n.2, p.124-146, April 1985 [doi>10.1145/282918.282938]
• 13: Siegel, Robert and John R. Howell, Thermal Radiation Heat Transfer, Hemisphere Publishing Corp., Washington DC, 198t.
• 14: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
• 15: 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
• 16: Gregory J. Ward , Francis M. Rubinstein , Robert D. Clear, A ray tracing solution for diffuse interreflection, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.85-92, Aug. 1988
• 17: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design