Game Development Reference

In-Depth Information

Note that there are algorithms that avoid generating and testing all vertices. By

comparing the direction of each box axis against the plane normal, we can trim down

the number of vertices that need to be checked. You may find such algorithms in other

topics or online.

Despite the marginal theoretical advantage of such an algorithm, I have found

them to have no efficiency gain in practice. Generating and testing a vertex is so fast

that additional checking has a marginal effect. If you are familiar with the technique,

you will also notice that this algorithm lends itself very easily to parallel implementa-

tion on SIMD hardware, which makes the alternatives even less attractive.

13.3.4

C
OLLIDING A
S
PHERE AND A
B
OX

A box complicates the calculations somewhat. When a sphere collides with a box, we

will have just one contact. But it may be a contact of any type: a face-face contact,

an edge-face contact, or a point-face contact. In each case the sphere (which has no

edges or vertices) contributes a face to the contact, but it may touch either a face,

edge, or point of the box. Figure 13.12 illustrates this.

Fortunately all three of these cases involve the same calculations for the normal

contact and penetration depth, as long as we assume that the sphere gets to decide the

contact normal in the case of a face-face contact. (Recall that, for face-face contacts,

one or other object has to work out the normal.)

Once again we can simplify this query to use a point rather than a sphere. In this

case we need to find the closest point in the box to the center of the sphere. This

closest point may be in a corner of the box, along an edge, or on a face. If the distance

between the closest point and the center of the sphere is less than the radius of the

sphere, then the two objects are touching.

Because we'll deal with all three types of contact in the same way—allowing the

properties of the sphere to determine the contact data—we won't need to keep track

of whether the closest point in the box is on a face, edge, or vertex.

F
IGURE
13.12

Contacts between a box and a sphere.