William C. Thibault
Abstract
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 representing a recursive partitioning of d-space by (sub-)hyperplanes, for any dimension d. Their previous application to computer graphics has been to organize an arbitrary set of polygons so that a fast solution to the visible surface problem could be obtained. We retain this property (in 3D) and show how BSP trees can also provide an exact representation of arbitrary polyhedra of any dimension. Conversion from a boundary representation (B-reps) of polyhedra to a BSP tree representation is described. This technique leads to a new method for evaluating arbitrary set theoretic (boolean) expressions on B-reps, represented as a CSG tree, producing a BSP tree as the result. Results from our language-driven implmentation of this CSG evaluator are discussed. Finally, we show how to modify a BSP tree to represent the result of a set operation between the BSP tree and a B-rep. We describe the embodiment of this approach in an interactive 3D object design program that allows incremental modification of an object with a tool. Placement of the tool, selection of views, and performance of the set operation are all performed at interactive speeds for modestly complex objects.
- Ayal85 D. Ayala, P. Brunet, R. Juan, and 1, Navazo, "Object Representation by Means of Nonminimal Division Quad trees and Octrees," ACM Transactions on Graphics Vol. 4(1) pp. 41-59 (January 1985). Google Scholar
Digital Library
- Bent79 Jon Louis Bentley and Jerome H. Friedman, "Data Structures for Range Searching," Computing Surveys Vol. 11(4), pp. 397-409 (December 1979). Google ScholarDigital Library
- Carl85 Ingrid Carlbom, Indranil Chakravarty, and David Vanderschel, "A Hierarchical Data Structure for Representing the Spatial Decomposition of 3-D Objects," 1EEE Computer Graphics and Applications, pp. 24-31 (April 1985).Google ScholarDigital Library
- Fuch80 H. Fuchs, Z. Kedem, and B. Naylor, "On Visible Surface Generation by a Priori Tree Structures," Computer Graphics 1Iol. 14(3), (June 1980). Google ScholarDigital Library
- Fuch83 Henry Fuchs, Gregory D. Abram, and Eric D. Grant, "Near Real-Time Shaded Display of Rigid Objects," Computer Graphics VoL 17(3) pp. 65-72 (July 1983). Google ScholarDigital Library
- Kala82 Yehuda E. Kalay, "Determining.the Spatial Containment ofa Point in General Polyhedra," Computer Graphics and Image Processing Vol. 19 pp. 303-334 (1982).Google ScholarCross Ref
- Laid86 David H. Laidlaw, W. Benjamin Trumbore, and John F. Hughes, "Constructive Solid Geometry for Polyhedral Objects," Computer Graphics Vol. 20(4)pp. 161-170 (August 1986). Google ScholarDigital Library
- Mant83 Martii Mantyla and Markku Tamminen, "Localized Set Operations for Solid Modeling," Computer Graphics I/ol. 17(3) pp. 279-288 (July 1983). Google ScholarDigital Library
- Meag82 D. Meagher, "Geometric Modeling using Octree Encoding," Computer Graphics and Image Processing 1Iol. 19(June 1982).Google Scholar
- Nayl81 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
- Nay186 Bruce F. Naylor and William C. Thibault, "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
- Prep85 Franco P. Preparata and Michael ion Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York (1985). Google ScholarDigital Library
- Putn86 L. K. Putnam and P. A. Subrahmanyam, "Boolean Operations on n-Dimensional Objects," IEEE Computer Graphics and Applications, pp. 43-51 (June 1986). Google ScholarDigital Library
- Requ78 Aristides A. G. Requicha and Robert B. Tilove, "Mathematical Foundations of Constructive Solid Geometry: General Topology of Closed Regular Sets," TM-27a, Production Automation Project, University of Rochester, Rochester, New York 14627 (June 1978).Google Scholar
- Requ80 Aristides A. G. Requicha, "Representations for Rigid Solids: Theory, Methods, and Systems," Computing Surveys 1Iol. 12(4) pp. 437-464 (December 1980). Google ScholarDigital Library
- Requ85 Aristides A. G. Requicha and Herbert B. Voelcker, "Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms," Proceedings of the IEEE Vol. 73(1) pp. 30-44 (January 1985).Google ScholarCross Ref
- Roth82 Scott D. Roth, "Ray Casting for Modeling Solids," Computer Graphics and Image Processing Vol. 18 pp. 109-144 (1982).Google ScholarCross Ref
- Schu69 R. A. Schumacker, R. Brand, M. Giltitand, and W. Sharp, "Study for Applying Computer-Generated Images to Visual Simulation," AFHRL-TR-69-14, U.S. Air Force Human Resources Laboratory (t969).Google Scholar
- Thib87 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
- Tilo80 Robert B. Tilove, "Set Membership Classification: A Unified Approach to Geometric Intersection Problems," IEEE Transactions on Computers VoL C-2900) pp. 874-883 (October 1980).Google Scholar
- Tilo84 Robert Tilove, "A Null-Object Algorithm for Constructive Solid Geometry," Communications of the ACM Vol. 27(7) (July 1984). Google ScholarDigital Library
- Wood82 J. R. Woodwark and K. M. Quinlan, "Reducing the effect of complexity on volume model evaluation," Computer Aided Design Vol. 14(2) (1982).Google Scholar
Index Terms
- Set operations on polyhedra using binary space partitioning trees
Recommendations
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 ...
Binary space partitioning trees: a multiresolution approach
IV '97: Proceedings of the IEEE Conference on Information VisualisationSpace partitioning techniques are a useful means of organizing geometric models into data structures. Such data structures provide easy and efficient access to a wide range of computer graphics and visualization applications like real time rendering of ...
Comments