Colliding in the Third Dimension

Running around a maze is one thing, but that’s just the beginning to the collision detection story. Consider the problem of determining if two objects have collided. Two of the most common approaches to this problem are bounding boxes and bounding spheres. For a bounding sphere, find the point furthest away from the center of the object. The distance of the point from the center defines the radius of the bounding sphere. You can see a bounding sphere around an object in Figure 6. Now imagine that the object and circle around it are actually 3D. As you can see, although the entire object is inside the sphere, it isn’t a snug fit. You can see how easy it would be to have an object that would hit the bounding sphere yet miss the object completely.

So why use a bounding sphere? Well, testing to see if a collision has occurred is really fast. If you measure the distance between two objects, and the distance is less than the radius of either bounding sphere, then there is a collision. This is a very quick test, so it’s easy to see why many games use spheres as at least a first line of defense. But if you need to determine exactly where two objects made contact, this won’t be enough.

Axis-aligned bounding boxes, or bounding boxes for short, are another simple method for collision detection. The box is called axis-aligned because the sides of the box are parallel to the principle world x, y, and z axes. This reduces the check for collision to a simple minimum-maximum test. You create the box by determining the minimum and maximum extents in each dimension. The collision test then consists of:

IF ( (point.x >= box.minX
and point.x <= box.maxX)
and (point.y >= box.minY
and point.y <= box.maxY)
and (point.z >= box.minZ
and point.z <= box.maxZ)
)then a collision occurred.

Figure 6. A bounding sphere.

Bounding boxes are a simple, fast way to check for rough collisions. However, like the bounding spheres, the fit is not necessarily very accurate. They’re generally used as a first test to check if further investigation is needed. You can improve the fit by maintaining a hierarchy of smaller bounding boxes or spheres that are tested after the initial collision is determined. For many games, such as 3D fighting games which require fairly detailed collision, this is enough for realism. If you need more detailed collision information, you need to look elsewhere. Other methods such as oriented bounding boxes (OBB), where the bounding box is allowed to rotate to an arbitrary orientation, will allow for a tighter fit than either above method. However, even OBBs do not provide information on the exact point of collision on an arbitrary mesh unless the object happens to be a box.

Getting to the Point

If you really need to know which point of an object has collided with another — say for your realistic physics simulation — you have some work in front of you. All the other techniques are good first steps, and serve to filter out unneeded calculations. I’m going to start out in 2D again to make things easy. Let me begin by considering only convex objects. Remember that convex objects are polygon meshes that contain no interior angles greater than 180 degrees. Figure 7 outlines the problem.

Figure 7. Two convex polygons.

I am interested in deciding whether polygon 1 is colliding with polygon 2. I could use my point-in-polygon test from earlier, and test every point in each polygon and see if it’s in the other. That wouldn’t be very efficient though, and in 3D it would be even less reasonable. What I really want to find is a single feature that makes it impossible for polygon 2 to be inside polygon 1. It turns out that if I can find a line that separates the two polygons, then they cannot be colliding. To make it easier, I will use the edges of each polygon as a test line. If all the vertices of polygon 2 are on the other side of an edge in polygon 1, they aren’t colliding.

You will recall from the convex point-in-polygon test that I used the dot product to determine if a point was inside an edge. I can use the same test to see if a point is outside. In other words, if vectorba dot vectorbc < 0, then point c is outside of polygon 1.

That dot product operation sure comes in handy. In 3D, you would be dotting the face normal with the test point, but it works out similarly. The first time you test to find this separating edge, you need to test all edges in each polygon against all the vertices in the opposite one. However, once you have found a separating edge, you can store this information so that edge is the first one you will test the next time you try. This caching of collision points can speed up testing quite a bit, and I highly recommend it.

That is all the time I have for this month. Next month, I will examine what exactly is required for detecting the collision point in 3D. I will also discuss what you can do with this information once you have it, and work out some cool samples to demonstrate it.

For Further Info:

• O’Rourke, Joseph. Computation Geometry in C. Cambridge University Press, 1993. A very good discussion of point-in-polygon strategies as well as path finding and convex hull operations (hint: may be handy).

• Heckbert, Paul S., Editor. Graphic Gems IV. Academic Press, 1994. Inside polygon strategies and routines.

• Baraff, David, and Andrew Witkin. "Physically Based Modeling," SIGGRAPH Course Notes, July, 1998, pp. D32 – D40. Collision detection and response methods.

Jeff Lander made a resolution this year to shrink his own bounding box and to spend more time away from the computer. Show him how futile this is by mailing him at jeffl@darwin3d.com.