Whether
it's your car crossing the finish line at 180 miles per hour, or a bullet
tearing through the chest of your best friend, all games make use of
collision detection for object interaction. This article describes some
simple intersection tests for the most useful shapes: spheres and boxes.
Sweep
Tests for Moving Objects
A
common approach to collision detection is to simply test for whether
two objects are overlapping at the end of each frame. The problem with
this method is that quickly moving objects can pass through each other
without detection. To avoid this problem, their trajectories can be
subdivided and the objects checked for overlap at each point; however,
this gets expensive if either object experienced a large displacement.
On the other hand, a sweep test can efficiently determine a lower and
upper bound for the time of overlap, which can then be used as more
optimal starting points for the subdivision algorithm.
A
SpherePlane Sweep Test
Figure
1 shows an example of a quickly moving sphere passing through a plane.
It can be seen that C_{0} is on the positive side of
the plane and C_{1} is on its negative side.

Figure
1. A sphere passes through a plane. 
In
general, if a sphere penetrated a plane at some point during the frame,
then d_{0}>r and d_{1}<r, where
r is the radius of the sphere and d_{0} and d_{1}
are the signed distances from the plane to C_{0} and
C_{1}, respectively. The signed distance from a point
C to a plane can be calculated with the formula
More
efficiently, we can store the plane in the form {n, D},
where
The
distance d is then calculated
The
trajectory from C_{0} to C_{1} can be
parameterized with a variable u, which may be thought of as normalized
time, since its value is 0 at C_{0} and 1 at C_{1}.
The normalized time at which the sphere first intersects the plane is
given by
The
center of the sphere at this time can then be interpolated with an affine
combination of C_{0} and C_{1}
This
formula interpolates C_{i} correctly as long as d_{0}
is not equal to d_{1} (which is the case if displacement
has occurred), even when r = 0 (the case of a line segment).
If desired, the parameter u can also be used to linearly interpolate
the orientation of an object at this point.
In
this example, it was assumed that the sphere approached the plane from
the positive side and that the sphere was not already penetrating the
plane at C_{0.}. In the case that there could have been
penetration on the previous frame, the condition d_{0}<=r
should also be checked. Listing 1 gives an implementation of this sphereplane
sweep test.
Listing
1. A sphereplane sweep test.
#include "vector.h"
class PLANE
{
public:
VECTOR N;
//unit normal
SCALAR D;
//distance from the plane to the origin
from a
//normal and a point
PLANE( const VECTOR&
p0, const VECTOR& n ): N(n),
D(N.dot(p0))
{}
//from 3 points
PLANE( const VECTOR&
p0, const VECTOR& p1,
const VECTOR& p2 ): N((p1p0).cross(p2p0).unit()),
D(N.dot(p0))
{}
//signed distance from the
plane topoint 'p' along
//the unit normal
const SCALAR distanceToPoint(
const VECTOR& p ) const
{
return N.dot(p) + D;
}
};
const bool SpherePlaneSweep
(
const SCALAR r, //sphere
radius
const VECTOR& C0, //previous
position of sphere
const VECTOR& C1, //current
position of sphere
const PLANE& plane, //the
plane
VECTOR& Ci, //position
of sphere when it first touched the plane
SCALAR& u //normalized
time of collision
)
{
const SCALAR d0
= plane.distanceToPoint( C0 );
const SCALAR d1 = plane.distanceToPoint(
C1 );
//check if
it was touching on previous frame
if( fabs(d0) <= r )
{
Ci = C0;
u = 0;
return true;
}
//check if
the sphere penetrated during this frame
if( d0>r && d1<r
)
{
u = (d0r)/(d0d1); //normalized
time
Ci = (1u)*C0 + u*C1; //point
of first contact
return true;
}
return false;
}
For
the definition of the VECTOR class, please see [3].