Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Pool Hall Lessons: Fast, Accurate Collision Detection Between Circles or Spheres
View All     RSS
June 16, 2021
arrowPress Releases
June 16, 2021
Games Press
View All     RSS







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Pool Hall Lessons: Fast, Accurate Collision Detection Between Circles or Spheres


January 18, 2002 Article Start Previous Page 2 of 3 Next
 

An Algorithm That Works

The first step to the right solution is to quickly determine that there can be no collision and avoid doing any more tests. So first we figure out if A is going far enough that it could conceivably hit B. That means that the movement vector must be at least as long as the shortest distance between the circles, which would be a straight line passing through their centers. So the movement vector must be at least the distance between the centers of the circles minus the radius of each. If it is not, then there is no way that the circles will collide. Note that this test does not take direction into account! Thus it does not tell us that A and B will collide; it tells us that they won't. See Figure 5 for an illustration.


Figure 5: The shortest length the movement vector can be for A and B to collide

Our next early escape test is to determine if A is actually moving towards B. If it's not, then obviously you don't have to worry about them colliding. To do this, we take advantage of our friend, the Dot Product. First, find C, the vector from the center of A to the center of B. Remember that a point minus a point is a vector, so C = B - A. Now get the dot product of C and the movement vector, V: if the result is less than or equal to 0, then A is not moving towards B, and no more testing needs to be done.

One more escape test: If the closest that A ever gets to B is more than the sum of their radii, then they do not hit. Dot product to the rescue again! If theta is the angle between any two vectors P and Q, then the dot product between P and Q is equivalent to:

In other words, the dot product of two vectors P and Q is equal to the cosine of the angle between them times the length of P and the length of Q.

Also recall that the cosine of an angle is equal to the side of a right triangle adjacent to that angle, divided by the hypotenuse of that same triangle. Therefore, the dot product of a vector P and a normalized (ie: has a length of 1) vector Q is equal to the length of P times the cosine between the two vectors. Which, in turn, is equal to the length of the vector P in the direction of the normalized vector Q. This is shown in Figure 6.


Figure 6


With this in mind, lets go back to the problem at hand. We have our movement vector V, and our vector from the center of circle A to the center of circle B, called vector C. We want to find the point on V that is closest to the center of B. Intuitively, if we were to draw a line from this point to the center of B, it would be at right angles to V. Therefore, we can use the dot product as described above to find the distance from the center of A to that point. Compute the normalized V (call it N) and then take the dot product of N and C. The result will be the floating point number D, the distance between the center of A and the closest point on V to B. See Figure 7 for a visual reference.

Figure 7: Calculating the closest point on V to B


The length of C and D are the lengths of two sides of a right triangle. Thus, we can use the Pythagorean Theorem (a^2 + b^2 = c^2) to find the length of the third side, represented in green in figure 7. Square the length of C, and subtract the square of D from it, and call the result F.
Now, to be accurate, the square root of F is the length from the center of B to the closest point to B on V. However, performing square roots take a lot of processor time. So we will perform our early escape test without taking the square root of F. What we need to know is, as stated before, do A and B touch when A is at the closest point to B along V? In other words, is sqrt(F) <= A.radius + B.radius? But rather than take the square root of F, check F <= (A.radius + B.radius)^2. If this comparison is false, then there is no collision and you can escape the routine.

At this point we've exhausted our early escape tests, and there is still a chance that the two circles will collide.

Figure 8 gives a visual explanation of the steps about to be described. The distance circle A can move before colliding with B is right up until it is just touching the edge of circle B. At that point, the distance between the centers of the circles is equal to the sum of the radii. Since we already know the shortest distance from V to the center of B, aka sqrt(F), we have the lengths of two sides of a right triangle. The third side is equal to D - distance A can travel before it hits B. So again we can use the Pythagorean theorem, and find the length T = (A.radius + B.radius)^2 - F. The distance A has to move along V to come into contact with B is D - sqrt(T).

Figure 8: Finding the farthest that A can go

One final check is needed. Remember when we tested the shortest distance between A and B, but it did not take into account direction? Here's where that can come back and bite us. Consider the situation illustrated in figure 9. Both arrows are the same length, but in slightly different directions. This shows that yes, the movement vector is long enough to bring the two circles close enough to touch, but the direction is such that they won't. So at this point in the algorithm we need to do a reality check: if Distance is greater than the length of V, then there is no collision.

Figure 9

If the final test is passed, we can normalize V and then multiply it by D - sqrt(T). Now Circle A will move until it is just touching circle B. The Java code implementing this algorithm is listed below.

 

// Early Escape test: if the length of the movevec is less
// than distance between the centers of these circles minus
// their radii, there's no way they can hit.
double dist = B.center.distance(A.center);
double sumRadii = (B.radius + A.radius);
dist -= sumRadii;
if(movevec.Magnitude() < dist){
  return false;
}

// Normalize the movevec
Vector N = movevec.copy();
N.normalize();

// Find C, the vector from the center of the moving
// circle A to the center of B
Vector C = B.center.minus(A.center);

// D = N . C = ||C|| * cos(angle between N and C)
double D = N.dot(C);

// Another early escape: Make sure that A is moving
// towards B! If the dot product between the movevec and
// B.center - A.center is less that or equal to 0,
// A isn't isn't moving towards B
if(D <= 0){
  return false;
}

// Find the length of the vector C
double lengthC = C.Magnitude();

double F = (lengthC * lengthC) - (D * D);

// Escape test: if the closest that A will get to B
// is more than the sum of their radii, there's no
// way they are going collide
double sumRadiiSquared = sumRadii * sumRadii;
if(F >= sumRadiiSquared){
  return false;
}

// We now have F and sumRadii, two sides of a right triangle.
// Use these to find the third side, sqrt(T)
double T = sumRadiiSquared - F;

// If there is no such right triangle with sides length of
// sumRadii and sqrt(f), T will probably be less than 0.
// Better to check now than perform a square root of a
// negative number.
if(T < 0){
  return false;
}

// Therefore the distance the circle has to travel along
// movevec is D - sqrt(T)
double distance = D - sqrt(T);

// Get the magnitude of the movement vector
double mag = movevec.Magnitude();

// Finally, make sure that the distance A has to move
// to touch B is not greater than the magnitude of the
// movement vector.
if(mag < distance){
  return false;
}

// Set the length of the movevec so that the circles will just
// touch
movevec.normalize();
movevec.times(distance);

return true;

Bank Shot: Collision between two moving circles

This problem seems even more complicated than the previous one. Given two moving circles, determine whether or not they collide. Looking at the problem in figure 10, we can see that just because their paths cross does not mean that the circles will come into contact. One may have moved out of the way in time. It also shows that, just because their paths do not cross does not mean that they don't collide.

Figure 10: the Dynamic-Dynamic collision problem

Thankfully, the solution to a very hard problem could not be simpler. What we are really interested in is not their movement vectors, but their movement relative to each other. If we translate circle A's movement such that B can be considered stationary, we can use the Dynamic-Static solution described above!

First of all, subtract the movement vector of one circle from another (or, you can think of it as adding the reverse of one vector to another). Then perform the dynamic-static collision algorithm on the circles and the new vector. If they collide, divide the length of the shortened vector by the length of the one you originally passed into the function. The result should be a floating-point number between 0 and 1. This represents when over the course of their movement the circles collided. Multiply the original movement vectors by this number, and the result is shortened movement vectors that take the circles up to the point where they touch for the first time.

Jumping the Cue ball: Applying these algorithms to 3D

Detecting proximity between two stationary spheres
The application of this algorithm to 3D environments couldn't be easier. Circles in 2D and spheres in 3D are both defined the same way mathematically: Given a center point, the boundaries of both circles and spheres are defined as all points that are a given distance (the radius) from the center point. So spheres can be mathematically specified in the same way as circles with a center point and a radius. There is one caveat for the 3D representation. The center point in 3D uses a third coordinate, z. So the distance between the centers of the two spheres can be found by:

If that distance is less than the sum of the radii of the two spheres, then they are in contact with each other.

Collision of a moving sphere with a stationary sphere

The Dynamic-Static collision algorithm works in 3D because the 3D scenario can be reduced to 2D. If you look at our solution for this problem in 2D, you'll notice that it is based around two vectors (V and C) and a common point (the center of A). These two vectors define the orientation of the plane in 3D, and the point provides a reference to where in space that plane lies. Figures 11 and 12 show two spheres, the red one in motion and the blue one at rest. These figures also show the movement vector of the red one and the vector between the centers of the spheres. Notice the 2D plane that is passing through the objects in the scene in both figures. This plane cuts right down the middle of the two spheres and along the two vectors, clearly showing that these vectors are coplanar. Also notice that the plane cuts the spheres perfectly in half, so that the areas of contact between the spheres and the plane are circles with the same center and radius as the spheres. All of the information needed to use the dynamic-static algorithm we described above is projected into a 2D space on the light blue plane.

There is a special case to be considered, although its resolution is trivial. If the vectors V and C lie along the same line, then there are an infinite number of planes in which the problem can be solved. This case should be checked for. Of course, if V and C are co-linear, that means that sphere A is moving directly towards sphere B, and the question of whether they collide reduces to only our first early escape test. Namely, "does A move far enough to hit B?", or in other words, "Is V greater than (C - sumRadii)?"

There are no changes needed to the code above in order for it to work in the 3D case. The changes that need to be done are in the classes that are assumed by the above code. For example, instead of the Vector class having only x and y member variables, it should be changed to include a third member variable, z.

Figure 11: Dynamic-Static Collision in 3D



Figure 12: The Dynamic-Static Collision, projected in 2D

Collision between two moving spheres

Again, by translation of the problem to one sphere's frame of reference, this problem is reduced to the Dynamic-Static 3D problem, which in turn scales down to the 2D case, as described above. Figure 13 shows two spheres, each with it's own movement vector, shown in green. The orange vector is opposite of B's movement vector, and the yellow movement vector from A (the red ball) is the movement of A as observed from B's point of reference. The 2D plane containing the yellow vector also contains the center of sphere B, and so it can be used to solve the problem.

Figure 13: Collision of two moving spheres in 3D, and how it can be reduced to one moving circle in 2D



Article Start Previous Page 2 of 3 Next

Related Jobs

SideFX
SideFX — Toronto, Ontario, Canada
[06.15.21]

3D Software Developer: Game Tools and Pipeline
Square Enix Co., Ltd.
Square Enix Co., Ltd. — Tokyo, Japan
[06.15.21]

Experienced Game Developer
Genvid Technologies
Genvid Technologies — CA/WA/NY, California, United States
[06.15.21]

Team Lead (Partner Services)
Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States
[06.14.21]

Audio Programmer





Loading Comments

loader image