Game Development Reference
In-Depth Information
places can pass every separating axis test and still not be touching. For general objects
this isn't particularly practical knowledge, of course, because we can't hope to test
every, possible axis. That would defeat the purpose of using this test to provide an
early-out.
When colliding two boxes, things are easier for us. There are fifteen axes we can
test. If none of the fifteen shows the objects separately, then we know the objects
touch.
These axes include the three principal axes of each box; there are also another nine
axes to test that are perpendicular to each pair of principal axes from each box. We
generate these further nine axes by taking the cross product of each pair of principal
axes (since the direction of the cross product is perpendicular to both its vectors).
The full implementation simply calculates these axes in turn and sends them to
the separateAlongAxis function for checking. The whole test returns false when the
first such function call fails.
Coherence and Contact Generation
The most efficient algorithms for calculating the collision between two boxes (and any
pair of convex objects) use shortcuts and optimizations that terminate the algorithm
when the point of deepest interpenetration is found. This is a single contact.
To generate a complete set of contacts is more difficult. One contact can be inter-
preted in several ways. A point-face contact could be interpreted as another point-
face contact on a different face, with a different penetration depth. The situation is
even more complex with edge-edge contacts.
To get the contact set, we need to provide a whole set of reasonably complex code
that checks to see whether new potential contacts have already been found and, if so,
whether the new way of interpreting them is better. And in the worst-case scenario
reinterpreting one contact may mean that all the other contacts in the set need reinter-
preting. If there weren't a simpler way, this might be worth the effort, but fortunately
we can avoid the whole issue.
At each frame we generate a single contact, based on the maximum penetration
of the two boxes. This is resolved in the normal way. Because we only have one con-
tact resolved, the boxes will likely reinterpenetrate in the next frame but often in a
different way. This new interpenetration is detected as a new contact, so now we have
two contacts. This continues a third time, when we have three contacts, sufficient to
keep the two boxes stacked in a stable manner. Figure 13.17 shows this in action for
two contacts in two dimensions.
The chances that an existing contact will be useful in the next frame are high when
the boxes are stable, but when they are moving, the contact may be completely wrong
at the following frame.
To avoid having to throw away the contacts when boxes are moving (which would
mean we'd be back to generating just a single contact at each frame), we don't store
the complete contact but only the features that are touching.
We've met features throughout this chapter: point, edge, and face. A point-edge
contact is a contact between a certain vertex and a certain face. To take advantage