Contents  Straightforward  Version  Improved Version  One More  Improvement  Printable version

One more improvement

The code in snippet 2 works quite well in many circumstances but there's a little problem with it. It is not a mathematical problem but a computer-related one. Think about the very last calculation

float D    = pv * pv - pp * vv;

Say the distance between the objects is about 100 units and the objects themselves move about 100 units per frame (this is just an order-of-magnitude estimation, so the exact values are not important). Then pv, vv and pp are generally all about numbers around 100*100=10000. Then their products are about 10000*10000=100000000! And we subtract these values. What happens is a fantastic loss of precision amd the result of the computation can off by miles. What's worse the sign can turn out completely wrong as well, so we may flag non-existant collisions or even dismiss perfectly legitimate ones. Your bullets might fly right through your enemy's head and and his ones might hit even though you have ducked at the last moment. Not good. We need something to tame the numbers in our calculations. What you can do is to divide the formula above by vv, that will bring down the numbers to a more manageable size. Since by that time we know vv is greater than 0 (if it is 0 then so will be pv and our check 2 will fail) so the sign will be unaffected. We do have to spend more cycles on the division but it happens only if all other tests have failed. Here's the final version of the collision test that does calculate the time.

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2)
{
  //Initialize the return value
  *t = 0.0f;

  // Relative velocity
  D3DVECTOR    dv    = obj2->prVelocity - obj1->prVelocity;
  // Relative position
  D3DVECTOR    dp    = obj2->prPosition - obj1->prPosition;
  //Minimal distance squared
  float r = obj1->fRadius + obj2->fRadius;
  //dP^2-r^2
  float pp = dp.x * dp.x + dp.y * dp.y + dp.z * dp.z - r*r;
  //(1)Check if the spheres are already intersecting
  if ( pp < 0 ) return true;

  //dP*dV
  float pv    = dp.x * dv.x + dp.y * dv.y + dp.z * dv.z;
  //(2)Check if the spheres are moving away from each other
  if ( pv >= 0 ) return false;

  //dV^2
  float vv = dv.x * dv.x + dv.y * dv.y + dv.z * dv.z;
  //(3)Check if the spheres can intersect within 1 frame
  if ( (pv + vv) <= 0 && (vv + 2 * pv + pp) >= 0 ) return false;

  //tmin = -dP*dV/dV*2 
  //the time when the distance between the spheres is minimal
  float tmin = -pv/vv;

  //Discriminant/(4*dV^2) = -(dp^2-r^2+dP*dV*tmin)
  return ( pp + pv * tmin > 0 );
}

Code Snippet 3

Conclusion

So here it is, the bounding-sphere collision detection algorithm. It might be useful as is (say, for a pool game) or can be a quick-and-dirty test before doing a more sophisticated check - polygon-level, for instance. You may also want to try to improve the accuracy of the collision detection by using a hierarchy of bounding spheres, breaking your object into several parts and enclosing each of them in a bounding sphere of its own.