Fast computation of shadow boundaries using spatial coherence and backprojections

ABSTRACT

This paper describes a fast, practical algorithm to compute the shadow boundaries in a polyhedral scene illuminated by a polygonal light source. The shadow boundaries divide the faces of the scene into regions such that the structure or “aspect” of the visible area of the light source is constant within each region. The paper also describes a fast, practical algorithm to compute the structure of the visible light source in each region. Both algorithms exploit spatial coherence and are the most efficient yet developed.Given the structure of the visible light source in a region, queries of the form “What specific areas of the light source are visible?” can be answered almost instantly from any point in the region. This speeds up by several orders of magnitude the accurate computation of first level diffuse reflections due to an area light source. Furthermore, the shadow boundaries form a good initial decomposition of the scene for global illumination computations.

REFERENCES

• 1: 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
• 2: A. T. Campbell, III , Donald S. Fussell, An Analytic Approach to Illumination with Area Light Sources, University of Texas at Austin, Austin, TX, 1991
• 3: Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jorge Stolfi. Lines in space: Combinatorics and algorithms. New York University, Courant Inst. of Math. Sc. Technical Report No. 491, (also in STOC 1989, pp. 382-393), February 1990.
• 4: 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
• 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: Franklin C. Crow, Shadow algorithms for computer graphics, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.242-248, July 20-22, 1977, San Jose, California
• 8: Georgios Drettakis , Eugene Fiume, Structured sampling and reconstruction of illumination for image synthesis, 1994
• 9: George Drettakis , Eugene Fiume, A fast shadow algorithm for area light sources using backprojection, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.223-230, July 1994 [doi>10.1145/192161.192207]
• 10: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 11: 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]
• 12: 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]
• 13: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
• 14: Paul Heckbert. Discontinuitymeshing for radiosity. Third EurographicsWorkshop on Rendering, pages 203-215, May 1992.
• 15: 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]
• 16: 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]
• 17: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• 18: K. Mulmuley, An efficient algorithm for hidden surface removal, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.379-388, July 1989
• 19: TomoyukiNishita and Eihachiro Nakamae. Half-tone representation of 3-d objects illuminated by area sources or polyhedron sources. COMPSAC'83, Proc. IEEE 7th Intl. Conf. Soft. and Appl. Conf., pages 237-242, November 1983.
• 20: George Salmon. A treatise on the Analytical Geometry of Three Dimensions. Longmans, Green and Co., 1912.
• 21: Arthur Scherk. personal communications.
• 22: Duncan M. Y. Sommerville. Analytical Geometry in three dimensions. Cambridge University Press, 1934.
• 23: A. James Stewart and Sherif Ghali. An output sensitive algorithm for the computa-tion of shadow boundaries. In Canadian Conference on ComputationalGeometry, pages 291-296, August 1993.
• 24: Jorge Stolfi. Oriented Projective Geometry. PhD thesis, StanfordUniversity, 1988.
• 25: Seth J. Teller, Computing the antipenumbra of an area light source, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.139-148, July 1992
• 26: Seth Jared Teller. Visibility Computations in Densely Occluded Polyhedral Envi-ronments. PhD thesis, University of California at Berkeley, 1993.
• 27: Oswald Veblen and Wesley Young. Projective Geometry. Blaisdell Publishing Co., 1938.

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:
Algorithms, Measurement, Performance, Theory

Keywords:
aspect graphs, backprojections, discontinuity mesh, efficient surface enumeration, radiosity, shadows, spatial coherence, visual events