Detecting Collisions
Using Hierarchy Trees
Now,
let’s assume that we have either our OBB or AABB trees. How do we actually
perform collision detection? We’ll take two trees and check whether
two initial boxes overlap. If they do, they might intersect, and we’ll
have to recursively process them further (recursive descent). If, along
the descent, we find that the subtrees do not intersect, we can stop
and conclude that no intersection has occurred. If we find that the
subtrees do intersect, we’ll have to process the tree until we hit its
leaf nodes to find out which parts overlap. So, the only thing we have
to figure out is how to check whether two boxes overlap. One of the
tests that we could perform would be to project the boxes on some axis
in space and check whether the intervals overlap. If they don’t, the
given axis is called a separating axis (Figure 8).
To
check quickly for overlap, we’ll use something called the Separating
Axis Theorem. This theorem tells us that we have only 15 potential separating
axes. If overlap occurs on every single separating axis, the boxes intersect.
Thus, it’s very easy to determine whether or not two boxes intersect.
Interestingly,
the time gradient problem mentioned earlier could easily be solved by
the separating axis technique. Remember that the problem involved determining
whether a collision has occurred in between any two given times. If
we add velocities to the box projection intervals and they overlap on
all 15 axes, then a collision has occurred. We could also use an structure
that resembles an AABB tree to separate colliders and collidees and
check whether they have a possibility of collision. This calculation
can quickly reject the majority of the cases in a scene and will perform
in an O(N logN) time that is close to optimal.

Figure
8. Separating axis (intervals
A and B don’t overlap).

Collision
Techniques Based on BSP Trees
BSP
(Binary Space Partitioning) trees are another type of space subdivision
technique that’s been in use for many years in the game industry (Doom
was the first commercial game that used BSP trees). Even though BSP
trees aren’t as popular today as they have been over the past couple
of years, the three most licensed game engines today — Quake II,
Unreal, and Lithtech — still use them quite extensively. The beauty
and extreme efficiency of BSP trees comes to light when we take a look
at collision detection. Not only are BSP trees efficient for geometry
culling, we also get very efficient worldobject collision almost for
free.
The
BSP tree traversal is the fundamental technique used with BSPs. Collision
detection basically is reduced to this tree traversal, or search. This
approach is powerful because it rejects a lot of geometry early, so
in the end, we only test the collision detection against a small number
of planes. As we’ve seen before, finding a separating plane between
two objects is sufficient for determining that those two objects don’t
intersect. If a separating plane exists, no collision has occurred.
So, we can recursively traverse a world’s tree and check whether separating
planes intersect the bounding sphere or bounding box. We can increase
the accuracy of this approach by checking for every one of the object’s
polygons. The easiest way to perform this check is to test whether all
parts of the object are on the same side of the plane. This calculation
is extremely simple. We can use the Cartesian plane equation, ax + by
+ cz + d = 0, to determine the side of the plane upon which the point
lies. If the equation is satisfied, then our point lies on the plane.
If ax + by + cz + d > 0, then the point is on the positive side the
plane. If ax + by + cz + d < 0, then the point is on the negative
side the plane.
The
only important thing to note is that for a collision not to occur, all
of the points of an object (or a bounding box) have to be on either
the positive or the negative side of a given plane. If we have points
on both the positive and negative side of the plane, a collision has
occurred and the plane intersects the given object.
Unfortunately,
we have no elegant way of checking whether a collision has occurred
in between the two intervals (although the techniques discussed at the
beginning of this article still apply). However, I have yet to see another
structure that has as many uses as a BSP tree.
Curved
Objects and Collision Detection
Now
that we’ve seen two approaches to collision detection for polygonal
objects, lets see how we can compute the collision of curved objects.
Several games will be coming out in 1999 that use curved surfaces quite
extensively, so the efficient collision detection of curved surfaces
will be very important in the coming year. The collision detection (which
involves exact surface evaluation at a given point) of curved surfaces
is extremely computationally intensive, so we’ll try to avoid it. We’ve
already discussed several methods that we could use in this case, as
well. The most obvious approach is to approximate the curved surface
with a lowesttessellation representation and use this polytope for
collision detection. An even easier, but less accurate, method is to
construct a convex hull out of the control vertices of the curved surface
and use it for the collision detection. In any case, curved surface
collision approximation is very similar to general polytope collision
detection. Figure 9 shows the curved surface and the convex hull formed
from the control vertices.

Figure
9. Hull of a curved object.

If
we combined both techniques into a sort of hybrid approach, we could
first test the collision against the hull and then recursively subdivide
the patch to which the hull belongs, thus increasing the accuracy tremendously.
Decide
for Yourself
Now
that we’ve gone over some of the more advanced collision detection schemes
(and some basic ones, too), you should be able to decide what type of
system would best suit your own game. The main thing you’ll have to
decide is how much accuracy you’re willing to sacrifice for speed, simplicity
of implementation (shorter development time), and flexibility.
For
Further Info
•
H. Samet. Spatial Data Structures: Quadtree, Octrees and Other Hierarchical
Methods. Addison Wesley, 1989.
•
For more information about AABBs take a look at J. Arvo and D. Kirk.
“A survey of ray tracing acceleration techniques,” An Introduction
to Ray Tracing. Academic Press, 1989.
•
For a transformation speedup, check out James Arvo’s paper in Andrew
S. Glassner, ed. Graphics Gems. Academic Press, 1990.
•
S. Gottschalk, M. Lin, and D. Manocha. “OBBTree: A hierarchical Structure
for rapid interference detection,” Proc. Siggraph 96. ACM Press, 1996.
has contributed a great deal to the discussion of OBBs in terms of accuracy
and speed of execution.
•
S. Gottschalk. Separating Axis Theorem, TR96024, UNC Chapel
Hill, 1990.
•
N. Greene. “Detecting intersection of a rectangular solid and a convex
polyhedron,” Graphics Gems IV. Academic Press, 1994. introduces several
techniques that speed up the overlap computation of a box and a convex
polyhedron.
Nick
Bobic is trying not to work 14 hours a day with very little success.
Any new collision tips and tricks should be sent to [email protected].