A Confinement-Based Hierarchy for Convex Differences Aggregates

S. Spitz and A. Rappoport

**
**
Constructive Solid Geometry (CSG) is a solid representation that is
appealing for interactive design of models through Boolean operations.
Unfortunately, there is a lack of efficient algorithms that render CSG
models at interactive rates using conventional computer graphics
hardware. The Convex Differences Aggregate (CDA) representation was
introduced to solve this problem. CDAs are defined as lists of cells
that represent the set theoretic difference of convex polyhedra, which
can be manipulated and rendered very efficiently during interactive
Boolean operations. Still, due to the linearity of the CDA structure,
the CDA algorithms do not scale well and are limited to the conceptual
design of relatively small models.

This paper extends the CDA representation through a confinement-based hierarchy. The Hierarchical CDA (HCDA) is organized as a tree of cells that has the advantage of a built-in spatial acceleration scheme and a level-of-detail (LOD) representation. We show how these mechanisms are exploited for scalability during interactive Boolean operations.