Shadow volume BSP trees for computation of shadows in dynamic scenes

ABSTRACT

This paper presents an algorithm for shadow calculation in dynamic polyhedral scenes illuminated by point light sources. It is based on a modification of Shadow Volume Binary Space Partition trees, to allow these to be constructed from the original scene polygons in arbitrary order and to support for fast reconstruction after a change in scene geometry. Timings using sample scenes are presented that indicate substantial savings both in terms of computation time and shadows produced.

REFERENCES

• 1: George S Carson , Eileen McGinnis, The reference model for computer graphics, IEEE Computer Graphics and Applications, v.6 n.9, p.17-23, Aug. 1986 [doi>10.1109/MCG.1986.276543]
• 2: Alvin Theophilus Campbell, III, Modeling global diffuse illumination for image synthesis, University of Texas at Austin, Austin, TX, 1992
• 3: 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
• 4: 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]
• 5: Chrysanthou, Y., and Slater, M. Dynamic changes to scenes represented as BSP trees. Eurographics 92, Computer graphics Forum 11, 3 (1992), 321-332.
• 6: Franklin C. Crow, Shadow algorithms for computer graphics, ACM SIGGRAPH Computer Graphics, v.11 n.2, p.242-248, Summer 1977
• 7: Henry Fuchs , Gregory D. Abram , Eric D. Grant, Near real-time shaded display of rigid objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.65-72, July 1983
• 8: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.124-133, July 1980
• 9: Dan Gordon , Shuhong Chen, Front-to-Back Display of BSP Trees, IEEE Computer Graphics and Applications, v.11 n.5, p.79-85, September 1991 [doi>10.1109/38.90569]
• 10: Bruce F. Naylor, Partitioning tree image representation and generation from 3D geometric models, Proceedings of the conference on Graphics interface '92, p.201-212, September 1992, Vancouver, British Columbia, Canada
• 11: Bruce Naylor , John Amanatides , William Thibault, Merging BSP trees yields polyhedral set operations, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.115-124, Aug. 1990
• 12: M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
• 13: Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
• 14: Schumacker, R., Brand, B., Gilliland, M., and Sharp, W. Study for applying computer-generated images to visual simulation. Tech. Rep. AFHRL-TR-69-14, NTIS AD700375, U.S. Air Force Human Resources Lab., Air Force Systems Command, Brooks AFB, TX,, September 1969.
• 15: Mel Slater, A comparison of three shadow volume algorithms, The Visual Computer: International Journal of Computer Graphics, v.9 n.1, p.25-38, Oct., 1992 [doi>10.1007/BF01901026]
• 16: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
• 17: Torres, E. Optimization of the binary space partition algorithm (BSP) for visualization of dynamic scenes. Eurographics 90, Computer graphics Forum 9, 3 (1990), 507-518. C.E. Vandoni and D.A. Duce (eds.), Elsevier Science Publishers B.V. North-Holland.
• 18: Usoh, M., Slater, M., and Chrysanthou, Y. The influence of shadows on presence in immersive virtual environments. Submitted for publication (1994).
• 19: 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]

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Performance

Keywords:
BSP Trees, SVBSP Trees, dynamic modification, shadows