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 pointsPLANE( 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 normalconst 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].
A SphereSphere Sweep Test
Figure 2 shows two spheres that collided between frames. If these spheres experienced acceleration during the frame, their trajectories will be second or higher order curves; however, usually their paths can be accurately approximated as linear segments according to the equations
Since both spheres traveled for the same amount of time, u is the same for both trajectories. The square of the distance between the lines is
and to calculate when they first make contact, we must solve for u such that
This leads to the quadratic equation
The vector v_{ba} can be thought of as the displacement of B observed by A. This equation is quadratic in u, so there may be no solution (the spheres never collided), one solution (they just glanced each other), or two solutions (in which case the lesser solution is when they began to overlap and the greater is when they became disjoint again). Again, it is a good idea to check for overlap at the beginning of the frame, since this will handle the case of two stationary spheres. Listing 2 shows an implementation of the spheresphere sweep test.
Listing 2. The spheresphere sweep test.
#include "vector.h"
template< class T >
inline
void SWAP( T& a, T& b )
//swap the values of a and b
{
const T temp = a;
a = b;
b = temp;
}
// Return
true if r1 and r2 are real
inline bool
QuadraticFormula
(
const SCALAR
a,
const SCALAR
b,
const SCALAR
c,
SCALAR&
r1, //first
SCALAR&
r2 //and second roots
)
{
const SCALAR q = b*b  4*a*c;
if( q >= 0 ){
const SCALAR sq = sqrt(q);
const SCALAR d = 1 / (2*a);
r1 = ( b + sq ) * d;
r2 = ( b  sq ) * d;
return true;//real roots}
else
{
return false;//complex roots
}
}
const
bool SphereSphereSweep
(
const SCALAR ra, //radius
of sphere A
const VECTOR& A0, //previous
position of sphere A
const VECTOR& A1, //current
position of sphere A
const SCALAR rb, //radius
of sphere B
const VECTOR& B0, //previous
position of sphere B
const VECTOR& B1, //current
position of sphere B
SCALAR& u0, //normalized
time of first collision
SCALAR& u1 //normalized
time of second collision
)
{
const VECTOR va = A1  A0;
//vector from A0 to A1
const VECTOR vb = B1  B0;
//vector from B0 to B1
const VECTOR AB = B0  A0;
//vector from A0 to B0
const VECTOR vab = vb  va;
//relative velocity (in normalized time)
const SCALAR rab = ra + rb;
const SCALAR a = vab.dot(vab);
//u*u coefficient
const SCALAR b = 2*vab.dot(AB);
//u coefficient
const SCALAR c = AB.dot(AB)  rab*rab;
//constant term
//check if they're currently overlapping
if( AB.dot(AB) <= rab*rab ){
u0 = 0;
u1 = 0;
return true;}
//check if they hit each other
// during the frame
if( QuadraticFormula( a, b, c, u0, u1 ) )
{
if( u0 > u1 )
SWAP( u0, u1 );
return true;}
return false;
}
An AxisAligned Bounding Box (AABB) Sweep Test
Just like the name says, the faces of an axisaligned bounding box are aligned with the coordinate axes of its parent frame (see Figure 3). In most cases AABBs can fit an object more tightly than a sphere, and their overlap test is extremely fast.
To see if A and B overlap, a separating axis test is used along the x, y, and zaxes. If the two boxes are disjoint, then at least one of these will form a separating axis. Figure 4 illustrates an overlap test in one dimension.
In this example the xaxis forms a separating axis because
Note that the separating axis test will return true even if one box fully contains the other. A more general separating axis test is given in the section below on oriented bounding boxes (OBB’s). Listing 3 defines an AABB class that implements this overlap test.
Listing 3. An AABB class.
#include "vector.h"
// An axisaligned bounding box
class
AABB
{
public:
VECTOR P; //position
VECTOR E; //x,y,z extents
AABB( const VECTOR& p,
const VECTOR& e ): P(p), E(e){}
//returns
true if this is overlapping b
const bool
overlaps( const AABB& b ) const
{
const VECTOR T = b.P  P;//vector from A to B
return fabs(T.x) <= (E.x + b.E.x)
&&
fabs(T.y) <= (E.y + b.E.y)
&&
fabs(T.z) <= (E.z + b.E.z);
}
//NOTE:
since the vector indexing operator is not const,
//we must cast
away the const of the this pointer in the
//following
min() and max() functions
//min x,
y, or z
const SCALAR min( long i ) const
{
return ((AABB*)this)>P[i]  ((AABB*)this)>E[i];
}
//max
x, y, or z
const SCALAR
max( long i ) const
{
return ((AABB*)this)>P[i] + ((AABB*)this)>E[i];
}
};
For more information on AABBs and their applications, please see [8].
Just like spheres, AABBs can be swept to find the first and last occurrence of overlap. In Figure 5(a), A and B experienced displacements v_{a} and v_{b}, respectively, while Figure 5(b) shows B's displacement as observed by A.
Figure 6 shows B's displacement as observed by A.
In this example, the normalized times it took for the xextents and yextents to overlap are given by
and it can be seen that the xextents will cross before the yextents. The two boxes cannot overlap until all the extents are overlapping, and the boxes will cease to overlap when any one of these extents becomes disjoint. If u_{0,x}, u_{0,y}, and u_{0,z} were the times at which the x, y, and zextents began to overlap, then the earliest time at which the boxes could have begun to overlap was
Likewise, if u_{1,x}, u_{1,y}, and u_{1,z} are the times at which the x, y, and zextents become disjoint, then the earliest time at which the boxes could have become disjoint was
In order for the two boxes to have overlapped during their displacement, the condition
must have been met. Just like in the sphere sweep test, the positions of first and last overlap can be linearly interpolated with u. Listing 4 gives an implementation of this AABB sweep algorithm.
Listing 4. An AABB sweep algorithm.
#include "aabb.h"
//Sweep
two AABB's to see if and when they first
//and last
were overlapping
const
bool AABBSweep
(
const VECTOR& Ea, //extents of AABB A
const VECTOR& A0, //its previous position
const VECTOR& A1, //its current position
const VECTOR& Eb, //extents of AABB B
const VECTOR& B0, //its previous position
const VECTOR& B1, //its current position
SCALAR& u0, //normalized time of first collision
SCALAR& u1 //normalized time of second collision
)
{
const AABB A( A0, Ea );//previous state of AABB A
const AABB B( B0, Eb );//previous state of AABB B
const VECTOR va = A1  A0;//displacement of A
const VECTOR vb = B1  B0;//displacement of B
//the problem is solved in A's frame of reference
VECTOR v = vb  va;
//relative velocity (in normalized time)VECTOR u_0(0,0,0);
//first times of overlap along each axisVECTOR u_1(1,1,1);
//last times of overlap along each axis//check if they were overlapping
// on the previous frame
if( A.overlaps(B) )
{
u0 = u1 = 0;
return true;}
//find the possible first and last times
//of overlap along each axis
for( long i=0 ; i<3 ; i++ )
{
if( A.max(i)<B.min(i) && v[i]<0 )
{
u_0[i] = (A.max(i)  B.min(i)) / v[i];}
else if( B.max(i)<A.min(i) && v[i]>0 )
{
u_0[i] = (A.min(i)  B.max(i)) / v[i];}
if( B.max(i)>A.min(i) && v[i]<0 )
{
u_1[i] = (A.min(i)  B.max(i)) / v[i];}
else if( A.max(i)>B.min(i) && v[i]>0 )
{
u_1[i] = (A.max(i)  B.min(i)) / v[i];}
}
//possible first time of overlap
u0 = MAX( u_0.x, MAX(u_0.y, u_0.z) );//possible last time of overlap
u1 = MIN( u_1.x, MIN(u_1.y, u_1.z) );//they could have only collided if
//the first time of overlap occurred
//before the last time of overlap
return u0 <= u1;
}
A BoxSphere Intersection Test
A very elegant boxsphere intersection test is described in [1]. Figure 7 shows two configurations of a sphere and a box in 2D. Sphere A is closest to an edge, whereas sphere B is closest to a corner. The algorithm calculates the square of the distance from the box to the sphere by analyzing the orientation of the sphere relative to the box in a single loop.
If the box is not axis aligned, simply transform the center of the sphere to the box's local coordinate frame. Listing 5 gives an implementation of Arvo's algorithm.
Listing 5. Arvo's algorithm.
#include "aabb.h"
//Check
to see if the sphere overlaps the AABB
const bool
AABBOverlapsSphere (
const AABB& B,
const SCALAR r,
VECTOR& C
)
{
float s, d = 0;
//find the square of the distance
//from the sphere to the box
for( long i=0 ; i<3 ; i++ )
{
if( C[i] < B.min(i) )
{
s = C[i]  B.min(i);
d += s*s;}
else if( C[i] > B.max(i) )
{
s = C[i]  B.max(i);
d += s*s;}
}
return d <= r*r;
}
An Oriented Bounding Box (OBB) Intersection Test
A drawback of using an axisaligned bounding box is that it can’t fit rotating geometry very tightly.
On the other hand, an oriented bounding box can be rotated with the objects, fitting the geometry with less volume than an AABB. This requires that the orientation of the box must also be specified. Figure 8 shows a 2D example, where A^{1}, A^{2}, B^{1} and B^{2} are the local axes of boxes A and B.
For OBBs, the separating axis test must be generalized to three dimensions. A box's scalar projection onto a unit vector L creates an interval along the axis defined by L.
The radius of the projection of box A onto L is
The same is true for B, and L forms a separating axis if
Note that L does not have to be a unit vector for this test to work. The boxes A and B are disjoint if none of the 6 principal axes and their 9 cross products form a separating axis. These tests are greatly simplified if T and B’s basis vectors (B^{1}, B^{2}, B^{3}) are transformed into A’s coordinate frame.
An OBB class and an implementation of the OBB overlap test is given in Listing 6 below.
Listing 6. An OBB class. #include "coordinate_frame.h"
class
OBB : public COORD_FRAME public:
};
//check
if two oriented bounding boxes overlap
) {
