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.

Figure 7. Separating two objects by an edge-plane.

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 jeffl@darwin3d.com. Test his collision efficiency by sending him questions and comments.