Refinement methods for geometric bounds in constructive solid geometry.
In constructive solid geometry, geometric solids are represented as trees whose leaves are labeled by primitive solids and whose internal nodes are labeled by set-theoretic operations. A bounding function in this context is an upper or lower estimate on the extent of the constituent sets; such bounds are commonly used to speed up algorithms based on such trees. We introduce the class of totally consistent bounding functions, which have the desirable properties of allowing surprisingly good bounds to be built quickly. Both outer and inner bounds can be refined using a set of rewrite rules, for which we give some complexity and convergence results. We have implemented the refinement rules for outer bounds within a solid modeling system, where they have proved especially useful for intersection testing in three and four dimensions. Our implementations have used boxes as bounds, but different classes (shapes) of bounds are also explored. The rewrite rules are also applicable to relatively slow, exact operations, which we explore for their theoretical insight, and to general Boolean algebras. Results concerning the relationship between these bounds and active zones are also noted.
Introduction
Outer bounds are commonly used to speed up geometric algorithms. For example, if we
wish to tell whether two geometric entities intersect, then if we form spheres around the
entities and the spheres do not intersect, we deduce that the entities cannot intersect. This
concept of a bound is so 'obvious' that it may seem strange that we can spend an entire
paper talking about bounds! However, some subtleties arise if we allow bounds which are
not bounds in the normal sense but do have desirable computational properties. We will
show that these other types of bounds are possible, and useful, when geometric entities
are described constructively.
In Constructive Solid Geometry (CSG), we build up complicated shapes from a collection
of simple shapes [11]. We can think of a CSG description as a tree, in which the
internal nodes correspond to set operations, and the leaf nodes correspond to the simple
shapes, or primitives, and the branches of the tree imply functional application. To compute
the shape represented by the tree, we start at the leaves and work our way up the
tree, applying set operations as we go. Many modelling systems use CSG as their primary
construction method (e.g., [3, 6]), and many other systems permit constructive operations
in making up their data-structures (e.g., [2]).
The normal way of applying bounds with a CSG tree is to attach suitable supersets of
the primitives (the bounds) to the leaf nodes. However we can then extend the notion of a
bound to every node in the tree, as follows. If we have a binary node T , corresponding to
a union operation, and we know that its child nodes represent shapes that are bounded by
S l and S r , then the shape represented by T must be contained within S l [ S r , and so this
set is a bound on T . Similarly, if the node corresponded to an intersection operation then
the corresponding composite bound would be S l " S r . In this way we could recursively
compute a bound for every node in the tree. Other considerations arise to make this idea
more involved: in particular, for efficiency of processing we may desire the bounds at each
node to be a 'rectangle' (of appropriate dimensionality). Then S l [ S r must be replaced
by the smallest enclosing rectangle. If other shapes are desired, the solution may not be
so obvious.
However, besides the propagation of bounds upwards in a tree, we can also have downward
propagation. Consider a simple example, where the 'shapes' are one dimensional
lines. If shape A can be bounded by the interval [0; 2], and shape B by [1; 3] then we can
bound A " B by [1; 2]. Thus if we want to compute the intersection, we should only have
to worry about intersection points within [1; 2], and so [1,2] should be a bound on both A
and B (in this new sense).
These observations form the basis for all of the work reported: from them we have
obtained practical insight that has allowed us to significantly speed up certain geometric
computations in a solid modelling system, as well as discovering a rich area for theoretical
results. The practical implementations have been detailed elsewhere [4, 5], and so the
emphasis in this paper is on the theoretical underpinnings. However for clarity we will
first describe the main results using the system of bounding boxes that form the basis of
our practical implementation (x2), and how it relates to other work (x3), before considering
the general cases that apply for any type of system of bounds that obey our rules (x4). x5
will continue the study of such bounds, with algebraic properties and convergence results
for different types of bounds (e.g., boxes, spheres, and convex hulls). We will then consider
two other, related, bounding systems. In x6 we will consider bounds based on subsets of
objects, rather than supersets, which turn out to have dual properties to the properties of
the superset bounds. All the above discussion is based on CSG trees limited to set union
and set intersection operations. In x7 we will show that these results do not entirely hold
if we have complement or difference operators in our CSG trees; however, we show that
a slightly less general system of bounds, called S-bounds, can be successfully applied in
these cases. (S-bounds are, in fact, the basis of our implementations.)

Overview

The one-dimensional example of x1 introduced the reasoning behind the rules that we use
to reason about the extent of expressions in a CSG tree; a two-dimensional example will
suffice to illustrate the practical use of these ideas. Consider figure 1(a), which shows a
small CSG tree with two operators, \Phi
and\Omega denoting union and intersection respectively.
The squares in the figure are frames that help to show the relative size and position of
polygons, three of which are primitive shapes (shown at the leaves of the tree), and the
fourth shows the final shape denoted by the tree 1 (i.e., the union of the triangle and the
parallelogram, intersected with the wedge.) We can now consider bounds on the tree nodes,
restricting ourselves to boxes aligned with the frames. Such a restriction makes a lot of
sense computationally, as each box can be denoted by four numbers, and they are easy
to work with. Figure 1(b) shows bounds that are larger than the primitive polygons, and
also shows bounds on the two internal nodes of the tree; as we have no a priori knowledge
of what constitutes sensible bounds for these nodes we will
use\Omega\Gamma the universal set,
as\Omega is bigger than any set.
We are now in a position to apply the reasoning described in x1. Working our way up
the tree, we take the union of the lower two primitives' bounds, and this indeed will be a
superset of the partial shape given by the union node in the tree. However, for computational
reasons we actually store a box that fits around the union of the two bounds, rather
than the union itself, and indeed this box can be generated directly (without explicitly
forming the union of the bounds) by taking maxima and minima of the coordinates that
defined the corners of the leaf-node boxes. This box is shown in figure 1(c) (the boxes that
were used to generate it are shown dashed). We now have two finite bounds below the
root node of the tree, and a finite bound for this node can now be generated, by taking
the intersection of the two bounds on its child nodes (figure 1(d)).
We now have supersets of the shapes formed by evaluating the CSG tree at every node
in the tree. If we now treat the box at the root node as a 'window' through which all of the
interesting parts of the tree can be viewed, we can take this window and intersect it with
the boxes at its child nodes. Repeating this process about the union node, we can intersect
the new bound found here with its two children, giving the bound set of figure 1(e). The
boxes that have been generated are no longer supersets of the partial shapes generated
if we were to evaluate the tree in the normal way (shown dotted), and in particular the
left-most node has an empty box (;) as its bound now. However, if we evaluate the tree,
1 The terminology will be made precise in x4.
using the bounds generated as windows on which parts of the partial shapes to bother
evaluating (throwing out parts that lie outside their windows), we will indeed obtain the
same shape as before at the root node of the tree.
The general form of the rules are as follows. Working our way up the tree, take the set
operation at a node, apply it to the two bounds in the child nodes, and intersect the result
with the bound that was already at the node. (The usage described in the example was
a special case of this rule, as the existing bounds were both \Omega\Gammah Working our way down
the tree, take the bound at a parent node and intersect it with the bound at the child
node, replacing the child's bound. As we shall see, the order of applying the rules does
not affect the validity of the process as we always end up with a suitable set of 'windows'.
However, the natural order of working our way from the bottom up, and then working our
way down again, is guaranteed to continue making progress. What may be surprising is
that we may often improve matters by repeating the process; the example of figure 1 is
a case in point, whereby performing another sweep up the tree and then down the tree
gives us the set of bounds of figure 1(f). In this case applying the rules again makes no
difference. The fact that the left-most node is bounded by ; means that we can ignore
this node entirely 2 , and we can in fact replace the original tree by a simpler tree that is
the intersection of the parallelogram and the wedge. Further, we only need to worry about
computing the intersection within the relatively small window (bound) that has formed
about the root node. This fact may not make much difference in this simple case, but
we can apply the same sort of reasoning for arbitrarily complex primitive shapes in any
number of dimensions.
As a three-dimensional example, figure 2(a) shows a robot (modelled using 19 primitive
shapes) in an environment (modelled using 4 primitive shapes). We can perform interference
testing between the robot and the environment by checking whether their intersection
set is empty (null). Thus we form, symbolically, the CSG tree that represents this intersection
set, and we could evaluate this immediately. Instead we use aligned three-dimensional
boxes to bound each node in the tree. Figure 2(b) shows the finite boxes 3 initially formed
about the primitive nodes; we can then work our way up and down the tree, using the
refinement rules, until the bounds are no longer changing. In this case, every node in the
tree becomes bounded by ; after two passes, implying that the intersection is null without
even having to consider the detailed geometry. Rotating the waist joint of the robot to
ensure interference gives us an example in which the objects do interfere: figure 2(c) shows
an outline of the objects, with the thick lines around the intersection volume showing the
5 non-empty bounds left after three passes. The smallness of these bounds means that the
subsequent processing required to prove interference requires little computation time [4].
We may be tempted to ask questions about the way that the bound system converges-
if at all. These issues are detailed later in this paper, but basically:
ffl This bound system always does converge. Further, using the natural application
sequence described, it always converges in at most n \Gamma 1 passes up and down the
tree, and it always converges to the same final state (given the same starting state).
ffl These results apply whatever the dimensionality of the boxes used.
Tilove calls such nodes ;-redundant [15].
3 Infinite half-spaces were used to model the robot, which are initially bounded by \Omega\Gamma
@
@
@ @
@
@ @
(b)
\Omega \Omega (c)
\Omega (d) (e)

Figure

1: Two-Dimensional Example
Y
Z
(b)
Y
Z
(c)

Figure

2: Three-Dimensional Example
ffl Rules also exist for trees with difference and complement operations in them.
ffl Similar (though not as powerful) results hold for other types of bounds, such as
bubbles and convex hulls.
3 Related Work
The use of bounds has passed into the folklore of computational geometry and solid mod-
elling. Most of the work described here has been heavily influenced by work at the University
of Rochester's Production Automation Project, which resulted in the padl series
of geometric modelling systems. In particular, Tilove introduced the notion of redundant
primitives [14] and others at the project investigated some of the 'obvious' rules described
here, which were later introduced into padl-2. However they did not introduce the abstraction
of a bounding function (which allows us to consider the algebraic and convergence
properties of these rules), and they did not generalise the rewrite rules to allow multiple
applications [9]. Instead they took the idea that we call 'consistency' and defined a concept
called the active zone, which is effectively (in our notation) the 'smallest' possible consistent
bound [12, 8]. Active zones have been used to design faster geometrical operations
on CSG trees, especially boundary evaluation, but instead of being evaluated directly they
are used to prune geometric information within complex geometric computations (such as
boundary evaluation). In contrast, our work has concentrated on a general, computational
framework for arbitrary bounds, which may be evaluated efficiently, normally as a preprocessing
stage. We have implemented this work as part of the robmod geometric modelling
system [6], where it has proved especially useful for interference detection [4] and collision
detection (by considering intersections in four-dimensional space-time [5]).
Totally-Consistent Bounds
We now start the formal analysis of systems of bounds. To characterise bounds we need
some notation and conventions that allow us to discuss them; in particular, we need to
be able to distinguish between the CSG tree as a data-structure within the computer,
and the set 4 represented by that data-structure. Thus we say that a tree consists of a
number of internal nodes, which we label with the symbols
\Phi,\Omega and \Psi, corresponding
to the operations [, " and \Gamma (set difference) respectively 5 . The leaf nodes of the tree
correspond to primitive shapes; we label these nodes as convenient (e.g., L, P n ). Any node
in the tree can also be given a convenient label to uniquely distinguish it for the purpose
of the discussion. We use T , T 1 , etc., as labels for general nodes, and reserve the label T
for the root node of the entire tree. We can also regard the label of a node as standing for
the subtree with that node as the root-these uses may be distinguished by context.
For most of this paper we will consider only trees with union and intersection nodes,
called positive trees. This is not a theoretical limitation as we can always rewrite a tree
that contains difference nodes using the set identity (where is the
set complement operation), and we can always rewrite a tree that contains complement
operations by repeated use of De Morgan's Laws, starting at the root node of the tree and
working down towards the leaves. However there may be practical reasons for preferring
to deal with the original tree, and in x7 we discuss the case where these other operators
are allowed.
These foundations allow us to describe a tree as a syntactic structure: to enable us to
assign some semantics to a tree we need to know what shapes each leaf node corresponds to.
We assume the existence of a primitive interpretation function, ', which takes a leaf node
and returns a shape (i.e., a subset of ! n ). Given this we can compute the corresponding
full interpretation function, j \Delta j, by the obvious rules: if L is a leaf node,
gives the set operation corresponding to the node ?. Thus
the shape of the entire tree is given by jT j.
How do we add the idea of a bound to this framework? We want to consider bounds
attached to every node of a tree, and to do this we define bounding functions; a bounding
function (BF) takes a node of a tree and returns a subset of space 6 . We use fi, fi 0 , etc., to
denote bounding functions. Then we say that a bounding function fi is a standard BF if
. (In this discussion we assume that we have some fixed tree
T and fixed primitive interpretation ' in mind.) The normal idea of a bound is to just use
standard bounds, but we will show that non-standard bounds are also useful.
If we have bounds in a tree, we expect it to imply that the bound fi(T ) for a node T
is a region, outside of which T can be ignored. (We will only consider outer bounds for
now; inner bounds will be considered in x6.) This leads us to define a new interpretation
function for a tree, the bounded interpretation (j \Delta j fi ), as follows:
4 Subset of ! n , for some n.
5 We distinguish the tree node labels from the corresponding set operations as we will want to alter the
bound (set) stored at the nodes.
6 A single bounding function can be 'implemented' by storing the specification of a set, say a simple
box, at each node in the tree; the rules we will describe can then refine this bound recursively without any
extra space requirements.
Otherwise, T is a leaf node, and jT j
Note that for standard bounds fi we will always have jT j
computing a shape jT j the important thing is not the intermediate computations, but
rather the final answer. Thus we further distinguish the consistent bounding functions, as
follows:
\Pi Definitions We say that fi is consistent (on T over ') if jT j and we
say that fi is totally consistent if jT j fi bounding functions
Here the notation f v g, or g w f , means that f and g are functions over the same domain
with f(T ) ' g(T ) for all arguments T .
The idea behind total consistency is that we should be able to expand a totally consistent
bound without losing consistency. In fact, consistency implies total consistency for
positive trees (proof below), and so to explain the difference between the two concepts
we will use an example containing a set difference operator. Consider a tree
under the primitive interpretation function Y the
two rectangles shown in figure 3(a); then jT Then the bounding
function
is consistent, but not totally consistent, as if we replace the bound on A by the set Z
shown in figure 3(c) then the new bounding function is no longer consistent. On the other
hand, the bounding function
is totally consistent (although it would not be generated by the procedures detailed in this
paper).
In the rest of this paper our main consideration will be the generation of bounding
functions that are totally consistent. We demand total consistency, rather than just con-
sistency, for two reasons. Firstly, because it is more in the spirit of the notion of a bound
that a bound should be a 'lower' bound, and so it should be possible to expand a bound
arbitrarily. Secondly, and more practically, we have introduced rewrite rules that allow us
to form smaller consistent bounds. However, if we start with, say, spherical bounds, which
are consistent but not totally consistent, we could not apply the rewrite rules without
generating non-spherical bounds. With totally consistent bounds we can generate a new
totally consistent bound with the rewrite rules, which can then be expanded to form (say)
a sphere.
We can prove that the notions of consistency and total consistency are equivalent for
positive trees by invoking the concept of monotonicity. If we are given a fixed CSG tree
T then we could write out the value returned by the bounded interpretation function as a
function of the bounds, say
(c)
(b)
(a)
Z
Y

Figure

3: An example of a consistent bounding function which is not totally consistent
are all of the nodes in the tree. This V would contain only [ and "
operations. But [ and " are monotonic, that is, whenever W ' X and Y ' Z we have
(Informally: a set of operations is monotonic if any formula over them gets bigger if the
arguments get bigger.) Now if fi is consistent (on T over ') with any fi 0 w fi, and
fi\Omega is the
BF that always
returns\Omega\Gamma we have
with the middle inequalities arising from the monotonicity of V , thus proving the conjecture

We will emphasis total consistency as the desirable property from now on. As a matter
of notation, we abbreviate totally consistent bounding function as TC-BF, and totally
consistent bound as TC-bound. We can see immediately that any standard bounding
function is totally consistent. To generate other bounding functions we may invoke the
principles explained earlier, viz:
\Pi The Upward Principle Given a BF fi over a tree T , and an internal
node T of the form replace the bound at T by a superset of
\Pi The Downward Principle Given a BF fi over a tree T , and a node T 6= T
with parent T p , replace the bound at T by a superset of fi(T
To justify these principles we have the two theorems:
\Pi The Upward Theorem Let T be a bounded tree with TC-BF fi. If T is
any subtree of T such that another TC-BF for T is given by
differs from fi only at T , with fi 0 (T
\Pi The Downward Theorem Let T be a bounded tree with TC-BF fi. If
T is any subtree of T , and T 0 is an immediate subtree of T , then another
TC-BF function for T is given by fi 0 , which differs from fi only at T 0 , with
Note that the fact that any BF that returns supersets of a TC-BF is also a TC-BF (from the
definition of total consistency) means that we can consider strict equality in the statement
of these theorems. The theorems will be generalised in x6, and a proof of the generalised
theorems is given in the appendix.
5 Applying TC-bounds
The Upward and Downward Principles (and the associated theorems) tell us how to make
legal rewrites of the bounds associated with a CSG tree. The Principles themselves are not
deterministic, as we have the freedom to chose any superset of the appropriate smallest
bound, but in practise we would chose a way of specifying a suitable superset, and use
deterministic rules instead. To chose the rules, we need to decide on a class K of bounds
(such as boxes, spheres, etc.), then we write down two operators, u and t, that are the
analogues of " and [ but always return results from K. That is, for all A; B 2 K, we we
require AuB 2 K and AtB 2 K, with AuB ' A `` B and AtB ' A[B, and we would
normally attempt to chose u and t to return the smallest such bound from K. Then the
rules are as follows:
\Pi The Upward Rule Given a BF fi over a tree T , and an internal node T of
the form replace the bound at T by fi(T ) u [fi(T l ) \Pi fi(T r )], where
\Pi is u if ?
is\Omega , and t if ? is \Phi.
\Pi The Downward Rule Given a BF fi over a tree T , and a node T 6= T
with parent T p , replace the bound at T by fi(T ) u
We have another choice to make when implementing these bounds, namely the order
in which to apply the rules. The examples of figure 1 and figure 2 used the natural
application order that we use in our work. We define an Up pass to be a bottom-up set of
applications of the Upward rule throughout the tree, and a Down pass to be a top-down
set of applications of the Downward rule throughout the tree. Thus our usual order of
application is to generate a TC-BF by computing standard bounds for the leaf nodes and
setting the internal bounds to \Omega\Gamma and then apply a number of Up pass/Down pass pairs.
It is then interesting to consider the convergence properties of a TC-BF system, the first
question being, does the set of bounds generated converge to some final value? Further,
even if the bounds converge we may not know whether they converge to a unique set of
values, as the final set of values might depend on the order in which the rules are applied.
However, if the bound operators are monotonic and converge (as is true for aligned boxes)
then a unique answer is assured:
Theorem 1 If the operators t and u are monotonic then any fixed-point
obtained by application of the Upward and Downward rules is unique (for a
given initial fi).
Proof If a fixed-point 7 is not unique then there exists distinct fi 1 and fi 2 such that fi 1 is
formed by some number of application of the rules; denote this as fi Similarly,
Now as each operation gives a smaller BF, we have
as oe 1 is a a fixed-point of the system, and so the left-most term of
(1) is fi 1 , and we have contradicting the fact that they are
distinct.
We will now consider some specific TC-BF systems, starting with what is probably the
most useful, the aligned box system.
5.1 The Aligned Box System
We consider in detail the case of a two-dimensional aligned box system; the same arguments
apply to any number of dimensions. In two dimensions each box (a rectangle) can be
described as a four-tuple, viz.:
To combine such boxes with the rewrite rules we need a pair of combination operators,
which we will write u and t to distinguish them from the general case. The obvious
operators to use are:
Note that we may
denote\Omega as h\Gamma1; \Gamma1; 1;1i, for which the above formulae hold, but
that the formulae given do not hold if any bounds are ;, and so we need to be able to
identify instances of ; when formed, and treat them explicitly (by using identities such as
These operators can be applied in unit time; other properties include the
identity A u B, and that both operators are commutative and associative, but
neither (in general) distributes over the other. A general BF system is a set of bounds,
plus a pair of specific operators (u; t). We call a system of bounds consisting of aligned
boxes (in some number of dimensions) and (u; t) a Box-BF system.
That the two-dimensional Box-BF system converges is easily seen, using an argument
that can be applied to other systems of bounds. Namely, if n is the total set of initial
bounds then there are at most n values for each parameter in the four-tuple, and as the
t and u operators do not generate new values then the set of all possible bounds is finite.
Convergence now follows from the fact that the set of bounds is monotonically decreasing
in size under this TC-BF system. In fact we can do better than this, and show that the
number of Up pass/Down pass pairs required is strictly limited to n, where n is the number
of leaf nodes in the tree.
7 A fixed-point of a bounding system is a set of bounds whose values are not changed by any of the
available rewrite rules
We call a BF system sensible if the operator X. All of
the systems we will consider are sensible (and, indeed, also satisfy X ' Y
and the operators u and t are all commutative.
BF is a fixed-point if the system is sensible and
Proof: by inspection of cases, and noting that the sensibility condition implies that u is
idempotent (X u
If we take a Box-BF and apply an Up pass followed by a Down
pass, the new Box-BF is a fixed-point if no new null (;) bounds were generated.
Proof of Lemma 2: Let fi 1 be the result of applying an Upward pass to fi 0 , and fi 2 the
result of applying a downward pass to fi 1 , and assume that there are no new null bounds
created. We wish to show that fi 2 satisfies the conditions of Lemma 1. Firstly, note that
if there are any existing null bounds (in fi 0 ), then all of the descendent nodes must also
be null bounded (otherwise the Down pass that generates fi 2 will force these to be null,
contradicting the fact that no new null bounds were generated). A simple case analysis
then confirms that any null-bounded internal node must satisfy the conditions of Lemma
1. So consider the values at any internal node T which is not null-bounded.
Case 1:
Note that fi 1 (T l Similarly,
Case 2:
As all of the resulting bounds are non-null, we can apply the conditional distributive
identity
to show
as To demonstrate that (2) holds first consider
the one-dimensional case, where each bound is a closed interval with, say,
with reference to the identities
and recalling that X u Y and X u Z must both be non-empty, we obtain
which proves the result for the one-dimensional case. The result extends to the multi-dimensional
case (for any number of dimensions) by considering each dimension separately,
as an aligned box is the Cartesian product of intervals.
\Pi Corollary The aligned box TC-BF system will converge after (at most) n
Up pass/Down pass pairs, where n is the number of leaves in the CSG tree.
The corollary follows because if a subtree becomes bounded by ; then it has reached
convergence 8 . But, by Lemma 2, after each Up pass/Down pass pair then either the
bounding function becomes a fixed-point or some subtree becomes null bounded. In prac-
tise, for examples that we have generated from models of real objects, only a few (say,
two or three) passes are required for convergence to be reached. However we can generate
artificial examples which require a linear number of passes to converge. Consider
the tree
have not made the binary tree structure explicit and where I k corresponds to the open
interval 1). (This example corresponds to finding the intersection of two interlocking
'combs'.) Then successive Up pass/Down pass pairs give the following bounds on T :
1), ;, and so we require approximately
to reach convergence, where n is the number of leaf nodes in the tree.

Figure

4 illustrates a two-dimensional case which requires exactly
consider a tree that takes the union of all the vertical bars, and intersects that with the
union of all the horizontal bars. After each Down pass the topmost or rightmost bar is
(alternately) bounded by ; 9 .
5.2 Other Practical TC-BF Systems
5.2.1 Spherical Bound System
If we use spheres (of any dimensionality) as our bounds, there are a unique natural pair of
operators -
t such that the new spheres resulting from applying the operators have
the smallest possible volume. A spherical bound is described by its centre and its radius,
say Given two such spheres, say d is the
Euclidean distance between c l and c s the operators are given by:
ffl if the operation is -
t, we get two cases:
8 We can use this fact to speed up algorithms based on these results by pruning out parts of the tree
that become null-bounded [4].
9 This is, in fact, a worst case for a Box-BF system. For if there were a tree with n leaves that takes
exactly n passes to converge, then after there must be 1 non-null leaf left.

Figure

4: Worst-case example for Box-BFs
sphere enveloped by larger sphere) then the result is the
same as the larger sphere;
- otherwise, the result is a new sphere, namely
ffl if the operation is -
u, we get three cases:
(spheres apart), the result is ;;
s , the result is the same as the smaller sphere;
- otherwise the result is a new sphere, namely
l r 2
=2d
In each case the centre of the resulting sphere lies on the line between the centres of the
original spheres, and the sphere has minimum radius consistent with being a superset of the
union/intersection of the original spheres. The results for -
are intuitive enough, as the new
sphere must contain the two original spheres. Figure 5 shows various configurations with
differing values of d. For -
u the case where (r l
s is slightly confusing:
the new sphere has to contain the common maximal-radius disc (or higher-dimensional
analogue) that lies perpendicular to the line joining the centres of the originals spheres.
This is illustrated in a two-dimensional slice in figure 5(b), where the maximal-radius line
and the resultant 'intersection' sphere are shown dotted.
These sphere operators are commutative, but lack many other, interesting algebraic
properties: they are neither associative, nor monotonic 10 . Thus theorem 1 does not hold,
Consider three spheres A, B and C with A ' B, A ' C, and B and C overlapping but without either
subsuming the other. Then in F (X; Y
uY we have A -

Figure

5: Various configurations for the sphere operators: (a)
s (from now on, the smaller sphere forms the 'intersection');
F

Figure

A collection of circles that exhibit two, distinct fixed-points.
and in fact the fixed-points of this system need not be unique. Consider figure 6, which
shows a number of circles with colinear centres. If we consider the circles A, B and C
as initial bounds on nodes A, B and C in the tree A " (B " C) and apply the normal
up-then-down procedure (with the internal nodes initially bounded by \Omega\Gamma we obtain the
circle
uC as the final bound on each node after two passes. (The other
circles shown are
uC and
uC), which are intermediate bounds on nodes.)
However, if we take a different order whereby we take the initial bound on A and pass it
up to the root node and then down to B and C, we find that C becomes null-bounded (as
and that this bound propagates to all the nodes. Thus this example exhibits
two, distinct fixed-points, depending on the order in which the (deterministic) rules are
applied.
5.2.2 Convex Hulls
Another possibility for a bounds system is to use convex hulls. That is, each bound is a
convex set, with operators -
t, so that -
u is equivalent to ", and -
t is equivalent to
[ followed by taking the convex hull. These operations are easily shown to be monotonic
and associative, and so the operators share some of the properties of a Box-BF system.
However the operators do not take constant time to compute. If we assume that we are
dealing with convex polytopes (rather than general convex sets) then two convex polygons
can be 'merged' in time linear in the number of edges in the polygons, and two convex
polyhedra can be merged in O(n log n) time [10]. This leads to a total cost bound of O(Nd)
for an Up pass or Down pass in the two-dimensional case, where N is the total number of
vertices in all of the leaf-node hulls and d is the depth of the tree, and thus a cost bound
of O(N log N) when the tree is balanced.
We have not implemented this bound system within our modelling system, but figure
7 illustrates a two-dimensional example. Imagine a two-dimensional robot arm, modelled
as the union of seven polygons, and an environment modelled as the union of 4 rectangles
(figure 7(a)). Let
R\Omega E be set up to test for interferences between the robot and its
environment, where R and E are the appropriate 13 and 7 node subtrees that model the
robot and the environment, and consider the bounds generated in this system on R and

Figure

7(b) shows these bounds after the initial Up pass, together with the outlines
of the primitives (shown dotted). The intersection of these two hulls is generated at the
root node, and passed back down the tree at the subsequent Down pass. Figure 7(c) gives
the same bounds after the next Up pass, and shows that much of the robot is now being
null-bounded. Figure 7(d) shows the next Up pass, and as these bounds do not overlap
all of the tree nodes becomes null-bounded after the next Down pass. (This proof of
non-interference would not have occurred if we had used box-bounds instead.)
5.2.3 Prism Bounds
Consider a case where we wish to evaluate the intersection of two entities, each of which
is described as a CSG tree. We construct a new tree,
one entity and T 2 the other, and apply the rules to generate a good TC-BF. We could use
box-bounds for T , all aligned with some standard coordinate axes; this is the approach
used in [4]. However we may have some reason for preferring to align the bounds in T 1 with
one set of axes, and those in T 2 with another set. Formally, this can be accommodated
by using arbitrary polytopes for the bounds, whilst choosing to store bounds at each node
which are boxes with the preferred alignment.
As a simple example, consider the intersection of the two two-dimensional shapes shown
in figure 8. This intersection is described by a simple, two-leaf tree. Using the standard
aligned bounds, the diagonal bar will be bound by a large square, and so we obtain only
the horizontal bar as a bound on each node. However, if we use a bound aligned with the
diagonal bar for that bar, we can compute the intersection of the two bounds exactly at the
root node, whilst passing down bounds to the leaves that have the appropriate alignment;
this gives the bounds shown with dotted lines for the two bars. The usefulness of just
having, in effect, a special rule at the root node is that we preserve the unit time cost for
the bound operations. In the general case we would have more structure in the trees T 1
and T 2 , but we can still use the standard box operations within each subtree as all the
bounds there have the same alignment, and use the special u operation at the root node
to combine information from the two subtrees.
The example of figure 8 may seem contrived, as the intersection of the bars is small.
However the method works for bounds of arbitrary dimension, and as the dimensionality
of the bounds increases, the number of simultaneous constraints increases, which conspires
to make the intersected region small. In particular, we have used these aligned bounds in
a collision detection application where the intersection test in performed in four dimensions
(the fourth dimension being time). Then we arrange the bounds on each object to
be aligned boxes, moving with their corresponding object, which gives rise to different
alignments of the four-dimensional prisms at the root node [5].
(d)
(c)
(b)
(a)

Figure

7: An example of the convex hull BF system.
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@

Figure

8: Example of TC-BFs with Different Alignments
5.3 Mixing Bounds
of bound is universally good for all situations; it might be useful if we
could use a number of different types of bounds and somehow 'combine' the results. To
do this meaningfully it would be nice if we could take two arbitrary TC-BFs for the same
tree, say fi 1 and fi 2 , and merge them by considering the sets fi(T
each node T . This is not strictly possible with TC-bounds, as the resulting fi need not
be totally consistent! (As an example, consider
However it is possible
to merge TC-BFs generated in the normal way (namely by taking a standard BF and
applying the rewrite rules). This follows as such TC-BFs are instances of S-bounds (see
x7), for which the merging property does hold. With this proviso in mind we can consider
different schemes for mixing bounds. One manner of mixing bounds would be to compute
a number of bounds in parallel (say a sphere and an aligned box), and leave it to the
application to use the different bounds as required. For example, in rendering applications
the application might generate potential edge segments to be membership classified against
the CSG tree [13, 12]; the segments can be pruned against all the bounds in the appropriate
(generating) node first.
An alternative possibility is to establish a hierarchy of bounds, using, say, aligned boxes
and convex hulls. Under this scheme the standard box bounds may be computed first, and
then convex hulls generated for the non-null bounded nodes. This has two advantages: we
do not waste time computing convex hull bounds for nodes that are easily proved to be
null-bounded, and the box bounds generated can be used as initial convex-hull bounds,
with the aligned boxes at the leaf nodes being replaced by their intersection with convex
hulls around the primitives. The key idea here is to refine the 'current' bounds only when
required. (Such an idea is used in the University of Leeds' isos system [1], in which they
use inner bounds as well as outer, standard bounds.)
5.4 Theoretical Aspects
For completeness we collect together here some results of interest in developing the theory
of TC-bounds, pertaining to what happens if we make the bounds exact, and the idea of
ordering different TC-BFs.
5.4.1 Exact Combination Operations
We can imagine a TC-BF system in which we start with some standard bound set which
has
\Omega bounds at the internal nodes, and then combine the bounds using the exact form
of the Upward and Downward rules (where t j [ and u j "). This system-the exact-
combination system-has interesting properties.
Theorem 2 The exact-combination system forms a fixed-point after exactly
one Upward pass, followed by a Downward pass.
Proof: Let fi 0 be the TC-BF generated after the Upward pass, and fi 00 the TC-BF
generated after the Downward pass. Then for a general internal node
have If the node is
a\Omega , after the Downward pass we will obtain
required by Lemma 1. If the node is \Phi, we have
set Z, and so
Similarly fi 00 (T r
Effectively the exact combination system is the best TC-BF we can generate, in the
sense that it gives the best fit. Further the BF generated in this way satisfies an exact
relationship with the active zones [12] for the tree, namely
where I(T ) is the I-zone for the node T and Z(T ) is its active zone [7].
5.4.2 Relative Consistency
Once we have an initial TC-BF fi for a particular tree the original primitive interpretation
' is almost incidental: any further TC-BFs that we generate will also be TC-BFs for any
other primitive interpretation ' 0 for which fi was a TC-BF. This observation suggests that
we can abstract away the interpretation, and just consider the rewrite rules as operating
on an arbitrary bounding function. This is the idea behind relative consistency.
\Pi Relative Consistency Given a tree T a bounding function fi 0 is relatively
consistent with respect to fi (written fi 0 - fi or fi - fi 0 ) if for every primitive
interpretation ' for which fi is totally consistent, fi 0 is totally consistent.
Then it is easily shown that the Upward and Downward principles produce new bounding
functions which are relatively consistent (i.e., if fi 0 is generated from fi by use of the Upward
or Downward principles then fi 0 - fi), and we have the properties:
ffl - is reflexive and transitive.
ffl - is preserved by the Upward and Downward principles.
6 Double Bounds
Totally-consistent bounds were derived from the idea of reasoning about supersets, or
upper bounds. Although we have been considering only examples using the set algebra,
all of our results apply to an arbitrary Boolean algebra (as they are demonstrated only by
reference to the axioms and theorems of Boolean algebra). The concept of superset is a
specialisation of the concept of supremum in the appropriate Boolean lattice (the powerset
lattice), and it is interesting to consider whether a dual system can be developed, based
around the lattice infimum. Indeed it can, and for the set algebra it is based around
the idea of finding subsets of set expressions. Such subsets could be used, say, to prove
interference by demonstrating a lower bound that is known to lie within the intersection
set. Without further ado, we introduce the appropriate definitions.
\Pi Definitions An double bounding function (DBF) is a function from tree-
nodes to pairs of subsets of space; one element of the pair is called the outer
bound, and the other element is called the inner bound. We denote DBFs
by B, B   , etc., and the outer and inner bounds of B(T ) by -
respectively.
A double-bounded interpretation, j is given by the rules:
Otherwise, T is a leaf node, and jT
In other words, we force the interpretation for the node to be a superset of the
inner bound, and then intersect with the outer bound.
We say that B is consistent (on T over ') if jT and we say that B is
totally consistent if jT
B.
We may consider as DBF a defining a 'skin' around the sets given by the subtrees in a CSG
tree, namely the difference between the outer bound and the inner bound. Indeed, if we take
the limiting case where the approximations are exact, by starting with the exact sets and
using the exact form of the combination operators, we end up with an exact relationship
between this skin and the active zone of a node 11 . The DBF whose outer bounds are
all
\Omega and whose inner bounds are all ; is a totally consistent double-bounding function
Specifically, -
are the I-zone and U-zone
of a node, respectively [12, 7].
(TC-DBF). Further, any DBF whose outer/inner bounds
are\Omega\Gamma ; on branch nodes, and
' '(L) on leaf nodes, is also a TC-DBF. Thus we can usually
generate an initial TC-DBF, and use Upward and Downward principles to generate new
TC-DBFs. Let the notation f [X ' S] denote the function that returns the same values as
f everywhere except on X, when it returns S. Then the appropriate principles are:
\Pi The Upward Principle (for DBFs) Given a DBF B over a tree T , and
an internal node T of the form replace the bound at T by a B 0
satisfying
\Pi The Downward Principle (for DBFs) Given a DBF B over a tree T ,
and a node T 6= T with parent T p , replace the bound at T by a B 0 satisfying
We outline the proof of the validity of these principles in the appendix. Note that if we start
with a TC-DBF whose inner bounds are all ;, we obtain the system of TC-BFs previously
described. Also, if we start with a TC-DBF whose outer bounds are
all\Omega\Gamma then we have
the immediate dual of the TC-BF system with inner bounds only. It is then tempting
to try to set up a specific inner bound system based on internal boxes. Figure 9 shows
such a construction for the two-dimensional outer bound example of figure 1. Figure 9(a)
shows a suitable set of initial internal bounds; figure 9(b) shows the bound set achieved
after a single pass of the Upward rule. The root node has been internally bounded by
;, and the system has converged. One reason for this is that there is no natural choice
for performing the bound operations, as there was with the outer bounds. In figure 9 we
picked a rectangle, interior to the set union, with the largest area. Another problem is that
the object given by the root node is small, and so any inner bound must be smaller. Figure
9(c) shows the bound set resulting from the same tree, but with the rightmost primitive
moved to the left slightly (by 10% of the width of the frame) so that the overlap area is
larger. In this case an overlap can be proven by observing the internal bounds.
7 S-bounds
In all of our discussion so far we have admitted CSG trees
containing\Omega and \Phi operations
only. If we admit set difference or complement operations the theory is not so tidy, as we
will illustrate by means of examples. (However the practical results are even more useful,
and are indeed what we have implemented within our solid modelling system.) Note that
the definitions of interpretation, bounded interpretation, etc., have natural extensions to
the case where these new operators are allowed. So consider a simple tree,
(a)
(b)
(c)

Figure

9: Two-Dimensional Example of TC-DBFs
(where \Psi is the symbol for the set difference operation \Gamma). Then, noting the identity
we see that the 'obvious' Upward rule for T is to refine the bound fi(T )
by fi(T is an outer bound on the extent of jBj. However, we have no
information in the existing bounds for such a bound. (This point will be returned to later,
when we consider double bounds again.) Thus we obtain:
\Pi Upward Principle for \Psi Nodes If replace fi(T ) by a superset
of fi(T
We already have a single downward principle (for all set operations), and it would be
nice to extend this to the difference case. However, as the following counterexample shows,
this rule does not then preserve total-consistency.
Counter-example Consider the tree B, and the primitive interpretation
so a TC-BF for this example
is given by However, the BF
is not TC, as the BF fi is not consistent.
If we examine this counter-example we see that fi, although totally-consistent, is not the
sort of BF that would be generated by starting with a standard BF, and applying the
Upward and Downward rules. This suggests that we might retrieve our rules by restricting
the 'interesting' bounds in some way. This may be done with S-bounds.
\Pi S-bound Functions Given a tree T with primitive interpretation ' the
bounding function fi is an S-bound function (on T over ') if it is totally consistent
with respect to all smaller primitive interpretations: i.e., if jT j 0
for all fi 0 w fi and all ' 0 v '. The sets returned by an S-bound function are
called S-bounds.
In other words, we have introduced an artificial constraint-that the BF must be
with respect to all smaller interpretations. S-bounds are explored in detail in [4], and so
we will only give an overview of their properties here.
Properties of S-bounds
ffl A standard BF is an S-bound function.
ffl S-bounds are preserved by the Upward principle and the Downward principle (in-
cluding the cases of \Psi and : operations).
ffl If fi 1 and fi 2 are two S-bound functions over the same tree (and primitive interpreta-
tion), then so is
Given the need for an additional rule if differences are allowed we might be tempted to
always convert a CSG tree into positive form (one with
only\Omega and \Phi internal nodes) and
to just use the rules for TC-BFs. However it is not true that the bounds generated will
necessarily be the same in both cases. As an example, consider the tree A \Psi (B \Psi C) with
initial bounds A, B and C about A, B and C respectively. Using a system in which the u
operation is equivalent to " (as in the Box-BF system) convergence will occur after one Up-
then-Down pass, with the bounds about the leaves being A,
if we convert to the 'equivalent' tree
A\Omega (:B \Phi C) before applying the rewrite rules we
will obtain a bound of A " C about C, rather than A Effectively the conversion
to positive form has meant that B can only 'export' a bound of \Omega\Gamma whereas in the original
form the bound on B could be exported locally to C.
7.1 Double Bounds
One problem with extending TC-BFs to trees containing difference operations was that it
is impossible to bound the complement of the interpretation of a subtree. However DBFs
contain both an outer and an inner bound, and so it seems plausible that meaningful,
symmetric rules could be developed. In particular, the 'obvious' Upward principle for a \Psi
is
Given a DBF B over a tree T , and an internal node T of the form
replace the bound at T by a B 0 satisfying
Unfortunately, this rule does not preserve consistency, as shown by a counter-example.
Consider and the DBF -
applying the 'rule' above gives B 0 with -
which is not consistent. This counter-example, together with others, has
convinced us that it is not possible to combine inner and outer bounds in a consistent
manner. Thus, the proper principle at a difference node is:
\Pi Upward Principle for Double-Bounds at \Psi Given a DBF B over a tree
T , and an internal node T of the form replace the bound at T by
Effectively, we cannot pass any useful information up from the right-hand child of a \Psi
node.
Conclusions
We have presented what might seem like a bewildering array of concepts and definitions
concerning various types of bounds. In fact we may organise the concepts along different,
orthogonal axes. One axis we could label 'Generality': as far as our work is concerned
standard bounds occupy one end of this axis and consistent bounds occupy the other, with
S-bounds and TC-bounds in between. We have concentrated on TC-bounds in this paper
as most of the results apply to them, but in practise we start with a standard BF and so
generate S-bounds (which are themselves, of course, totally consistent). Another axis could
be labelled 'Accuracy of Bound': for this, boxes and spheres might be at one end, convex
hulls a little further along, and the exact-shapes at the far end. Conversely, we might label
the same axis as 'Speed of Computation', with a note that we are talking about speed for
explicitly computing these bounds (active zones being exact, but computed implicitly).
The bound systems are a rich source of algebraic problems. Most of our work has been
done on the Box-BF system, as this is computationally very useful and has nice algebraic
properties. Unfortunately the other practical systems are much harder to analyse, despite
their apparent simplicity. Monotonicity has been shown to be a desirable property, as it
guarantees a unique fixed point, but we would not suggest that the sphere system is not
used simply on the grounds that it is not monotonic!
We have not said too much about the applications of these techniques. In our CSG
modeller, robmod [6], we use the Box-BF system for all of our geometric computations
as a matter of course, as convergence is so rapid that we can ignore the time that it takes.
For drawing, volume property calculation, and the like, the advantages of performing these
bound computations tend to be small (but measurable); however for interference detection
and collision detection the advantages are huge (speedups of an order of magnitude or more
are common). This is because there is then an implicit intersection node at the root of the
CSG tree, and so the reductions in the size of the bounds tend to be large [4]. Ray-casting
could also benefit from the use of TC-bounds, as we can perform a bound analysis between
the ray (bounded by a thin box) and the objects.
Another way of thinking about the bound systems is as a set of constraints on sub-
expressions. For example, a standard bound places definite constraints on the values of
x, y and z that are coordinates of points in the set given by the sub-expression. Turning
this observation around we can regard the rewrite rules for TC-bounds as the rules of a
constraint manipulation system, and use them to solve constraint problems which might
not normally be given a geometric significance. Indeed, as the definitions and rewrite
rules hold for any Boolean algebra, the rewrite-rules could (in principle) be used to set up
TC-bounds for elements in any such algebra.
As we stated, this topic has proved to be a rich ground for theoretical results, and
there is much work still to be done. In particular, we would like to strengthen the convergence
results for the BF systems that show the most practical promise, namely spheres
and convex hulls. In the meantime though the general applicability of the Upward and
Downward theorems means that we can safely use these bound systems to practical effect.
Another area of interest is in alternative orderings for the application of the rules, and in
implementations that make use of multiple BF systems. All in all, there have been a lot
of surprises generated by the simple observations with which we started!

Acknowledgement

Most of the work of the first author described in this paper was supported by an SERC
studentship at the University of Edinburgh Department of Artificial Intelligence. The
second author was partially supported by NSF grants #CCR-8703458 and #DCR-8401898.
Both authors would like to thank Mike Brady for encouragement and for promoting the
collaboration that lead to this work.



--R

Boundary evaluation using inner and outer sets: the ISOS method.
GMSolid: interactive modeling for design and analysis of solids.

Efficient intersection tests for objects defined constructively.
Collision detection by four-dimensional intersection testing
A geometry engine for robotics.
Relationship between S-bounds and active zones in constructive solid geometry
Generalizing active zones for set-theoretic solid models
An experimental study of null object detection algorithms in E 2
Computational Geometry: An Introduction.
Solid modeling: A historical summary and contemporary assessment.
Active zones in CSG for accelerating boundary evaluation
Set membership classification: A unified approach to geometric intersection problems.
Expoiting Spatial and Structural Locality in Geometric Modelling.

--TR
Computational geometry: an introduction
Active zones in CSG for accelerating boundary evaluation, redundancy elimination, interference detection, and shading algorithms
Generalizing active zones for set-theoretic solid models
Efficient intersection tests for objects defined constructively
Relationship between s-bounds and active zones in constructive solid geometry
Boundary Evaluation Using Inner and Outer Sets

--CTR
Stephen Cameron, Efficient Bounds in Constructive Solid Geometry, IEEE Computer Graphics and Applications, v.11 n.3, p.68-74, May 1991
John Hable , Jarek Rossignac, Blister: GPU-based rendering of Boolean combinations of free-form triangulated shapes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Marco Mazzetti , Luigi Ciminiera, Computing CSG tree boundaries as algebraic expressions, Proceedings on the second ACM symposium on Solid modeling and applications, p.155-162, May 19-21, 1993, Montreal, Quebec, Canada
A. Aguilera , D. Ayala, Orthogonal polyhedra as geometric bounds in constructive solid geometry, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.56-67, May 14-16, 1997, Atlanta, Georgia, United States
Stephen Cameron, Approximation hierarchies and S-bounds, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.129-137, June 05-07, 1991, Austin, Texas, United States
representation simplification;robotics;collision detection;constructive solid geometry;solid modeling;boolean algebra;interference detection