Game Development Reference
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 , while GJK is more comprehensively described in van den
Bergen , reflecting each author's use of their favorite technique in their collision
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-
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 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.