Global illumination using local linear density estimation

ABSTRACT

This article presents the density estimation framework for generating view-independent global illumination solutions. It works by probabilistically simulating the light flow in an environment with light particles that trace random walks origination at luminaires and then using statistical density estimation techniques to reconstruct the lighting on each surface. By splitting the computation into separate transport and reconstruction stages, we gain many advantages including reduced memory usage, the ability to simulate nondiffuse transport, and natural parallelism. Solutions to several theoretical and practical difficulties in implementing this framework are also described. Light sources that vary spectrally and directionally are integrated into a spectral particle tracer using nonuniform rejection. A new local linear density estimation technique eliminates boundary bias and extends to arbitrary polygons. A mesh decimation algorithm with perceptual calibration is introduced to simplify the Gouraud-shaded representation of the solution for interactive display.

REFERENCES

• 1: APPEL, A. 1968. Some techniques for shading machine renderings of solids. In AFIPS 1968 Spring Joint Computing Conference, 37-49.
• 2: ARVO, J. 1986. Backward ray tracing. In Developments in Ray Tracing, ACM SIGGRAPH '86 Course Notes, ACM, New York, 259-263.
• 3: Shenchang Eric Chen , Holly E. Rushmeier , Gavin Miller , Douglass Turner, A progressive multi-pass method for global illumination, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.165-174, July 1991
• 4: Michael F. Cohen , John Wallace , Pat Hanrahan, Radiosity and realistic image synthesis, Academic Press Professional, Inc., San Diego, CA, 1993
• 5: COHEN, M. F., GREENBERG, D. P., IMMEL, D. S., AND BROCK, P.J. 1986. An efficient radiosity approach for realistic image synthesis. IEEE Comput. Graph. Appl. 6, 2, 26-35.
• 6: COLLINS, S. 1994. Adaptive splatting for specular to diffuse light transport. In Proceedings of the Fifth Eurographics Workshop on Rendering, (June), 119-135.
• 7: DANIELSON, D.A. 1991. Vectors and Tensors in Engineering and Physics. Addison-Wesley, New York.
• 8: Eliot A. Feibush , Marc Levoy , Robert L. Cook, Synthetic texturing using digital filters, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.294-301, July 14-18, 1980, Seattle, Washington, United States
• 9: Reid Gershbein , Peter Schröder , Pat Hanrahan, Textures and radiosity: controlling emission and reflection with texture maps, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.51-58, July 1994 [doi>10.1145/192161.192171]
• 10: GLASSNER, A.S. 1994. A model for fluorescence and phospherescence. In Proceedings of the Fifth Eurographics Workshop on Rendering (June), 57-68.
• 11: Andrew S. Glassner, Principles of Digital Image Synthesis, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 12: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
• 13: HASTIE, T. AND LOADER, C. 1993. Local regression: Automatic kernel carpentry. Statist. Sci. 8, 120-143.
• 14: Paul S. Heckbert, Adaptive radiosity textures for bidirectional ray tracing, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.145-154, Aug. 1990
• 15: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 16: HUGHES, M., LASTRA, A. A., AND SAXE, E. 1996. Simplification of global-illumination meshes. In Proceedings of Eurographics '96.
• 17: Henrik Wann Jensen, Global illumination using photon maps, Proceedings of the eurographics workshop on Rendering techniques '96, p.21-30, December 1996, Porto, Portugal
• 18: JUDD, D. B. AND WYSZECKI, G. 1975. Color in Business, Science, and Industry. Wiley, New York.
• 19: 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]
• 20: Lo, C., PALMER, B. g., DROST, M. K., AND WELTY, g.R. 1995. Incorporation of polarization effects in Monte Carlo simulations of radiative heat transfer. Numer. Heat Trans. Part A, 27, 129-142.
• 21: MOTTA, R. g. 1993. Visual characterization of color crts. In Device-Independent Color Imaging and Imaging Systems Integration, SPIE, 212-221.
• 22: PATTANAIK, S.N. 1993. Computational methods for global illumination and visualisation of complex 3D environments. Ph.D. Thesis, Birla Institute of Technology & Science, Computer Science Department, Pilani, India, February.
• 23: K. Perlin , E. M. Hoffert, Hypertexture, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.253-262, July 1989
• 24: Richard A. Redner , Mark E. Lee , Samuel P. Uselton, Smooth B-spline illumination maps for bidirectional ray tracing, ACM Transactions on Graphics (TOG), v.14 n.4, p.337-362, Oct. 1995 [doi>10.1145/225294.225296]
• 25: RUPPERT, D. 1995. Personal communications.
• 26: RUSHMEIER, H., PATTERSON, C., AND VEERASAMY, A. 1993. Geometric simplification for indirect illumination calculations. In Proceedings of Graphics Interface '93, (Toronto, May), Canadian Information Processing Society, 227-236.
• 27: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 28: SEZAN, M. I., YIP, K.-L., AND DALY, S.J. 1987. Uniform perceptual quantization: Applications to digital radiography. IEEE Trans. Syst. Man Cybern. 17, 4 (Aug.), 622-634.
• 29: SHIRLEY, P., WADE, B., ZARESKI, D., HUBBARD, P., WALTER, B., AND GREENBERG, D.P. 1995. Global illumination via density estimation. In Proceedings of the Sixth Eurographics Workshop on Rendering (June) 187-199.
• 30: SILVERMAN, B.W. 1986. Density Estimation for Statistics and Data Analysis. Chapman and Hall, London.
• 31: 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]
• 32: Seth Teller , Celeste Fowler , Thomas Funkhouser , Pat Hanrahan, Partitioning and ordering large radiosity computations, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.443-450, July 1994 [doi>10.1145/192161.192279]
• 33: TOOR, J. S. AND VISKANTA, R. 1968. A numerical experiment of radiant heat interchange by the Monte Carlo method. Int. J. Heat Mass Transf. 11, 883-897.
• 34: WADE, B.S. 1996. Kernel based density estimation for global illumination. Master's Thesis, Program of Computer Graphics, Cornell University, January.
• 35: WAND, M. P. AND JONES, M.C. 1995. Kernel Smoothing. Chapman and Hall, London.
• 36: Gregory J. Ward, The RADIANCE lighting simulation and rendering system, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.459-472, July 1994 [doi>10.1145/192161.192286]
• 37: Stephen Wolfram, Mathematica: a system for doing mathematics by computer (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991
• 38: David Zareski , Bretton Wade , Philip Hubbard , Peter Shirley, Efficient parallel global illumination using density estimation, Proceedings of the IEEE symposium on Parallel rendering, p.47-54, October 30-31, 1995, Atlanta, Georgia, United States [doi>10.1145/218327.218336]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms

Keywords:
decimation, density estimation, particle tracing, realistic image synthesis, regression