Game Development Reference
In-Depth Information
The first step of our process is to convert the center point of the sphere into the
object coordinates of the box. Remember that the box can be oriented in any direc-
tion. It will be easier to process if coordinates of the point we're working with are
relative to the orientation of the box. We can do this simply by using the following
code.
Excerpt from src/collide_fine.cpp
// Transform the center of the sphere into box coordinates
Vector3 center = sphere.getAxis(3);
Vector3 relCenter = box.transform.transformInverse(center);
Note that we've taken into account both the orientation of the box and its center.
This then allows us to perform a quick early-out test to see whether the point will
be close enough to bother with. The contact generation will be reserved for points
that pass this early test. As we shall see, the contact generation algorithm is hardly
complex, and we don't gain a huge amount by having the early-out test. Neverthe-
less it can be worth it in some cases (particularly if the coarse collision detection is
inefficient and generates lots of potential collisions).
The early-out test relies on the principle of separating axes.
Separating Axes
Separating axes is one of the most useful concepts in collision detection. It has many
nuances, which I can't hope to cover here. See van den Bergen [2003] or Ericson
[2005] for a complete discussion and lots of helpful diagrams.
The basic idea is simple: if we can find any direction in space in which two (con-
vex) objects are not colliding, then the two objects are not colliding at all. In our case
we can simply test the three axes of the box and check if the point is too far away to
be colliding. If any of these axes shows that the point is too far away, then we know
there is no contact and we can exit earlier. Figure 13.13 illustrates this in 2D.
Note, however, that we can have a situation where the sphere and the box aren't in
contact, but the separating axes test doesn't detect this. A case is shown in the diagram
in figure 13.13.
In this case the algorithm will pass on to the more complete contact generation
step and will detect that there is no contact later on. We could improve the separating
axes test to check further axes in this case (the axis from the center of the box to the
center of the sphere in figure 13.13 would help). Remember, however, that this step
is designed to give us an early-out. We don't want to waste processing time, and we
could spend just as much time trying to determine whether there is a contact in this
phase as we'd save by not performing the full contact generation in the next phase.
For each test axis we simply check if the half-width of the box plus the radius of
the sphere is greater than one component of the relative position of the sphere center
(i.e., the transformed position we found earlier). See the next block of code.