is Valentine’s month. Spring is in the air. People can meet, fall in love,
and have their hearts broken all before their first cup of coffee. I don’t
think we’ve reached the point, yet, where we can adequately simulate a
broken heart. However, I do think we can reasonably detect whether two
people are close enough for their hearts to collide.
article we’ll look at how to apply the same principles to 3D. Most discussions
of collision detection for real-time game applications begin with bounding
spheres and bounding boxes. These two tests are very rough indicators
of whether or not a collision has occurred. Bounding spheres are a very
fast method for testing collisions. However, bounding spheres don’t generally
provide the best approximation of an object’s extents.
Box Me In
bounding box (AABB) is also a very quick way of determining collisions.
The fit is generally better than a bounding sphere (especially if the
object you are bounding is a box itself). You can see an AABB on an object
in Figure 1. However, once you rotate the object a little, the bounding
box may not be nearly as efficient, as you can see in Figure 2.
could clearly lead to cases in which you mistakenly assume that a collision
has occurred. But, as a first step, calculating an AABB may not be too
bad. We could allow the original bounding box as calculated in Figure
1 to orient along with the object (Figure 3). This is called an oriented
bounding box (OBB). It’s definitely a better fit than Figure 2, however,
I have lost the key benefit of AABBs. Aligned axes make AABBs easy to
use in collision detection. Checking whether a point has entered the box
involves only a trivial calculation. With OBBs, checking for collisions
is more complicated. In many applications, OBBs may be worth pursuing
further, but for a quick first check, I want to stick with AABBs.
1. Axis-aligned bounding box on an object.
2. Axis-aligned bounding box on a
are the main problems with coding up AABBs? Well, the biggest issue with
using AABBs is that they need to be recreated every time the object changes
orientation. This means that every vertex must be transformed by the object’s
matrix and the minimum and maximum extents must be calculated. Listing
1 contains a routine that calculates an AABB for an object. The noteworthy
line in this code is the MultVectorByMatrix() call. This function transforms
each vertex coordinate of the object into world space, given the current
1. Calculate an Axis-aligned Bounding Box for an Object.
// Procedure: RecalcFullBBox
// Purpose: Recalculates
the BBox associated with a bone based on the
position for the vertices. Tighter fit in
cases. However, has to process all vertices
*curBone, tVector *min,tVector *max)
/// Local Variables ///////////////////////////////////////////////////////////
tVector *temp,tempRes; //
tNormalVertex *nvData; //
VERTEX WITH NX,NY,NZ,X,Y,Z
visual = curBone->visuals; // GET AT THE VISUAL ATTACHED
TO A BONE
nvData = (tNormalVertex
*)visual->vertexData; // THE ACTUAL INTERLEAVED VERTEX DATA
for (int loop = 0; loop < visual->faceCnt * visual->vPerFace;
temp = (tVector
*)&nvData->x; // POINTER TO THE VERTEX XYZ VALUES
temp,&tempRes); // MULT BY THE BONE MATRIX
// FIRST VERTEX,
SET IT AS THE MAX AND MIN
if (loop == 0)
if (tempRes.x >
max->x) max->x = tempRes.x;
if (tempRes.y >
max->y) max->y = tempRes.y;
if (tempRes.z >
max->z) max->z = tempRes.z;
if (tempRes.x <
min->x) min->x = tempRes.x;
if (tempRes.y <
min->y) min->y = tempRes.y;
if (tempRes.z <
min->z) min->z = tempRes.z;
3. Oriented bounding box on a rotated object.
In the best
case, this transformation can be reused when it comes to drawing the model.
However, in the worst case, you’ll be duplicating transformation work.
In any case, the CPU is handling the matrix transformation for these bounding
boxes. With the appearance of transformation hardware on graphics cards
(such as the 3Dlabs Glint GMX and Diamond Fire GL 5000), this is a very
costly operation. As this kind of hardware begins to dip into the consumer
3D hardware space, programmers need to be very careful to avoid using
techniques that require vertex transformation by the CPU. Calculating
a bounding box for a model with many vertices is a fairly expensive process.
If your models are large, this can be a big frame-rate vampire that sucks
the life right out of your game.