“Near real-time shadow generation using BSP trees” by Chin and Feiner

This paper describes an object-space shadow generation algorithm for static polygonal environments illuminated by movable point light sources. The algorithm can be easily implemented on any graphics system that provides fast polygon scan-conversion and achieves near real-time performance for environments of modest size. It combines elements of two kinds of current shadow generation algorithms: two-pass object-space approaches and shadow volume approaches. For each light source a Binary Space Partitioning (BSP) tree is constructed that represents the shadow volume of the polygons facing it. As each polygon’s contribution to a light source’s shadow volume is determined, the polygon’s shadowed and lit fragments are computed by filtering it down the shadow volume BSP tree. The polygonal scene with its computed shadows can be rendered with any polygon-based visible-surface algorithm. Since the shadow volumes and shadows are computed in object space, they can be used for further analysis of the scene. Pseudocode is provided, along with pictures and timings from an interactive implementation.

1. Appel, A. “Some Techniques for Shading Machine Renderings of Solids.” AFIPS SJCC 68, 32, 1968, 37-45.
2. Atherton, P., Weiler, K., and Greenberg, D. “Polygon Shadow Generation.” Proc. S1GGRAPH ’78. In Computer Graphics, 12:3, July 1978, 275-281.
3. Bergeron, P. “A General Version of Crow’s Shadow Volumes.” IEEE CG&A, 6:9, September 1986, 17-28.
4. Blinn, J. “Jim Blinn’s Corner: Me and My (Fake) Shadow.” IEEE CG&A, 8:1, January 1988, 82-86.
5. Brotman, L.S., and Badler, N. “Generating Soft Shadows with a Depth Buffer Algorithm.” IEEE CG&A, 4:10, October 1984, 5-12.
6. Chin, N. “Shadow Generation Using BSP Trees.” M.S. Thesis, Dept. of Computer Science, Columbia University New York (forthcoming), 1989.
7. Cohen, M. and Greenberg, D. “The Hemi-Cube: A Radiosity Solution for Complex Environments.” Proc. SIGGRAPH ‘ 85. In Computer Graphics, 19:3, July 1985, 31-40.
8. Crow, F. “Shadow Algorithms for Computer Graphics.” Proc. S{GGRAFH ’77. In Computer Graphics, 11:3, July 1977, 242-248.
9. Foumier, A, and FusselI, D. “On the Power of the Frame Buffer.'” ACM Trans. on Graphics, 7:2, April 1988, 103- 128.
10. Fuchs, H., Kedem, A., and Naylor, B. “On Visible Surface Generation by A Priori Tree Structures.” Prec. SIGGRAPH “80. In Computer Graphics, 14:3, July t980, 124-I33.
11. Fuchs, H., Abram, G., and Grant, E. “Near Real-Time Shaded Display of Rigid Objects.” Proc. SIGGRAPH ’83. In Computer Graphics, 17:3, July 1983, 65-72.
12. Fuchs, H., Goldfeather, J’., Hultquist, J’., Spach, S., Austin, J., Brooks, Jr., F., Eyles, J., and Poulton, J. “Fast Spheres, Shadows, Textures, Transparencies, and image Enhancements in PixeI Planes.” Proc. SIGGRAPH ’85. In Computer Graphics, 19:3, July 1985, 111-120.
13. Haines, E. “A Proposal for Standard Graphics Environments.” IEEE CG&A, 7:11, November 1987, 3- 5.
14. Max, N. “Atmospheric Illumination and Shadows.” Proc. SIGGRAPH ‘ 86, In Computer Graphics, 20:4, August 1986, 117-124.
15. Nishita, T. and Nakamae, E. “Half-Tone Representation of 3-D Objects Illuminated by Area Sources or Polyhedron Sources.” IEEE COMPSAC, November 1983, 237-242.
16. Nishita, T., Okamura, I., Nakamae, E., “Shading Models for Point and Linear Light Sources.” ACM Trans. on Graphics, 4:2, April 1985, 124-146.
17. Nishita, T. and Nakamae, E. “‘Continuous Tone Representation of Three-Dimensional Objects Taking Account of Shadows and Interreflection.” Proc. SIGGRAPH ’85. In Computer Graphics, 19:3, July 1985, 23-30.
18. Schumacker, R., Brand, B., Gilliland, M., and Sharp, W. “‘Study for Applying Computer-Generated Images to Visual Simulation.” AFHRL-TR-69-14, USAF Human Resources laboratory, September 1969.
19. Sutherland, I., Sproull, R., and Schumacker, R. “A Characterization of Ten Hidden-Surface Algorithms.” ACM Comp. Surv., 6:1, March 1974, 1-55.
20. Thibault, W. and Naylor, B. “Set Operations on Polyhedra Using Binary Space Partitioning Trees.” Proc. SIGGRAPH “87. In Computer Graphics, 21:4, July 1987, 153-162.
21. Warn, D. “Lighting Controls for Synthetic Images.” Proc. SIGGRAPH ‘ 83. In Computer Graphics, 17:3, July 1983, 13-21.
22. Weiler, K. and Atherton, P. “Hidden Surface Removal Using Polygon Area Sorting.” Proc. SIGGRAPH ’77. In Computer Graphics, 11:2, July 1977, 214-222.
23. Weiler. K. “Polygon Comparison using a Graph Representation.” Proc. SIGGRAPH ’80. In Computer Graphics, 14:3, July 1980, 10-18.
24. Whitted, T. “Art Improved Illumination Model for Shaded Display.” CACM, 23:6, June 1980, 343-349.
25. Williams, L. “Casting Curved Shadows on Curved Surfaces.” Proc. SIGGRAPH’78. In Computer Graphics, 12:3, August 1978, 270-274.