A fast shadow algorithm for area light sources using backprojection

ABSTRACT

The fast identification of shadow regions due to area light sources is necessary for realistic rendering and for discontinuity meshing for global illumination. A new shadow-determination algorithm is presented that uses a data structure, called a backprojection, to represent the visible portion of a light source from any point in the scene. A complete discontinuity meshing algorithm is described for polyhedral scenes and area light sources, which includes an important class of light/geometry interactions that have not been implemented before. A fast incremental algorithm for computing backprojections is also described. The use of spatial subdivision, and heuristics based on computed statistics of typical scenes, results in efficient mesh and backprojection computation. Results of the implementation show that the use of the backprojection and discontinuity meshing permits accelerated high-quality rendering of shadows using both ray-casting and polygon-rendering with interpolants.

REFERENCES

• Aman84: John Amanatides, Ray tracing with cones, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.129-135, January 1984
• AmW87: Amanatides, John and Andrew Woo, ''A Fast Voxel Traversal Algorithm for Ray Tracing,'' Proc. of Eurographics '87, 1987.
• Appe68: Appel, A., ''Some Techniques for Shading Machine Renderings of Solids,'' Proc. of AFIPS JSCC, vol. 32, pp. 37-45, 1968.
• AWG78: Peter Atherton , Kevin Weiler , Donald Greenberg, Polygon shadow generation, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.275-281, August 23-25, 1978
• BaRW89: 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
• BoKe70: Bouknight, W. J. and K. Kelley, ''An Algorithm for Producing Half-Tone Computer Graphics Presentations with Shadows and Movable Light Sources,'' SJCC, AFIPS, vol. 36, 1970.
• CaFu90: 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
• CaFu91: A. T. Campbell, III , Donald S. Fussell, An Analytic Approach to Illumination with Area Light Sources, University of Texas at Austin, Austin, TX, 1991
• ChFe90: 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
• ChFe92: Norman Chin , Steven Feiner, Fast object-precision shadow generation for area light sources using BSP trees, Proceedings of the 1992 symposium on Interactive 3D graphics, p.21-30, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147159]
• Dret94a: Georgios Drettakis , Eugene Fiume, Structured sampling and reconstruction of illumination for image synthesis, 1994
• Dret94b: Drettakis, George, ''Simplifying the Representation of Radiance from Multiple Emitters,'' Submitted for publication, April 1994.
• DrFi93: Drettakis, George and Eugene Fiume, ''Accurate and Consistent Reconstruction of Illumination Functions Using Structured Sam-pling, '' Computer Graphics Forum (Eurographics '93 Conf. Issue), vol. 12, no. 3, Barcelona Spain.
• GiCS91: Ziv Gigus , John Canny , Raimund Seidel, Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.6, p.542-551, June 1991 [doi>10.1109/34.87341]
• GiMa90: Z. Gigus , J. Malik, Computing the Aspect Graph for Line Drawings of Polyhedral Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.2, p.113-122, February 1990 [doi>10.1109/34.44399]
• Glass91: Glassner, Andrew S., ''Maintaining Winged-Edge Models,'' In Graphics Gems II, edit. by Jim Arvo, Academic Press, 1991. -
• Heck92a: Heckbert, Paul, ''Discontinuity Meshing for Radiosity,'' 3rd Eurographics Workshop on Rendering, Bristol, UK May 1992.
• Heck92b: Heckbert, Paul, ''Radiosity in Flatland,'' Proc. of Eurographics '92, Cambridge, Elsevier, September 1992.
• LiTG92: Dani Lischinski , Filippo Tampieri , Donald P. Greenberg, Discontinuity Meshing for Accurate Radiosity, IEEE Computer Graphics and Applications, v.12 n.6, p.25-39, November 1992 [doi>10.1109/38.163622]
• NiNa83: Nishita, Tomoyuki and Eihchiro Nakamae, ''Half Tone Represen-tation of 3-D Objects Illumination By Area Source or Polyhedron Sources,'' COMPSAC'83, Proc IEEE 7th Intl. Comp. Soft. and Applications Conf., pp. 237-242, November 1983.
• PoAm90: Poulin, Pierre and John Amanatides, ''Shading and Shadowing with Linear Light Sources,'' Proc. of Eurographics '90, 1990.
• RoAd90: D. F. Rogers , J. A. Adams, Mathematical elements for computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1989
• Sa1874: Salmon, G., ''Analytic Geometry of Three Dimensions,'' Metcalfe, Cambridge, England 1874.
• StGa93: Stewart, A. James and Sherif Ghali, ''An Output Sensitive Algo-rithm for the Computation of Shadow Boundaries,'' Fifth Cana-dian Conference on Computational Geometry, August 1993.
• StGa94: A. James Stewart , Sherif Ghali, Fast computation of shadow boundaries using spatial coherence and backprojections, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.231-238, July 1994 [doi>10.1145/192161.192210]
• TaTo91: Tanaka, Toshimitsu and Tokiichiro Takahashi, ''Shading with Area Light Sources,'' Proc. of Eurographics '91, 1991.
• Tell92: Seth J. Teller, Computing the antipenumbra of an area light source, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.139-148, July 1992

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

General Terms:
Measurement, Theory

Keywords:
backprojection, discontinuity meshing, global illumination, penumbra, shadows, umbra