Getting More Bang For My Buck

You may wonder if there is any way to avoid having to transform every vertex into world space in order to find the bounding box. There is a way. However, like many things in computer game programming, there is a trade-off. Because I’ve already calculated the bounding box of the object in its rest position, it’s possible to transform only those extreme points by the current orientation and get a new bounding box. In other words, I can take the vertices of the object’s OBB and use the maximum and minimum of those positions to create a new AABB. I’m guaranteed that the new bounding box will completely contain the object because I’ve used the extreme extents of the initial position to create this new box. It may not be a tight fit, but it will fit. The good part is that this solution only takes eight transformations to calculate this new box — quite a bit of savings if your model contains many vertices. You can see the difference in Figure 4. The image on the right is the true AABB for the object. The image on the left is created using the yellow OBB as the source for the AABB. Listing 2 contains the code for calculating a bounding box this way.

Listing 2. Faster AABB Calculation Using Starting OBB.

{
MultVectorByMatrix(&curBone->matrix, &curBone->visuals->bbox[loop],&tempRes);
memcpy(&curBone->visuals->transBBox[loop],&tempRes,sizeof(tVector));
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;
}

}

Figure 4. Fast and slow methods for calculating AABBs.

Obviously, for some cases, this method doesn’t result in nearly as snug a fit as our original AABB calculation. However, it’s certainly faster, and on a system with hardware vertex transformation, you may prefer it. Which method is right for your game? How should I know? Try them both and see. If you’re using bounding boxes as a quick early check and have more sophisticated methods in follow-up tests, this quicker method may be good enough.

When creating the initial bounding box for the faster AABB method, it’s easiest to calculate the AABB of the object in its initial rest position. However, the initial bounding box doesn’t have to be axis-aligned. You can achieve a better fit by defining an OBB in the modeling program when the object is built. The method will then use the OBB to calculate the current AABB. Depending on the model, an initial OBB may really help. Certainly, a box built on a diagonal is a perfect candidate for an initial OBB.

When Two Boxes Collide

My nice new bounding boxes overlap in two of my objects. Chances are, I have a collision occurring between them. But I have to make sure. Also, in order to do some interesting things, I need to determine exactly where they are touching. Take a look at Figure 5.

Figure 5. Two objects near a collision.

The bounding box of the two objects clearly are colliding. It’s also just as clear that the objects themselves are not. This is why being a human is great and being a game programmer is difficult. A child can easily determine that the two objects in the picture are not actually hitting each other. If a game relies solely on bounding boxes for collision detection, players may feel cheated when two objects "hit" when it appears as if they didn’t. So, how can the computer determine that this is really not a hit? Notice that both of these objects are convex. This distinction is very important. I’ll talk about what to do if your object is concave later, but for now, let me only consider the case where the two objects being tested are convex.

When dealing with 3D, if I can find a plane that separates the two objects, then I know for certain that the objects are not colliding. I’ll begin by considering each face of each object as the separating plane. It should be clear that the face highlighted in yellow in Figure 6 defines a plane that completely separates the two objects.

Figure 6. Finding a separating plane.

In order to test this separation plane, I need to make sure that all the vertices of the right object are on the other side of this plane from the test object on the left. It’s helpful to have a normal defined for each face in the model. If you don’t have face normals defined in the model file, you can create them by averaging the vertex normals or by taking the cross product of two of the vectors that make up the face. I can begin once I have a face normal to test with — such as N in Figure 6. I create a vector between a vertex on the test face and each vertex on the colliding object. For example, I create a vector between points A and B in Figure 6 and call it Vector AB. Then I take the dot product of that vector and the face normal, N • Vector AB. If this value is positive, vertex A is not colliding with the object. If all the vertices in the colliding object are on the far side of the separating plane, then I definitely don’t have a collision, and I’m done.

What happens if I’ve gone through all of the faces and cannot find a separating plane? Do I definitely have a collision? Unfortunately, no. There may be a separating plane that’s not a face on either object. An infinite number of planes exist, so how can I find one that separates the two objects?