1990 · 213 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometrySet TheoryBoolean AlgebraBoolean OperationsSpatial Data StructuresSpatial PartitioningB-treesBoolean Operations On ShapesPolyhedral Boolean OperationsSet-theoretic Boolean OperationsSpatial Subdivision AlgorithmsSubdivisionTree AlgorithmsTree Merging
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.
15
On visible surface generation by a priori tree structures
Henry Fuchs, Zvi M. Kedem, Bruce Naylor · 1980 · 698 citations · Full text
Christoph M. Hoffmann · 1989 · 390 citations
Architecture, Manufacturing Engineering, Computational Geometry +6
Near real-time shadow generation using BSP trees
Norman Chin, Steven Feiner · 1989 · 140 citations