Active Zones in CSG for Accelerating Boundary Evaluation, Redundancy Elimination, Interference Detection, and Shading Algorithms

Abstract

Solids defined by Boolean combinations of solid primitives may be represented in constructive solid geometry (CSG) as binary trees. Most CSG-based algorithms (e.g., for boundary evaluation, graphic shading, interference detection) do various forms of set-membership classification by traversing the tree associated with the solid. These algorithms usually generate intermediate results that do not contribute to the final result, and hence may be regarded as redundant and a source of inefficiency. To reduce such inefficiencies, we associate with each primitive A in a tree S an active zone Z that represents the region of space where changes to A affect the solid represented by S, and we use a representation of Z instead of S for set-membership classification. In the paper we develop a mathematical theory of active zones, prove that they correspond to the intersection of certain nodes of the original trees, and show how they lead to efficient new algorithms for boundary evaluation, for detecting and eliminating redundant nodes in CSG trees, for interference (null-set) detection, and for graphic shading. © 1988, ACM. All rights reserved.