“A fast shadow algorithm for area light sources using backprojection” by Drettakis and Fiume

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.

1. Amanatides, John, ”Ray Tracing with Cones,” ACM Computer Graphics (Proc. SIGGRAPH ’84), vol. 18, no. 3, July 1984.
2. Amanatides, John and Andrew Woo, ”A Fast Voxel Traversal Algorithm for Ray Tracing,” Proc. of Eurographics ’87, 1987.
3. Appel, A., ”Some Techniques for Shading Machine Renderings of Solids,” Proc. of AFIPS JSCC, vol. 32, pp. 37-45, 1968.
4. Atherton, P., K. Weiler, and Donald P. Greenberg, ”Polygon Sha-dow Generation,” ACM Computer Graphics (Proc. SIGGRAPH ’78), vol. 12, no. 3, July 1978.
5. Baum, Daniel R., Holly E. Rushmeier, and James M. Winget, ”Improving Radiosity Solutions Through the Use of Anaytically Determined Form-Factors,” ACM Computer Graphics (Proc. SIGGRAPH ’89), vol. 23, no. 3, July 1989.
6. 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.
7. Campbell, A. T., III and Donald S. Fussell, ”Adaptive Mesh Gen-eration for Global Diffuse Illumination,” ACM Computer Graph-ics (Proc. SIGGRAPH ’90), vol. 24, no. 4, August 1990.
8. Campbell, A. T. III and Donald S. Fussell, ”An Analytic Approach to Illumination with Area Light Sources,” Tech. Report TR-91-25, Comp. Sci. Dept, Univ. of Texas Austin, August 1991.
9. Chin, Norman and Steven Feiner, ”Near Real-Time Shadow Gen-eration for Global Diffuse Illumination,” ACM Computer Graph-ics (Proc. SIGGRAPH ’90), vol. 24, no. 4, August 1990.
10. Chin, Norman and Steven Feiner, ”Fact Object Precision Shadow Generation for Area Light Source using BSP Trees,” ACM Com-puter Graphics (SIGGRAPH Symp. on Inter. 3D Graphics), 1992.
11. Drettakis, George, ”Structured Sampling and Reconstruction of Illumination for Image Synthesis,” Ph.D. Thesis, Dept. of Com-puter Sci., University of Toronto, (CSRI T.R. 293 ftp:ftp.csri.toronto.edu:csri-technical-reports/293), January 1994.
12. Drettakis, George, ”Simplifying the Representation of Radiance from Multiple Emitters,” Submitted for publication, April 1994.
13. 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.
14. Gigus, Ziv, John Canny, and Raimund Seidel, ”Efficiently Com-puting and Representing Aspect Graphs of Polyhedral Objects,” IEEE Trans. on Pat. Matching & Mach. Intelligence, vol. 13, no. 6, June 1991.
15. Gigus, Ziv and Jitendra Malik, ”Computing the Aspect Graph for the Line Drawings of Polyhedral Objects,” IEEE Trans. on Pat. Matching & Mach. Intelligence, vol. 12, no. 2, February 1990.
16. Glassner, Andrew S., ”Maintaining Winged-Edge Models,” In Graphics Gems II, edit. by Jim Arvo, Academic Press, 1991. –
17. Heckbert, Paul, ”Discontinuity Meshing for Radiosity,” 3rd Eurographics Workshop on Rendering, Bristol, UK May 1992.
18. Heckbert, Paul, ”Radiosity in Flatland,” Proc. of Eurographics ’92, Cambridge, Elsevier, September 1992.
19. Lischinski, Dani, Fillipo Tampieri, and Donald P. Greenberg, ”Discontinuity Meshing for Accurate Radiosity,” IEEE C.G. & Appl., vol. 12, no. 6, pp. 25-39, November 1992.
20. 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.
21. Poulin, Pierre and John Amanatides, ”Shading and Shadowing with Linear Light Sources,” Proc. of Eurographics ’90, 1990.
22. Rogers, David F. and J. Alan Adams, ”Mathematical Elements for Computer Graphics,” (2nd Edition) McGraw-Hill, 1990.
23. Salmon, G., ”Analytic Geometry of Three Dimensions,” Metcalfe, Cambridge, England 1874.
24. 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.
25. Stewart, A. James and Sherif Ghali, ”Fast Computation of Sha-dow Boundaries Using Spatial Coherence and Backprojections,” ACM SIGGRAPH Annual Conference Series, July 1994.
26. Tanaka, Toshimitsu and Tokiichiro Takahashi, ”Shading with Area Light Sources,” Proc. of Eurographics ’91, 1991.
27. Teller, Seth, ”Computing the Antipenumbra of an Area Light Source,” Computer Graphics (Proc. SIGGRAPH ’92), vol. 26, no. 2, pp. 139-148, July 1992.