Active Zones in Constructive Solid Geometry for Redundancy and Interference Detection
Voelcker, Herbert B., Rossignac, Jaroslaw R. · UR Research (University of Rochester)
Solids are represented in Constructive Solid Geometry (CSG) as Boolean combinations (binary trees) of primitive solids. CSG representations are not unique, and may contain primitives and sub-trees that are redundant, i.e.: may be removed without altering the represented solid. Null (empty) solids, which are important in collision detection and other applications, provide a blatant example, because they may have arbitrarily elaborate CSG representations in which all primitives are redundant. Tilove's pioneering work on null object detection (NOD) in CSG provided a definition of redundancy, a proof that all primitives are redundant in CSG representations of the empty set, and a test for detecting redundancy in empty set representations. We extend Tilove's work considerably by associating with each sub-tree of a CSG representation an active zone which is the region of space where changes to the set represented by the sub-tree affect the set represented by the whole tree. Properties of the active zones developed in this paper lead to improvements of Tilove's NOD test, to a simple and efficient formulation of redundancy in CSG representations of sets that may be non-empty, and to the design of more efficient set membership classification algorithms that are central to some more important applications of CSG.