|
 Features
Pool
Hall Lessons:
Fast, Accurate Collision Detection between Circles or Spheres
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.
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.
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.
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).
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.
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.
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.
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.
______________________________________________________
|
|
|
|
|
