Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
0Likes
Dislike

Simple Bounding-Sphere Collision Detection

By Oleg Dopertchouk | Published Nov 12 2000 01:21 PM in Math and Physics

float relpos return collision code spheres snippet time
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

Introduction

Collision detection is an important part of most 3D games. Shooting enemies, avoiding (or failing to avoid) obstacles, even simply staying on the ground usually requires some form of collision-detection. It's a vast subject and there are many excellent articles written about it. However, most of them concern the more sophisticated algorithms, such as BSP and the simple bounding-sphere check receives no more than a passing mention. It is a quite simple procedure but it still could be very useful and there are a couple of subtle points involved. So I thought perhaps I should write something about it.


Straightforward version

The simplest possible way to do bounding-sphere test is to measure the (squared) distance between the two objects in question and to compare the result with the (squared again) sum of their radii. The reason we use the squared distances is to avoid the costly square-root calculation. The code will look something like this:

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}

Code Snippet 1

Note: This and the following code snippets use the D3DVECTOR type from Microsoft's Direct3D, if you are using some other 3D library, change the code accordingly.

This procedure is easy indeed and some cases may be even adequate but what if your objects are moving at a considerable speed? Then it could happen that at the beginning of a frame the bounding spheres do not intersect yet by the end of the frame they have passed through each other. If the distance your objects travel in one frame is greater than the size of the object this scenario is quite likely. Clearly we need something more advanced to handle this case.


Improved version

What we need is to somehow incorporate the object velocities into the calculation. That is quite simple if you do just a little bit of vector math (you can skip this section if you have a math phobia).

Let Attached Image: article_gr_1.gif and Attached Image: article_gr_2.gif be the positions of the objects at the time Attached Image: article_gr_3.gif .We'll take Attached Image: article_gr_4.gif at the beginning of the frame and Attached Image: article_gr_5.gif at the end of the frame. Also let Attached Image: article_gr_6.gif and Attached Image: article_gr_7.gif be the velocities of the objects. Then

Attached Image: article_gr_8.gif

Equation 1

and their relative position will be

Attached Image: article_gr_9.gif

The distance between the objects will be just the magnitude of the relative-position vector or, which is the same thing, the square of the distance will be equal to the square of the vector:

Attached Image: article_gr_10.gif

Note: I use * to denote the dot product between two vectors.

Now all we need is to find if Attached Image: article_gr_11.gif ever gets less than the minimal allowed distance Attached Image: article_gr_12.gif (i.e the sum of the radii of the bodies) during the next frame, that is betweenAttached Image: article_gr_13.gif and Attached Image: article_gr_14.gif .

The way to do it is to check if the distance already less than the minimal (we might have somehow missed the collision on the previous frame, because of physics and AI corrections or whatever) and if not then we need to solve the equation Attached Image: article_gr_15.gif . This will be the moment Attached Image: article_gr_3.gif when the objects are exactly at the distance Attached Image: article_gr_12.gif . Generally there will be two such cases- corresponding to the moments when the bounding spheres touch for the first time and when they touch for the last time after passing through each other. You will probably be more interested in the former, that is the least of the two values. If we write everything out we get:

Attached Image: article_gr_18.gif

I have omitted [0] to make the formula more readable.

This is a simple quadratic equation and we solve it in the usual way, by finding the determinant:

Attached Image: article_gr_19.gif

Equation 2


If D<0 then the equation does not have a solution, that is the spheres do not collide at all. If D>0 then the spheres collide (if D=0 then the spheres merely touch each other, you can handle this case either way, depending on the specifics of the situation). The roots of the equation are:

Attached Image: article_gr_20.gif

Attached Image: article_gr_21.gif

Equation 3

Then we can take Attached Image: article_gr_22.gif , test if it is between 0 and 1 and if it is then we have the collision. It's straighforward enough but we can take a few shortcuts for the sake of optimisation. First of all, and this is just an arithmetic manipulation, we can cancel the 2's:

Attached Image: article_gr_23.gif

Second, and more important we can test if the roots are between 0 and 1 even before calculating Attached Image: article_gr_22.gif , in fact even before calculating D. To see how, note that

Attached Image: article_gr_25.gif

Equation 4

This is a case of what is called Viete's theorem. Let's look closer at this, specifically let's look at the signs of these values. If Attached Image: article_gr_26.gif then we can say for sure that Attached Image: article_gr_27.gif and Attached Image: article_gr_28.gif . In that case the collision is already in progress - the spheres are intersecting each other right at the beginning. If Attached Image: article_gr_29.gif but Attached Image: article_gr_30.gif then both Attached Image: article_gr_31.gif and Attached Image: article_gr_32.gif and that is another easy case - the spheres are flying away from each other and no collision is going to happen.

To make these cases even easier note that the denominators in both cases are greater than 0 - just like the square of any real number. (if they are equal to 0 then the relative speed of the spheres is 0, not moving at all. Then everything is just like in the previous section). Therefore the signs of these expressions are the same as the signs of their numerators. The numerator of the second expression is just the square of the distance between the spheres at t=0 minus the Attached Image: article_gr_33.gif - the square of the minimal allowed distance. That is exactly what we have calculated in the code snippet 1. So we are going to reuse that code in our new and improved version! Calculating Attached Image: article_gr_34.gif will be our next step, we'll need that value later anyway.

Ok, so we can find the cases where solution is <0 that is when the collision has already happened. Now we need also to weed out the cases when the solution is >1. That is the collision might happen but not within the next frame, so we are not interested. (if you are interested in these situations as well just skip this check). To find out we just write the condition out:

Attached Image: article_gr_35.gif

Or, after some algebraic manipulations, we arrive at these 2 conditions

Attached Image: article_gr_36.gif

Attached Image: article_gr_37.gif

If these two inequalities hold true then Attached Image: article_gr_38.gif and we know there is no collision withing the next frame.

Now, If we passed all the tests then we have no choice but to calculate D and see if it is >0. If you wish to know the exact time (or position) of the collision then you can go on and calculate its square root, find Attached Image: article_gr_39.gif and so forth. In my code I'll skip those steps for simplicity.

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  // 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;

  //Discriminant/4
  float D	= pv * pv - pp * vv; 
  return ( D > 0 );
}

Code Snippet 2


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.





Comments
Am I crazy or should the last line be this?


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

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS