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