DIMENSION-INDEPENDENT BSP (2): BOUNDARY-TO-INTERIOR MAPPING
Claudio Baldazzi, Alberto Paoluzzi · International Journal of Shape Modeling · 1998
In this paper we discuss a CSG/BSP algorithm to perform the conversion from the boundary to the interior of d-dimensional polyhedra. Both a d-dimensional polyhedral point-set and its boundary (d;1)-faces are here represented as BSP trees. In this approach no structure, no ordering and even no orientation is required for such boundary BSPtrees. In particular it is shown that the interior point-set may be implicitly represented as the Boolean XOR of unbounded polyhedral "stripes" of dimension d, which are bijectively associated to the (d - 1)-faces of the d-polyhedron. A set of quasi-disjoint convex cells which partitionate the polyhedron interior may be computed by explicitly evaluating such CSG tree with XOR operations on the non-leave nodes and with BSP (stripe) trees on the leave nodes.