Minimal hierarchical collision detection.
We present a novel bounding volume hierarchy that allows for extremely small data structure sizes while still performing collision detection as fast as other classical hierarchical algorithms in most cases. The hierarchical data structure is a variation of axis-aligned bounding box trees. In addition to being very memory efficient, it can be constructed efficiently and very fast.We also propose a criterion to be used during the construction of the BV hierarchies is more formally established than previous heuristics. The idea of the argument is general and can be applied to other bounding volume hierarchies as well. Furthermore, we describe a general optimization technique that can be applied to most hierarchical collision detection algorithms.Finally, we describe several box overlap tests that exploit the special features of our new BV hierarchy. These are compared experimentally among each other and with the DOP tree using a benchmark suite of real-world CAD data.
INTRODUCTION
Fast and exact collision detection of polygonal objects undergoing
rigid motions is at the core of many simulation algorithms
in computer graphics. In particular, virtual reality
applications such as virtual prototyping need exact collision
detection at interactive speed for very complex, arbitrary
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
VRST'02, November 11-13, 2002, Hong Kong.
"polygon soups". It is a fundamental problem of dynamic
simulation of rigid bodies, simulation of natural interaction
with objects, and haptic rendering. It is very important for
a VR system to be able to do all simulations at interactive
frame rates. Otherwise, the feeling of immersion or the
usability of the VR system will be impaired.
The requirements on a collision detection algorithm for
virtual prototyping are: it should be real-time in all sit-
uations, it should not make any assumption about the in-
put, such as convexity, topology, or manifoldedness (because
CAD data is usually not "well-behaved" at all), and it should
not make any assumptions or estimations about the position
of moving objects in the future. Finally, polygon numbers
are very high, usually in the range from 10,000 up to 100,000
polygons per object.
The performance of any collision detection based on hierarchical
bounding volumes depends on two factors: (1)
the tightness of the bounding volumes (BVs), which will influence
the number of bounding volume tests, and (2) the
simplicity of the bounding volumes, which determines the
e#ciency of an overlap test of a pair of BVs [11]. In our
algorithm, we sacrifice tightness for a fast overlap test.
Our hierarchical data structure is a tree of boxes, which
are axis-aligned in object space. Each leaf encloses exactly
one polygon of the object. Unlike classical AABB trees,
however, the two children of a box cannot be positioned
arbitrarily (hence we call this data structure restricted box-
tree, or just boxtree). This allows for very fast overlap tests
during simultaneous traversal of "tumbled" boxtrees. 1
Because of the restriction we place on the relation between
child and parent box, each node in the tree needs very little
memory, and thus we can build and store hierarchies for
very large models with very little memory. This is important
as the number of polygons that can be rendered at interactive
frame rates seems to increase currently even faster than
Moore's Law would predict.
We also propose a very e#cient algorithm for constructing
good boxtrees. This is important in virtual prototyping
because the manufacturing industries want all applications
to compute auxiliary and derived data at startup time,
so that they do not need to be stored in the product data
management system. With our algorithm, boxtrees can be
constructed at load-time of the geometry even for high complexities

extended version of this paper can be found at http:
//web.cs.uni-bonn.de/~zach/index.html#publications
In order to guide the top-down construction of bounding
volume hierarchies, a criterion is needed to determine a good
split of the set of polygons associated with each node. In this
paper, we present a more formal argument than previous
heuristics did to derive such a criterion that yields good hierarchies
with respect to collision detection. The idea of the
argument is generally applicable to all hierarchical collision
detection data structures.
The techniques presented in this paper can be applied to
other axis-aligned bounding volumes, such as DOPs, as well.
They would probably yield similar savings in memory and
computational costs, since the motivation for our techniques
is valid if the bounding volume hierarchy is constructed in
a certain "natural" way. We also propose a general optimization
technique, that can be applied to most hierarchical
collision detection algorithms.
Our new BV hierarchy can also be used to speed up ray
tracing or occlusion culling within AABBs.
The rest of the paper is organized as follows. Section 2
gives an overview of some of the previous work. Our new
data structure and algorithms are introduced in Section 3,
while Section 4 describes the e#cient computation of box-
trees. Results are presented in Section 5.
2. RELATED WORK
Bounding volume trees seem to be a very e#cient data
structure to tackle the problem of collision detection for rigid
bodies.
Hierarchical spatial decomposition and bounding volume
data structures have been known in computational geome-
try, geometrical data bases, and ray tracing for a long time.
Some of them are k-d trees and octrees [18], R-trees [4], and
OBB trees [2].
For collision detection, sphere trees have been explored
by [12] and [17]. [11] proposed an algorithm for fast overlap
tests of oriented (i.e., non-axis-parallel) bounding boxes
(OBBs). They also showed that an OBB tree converges
more rapidly to the shape of the object than an AABB tree,
but the downside is a much more expensive box-box intersection
test. In addition, the heuristic for construction of
OBB trees as presented in [11] just splits across the median
of the longest side of the OBB.
trees have been applied to collision detection by [14]
and [21]. AABB trees have been studied by [20, 19, 15]. All
of these data structures work quite e#ciently in practice,
but their memory usage is considerably higher than needed
by our hierarchy, even for sphere trees.
More recently, hierarchical convex hulls have been proposed
for collision detection and other proximity queries by
While showing excellent performance, the memory footprint
of this data structure is even larger than that of the
previously cited ones. This is even further increased by the
optimization techniques the authors propose for the collision
detection algorithm.
Non-hierarchical approaches try to subdivide object space,
for instance by a voxel grid [16] or Delaunay triangulation
[9]. In particular, non-hierarchical approaches seem to be
more promising for collision detection of deformable objects
[1, 13, 8].
Regarding the name of our data structure, we would like
to point out that [3] presented some theoretical results on
a class of bounding volume hierarchies, which they called
BOXTREE, too. However, their data structure is substantially
di#erent from ours, and they do not provide any run-time
results.
Bounding volume hierarchies are also used in other areas,
such as nearest-neighbor search and ray tracing. For point
k-d trees, [5] have shown that a longest-side cut produces
optimal trees in the context of nearest-neighbor searches.
However, it seems that this rule does not apply to collision
detection.
3. DATASTRUCTUREANDALGORITHMS
Given two hierarchical BV data structures for two objects,
the following general algorithm scheme can quickly discard
sets of pairs of polygons which cannot intersect:
if A and B do not overlap then
return
if A and B are leaves then
return intersection of primitives
enclosed by A and B
else
for all children A[i] and B[j] do
traverse(A[i],B[j])
end for
Almost all hierarchical collision detection algorithms implement
this traversal scheme in some way. It allows to
quickly "zoom in" on pairs of close polygons. The characteristics
of di#erent hierarchical collision detection algorithms
lie in the type of BV used, the overlap test for a pair of
nodes, and the algorithm for construction of the BV trees.
In the following, we will first introduce our type of BV,
then we will present several algorithms to check them for
overlap.
3.1 Restricted Boxtrees
In a BV hierarchy, each node has a BV associated that
completely contains the BVs of its children. Usually, the
parent BV is made as tight as possible. In binary AABB
trees, this means that a parent box touches each child box
on 3 sides on average. We have tried to quantify this observation
further: in the AABB tree of three representative
objects, we have measured the empty space between each of
its nodes and their parent nodes. 2 Our experiments show
that for about half of all nodes the volume of empty space
between its bounding box and its parent's bounding box is
only about 10%.
Consequently, it would be a waste of memory (and computations
during collision detection), if we stored a full box
at each node. Therefore, our hierarchy never stores a box
explicitly. Instead, each node stores only one plane that is
perpendicular to one of the three axes, which is the (almost)
least possible amount of data needed to represent a box that
is su#ciently di#erent from its parent box. We store this
plane using one float, representing the distance from one of
the sides of the parent box (see Figure 1). The reason for
this will become clear below. 3 In addition, the axis must
be stored (2 bits) and we need to distinguish between two
2 For all nodes, one side was excluded in this calculation,
which was the side where the construction performed the
split.
3 One could picture the resulting hierarchy as a cross between
k-d trees and AABB trees.
splitting planes
lower child c l
cu upper child

Figure

1: Child nodes are obtained from the parent node by
splitting o# one side of it. The drawing shows the case where
a parent has a lower and an upper child that have coplanar
splitting planes.
cases: whether the node's box lies on the lower side or on
the upper side of the plane (where "upper" and "lower" are
defined by the local coordinate axes of the object).
Because each box in such a hierarchy is restricted on most
sides, we call this a restricted boxtree. Obviously, this restriction
makes some nodes in the boxtree hierarchy slightly
less tight than in a regular AABB tree. But, as we will see,
this does not hurt collision detection performance. The observation
we made above for AABB trees is probably also
true for other hierarchies utilizing some kind of axis-aligned
BV (such as DOPs). Section 4 will describe in detail our
algorithm to construct a restricted boxtree.
3.2 Box Overlap Tests
In the following, we will describe several variations of an
algorithm to test the overlap of two restricted boxes, exploiting
the special properties of the restricted boxtree. All
algorithms will assume that we are given two boxes A and
B, and that (b 1 , b 2 , b 3 ) is the coordinate frame of box B
with respect to A's object space.
3.2.1 Axis alignment
Since axis-aligned boxes o#er probably the fastest overlap
test, the idea of our first overlap test is to enclose B by an
axis-aligned box (l, h) # R 3
then test this against
A (which is axis-aligned already). In the following, we will
show how this can be done with minimal computational effort
for restricted boxtrees.
We already know that the parent boxes of A and B must
overlap (according to the test proposed here). Notice that
we need to compute only 3 values of (l, h), one along each
axis. The other 3 can be reused from B's parent box. Notice
further that we need to perform only one operation to derive
box A from its parent box.
Assume that B is derived from its parent box by a splitting
plane perpendicular to axis b # {b 1 , b 2 , b 3
which
is distance c away from the corresponding upper side of the
parent box (i.e., B is a lower child). We have already computed
the parent's axis-aligned box, which we denote by
(l can be computed by (see Figure 2)
and
l
l 0
l 0
Similarly, l x , hx can be computed if B is an upper child, and
analogously the new value along the other 2 axes.
In addition to saving a lot of computations, we also save
half of the comparisons of the overlap tests of aligned boxes.
Notice that we need to compare only 3 pairs of coordinates
(instead of 6), because the status of the other 3 has not
changed. For example, the comparison along the x axis to
be done is
and A do not overlap if
hx < l A
l x > h A
where l A
x are the x-coordinates of box A. Note that the
decision bx 7 0 has been made already when computing hx
or l x .
this method needs 12 floating point operations (3
checking the overlap of a pair of
nodes of a restricted boxtree.
3.2.2 Lookup tables
Since the b i are fixed for the complete traversal of two
boxtrees, and the c's can be only from a range that is known
at the beginning of the traversal, it would seem that the
computations above could possibly be sped up by the use of
a lookup table.
At the beginning of the traversal, we compute 3x3 lookup
tables
with 1000 entries each, one table for each component
during traversal, a term of the form
x is replaced by
c now is an integer and s is the splitting axis.
See below for results and discussion.
3.2.3 Separating axis test
The separating axis test (SAT) is a di#erent way to look
at linear separability of two convex polytopes: two convex
bodies are disjoint if and only if we can find a separating
plane, which is equivalent to finding an axis such that the
two bodies projected onto that axis (yielding two line inter-
vals) are disjoint (hence "separating axis"). For boxes, [11]
have shown that it su#ces to consider at most 15 axes.
We can apply this test to the nodes in our restricted box-
tree. 4 As previously, we do not need to compute all line
intervals from scratch. Instead, we modify only those ends
of the 15 line intervals that are di#erent from the ones of
the parent.
Let s be one of the candidate separating axes and assume
that B is a lower box (see again Figure 2). As above, for a
lower box we compute only
l
(and analogously for an upper box). Of course, we can pre-compute
all 3x15 possible products b i
The advantage of this test is that it is precise, i.e., there
are no false positives. One disadvantage of this test is that
In fact, our test by axis alignment can be considered a variant
of the separating axis test, where only a special subset
of axes is being considered instead of the full set.
A
s
c A
c A

Figure

2: Only one value per axis s needs to be recomputed
for the overlap test.

Figure

3: A reduced version of the separating axis test seems to
be a good compromise between the number of false positives
and computational e#ort.
there are 9 axes that are not perpendicular to A nor to B
(these are the edge-edge cross products).
In total, this method needs 82 FLOPS in the worst case,
which is much higher than the method above, but still less
than 200 FLOPS worst case for OBBs. 5
3.2.4 SAT lite
As we have seen in the section above, the 9 candidate axes
obtained from all possible cross products of the edge orientations
do not lend themselves to some nice optimizations.
Therefore, a natural choice of a subset of the 15 axes would
be the set of 6 axes consisting of the three coordinate axes of
A and B resp. (see Figure 3). This has been proposed by [19]
(who has called it "SAT lite"). Here, we apply the idea to
restricted boxtrees and show that even more computational
e#ort can be saved.
This variant can also be viewed as the first variant being
executed two times (first using A's then B's coordinate
frame). The total operation count is 24.
3.3 Further Optimizations
In this section, we will describe several techniques to further
improve the speed of restricted boxtrees and hierarchical
collision detection in general.
The first optimization technique is a general one that can
be applied to all algorithms for hierarchical collision detection
if the overlap test of a pair of nodes involves some
node-specific computations that can be performed independently
for each node (as opposed to pair-specific computa-
tions). The idea is to shift the node-specific computations
up one level in the traversal. Assume that the costs of a
node pair overlap test consist of a node-specific part c1 and
an overlap-test-specific part c2 . Then, the costs for a pair
(A, B) are C(A,
because if (A,B) are found to overlap, all 4 pairs of children
need to be checked. However, we can compute the node-
specific computations already while still visiting (A,B) and
pass them down to the children pairs, which reduces the
costs to C(A,
If the node-specific computations have to be applied only
to one of the two hierarchies (or the node-specific costs of
the other hierarchy are neglectible), then the di#erence is
even larger, i.e., 9c1
5 The worst case actually happens for exactly half of all node
pairs being visited during a simultaneous traversal.
Depending on the actual proportions of c1 and c2 , this
can result in dramatic savings. In the case of restricted
boxtrees with our first overlap test (axis alignment), this
technique reduces the number of floating point operations
to 1.5 multiplications, 2 additions, and 5 comparisons!
While this technique might already be implemented in
some collision detection code, it has not been identified as a
general optimization technique for hierarchical collision detection

As usual, we keep only one pointer in the parent to the
first of its children. This does save considerable memory
for our restricted boxtrees, because its nodes have a small
memory footprint.
4. CONSTRUCTION OF BOXTREES
The performance of any hierarchical collision detection depends
not only on the traversal algorithm, but also crucially
on the quality of the hierarchy, i.e., the construction algorithm

Our algorithm pursues a top-down approach, because that
usually produces good hierarchies and allows for very efficient
construction. Other researchers have pursued the
bottom-up approach [3], or an insertion method [10, 4].
4.1 A General Criterion
Any top-down construction of BV hierarchies consists of
two steps: given a set of polygons, it first computes a BV (of
the chosen type) covering the set of polygons, then it splits
the set into a number of subsets (usually two).
Before describing our construction algorithm, we will derive
a general criterion that can guide the splitting process,
such that the hierarchy produced is good in the sense of fast
collision detection.
Let C(A,B) be the expected costs of a node pair (A, B)
under the condition that we have already determined during
collision detection that we need to traverse the hierarchies
further down. Assuming binary trees and unit costs for an
overlap test, this can be expressed by
are the children of A and B, resp., and P
is the probability that this pair must be visited (under the
condition that the pair (A, B) has been visited).
d
A
possible
locus of
anchor points
d

Figure

4: By estimating the volume of the Minkowski sum of
two BVs, we can derive an estimate for the cost of the split of
a set of polygons associated with a node.
An optimal construction algorithm would need to expand
(1) down to the leaves:
.
(2)
and then find the minimum. Since we are interested in finding
a local criterion, we approximate the cost function by
discarding the terms corresponding to lower levels in the
hierarchy, which gives
Now we will derive an estimate of the probability P (A1 , B1 ).
For sake of simplicity, we will assume in the following that
AABBs are used as BVs. However, similar arguments should
hold for all other kinds of convex BVs.
The event of box A intersecting box B is equivalent to
the condition that B's ``anchor point'' is contained in the
Minkowski sum A # B. This situation is depicted in Figure
4.Because B1 is a child of B, we know that the anchor
point of B1 must lie somewhere in the Minkowski sum
A#B#d, where
inside A and B1 inside B, we know that A1#B1 # A#B#d.
So, for arbitrary convex BVs the probability of overlap is
In the case of AABBs, it is safe to assume that the aspect
ratio of all BVs is bounded by #. Consequently, we can
bound the volume of the Minkowski sum by
So we can estimate the volume of the Minkowski sum of two
boxes by
yielding
Since Vol(A) +Vol(B) has already been committed by an
earlier step in the recursive construction, Equation 3 can be
minimized only by minimizing This is
our criterion for constructing restricted boxtrees.
4.2 The Algorithm
According to the criterion derived above, each recursion
step will try to split the set of polygons so that the cost
function (3) is minimized. This is done by trying to find
a good splitting for each of the three coordinate axes, and
then selecting the best one. Along each axis, we consider
three cases: both subsets form lower boxes with respect to
its parent, both are upper boxes, or one upper and one lower
box.
In each case, we first try to find a good "seed" polygon
for each of the two subsets, which is as close as possible to
the outer border that is perpendicular to the splitting axis.
Then, in a second pass, we consider each polygon in turn,
and assign it to that subset whose volume is increased least.
After good splitting candidates have been obtained for all
three axes, we just pick the one with least total volume of
the subsets.
The algorithm and criterion we propose here could also be
applied to construct hierarchies utilizing other kinds of BVs,
such as OBBs, DOPs, and even convex hulls. We suspect
that the volume of AABBs would work fairly well as an
estimate of the volume of the respective BVs.
We have also tried a variant of our algorithm, which considers
only one axis (but all three cases along that axis).
This was always the axis corresponding to the longest side
of the current box. This experiment was motivated by a
recent result for k-d trees [5]. For the result, see Section 5.
In our current implementation, the splitting planes of both
children are coplanar. We have not yet explored the full
potential of allowing perpendicular splitting planes.
Our algorithm has proven to be geometrically robust, since
there is no error propagation. Therefore, a simple epsilon
guard for all comparisons su#ces.
4.3 Complexity
Under certain assumptions, the complexity of constructing
a boxtree is in O(n), where n is the number of polygons.
This is supported by experiments (see Section 5).
Our algorithm takes a constant number of passes over all
polygons associated with a node in order to split a set of
polygons F . Each pass is linear in the number of polygons.
BV hierarchy Bytes FLOPS
Restr. Boxtree (3.2.1) 9 12
Restr. Boxtree (3.2.4) 9 24
Restr. Boxtree (3.2.3) 9 82
sphere trees
AABB tree 28 90
OBB tree 64 243
tree 100 168

Table

1: This table summarizes the amount of memory per
node needed by the various BV hierarchies, and the number
of floating point operations per node pair in the worst case
during collision detection. The number of bytes also includes
one pointer to the children. If the optimization technique from
Section 3.3 is applied, then all FLOPS counts can be further
reduced (about a factor 2 for boxtrees).
sphere
car
lock
headlight
pgons / 1000
time

Figure

5: This plot shows the build time of restricted boxtrees
for various objects.
Every split will produce two subsets such that
#F2 .
Let us assume that |F1 | # |F2 | #n, with 1
for depth d of a boxtree
Let T (n) be the time needed to build a boxtree for n
polygons. Then,
d
5. RESULTS
Memory requirements of di#erent hierarchical data structures
can be compared by calculating the memory footprint
of one node, since a binary tree with n leaves always has
summarizes the number of bytes per
node for di#erent BV hierarchies .

Table

also compares the number of floating point operations
needed for one node-node overlap test by the methods
described above and three other fast hierarchical collision
detection algorithms (OBB, DOP, and sphere tree).
In the following, all results have been obtained on a
Pentium-III with 1 GHz and 512 MB. All algorithms have
been implemented in C++ on top of the scene graph OpenSG.
The compiler was gcc 3.0.4.
For timing the performance of our algorithms, we have
used a set of CAD objects, each of which with varying complexities
(see Figure 6), plus some synthetic objects like
sphere and torus. Benchmarking is performed by the following
scenario: two identical objects are positioned at a
certain distance d = d start from each other. The distance
is computed between the centers of the bounding boxes of
the two objects; objects are scaled uniformly so they fit in a
cube of size 2 3 . Then, one of them performs a full tumbling
turn about the z- and the x-axis by a fixed, large number
of small steps (5000). With each step, a collision query is
done, and the average collision detection time for a complete
revolution at that distance is computed. Then, d is
decreased, and a new average collision detection time is com-
puted. When comparing di#erent algorithms, we summarize
these times by the average time taken over that range of dis-
full
lite
axis alignm
pgons / 1000
time
millisec60402001.61.20.80.4
Figure

7: A comparison of the di#erent overlap tests for pairs
of boxtree nodes shows that the "SAT lite" test seems to o#er
the best performance.
tances which usually occur in practical applications, such as
physically-based simulation.

Figure

7 compares the performance of the various box
overlap tests presented in Section 3.2 for one of the CAD
objects. Similar results were obtained for all other objects
in our suite. Although the full separating axis test can determine
the overlap of boxes without false positives, it seems
that the computational e#ort is not worth it, at least for
axis-aligned boxes ([19] has arrived at a similar conclusion
for general AABB trees). From our experiments it seems
that the "SAT lite" o#ers the best performance among the
three variants.
A runtime comparison between our boxtree algorithm and
DOP trees for various objects can be found in Figure 8.
It seems that boxtrees o#er indeed very good performance
(while needing much less memory). This result puts restricted
boxtrees in the same league as DOP trees [21] and
OBB trees [11].
For sake of brevity, we have omitted our experiments assessing
the performance of the lookup table approach. It has
turned out that lookup tables o#er a speedup of at most 8%,
and they were even slower than the non-lookup table version
for the lower polygon complexities because of the setup time
for the tables. The reason might be that floating point and

Figure

Some of the objects of our test suite. They are (left to right): body of a car, a car headlight, the lock of a car door (and
a torus). (Data courtesy of VW and BMW)
integer arithmetic operations take almost the same number
of cycles on current CPUs.
As shown in Section 4, boxtrees can be built in O(n). Figure
5 reveals that the constant is very small, too, so that the
boxtrees can be constructed at startup time of the application

6. CONCLUSION
We have proposed a new hierarchical BV data structure
(the restricted boxtree) that needs arguably the least possible
amount of memory among all other BV trees while
performing about as fast as DOP trees. It uses axis-aligned
boxes at the nodes of the tree, but it does not store them
explicitly. Instead, it just stores some "update" information
with each node, so that it uses, for instance, about a factor
7 less memory than OBB trees.
In order to construct such restricted boxtrees, we have
developed a new algorithm that runs in O(n) (n is the number
of polygons) and can process about 20,000 polygons per
second on a 1 GHz Pentium-III.
We also propose a better theoretical foundation for the
criterion that guides the construction algorithm's splitting
procedure. The basic idea can be applied to all BV hierarchies

A number of algorithms have been developed for fast collision
detection utilizing restricted boxtrees. They gain their
e#ciency from the special features of that BV hierarchy.
Benchmarking them has shown that one of them seems to
perform consistently better than the others.
Several optimization techniques have been presented that
further increases the performance of our new collision detection
algorithm. The most important one can also be applied
to most other hierarchical collision detection algorithms, and
will significantly improve their performance.
Finally, using a suite of CAD objects, a comparison with
trees suggested that the performance of restricted box-
trees is about as fast in most cases.
6.1 Future Work
While BV trees work excellently with rigid objects, it is
still an open issue to extend these data structures to accommodate
deforming objects.
Our new BV hierarchy could also be used for other queries
such as ray tracing or occlusion culling. It would be interesting
to evaluate it in those application domains.
As stated above, most BV trees are binary trees. However,
as [6] have observed, other arities might yield better per-
formance. This parameter should be optimized, too, when
constructing boxtrees.
So far, we have approximated the cost equation only to
first order (or rather, first level). By approximating it to a
higher order, one could possibly arrive at a kind of "look-
ahead" criterion for the construction algorithm, which could
result in better hierarchies.
7.



--R

tiling for kinetic collision detection.
A survey of ray tracing acceleration techniques.
BOXTREE: A hierarchical representation for surfaces in 3D.



Accurate and fast proximity queries between polyhedra using convex surface de- composition
Fast penetration depth estimation for elastic bodies using deformed distance fields.

Automatic creation of object hierarchies for ray tracing.
A hierarchical structure for rapid interference detection.
Approximating polyhedra with spheres for time-critical collision detection
Collision resolutions in cloth simulation.


Six degrees-of-freedom haptic rendering using voxel sam- pling
Collision detection for animation using sphere-trees
Computational Ge- ometry: An Introduction


Rapid collision detection by dynamically aligned DOP-trees
--TR
Computational geometry: an introduction
Automatic creation of object hierarchies for ray tracing
A survey of ray tracing acceleration techniques
The R*-tree: an efficient and robust access method for points and rectangles
OBBTree
Six degree-of-freedom haptic rendering using voxel sampling
Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs
K-D Trees Are Better when Cut on the Longest Side
Efficient collision detection of complex deformable models using AABB trees
Real-Time Collision Detection and Response for Complex Environments
Rapid Collision Detection by Dynamically Aligned DOP-Trees

--CTR
Jan Klein , Gabriel Zachmann, Time-critical collision detection using an average-case approach, Proceedings of the ACM symposium on Virtual reality software and technology, October 01-03, 2003, Osaka, Japan
Kavan , Carol O'Sullivan , Ji ra, Efficient collision detection for spherical blend skinning, Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia, November 29-December 02, 2006, Kuala Lumpur, Malaysia
Esther M. Arkin , Gill Barequet , Joseph S. B. Mitchell, Algorithms for two-box covering, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
physically-based modeling;hierarchical partitioning;virtual prototyping;hierarchical data structures;r-trees;interference detection