The idea of using boxes to bound complex shapes and prune costly geometric computations has been used in several fields for over a decade (see my work with N. Badler [1]). Within solid modeling, bounding “has passed into the folklore,” as the authors say. This paper presents the first formal analysis of using general bounds in constructive solid geometry (CSG), however. Here objects are represented as trees whose nodes represent set intersection, union, and perhaps difference, and whose leaves represent primitive solids. Bounding involves assigning bounding regions for the leaves and computing bounding regions for the internal nodes and ultimately for the root. These bounds can then be used as quick tests for collision detection in robotics, intersection detection for graphics ray tracing, and so on.

The simplest “bounding function” consists of circumscribing boxes, all aligned with the same coordinate axes. First consider positive trees, those employing only intersection and union nodes. Then bounds can be computed as follows. In an upward pass, a union node is assigned a box to circumscribe the union of the boxes of its children, and an intersection node is assigned the intersection of its children’s boxes. After this propagates to the root, a downward pass commences: each child’s box is replaced by its intersection with its parent’s box. The authors prove that this process converges to a unique fixed point after at most n up/down pass pairs, where n is the number of leaves of the tree.

What is more surprising is that natural variants of this procedure fail in some regard. Using spheres as bounding functions does not lead to unique fixed points. Convex hulls do converge to fixed points, but they are computationally expensive.

The authors classify bounding functions according to various useful properties, and they prove theorems that permit refining the bounds while preserving the properties. They also investigate “double-bounding functions,” which bound the objects from both inside and outside. They discuss the complications introduced by trees that include set difference nodes. After considering counterexamples to desired properties for double-bounding functions on difference trees, they reach the depressing conclusion that “it is not possible to combine inner and outer bounds in a consistent matter.” On the positive side, simple box-bounding exhibits rapid convergence in practice.

The paper oscillates between lucid high-level discussion supported by clear examples and turgid notation that takes some perseverance to penetrate. Effort is amply rewarded, however.