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.

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.

Listing 1. Calculate an Axis-aligned Bounding Box for an Object.

///////////////////////////////////////////////////////////////////////////////
// Procedure: RecalcFullBBox
// Purpose: Recalculates the BBox associated with a bone based on the
// new position for the vertices. Tighter fit in
// most cases. However, has to process all vertices
///////////////////////////////////////////////////////////////////////////////

GLvoid COGLView::RecalcFullBBox(t_Bone *curBone, tVector *min,tVector *max)

{

/// Local Variables ///////////////////////////////////////////////////////////
tVector *temp,tempRes; // X,Y,Z VECTORS
tNormalVertex *nvData; // VERTEX WITH NX,NY,NZ,X,Y,Z
t_Visual *visual;
///////////////////////////////////////////////////////////////////////////////

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; loop++)
{

}

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.

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.

///////////////////////////////////////////////////////////////////////////////
// Procedure: RecalcBBox
// Purpose: Recalculates the BBox associated with a bone based on the
// original bounding box. This is faster then the true BBox in
// most cases. However, this BBox is not as tight a fit.
///////////////////////////////////////////////////////////////////////////////

GLvoid COGLView::RecalcBBox(t_Bone *curBone, tVector *min,tVector *max)

{

/// Local Variables ///////////////////////////////////////////////////////////
tVector tempRes;
int loop;
///////////////////////////////////////////////////////////////////////////////

for (loop = 0; loop < 8; loop++) // LOOP THROUGH ALL 8 BBOX COORDS

}

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.

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.

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?

Balancing on a Polygon Edge

Luckily for me, I don’t have to try arbitrary planes to see if they separate the objects. It turns out that if the separating plane is made up of a face on the object, then it must contain an edge in the object. Figure 7 displays two bjects that cannot be separated by any face in either object.

In this case, I create a plane composed of edge A and vertex B. If all of the vertices of Object 1, with the exception of those that make up edge A, are on one side of the plane, and all of the vertices of Object 2, with the exception of vertex B, are on the other side, then I may have found a separating plane. One last check has to be made in order to make sure that vertex B isn’t actually on edge A. If they were collinear, that would obviously be a collision. Once that possibility is ruled out, I can mark this as the separating plane.

Once I’ve tried every edge/vertex pair as well as all the faces, then the objects must be colliding. However, once I’ve found this separating plane, I can be sure that the objects are not colliding and I can move on. After the separating plane is found, it should be stored. Going through all of the faces and edges to find a plane is obviously pretty expensive to calculate. By saving the separating plane from the previous frame, I can take advantage of the fact that the separating plane tends to remain the same over several frames.

As I mentioned earlier, all of these tests only handle convex objects. It is much easier to determine collision on convex objects. If your objects are concave, you will need a method for creating a convex hull around the object. You can do this through a variety of methods. The concave object can be broken into several convex objects. There are also automatic methods of generating a convex hull around a concave object. One of the most popular methods is called QHull. You can find a link to it in the references. However, it may be much more efficient to have the artists create a convex collision object for every object in the game. That way, the artist can make the decisions about exactly what features are important to define as part of the collision boundary. This approach abides well by the game developer’s philosophy: "Do as much work up front as possible, especially if it saves run time."

Boom, Boom, Out Go the Lights

That’s all the time for this month. The sample application will allow you to load an object and play around with bounding boxes. When two objects have overlapping bounding boxes, a separating plane will be found, if possible. If not, a collision will be reported. Next month, I’ll take up the issue of collision response so we can find out what to do once a collision has happened.

References:

Collision detection is a very active area of research. This method represents only one.

• Gottschalk, Lin, and Manocha. "OBBTree: A Hierarchical Representation for Rapid Interference Detection." University of North Carolina, Chapel Hill. http://www.cs.unc.edu/~geom/OBB/OBBT.html

I mentioned the use of oriented bounding boxes. This paper extends this method to include a hierarchy of OBBs. Also, several sources discuss the use of tracking the closest features of two objects in order to determine when a collision occurs.

• Gilbert, Johnson, and Keerthi. "A fast procedure for computing the distance between complex objects in three-dimensional space." IEEE Transactions on Robotics and Automation, April 1988, pp. 193-203.

• Lin, M. C. "Efficient Collision Detection for Animation and Robotics." Ph.D. Thesis, University of California, Berkeley, December 1993.

• Baraff, David, and Andrew Witkin, "Physically Based Modeling," SIGGRAPH Course Notes, July, 1998, pp. D32-D40. This paper also describes a method for using bounding box frame coherence to achieve more efficiency.

• Barber, Dobkin, and Huhdanpaa, "The Quickhull algorithm for convex hulls," ACM Transactions on Mathematical Software, Dec. 1996. This is the QHull library for calculating convex hulls. You can find more info at http://www.geom.umn.edu/software/qhull/

• There are also several libraries of collision routines available for use in non-commercial applications. Commercial applications may require a fee, so be sure to contact the source before using any library in a game application. These include I-Collide, V-Collide, Enhanced GJK, and others. A good link for all of these is at the University of North Carolina, Chapel Hill web site, http://www.cs.unc.edu/~geom.

Jeff Lander watches over a vast empire at Darwin 3D. He is also responsible for any collisions involving his email at [email protected]. Test his collision efficiency by sending him questions and comments.