Set operations on polyhedra using binary space partitioning trees
William C. Thibault, Bruce F. Naylor · ACM SIGGRAPH Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH) · 1987
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.
Cited by 122 works. doi:10.1145/37401.37421
Authors
References
- Computational Geometry--An Introduction.
- Representations for Rigid Solids: Theory, Methods, and Systems
- Data Structures for Range Searching
- Geometric modeling using octree encoding
- Ray casting for modeling solids
- STUDY FOR APPLYING COMPUTER-GENERATED IMAGES TO VISUAL SIMULATION
- On visible surface generation by a priori tree structures
- Set Membership Classification: A Unified Approach to Geometric Intersection Problems
- On visible surface generation by a priori tree structures
- Mathematical Foundations of Constructive Solid Geometry: General Topology of Closed Regular Sets