Game Development Reference
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.
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.