Lightcuts: a scalable approach to illumination

ABSTRACT

Lightcuts is a scalable framework for computing realistic illumination. It handles arbitrary geometry, non-diffuse materials, and illumination from a wide variety of sources including point lights, area lights, HDR environment maps, sun/sky models, and indirect illumination. At its core is a new algorithm for accurately approximating illumination from many point lights with a strongly sublinear cost. We show how a group of lights can be cheaply approximated while bounding the maximum approximation error. A binary light tree and perceptual metric are then used to adaptively partition the lights into groups to control the error vs. cost tradeoff.We also introduce reconstruction cuts that exploit spatial coherence to accelerate the generation of anti-aliased images with complex illumination. Results are demonstrated for five complex scenes and show that lightcuts can accurately approximate hundreds of thousands of point lights using only a few hundred shadow rays. Reconstruction cuts can reduce the number of shadow rays to tens.

REFERENCES

• 1: Sameer Agarwal , Ravi Ramamoorthi , Serge Belongie , Henrik Wann Jensen, Structured importance sampling of environment maps, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 2: Blackwell, H. R. 1972. Luminance difference thresholds. In Handbook of Sensory Physiology, vol. VII/4: Visual Psychophysics. Springer-Verlag, 78--101.
• 3: Cohen-Or, D., Chrysanthou, Y. L., Silva, C. T., and Durand, F. 2003. A survey of visibility for walkthrough applications. IEEE Transactions on Visualization and Computer Graphics 9, 3, 412--431.
• 4: Paul Debevec, Rendering synthetic objects into real scenes: bridging traditional and image-based graphics with global illumination and high dynamic range photography, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.189-198, July 1998 [doi>10.1145/280814.280864]
• 5: Sebastian Fernandez , Kavita Bala , Donald P. Greenberg, Local illumination environments for direct lighting acceleration, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 6: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
• 7: Hasenfratz, J.-M., Lapierre, M., Holzschuch, N., and Sillion, F. 2003. A survey of real-time soft shadows algorithms. In Eurographics, Eurographics, Eurographics. State-of-the-Art Report.
• 8: Henrik Wann Jensen, Realistic image synthesis using photon mapping, A. K. Peters, Ltd., Natick, MA, 2001
• 9: Alexander Keller, Instant radiosity, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.49-56, August 1997 [doi>10.1145/258734.258769]
• 10: Kok, A. J. F., and Jansen, F. W. 1992. Adaptive sampling of area light sources in ray tracing including diffuse interreflection. Computer Graphics Forum (Eurographics '92) 11, 3 (Sept.), 289--298.
• 11: Thomas Kollig , Alexander Keller, Efficient illumination by high dynamic range images, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
• 12: Jaroslav Krivanek , Pascal Gautron , Sumanta Pattanaik , Kadi Bouatouch, Radiance Caching for Efficient Global Illumination Computation, IEEE Transactions on Visualization and Computer Graphics, v.11 n.5, p.550-561, September 2005 [doi>10.1109/TVCG.2005.83]
• 13: Gregory J. Ward, Measuring and modeling anisotropic reflection, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.265-272, July 1992
• 14: J. Painter , K. Sloan, Antialiased ray tracing by adaptive progressive refinement, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.281-288, July 1989
• 15: Paquette, E., Poulin, P., and Drettakis, G. 1998. A light hierarchy for fast rendering of scenes with many lights. Computer Graphics Forum 17, 3, 63--74.
• 16: Bui Tuong Phong, Illumination for computer generated pictures, Communications of the ACM, v.18 n.6, p.311-317, June 1975 [doi>10.1145/360825.360839]
• 17: A. J. Preetham , Peter Shirley , Brian Smits, A practical analytic model for daylight, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.91-100, July 1999 [doi>10.1145/311535.311545]
• 18: Annette Scheel , Marc Stamminger , Hans-Peter Seidel, Thrifty Final Gather for Radiosity, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.1-12, June 25-27, 2001
• 19: Scheel, A., Stamminger, M., and Seidel, H. 2002. Grid based final gather for radiosity on complex clustered scenes. Computer Graphics Forum 21, 3, 547--556.
• 20: Peter Shirley , Changyaw Wang , Kurt Zimmerman, Monte Carlo techniques for direct lighting calculations, ACM Transactions on Graphics (TOG), v.15 n.1, p.1-36, Jan. 1996 [doi>10.1145/226150.226151]
• 21: Francois X. Sillion , Claude Puech, Radiosity and Global Illumination, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 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: Eric Tabellion , Arnauld Lamorlette, An approximate global illumination system for computer generated films, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 24: Eric Veach , Leonidas J. Guibas, Metropolis light transport, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.65-76, August 1997 [doi>10.1145/258734.258775]
• 25: Ingo Wald , Thomas Kollig , Carsten Benthin , Alexander Keller , Philipp Slusallek, Interactive global illumination using fast ray tracing, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 26: Ingo Wald , Carsten Benthin , Philipp Slusallek, Interactive global illumination in complex and highly occluded environments, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
• 27: Bruce Walter , Gün Alppay , Eric Lafortune , Sebastian Fernandez , Donald P. Greenberg, Fitting virtual lights for non-diffuse walkthroughs, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.45-48, August 1997 [doi>10.1145/258734.258766]
• 28: Walter, B. 2005. Notes on the Ward BRDF. Technical Report PCG-05-06, Cornell Program of Computer Graphics, Apr.
• 29: Ward, G. J., and Heckbert, P. 1992. Irradiance gradients. In Third Eurographics Workshop on Rendering, 85--98.
• 30: Ward, G. 1994. Adaptive shadow testing for ray tracing. In Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering), Springer-Verlag, New York, 11--20.
• 31: Andrew Woo , Pierre Poulin , Alain Fournier, A Survey of Shadow Algorithms, IEEE Computer Graphics and Applications, v.10 n.6, p.13-32, November 1990 [doi>10.1109/38.62693 ]
• 32: Zaninetti, J., Boy, P., and Peroche, B. 1999. An adaptive method for area light sources and daylight in ray tracing. Computer Graphics Forum 18, 3 (Sept.), 139--150.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

Keywords:
many lights, raytracing, shadowing