Bruce Naylor
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.
- Bloomberg 86 Sandra H. Bloomberg,"A Representation of Solid Objects for Performing Boolean Operations", U.N.C. Computer Science Technical Report 86-006 (1986).Google Scholar
- Chin and Feiner 89 N. Chin and S. Feiner,"Near Real-Time Shadow Generation Using BSP Trees", Computer Graphics Vol. 23(3), pp. 99-106, (Aug. 1989). Google ScholarDigital Library
- Fuchs, Kedem, and Naylor 80 H. Fuchs, Z. Kedem, and B. Naylor, "On Visible Surface Generation by a Priori Tree Structures," Computer Graphtcs Vol. 14(3), pp, 124-133, (June 1980). Google ScholarDigital Library
- Fussell and Campbell 90 Donald Fussell and A.T. Campbell, "Adaptive Mesh Generation for Global Diffuse Illumination," Computer Graphics Vol. 24(3), (Aug. 1990). Google ScholarDigital Library
- Hoffmann 89 Christoph M. Hoffmann, Geometric and Solid Modeling, Morgan Kaufmann, 1989. Google ScholarDigital Library
- Karasick 89 Michael Karasick, "On the Representation and Manipulation of Rigid Solids," Ph.D. Thesis, ComeU University (March 1989). Google ScholarDigital Library
- Mantyla 88 Martti Mantyla, Solid Modeling, Computer Science Press, 1988.Google Scholar
- Naylor 81 Bruce F. Naylor, "A Priori Based Techniques for Determining Visibility Priority for 3-D Scenes," Ph.D. Thesis, University of Texas at Dallas (May 1981), Google ScholarDigital Library
- Naylor 90a Bruce F. Naylor, "SCULPT : An Interactive Solid Modeling Tool", Proc. of Graphics Interface, (May 1990). Google ScholarDigital Library
- Naylor 90b Bruce F. Naylor, "Binary Space Partitioning Trees as an Alternative Representation of Polytopes", Computer Aided Design, Vol 22(4), (May 1990). Google ScholarDigital Library
- 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).Google Scholar
- Paterson and Yao 89 M.S. Paterson and F.F. Yao, "Binary partitions with applications to hidden-surface removal and solid modeling", Proceedings of Fifth Syrup. on Computational Geometry, pp. 23-32, (1989). Google ScholarDigital Library
- Paterson and Yao 90 M.S. Paterson and F.F. Yao, "Optimal Binary Space Partitions for Orthogonal Objects", Proceedings of Ist Syrup. on Discrete Algorithms, pp. 100-106, (Jan. 1990). Google ScholarDigital Library
- 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).Google Scholar
- Sutherland, Sproull and Schumaker 74 I.E. Sutherland, R.F. Sproull and R. A. Schumacker, "A Characterization of Ten hidden Surface Algorithms," ACM Computing Surveys Vol 6(1), (1974). Google ScholarDigital Library
- Thibault and Naylor 87 W. Thibault and B. Naylor, "Set Operations On Polyhedra Using Binary Space Partitioning Trees," Computer Graphics Vol. 21(4), (July 1987). Google ScholarDigital Library
- Thibault 87 William C. Thibault, "Application of Binary Space Partitioning Trees to Geometric Modeling and Ray- Tracing", Ph.D. Dissertation, Georgia Institute of Technology, Atlanta, Georgia, (1987). Google ScholarDigital Library
- Torres 90 Enric Torres, "Optimization of the Binary Space Partition Algorithm (BSP) for the Visualization of Dynamic Scenes" Eurographics '90 (Sept. 1990).Google Scholar
Index Terms
- Merging BSP trees yields polyhedral set operations
Recommendations
Set operations on polyhedra using binary space partitioning trees
We introduce a new representation for polyhedra by showing how Binary Space Partitioning Trees (BSP trees) can be used to represent regular sets. We then show how they may be used in evaluating set operations on polyhedra. The BSP tree is a binary tree ...
Set operations on polyhedra using binary space partitioning trees
SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniquesWe introduce a new representation for polyhedra by showing how Binary Space Partitioning Trees (BSP trees) can be used to represent regular sets. We then show how they may be used in evaluating set operations on polyhedra. The BSP tree is a binary tree ...
Merging BSP trees yields polyhedral set operations
SIGGRAPH '90: Proceedings of the 17th annual conference on Computer graphics and interactive techniquesBSP 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, ...
Comments