Analyzing bounding boxes for object intersection.
Heuristics that exploit bouning boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded that bounding boxes perform poorly in the worst case. This paper reconciles this discrepancy by analyzing intersections among n geometric objects in terms of two parameters: &agr; an upper bound on the aspect ratio or elongatedness of each object; and &sgr; an upper bound on the scale factor or size disparity between the largest and smallest  objects. Letting Ko and Kb be the number of intersecting object       pairs and bounding box pairs, respectively, we analyze a ratio measure of the   bounding boxes'  efficiency,   r=Kb/n+Ko  . The analysis proves that   r=Oas log2s   and   r=Was  . One important consequence is that if &agr; and &sgr; are small constants (as is often the case in practice), then Kb= O(Ko)+ O(n, so an algorithm that uses bounding boxes has time complexity proportional to the number of actual object intersections. This theoretical result validates the efficiency that bounding boxes have demonstrated in practice. Another consequence of our analysis is a proof of the output-sensitivity of an algorithm for reporting all intersecting pairs in a set of n convex polyhedra with constant &agr; and &sgr;. The algorithm takes time O(nlogd1n+ Kolog d1n) for dimension 3. This running time improves on the performance of previous algorithms, which make no assumptions about &agr; and &sgr;.
Introduction
Many computer graphics algorithms improve their performance by using bounding
boxes. The bounding box of a geometric object is a simple volume that encloses
the object, forming a conservative approximation to the object. The most common
form is an axis-aligned bounding box, whose extent in each dimension of the space is
bounded by the minimum and maximum coordinates of the object in that dimension.
(See

Figure

1 (a) for an example.)
Bounding boxes are useful in algorithms that should process only objects that
intersect. Two objects intersect only if their bounding boxes intersect, and intersection
testing is almost always more efficient for objects' bounding boxes than for
the objects themselves. Thus, bounding boxes allow an algorithm to quickly perform
a "trivial reject" test that prevents more costly processing in unnecessary cases.
This heuristic appears in algorithms for rendering, from traditional algorithms for
visible-surface determination [10], to algorithms that optimize clipping through view-frustum
culling [13], and recent image-based techniques that reconstruct new images
from the reprojected pixels of reference images [23]. Bounding boxes are also common
in algorithms for modeling, from techniques that define complex shapes as Boolean
combinations of simpler shapes [18] to techniques that verify the clearance of parts
in an assembly [11]. Animation algorithms also exploit bounding boxes, especially
collision detection algorithms for path planning [21] and the simulation of physically
based motion [2, 20, 25].
While empirical evidence demonstrates that the bounding box heuristic improves
performance in practice, the goal of proving that bounding boxes maintain high performance
in the worst case has remained elusive. Such a proof is important to reassure
practitioners that their application will not be the one in which bounding boxes happen
to perform poorly. To understand the difficulties in such a proof, consider the
use of bounding boxes when detecting pairs of colliding objects from a set, S, of n
polyhedra. Let K o be the number of colliding pairs of objects, and let K b be the
number of colliding pairs of bounding boxes. Figure 1 (b) shows an example in which
meaning that the bounding box heuristic adds only
unnecessary overhead, and a collision detection algorithm that uses the heuristic is
slower than one that naively tests every pair of objects for collision.
Intuitively, the poor performance in this example is due to the pathological shapes
of the objects in S. In this paper, we identify two natural measures of the degree to
which objects' shapes are pathological, and we analyze the bounding box heuristic in
terms of these measures. We show that if the aspect ratio, ff, and scale factor, oe, are
bounded by small constants (as is generally the case in practice) then the bounding
box heuristic avoids poor performance in the worst case.
The aspect ratio measures the elongatedness of an object. In classical geometry,
the aspect ratio of a rectangle is defined as the ratio of its length to its width. This
definition can be extended in a variety of ways to general objects and dimensions
(a) (b)

Figure

1: (a) A polygonal object and its axis-aligned bounding box. (b)
An example with K
greater than two. It is often defined as the ratio between the volumes of the smallest
ball enclosing the object and the largest ball contained in the object. We will find it
convenient to use the volumes of L1-norm balls in the d-space. 1 Given a solid object
P in d-space, let b(P ) denote the smallest L1 ball containing P , and let c(P ) denote
the largest L1 ball contained in P . The aspect ratio of P is defined as
where vol(P ) denotes the d-dimensional volume of P . We will call b(P ) the enclosing
box , and c(P ) the core of P . Thus, the aspect ratio measures the volume of the
enclosing box relative to the core. For a set of objects the
aspect ratio is the smallest ff such that ff - ff(P i ), for
The scale factor for a set of objects measures the disparity between the largest
and smallest objects. For a set of objects in d-space, we say
that S has scale factor oe if, for all 1 -
The analysis in this paper focuses on the ratio
In two dimensions, for instance, the L1 ball of radius r and center o is the axis-aligned square
of side length 2r, with center o. The choice of the norm affects only the small dimension-dependent
constant factors, and our results apply also to L 2 balls or other commonly used norms with small
changes in the constant. Note also that the estimates derived with the L1 norm are the most
pessimistic since L1 box is the most conservative bounding volume.
where K o is the number of object pairs in S with nonempty intersection, and K b is the
number of object pairs whose enclosing boxes intersect. 2 The denominator represents
the best-case work for an algorithm using the bounding box heuristic, so the ratio can
be seen as the relative performance measure of the heuristic. Ideally, this ratio would
be a small constant. Unfortunately, the pathological case of Figure 1 (b) shows that
without any assumptions on ff and oe, we can have ae = \Omega\Gamma n). However, if we include
aspect ratio and scale factors in the analysis, we can prove the following theorem,
which is the main result of our paper.
Theorem 1.1 Let S be a set of n objects in d dimensions, with aspect bound ff and
scale factor oe, where d is a constant. Then,
oe log 2 oe). Asymptotically,
this bound is almost tight, as we can show a family S achieving
oe).
There are two main implications of this theorem. First, it provides a theoretical
justification for the efficiency that the bounding box heuristic shows in practice. In
most applications, ff and oe are small constants, so ae is also constant. The theorem
then indicates that K O(n). An algorithm that uses the bounding box
heuristic is thus nearly optimal in the asymptotic sense: it does not waste time
processing bounding box intersections because their number grows no faster than the
number of actual object intersections (plus an O(n) factor which matches the overhead
the algorithm must incur if it does anything to each object). Poor performance
requires uncommon situations in which ff
n), as in Figure 1 (b). The theorem
also shows that performance is affected more by the aspect ratio than the scale factor,
so it may be worthwile to decompose irregularly-shaped objects into more regular
pieces to reduce the aspect ratio.
The second implication of the theorem is an output-sensitive algorithm for reporting
all pairs of intersecting objects in a set of n convex polyhedra in two or three
dimensions. By using the bounding box heuristic, the algorithm can report the K
pairs of intersecting polyhedra in O(n log
m) time, for
is the maximum number of vertices in a polyhedron. (We assume
that each polyhedron has been preprocessed in linear time for efficient pairwise intersection
detection [6].) Without the aspect and scale bounds, we are not aware of
any output-sensitive algorithm for this problem in three dimensions. Even in two
dimensions, the best algorithm for finding all intersecting pairs in a set of n convex
polygons takes O(n 4=3 and oe are constants, as is common in
practice, then the algorithm runs in time O(n log
which is nearly optimal.
2 Notice that the L1 ball is a more conservative estimate than the axis-aligned bounding box and
so K b
is an upper bound on the number of bounding box intersections.
Related Work
The use of the bounding box heuristic in collision detection algorithms is representative
of its use in other algorithms. Thus, our analysis focuses on collision detection,
but we believe that our results extend to other applications.
Most collision detection algorithms that use bounding boxes can be considered
as having two phases, which we call the broad phase and narrow phase. The basic
structure of the algorithms is as follows:
ffl Broad phase: find all pairs of intersecting bounding boxes.
ffl Narrow phase: for each intersecting pair found by the broad phase, perform a
detailed intersection test on the corresponding objects.
The broad and narrow phases have distinct characteristics, and often have been
treated as independent problems for research.
Efficient algorithms for the broad phase must avoid looking at all O(n 2 ) pairs of
bounding boxes, and they do so by exploiting the specialized structure of bounding
boxes. Edelsbrunner [8] and Mehlhorn [24] describe provably efficient algorithms for
axis-aligned bounding boxes in d-space, algorithms that find the k intersecting pairs
in O(n log d\Gamma1 n+ time and O(n log d\Gamma2 n) space. A variety of heuristic methods are
used in practice [2, 19], and empirical evidence suggest that these algorithms perform
well; the "sweep-and-prune" algorithm implemented in the I-COLLIDE package of
Cohen et al. [2] currently appears to be the method of choice. It might seem desirable
to use a broad phase the replaces axis-aligned bounding boxes with objects' convex
hulls, which provide a tighter form of bound. Unfortunately, no provably efficient
algorithm is known for finding the intersections between n convex polyhedra in three
dimensions. In two dimensions, though, a recent algorithm of Gupta et al. [14] can
report the intersecting pairs of convex polygons in time O(n 4=3
The narrow phase solves the problem of determing the contact or interpenetration
between two objects. Thus, the performance of a narrow phase algorithm does not
depend on n, the number of objects in the set, but rather on the complexity of
each object. If the objects are convex polyhedra, then a method due to Dobkin and
Kirkpatrick [6] can decide whether two objects intersect in O(log d\Gamma1 m) time, where
m is the total number of edges in the two polyhedra, and d - 3 is the dimension.
This algorithm preprocesses the polyhedra in a separate phase that runs in linear
time. Using this preprocessing, one can also compute an explicit representation of
the intersection of two convex polyhedra in time O(m), as shown by Chazelle [1].
If only one of the objects in the pair is convex, then intersection detection can be
performed in time O(m log m) [5]. The problem is more difficult if both polyhedra are
nonconvex, and only recently has a subquadratic time algorithm been discovered for
deciding if two nonconvex polyhedra intersect [27]. This algorithm takes O(m 8=5+" )
time to determine the first collision between two polyhedra, one of which is stationary
and the other is translating. While the provable running times of these algorithms are
important results, they are primarily of theoretical interest because the algorithms
are too complicated to be practical. As an alternative, a variety of heuristic methods
have been developed that tend to work well in practice [12, 20]. These methods use
hierarchies of bounding volumes and tree-descent schemes to determine intersections.
Our analysis of the bounding box heuristic is related to the idea of "realistic input
models," which has become a topic of recent interest in computational geometry. In
a recent paper, de Berg et al. [4] have suggested classifying various models of realistic
input models into four main classes: fatness, density, clutter, and cover complexity.
Briefly, an object is fat if it does not have long and skinny parts; a scene has low
clutter if any cube not containing a vertex of an object intersects at most a constant
number of objects; a scene has low density if a ball of radius r intersects only a
constant number of objects whose minimum enclosing ball has radius at least r; the
cover complexity is a measure of the relative sparseness of an object's neighborhood.
One of the first nontrivial results in this direction is by Matou-sek et al. [22], who
showed that the union of n fat triangles has complexity O(n log log n), as opposed to
arbitrary triangles; a triangle is fat if its minimum angle exceeds ffi, for a
constant this result to show that the union of
convex objects has complexity O(n 1+" ) provided that each object is fat and each
pair of objects intersects only in a constant number of points. Additional results on
fat or uncluttered objects can be found in [3, 15, 29].
3 Analysis Overview
Our proof for the upper bound on ae consists of three steps. We first consider the case
of arbitrary ff but fixed oe (Section 4). Next, in Section 5, we allow both ff and oe to
be arbitrary but assume that there are only two kinds of objects: one with box sizes
ff and the other with box sizes ffoe (the two extreme ends of the scale factor). Finally,
in Section 6, we handle the general case, where objects can have any box size in the
range [ff; ffoe]. We first detail our proof for two dimensions, and then sketch how to
extend it to arbitrary dimensions in Section 7.
Arbitrary Aspect Ratio but Fixed Scale
We start by assuming that the set S has scale factor one, that is, the aspect
ratio bound ff can be arbitrary. (Any constant bound for oe will work for our proof;
we assume one for convenience. The most straightforward way to enforce this scale
bound is to make every object's enclosing box to be the same size.) We will show that
in this case ae(S) = O(ff). We describe our proof in two dimensions; the extension to
higher dimensions is quite straightforward, and is sketched in Section 7.
Without loss of generality, let us assume that each object P in S has vol(c(P
and vol(b(P Recall that a L1 box of volume ff in two dimensions is a square
of side length p
ff. We call this a size ff box. Consider a tiling of the plane by size
ff boxes that covers the portion of the plane occupied by the bounding boxes of the
objects, namely,
Figure 2. We will consider each box semi-open, so that
the boundary shared by two boxes belongs to the one on the left, or above. Thus,
each point of the plane belongs to at most one box.

Figure

2: Tiling of the plane by boxes of size ff. The unit size core for the
object in B 1 is also shown.
We assume an underlying unit lattice in the plane, and assign each object P to the
lexicographically smallest lattice point contained in P . (Such a point exists
because the core is closed and has volume at least one.) Let m(q) be the number of
objects assigned to a lattice point q, and let M i denote the total number of objects
assigned to the lattice points contained in a box B i . That is,
means that the lattice point q lies in the box B i . Since the boxes in the
tiling are disjoint, we have the equality
We will derive the bounds on K b
and K o in terms of M i .
Lemma 4.1 Given a set of objects S with aspect bound ff and scale bound oe = 1, let
denote a tiling by size ff boxes as defined above, and let M i denote
the total number of objects assigned to lattice points in B i , for
Proof. Consider an object P assigned to B i , and let P j be another object whose
box intersects b(P ). Suppose P j is assigned to the box B j . Since b(P
the L1 norm distance between the boxes B i and B j is at most 2
ff. This means that
is among the 24 boxes that lie within 2
ff wide corridor around B i .

Figure

3: A box, shown in dark at the center, and its 24 neighbors.
Suppose that the boxes are labeled in the row-major order-top
to bottom, left to right in each row. Assume that the number of columns in the box
tiling is k. Then, the preceding discussion shows that if the boxes of objects P i and
intersect and these objects are assigned to boxes B i and B j , then we must have
ck
where c; d 2 f\Gamma2; \Gamma1; 0; 1; 2g. (The box B j can be at most two rows and two columns
away from B i . For instance, the box preceding two rows and two columns from B i
is B i\Gamma2k\Gamma2 .) See Figure 3. The number of box pair intersections contributed by B i
and B j is clearly no more than M i M j . Thus, the total number of such intersections
is bounded by
where c; d 2 f\Gamma2; \Gamma1; 0; 1; 2g. Recalling that x 1 x 2 - 1(x 2
can bound the intersection count by
There are 5 possible values for c and d each, and so altogether 25 values for j for
each i. Since each index can appear once as the i and once as the j, we get that the
maximum number of intersections is at most
This completes the proof of the lemma. 2
Next, we establish a lower bound on the number of intersecting object pairs. We
will need the following elementary fact.
Lemma 4.2 Consider non-negative numbers a 1 ; a
a i
Proof. Let m denote the index for which the ratio a i =b i is maximized. Since
summing it over all i, we get
am
Dividing both sides by
completes the proof of the lemma. 2
Let us now focus on objects assigned to a box B i in our tiling. If L i is the number
of intersecting pairs among objects assigned to B i , then we have the following:
where the second to last inequality follows from the fact that
last
inequality follows from the preceding lemma. We will establish an upper bound on
the right hand side of this inequality by proving a lower bound on the denominator
term.
Fix a box B i in the following discussion, where 1 - i - p, and consider a lattice
point q in it. Since m(q) objects have q in common, at least
object pair
intersections are contributed by the objects assigned to q. (Observe that each object
is assigned to a unique lattice point, and so we count each intersection at most once.)
Thus, the total number of pairwise intersections L i among objects assigned to B i is
at least
We will show that the ratio 25M 2
never exceeds cff, where c is an absolute
constant. Considering M i fixed, this ratio is maximized when L i is minimized.
Lemma 4.3 Let x non-negative numbers that sum to z. The minimum
value of
is z(z \Gamma n)=2n, which is achieved when x
Proof. We observe the following equalities:
x i!
Thus,
is minimized when
iis minimized. Using Cauchy's Inequality
[16], the latter is minimized when x z=n. The lemma follows. 2
Since no square box of size ff can have more than 2dffe lattice points in it, we get
a lower bound on L i by setting
2dffe
, for all q. Thus,
Lemma 4.4
Proof. Using the bound for L
2dffe
100dffe:
This completes the proof. 2
Theorem 4.5 Let S be a set of n objects in the plane, with aspect bound ff and scale
5 Objects of two Fixed Sizes
In this section, we generalize the result of the previous section to the case where
objects come from the two extreme ends of the scale: their box size is either ff or ffoe.
To simplify our analysis, we will assume that
just use the next nearest powers of 4 as upper bounds for ff; oe.
In d dimensions, ff and oe are assumed to be integral powers of 2 d .)
Let us call an object large if its enclosing box has size ffoe, and small otherwise.
Clearly, there are only three kinds of intersections: large-large, small-small, and large-
small. Let K l
b and K sl
b , respectively, count these intersections for the enclosing
boxes. So, for example, K sl
b is number of pairs consisting of one large and one small
object whose boxes intersect. Similarly, define the terms K l
object
intersections. The ratio bound can now be restated as
K l
(1)
K l
K sl
where
We know from the result of the previous section that
K l
- cff, for some constant c. So, we only need to establish a bound on the
third ratio, K sl
K l
, which we do as follows.
Let us again tile the plane with boxes of volume ffoe. Call these boxes
. Underlying this tiling are two grids: a level oe grid, which divides the boxes into
cells of size oe, and a level 1 grid, which divides the boxes into cells of size 1. The
level oe grid has vertices at coordinates (i
oe), while the finer grid has vertices
at coordinates (i; j), for integers j. The level oe grid is used to reason about large
objects, while the level 1 grid is used for small objects. We will mimic the proof of
the previous section, and assign objects of each class to an appropriate box. In order
to do that, we need to define subboxes of size ff within each size ffoe original box.
s

Figure

4: The box on the left shows large grid, and the one on the right
shows small grid as well as the subboxes. In this figure,
Consider a large box B i . The level oe grid partitions B i into ff boxes of volume oe
each. Next, we also partition B i into oe subboxes, each of volume ff. Since
these subboxes are perfectly aligned with both the level
1 and level oe grids. (Along a side of B i , the oe grid has vertices at distance multiples
of
while the vertices of the subboxes lie at distance multiples of
We label the oe subboxes within B row major order. Figure 4
illustrates these definitions, by showing two boxes side by side.
Now, each member of the large object set (resp. small object set) contains at
least one grid point of the large (resp. small) grid. Just as in the previous section, we
assign each object to a unique grid point (say, the one with lexicographically smallest
coordinates). Let X i denote the number of large objects assigned to all the grid points
in B i . Let y ij , for oe, denote the number of small objects assigned to the
to be the total number of small objects assigned
to level one grid points in B i .
We estimate an upper bound on K sl
b and a lower bound on K sl
in terms of X i
and Y i . Fix a box B i . The enclosing box of a large object P i , assigned to B i , can
intersect the box of a small object P j , assigned to B j , only if B j is one of the 25
neighbors of B i (including itself) that form the two layers of boxes around B i . (See

Figure

i be the box with a maximum number of small objects among
the 25 neighbors of B i , and let Y m
i be the count of the small objects in B m
. That is,
is one of 25 neighbors of B i g, and B m
i is the box corresponding
to Y m
. Then, we have the following upper bound:
K sl
Next, we estimate lower bounds on the number of object pair intersections. Let
the number of object pair intersections among the large objects assigned to
denote the object pair intersections among the small objects assigned
to B i . Since there are only ff grid points for the large objects in B i , by Lemma 4.3,
we have
ff
Similarly, each of the subboxes points of the
level 1 grid. Thus, we also have
oe
y
ff
In deriving our bound, we will use the conservative estimate of
only count the intersections between two large or two small objects. We
also use the notation S m
i for the number of object-pair intersections among the small
objects assigned to B m
i . We have the following inequalities:
K sl
where the second inequality follows from the fact that
the third
follows from the fact that a particular
can contribute the Y m
i term to at most
its 25 neighbors; and the final inequality follows from Lemma 4.2. The remaining step
of the proof now is to show that the above inequality is O(ff
oe). First, by summing
up the terms in Eqs. (2) and (3), we observe the following:
where recall that
. Thus, we have
where once again Cauchy's inequality is invoked to show that
oe
It can be easily shown that this ratio is at most 2ff p
oe, as follows. If Y m
then we have
oe:
and we have
oe:
This shows that K sl
oe): Combining this with Ineq. (2), we get the
desired result, which is stated in the following theorem.
Theorem 5.1 Suppose S is a set of n objects in the plane, such that each object has
aspect ratio at most ff, and the enclosing box of each object has size either ff or ffoe.
oe).
6 The General Case
We now are in a position to prove our main theorem. Suppose S is a set of n
polyhedral objects, with aspect ratio bound ff and scale factor oe. Recall that for
simplicity we assume that both ff and oe are powers of four. We partition the set
S into O(log oe) classes, C log oe, such that a polyhedron P
belongs to class C (Equivalently, the enclosing boxes of
objects in class C i have volumes between ff2 i and ff2 i+1 .) Each class behaves like a
fixed size family (the case considered in Section 4), and so we have ae(C
log oe. Any pair of classes behaves like the case considered in Section 5,
implying that ae(C i [
log oe. We can now formalize this
argument to show that
oe log 2 oe).
b , for 0 - log oe, denote the number of object pairs
enclosing boxes intersect such that Similarly, define K ij
we have the following:
log 2 oe
oe log 2 oe)
where the second inequality follows from the fact that i; j are each bounded by log oe,
and the last inequality follows directly from Theorem 5.1. This proves our main
result, which we restate in the following theorem.
Theorem 6.1 Let S be a set of n objects in the plane, with aspect ratio bound ff and
scale factor bound oe. Then,
oe log 2 oe).
7 Extension to Higher Dimensions
The 2-dimensional result might lead one to suspect that the bound in d dimensions,
for d - 2, will be O(ff oe 1=d ). In fact, the asymptotic bound in d dimension turns
out to be the same as in two dimensions-only the constant factors are different. A
closer examination shows that the exponent on oe in Theorem 6.1 arises not from the
dimension, but rather from Cauchy's inequality.
Our proof of Theorem 6.1 extends easily to d dimensions, for d - 3. The structure
of the proof remains exactly the same. We tile the d-dimensional space with boxes
(L1 balls). The main difference arises in the number of neighboring boxes for a
. While in the plane, a box has at most 5 2 neighboring boxes in the two
surrounding layers, this number increases to 5 d in d dimensions. Since our arguments
have been volume based, they hold in d dimensions as well. Our main theorem in d
dimensions can be stated as follows.
Theorem 7.1 Let S be a set of n polyhedral objects in d-space, with aspect ratio
bound ff and scale factor bound oe. Then,
oe log 2 oe), where the constant
is about 5 d .
8 Lower Bound Constructions
We first describe a construction of a family S with
The construction works in any dimension d, but for ease of exposition, we describe it
in two dimensions. See Figure 5 for illustration.
a

Figure

5: The lower bound construction showing
Consider a square box B of size ff in the standard position, namely,
ff] \Theta
ff]. We can pack roughly ff unit boxes in B, in a regular grid pattern; the
number is b
ffc 2 to be exact. We convert each of these unit boxes into a polyhedral
object of aspect ratio ff, by attaching two "wire" extensions at the two endpoints
of its main diagonal. Specifically, consider one such unit box u, the endpoints of
whose main diagonal have coordinates (a 1 ; a 2 ) and (b of u is
connected to the point (
ff) with a Manhattan path, whose ith edge is parallel
to the positive i-coordinate axes and has length p
. Similarly, the a endpoint
of u is connected to the origin with a Manhattan path, whose ith edge is parallel to
the negative i-coordinate axes and has length a i . It is easy to see that each unit box,
together with the two wire extensions forms a polyhedral object with aspect ratio ff.
By a small perturbation, we can ensure that no two objects intersect. The bounding
boxes of each object pair intersect, however, and so we have at least
bounding
box intersections in B.
We can group our n objects into bn=ffc groups, each group corresponding to a
ff-size box as above. This gives us
ff
c \Theta
On the other hand, K
We next generalize this construction to establish a lower bound of \Omega\Gamma ff
oe), assuming
that ffoe - n. See Figure 6.
objects
objects
small
d
c
large

Figure

The lower bound construction, showing
oe).
We take a square box B 0 of volume 4ffoe. We divide the lower right quadrant of
subboxes of size oe. We take a copy of the construction of Figure 5, scale
it up by a factor of oe, and put it in place of the lower right quadrant of B 0 . We
extend the wires attached to each object to the corners c, d of B 0 . Thus, the smallest
enclosing box of each object is now exactly B 0 , and aspect ratio is 4ff. These are the
big objects. Next, we take the upper-left quadrant, divide it into oe subboxes of size ff
each. At each ff-size subbox, we place a copy of the construction in Figure 5. These
are the small objects.
Altogether we want
small
objects. Since there are a total of ff locations for big objects, we superimpose X=ff
copies of the big object at each location. Similarly, there are ffoe locations for the
small objects, so superimpose Y =ffoe copies of the small object at each location. (This
is where we need the condition ffoe - n, since we want so ensure that each location
receives at least one object.) Let us now estimate bounds for K b and K o . The
enclosing box of every big object intersects the enclosing box of every small object,
we have
oe
On the other hand, the only object pair intersections exist between objects assigned
to the same location. We therefore have
Y =ffoe!
ffoe
Thus,
oe
ff
oe
for some constant c ? 0. (The ratio ff(1+
n is bounded by a constant, since ffoe - n.)
Theorem 8.1 There exists a family S of n polyhedral objects with aspect ratio bound
ff and scale factor oe such that
oe), assuming ffoe - n.
9 Applications and Concluding Remarks
Theorems 6.1 and 7.1 have two interesting consequences. The first is a theoretical
validation of the bounding box heuristic mentioned in Section 1. In practice, the
object families tend to have bounded aspect ratio and scale factor. Thus, the number
of extraneous box intersections is at most a constant factor of the number of actual
object-pair intersections. This result needs no assumption about the convexity of the
objects.
If the aspect ratio and scale factor grow with n, our theorem indicates their impact
on the efficiency of the heuristic. The degradation of the heuristic is smooth, and not
abrupt. Furthermore, the result suggests that the dependence on aspect ratio and
scale factor is not symmetric-the complexity grows linearly with ff, but only as a
square root of oe. It is common in practice to decompose complex objects into simpler
parts. Our work suggests that for collision detection purposes, reducing aspect ratio
may have higher payoff that reducing scale factor. It would be interesting to verify
empirically how this strategy performs in practice.
The second consequence of our theorems is an output sensitive algorithm for reporting
intersections among polyhedra; the bound is the strongest for convex
polyhedra in dimensions 3. We are aware of only one non-trivial result for this
problem, which holds in two dimensions. Gupta et al. [14] give an O(n 4=3 +K
algorithm for reporting K o pairs of intersecting convex polygons in the plane. The
problem is wide open in three and higher dimensions.
Our theorem leads to a significantly better result in two and three dimensions for
small aspect and scale bounds, and nearly optimal result for convex polyhedra. Given
n polyhedra in two or three dimensions, we can report all pairs whose bounding boxes
intersect in time O(n log is the number of intersecting
bounding box pairs. If the polyhedra are convex, then the narrow phase intersection
test can be performed in O(log d\Gamma1 m) time [6], assuming that all polyhedra have
been preprocessed in linear time; m is the maximum number of vertices in a polyhe-
dron. If the convex polyhedra have aspect ratio at most ff and scale factor at most
oe, then by Theorem 7.1, the total running time of the algorithm is O(n log
ff
3. If ff and oe are constants, then the running time
is O(n log m), which is nearly optimal.
Finally, an obvious open problem suggested by our work is to close the gap between
the upper and lower bounds on ae(S). We believe the correct bound is \Theta(ff
oe). Our
analysis is quite loose and the actual constants of proportionality are likely to be much
smaller than our estimates. It would be interesting to establish better constants both
theoretically and empirically.

Acknowledgement

The authors wish to thank Peter Shirley for his valuable comments on earlier versions
of the proof.



--R

An optimal algorithm for intersecting three-dimensional convex polyhedra
I-COLLIDE: An interactive and exact collision detection system for large-scale environments
Linear size binary space partitions for fat objects.
Realistic input models for geometric algorithms.
Computing the intersection-depth of polyhedra
Determining the separation of preprocessed polyhedra-a unified approach
A complete and efficient algorithm for the intersection of a general and a convex polyhedron.
A new approach to rectangle intersections (Parts I and II).
On the complexity of the union of fat objects in the plane.

Solving the Collision Detection Problem.
OBBTree: A hierarchical structure for rapid interference detection.
Detecting Intersection of a Rectangular Solid and a Convex Polyhe- dron
Efficient algorithms for counting and reporting pairwise intersection between convex polygons.

Cambridge University Press
Collision detection for fly- throughs in virtual environments
Morgan Kaufmann
Collision detection for interactive graphics applications.

Robot Motion Planning.
Fat triangles determine linearly many holes.
An Image-Based Approach to Three-Dimensional Computer Graph- ics
Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry
Collision Detection and Response for Computer Animation.
Computational Geometry: An Introduction.
Efficient collision detection for moving polyhedra.
A Simple and Efficient Method for Accurate Collision Detection among Deformable Objects in Arbitrary Motion.
Efficient algorithms for exact motion planning amidst fat obstacles.
--TR
Data structures and algorithms 3: multi-dimensional searching and computational geometry
Geometric and solid modeling: an introduction
Determining the separation of preprocessed polyhedra: a unified approach
An optimal algorithm for intersecting three-dimensional convex polyhedra
Fat Triangles Determine Linearly Many Holes
Solving the Collision Detection Problem
Spheres, molecules, and hidden surface removal
Detecting intersection of a rectangular solid and a convex polyhedron
Computer graphics (2nd ed. in C)
Efficient collision detection for moving polyhedra
OBBTree
Collision detection for fly-throughs in virtual environments
On the complexity of the union of fat objects in the plane
Realistic input models for geometric algorithms
An image-based approach to three-dimensional computer graphics
Analysis of a bounding box heuristic for object intersection
Robot Motion Planning
Collision Detection for Interactive Graphics Applications
Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs
Linear Size Binary Space Partitions for Fat Objects

--CTR
Yunhong Zhou , Subhash Suri, Algorithms for minimum volume enclosing simplex in


R
Pankaj K. Agarwal , Mark de Berg , Sariel Har-Peled , Mark H. Overmars , Micha Sharir , Jan Vahrenhold, Reporting intersecting pairs of convex polytopes in two and three dimensions, Computational Geometry: Theory and Applications, v.23 n.2, p.195-207, September 2002
Orion Sky Lawlor , Laxmikant V. Kale, A voxel-based parallel collision detection algorithm, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
collison detection;bounding boxes;aspect ratio