Game Development Reference

In-Depth Information

Contact Generation

So we've reduced the complex task of generating a set of contacts between two boxes

to the problem of finding the point of deepest interpenetration. In addition, however,

we find that the point of deepest penetration has to be able to return the features on

which the contact takes place.

A range of algorithms can help us do this for both boxes and general convex ob-

jects. V-Clip is one of the best known, but the detection phase of Lin-Canny, and

Gilbert, Johnson, and Keerthi's algorithm (GJK) are also useful. V-Clip is described

in detail in Ericson [2005], while GJK is more comprehensively described in van den

Bergen [2003], reflecting each author's use of their favorite technique in their collision

detection libraries.

All these algorithms are
distance
algorithms: they can return the shortest distance

between two polyhedra. In our case this is useful when the distance returned is less

than zero: the objects are interpenetrating. Lin-Canny in particular has problems with

this case; it needs to be tweaked to catch the interpenetration case and avoid an infi-

nite loop.

Both V-Clip and GJK intelligently search the possible combinations of features

that can be in contact. They are sufficiently intelligent about this that there is little

speed advantage in performing a separating axis test as an early-out for boxes.

To build a robust and efficient collision detection system for general polyhedra,

you will eventually need to use something like these techniques. Be careful, however.

Various efficient collision detection algorithms, including V-Clip and some of its vari-

ants, are protected by patents. If you implement these algorithms in your code, you

may need to get a license agreement or pay a licensing fee.

To allow us to test out the physics without writing a full collision detection sys-

tem, we can build a naive algorithm that checks all possible interpenetrations. This

is workable for a box with six faces, eight vertices, and twelve edges but shouldn't be

considered production-ready for anything more complex.

Our naive contact generator simply checks for both of the contact types we are

interested in: point-face contacts and edge-edge contacts. If it finds more than one

such contact, then the contact that has the greatest interpenetration is returned. Re-

member that we aren't returning multiple contacts, because getting a self-consistent

set of such contacts can be difficult.

To exhaustively check for contacts we perform two kinds of check: a point-face

check of each vertex on each object against the other object, and an edge-edge check

of each edge on one object against the other.

Point-Face Contact

Point-face contacts are easy to detect: they use the same logic as for sphere-box col-

lisions but with a zero-radius sphere. We simply project each vertex from one box

into the principal axes of the other. If the vertex is inside the box, then a point-face

collision is required. If the vertex is inside the box on more than one axis, then the

axis with the shallowest penetration is used. Figure 13.18 shows this.