Merging BSP trees yields polyhedral set operations

ABSTRACT

BSP trees have been shown to provide an effective representation of polyhedra through the use of spatial subdivision, and are an alternative to the topologically based b-reps. While bsp tree algorithms are known for a number of important operations, such as rendering, no previous work on bsp trees has provided the capability of performing boolean set operations between two objects represented by bsp trees, i.e. there has been no closed boolean algebra when using bsp trees. This paper presents the algorithms required to perform such operations. In doing so, a distinction is made between the semantics of polyhedra and the more fundamental mechanism of spatial partitioning. Given a partitioning of a space, a particular semantics is induced on the space by associating attributes required by the desired semantics with the cells of the partitioning. So, for example, polyhedra are obtained simply by associating a boolean attribute with each cell. Set operations on polyhedra are then constructed on top of the operation of merging spatial partitionings. We present then the algorithm for merging two bsp trees independent of any attributes/semantics, and then follow this by the additional algorithmic considerations needed to provide set operations on polyhedra. The result is a simple and numerically robust algorithm for set operations.

REFERENCES

• Bloomberg 86: Sandra H. Bloomberg,"A Representation of Solid Objects for Performing Boolean Operations", U.N.C. Computer Science Technical Report 86-006 (1986).
• Chin and Feiner 89: 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
• Fuchs, Kedem, and Naylor 80: 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
• Fussell and Campbell 90: 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
• Hoffmann 89: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• Karasick 89: M. S. Karasick, On the representation and manipulation of rigid solids, McGill University, Montreal, Que., Canada, 1989
• Mantyla 88: Martti Mantyla, Solid Modeling, Computer Science Press, 1988.
• Naylor 81: Bruce Fountain Naylor, A priori based techniques for determining visibility priority for 3-d scenes, 1981
• Naylor 90a: B. Naylor, SCULPT: an interactive solid modeling tool, Proceedings on Graphics interface '90, p.138-148, June 1990, Halifax, Nova Scotia
• Naylor 90b: B. Naylor, Binary space partitioning trees as an alternative representation of polytopes, Computer-Aided Design, v.22 n.4, p.250-252, May 1990 [doi>10.1016/0010-4485(90)90055-H]
• Naylor and Thibault 86: Bruce F. Naylor and William C. Thibauh, "Application of BSP Trees to Ray-Tracing and CSG Evaluation," Technical Report GIT-ICS 86/03, School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Georgia 30332 (February 1986).
• Paterson and Yao 89: 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]
• Paterson and Yao 90: Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.100-106, January 22-24, 1990, San Francisco, California, United States
• Schumaker et al 69: R. A. Schumacker, R. Brand, M. G illiland, and W. Sharp, "Study for Applying Computer-Generated Images to Visual Simulation," AFHRL-TR-69-14, U.S. Air Force Human Resources Laboratory (1969).
• Sutherland, Sproull and Schumaker 74: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• Thibault and Naylor 87: 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
• Thibault 87: William Charles Thibault , Bruce F. Naylor, Application of binary space partitioning trees to geometric modeling and ray-tracing, 1987
• Torres 90: Enric Torres, "Optimization of the Binary Space Partition Algorithm (BSP) for the Visualization of Dynamic Scenes" Eurographics '90 (Sept. 1990).

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  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: Curve, surface, solid, and object representations

General Terms:
Algorithms