February 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.

In this 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.

Don’t Box Me In

An axis-aligned 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.

This discrepancy 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.

Figure 1. Axis-aligned bounding box on an object.

Figure 2. Axis-aligned bounding box on a rotated object.

So what 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 object orientation.

temp = (tVector *)&nvData->x; // POINTER TO THE VERTEX XYZ VALUES
MultVectorByMatrix(&curBone->matrix, temp,&tempRes); // MULT BY THE BONE MATRIX
// FIRST VERTEX, SET IT AS THE MAX AND MIN
if (loop == 0)
{
memcpy(min,&tempRes,sizeof(tVector));
memcpy(max,&tempRes,sizeof(tVector));
}
else
{
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;
}
nvData++;
}

}

Figure 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.