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;
}
Dave Moss 
20 Mar 2012 at 11:23 am PST

The scaler u0 and u1 represent the time the objects will collide...


