 |
|
|
| Home Products Screenshots Company
2D Collision Detection Development Part I: Introduction and Frustrations When we first began working on our Abound screensaver, we knew we needed to be able to accurately and quickly detect collisions between two different types of objects in two-dimensions (2D):
All we wanted to do was determine whether our balls moving around the screen were colliding either with other moving balls, stationary balls, or the walls surrounding the screen. We found nothing suitable for this simple situation, so we decided to write the functions ourselves. Now, it does not sound very hard to write this type of library, but in practice it took us a tremendous amount of development time to create it, debug it, and finally get it working serviceably. In retrospect, we should have tried to make one of the existing libraries work for us, and saved time. We are going to explain in depth how we came up with the algorithms and implemented them to solve these problems. Hopefully you can then use the code we offer for download in your own programs, and modify it as needed for your specific application. We will assume here that you have already created a Ball and Wall class which can have objects instantiated from them. The Ball class needs to have the ability to move the ball based on its current position, velocity, and acceleration, using the Newtonian motion equations. If you don't know how to do this, it is an excellent exercise which will help you understand this article more, so we will give you the opportunity to figure it out on your own. Part II: Ball to Wall Collisions The first collision detection we did was for balls hitting walls:  Ball moves toward wall and should collide with it We need to have the collision
detection function take as parameters the ball and wall objects, and
give us back the following information:
Ball movement dynamics What is the nature of this collision? Since the ball moves in parabolic motion (due to gravitational acceleration in the -y direction), it is actually a parabola-to-line segment collision. Eek! How do you determine a collision between part of a parabola and a line segment? For us, the answer was, "We have no idea". However, we had a book that told us how to do line segment to line segment collisions, so could we use that? In other words, can we approximate parabola to line segment with line segment to line segment?  The true collision point is the parabolic one, but the line segment is close What we see in the above diagram
is the trajectory of the ball following its true parabolic motion
versus the straight line path from its current position to the position
after some time duration. The collision points for these two
cases are slightly different, as you can see, and it is important to
realize that these points could be
even further apart depending on the position, velocity, and
acceleration of the ball.
An idea occurred to us: To determine a collision, we could first move the ball forward for the default time step, which moves it along its parabolic trajectory, then obtain the line segment from its initial position to the new position, and use that line segment and the wall's line segment to see if a collision even exists. Then, if a collision does exist, we can use the fact that we know with certainity the y position of the wall, and solve the parabolic (quadratic) equation of when the ball will intersect that y position! Finding the collision point The details will help you understand what we mean here. The equation for the ball's position at a given time t is: x(t)
= 1/2 * Accelx * t^2 + Velx
* t + x
where: x(t) = the ball's new position at time t Accelx = current acceleration in the x direction Velx = current velocity in the x direction x = current position in the x axis t = time step This gives the position in the x axis at time t, and for the y position, it's similar: y(t) = 1/2 * Accely * t^2 + Vely
* t + y
The t^2 (t-squared) term makes the
equation a quadratic or parabolic one. Acceleration in the x is
zero for Abound unless there are black holes. For now we say
there are none. Acceleration in the y direction is from the force
of gravity and is in the negative (downward) direction.
We now have the current position, velocity, and acceleration of the ball in both the x and y directions, so we store these, move the ball forward one time step, recalculate the position and velocity since they will change (acceleration is constant), and then make a line segment out of the first (x,y) point and the second one. Just in case you are wondering, the equations for velocity are well known: Velx(t) = Accelx * t + Velx Vely(t) = Accely * t + Vely To solve for an interesection of
these line segments, we use parametric equations. To make the
math easier, we define the first and second ball position as
(pt0x,pt0y) and (pt1x,pt1y), and the two wall endpoints as (pt2x,pt2y)
and
(pt3x,pt3y). Now define values S1x, S1y, S2x, S2y which are the
vectors to these points. We make these like so:
S1x = pt1x - pt0x; S1y = pt1y - pt0y; S2x = pt3x - pt2x; S2y = pt3y - pt2y; Now the equation for whether these overlap is this: double s, t; s = (-S1y*(pt0x-pt2x) + S1x*(pt0y-pt2y)) / (-S2x*S1y + S1x*S2y); t = ( S2x*(pt0y-pt2y) - S2y*(pt0x-pt2x)) / (-S2x*S1y + S1x*S2y); if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { // Collision detected, find collision point double Ux, Uy; Ux = pt0x + t*S1x; Uy = pt0y + t*S1y; ... } Alright, now we are getting somewhere. This gives us the collision point. Note that we are using the center point of the ball (circle) for the position. So we have actually found the collision between the wall and the center point of the ball.  The collision point is found for the center of the ball to the wall Okay, so now that we know we have
a collision, let's find the true collision point by following the
parabolic trajectory of the ball and solving for when it hits the
wall. Since the equation for the ball's y position is determined
by 2nd degree polynomial equation, we can use the y position of the
wall as the value to solve y(t) for, like so:
y(t) = Wall y position = 1/2 *
Accely * t^2 + Vely * t + y
Now move the Wall position to the
other side of the equation by subtracting it from both sides, and we
have a quadratic equation which we can solve for:
0 = 1/2 * Accely * t^2 + Vely *
t + (y - Wall y position)
We have the quadratic formula
to solve for t, because Accely is known (gravity), Vely and y are known
(members of the Ball object, its velocity in the y direction and
current y position), and so we use:
at^2 + bt + c = 0
t = (-b +/- sqrt(b^2 - 4ac)) / 2a so... t = (-Vely +/- sqrt(Vely^2 - 4*1/2*Accely*(y - Wall y position)) / 2*1/2*Accely t = (-Vely +/- sqrt(Vely^2 - 2*Accely*(y - Wall y position)) / Accely One of these t values will be
outside of our time range, which is [0, max time step]. Likely it
will be a negative value. The other value is the exact amount of
time we want to move the ball so that it collides with the wall.
So we plug this t value into our movement formulas to move the ball
forward. Once we move it this far, the center point of the ball
is the collision point. Later, we will see how to correct this so
that the ball collides with the wall at the right point on the
circumference of the ball.
 This is the true collision point after moving the ball forward the timestep we found Now we want to correct the
collision to be the exact point on the circumference of the ball that
first contacts the wall. How can we figure that out? Well,
we came up with this trick that keeps everything else the same and
makes it easy. Remember that (pt2x,pt2y) and (pt3x,pt3y) are the
two endpoints of the wall line segment. To account for the fact
that we are using the center point of the ball for the collision
calculations, let's move the wall upwards
toward the ball one ball radius distance, so that way when we find the
collision point, the ball will collide sooner with the wall, and the
collision will look exactly right on the screen.
 Move the wall upwards just for calculating the collision point. Just
before we begin the initial
calculations to detect for a collision, move the wall upward by adding
the ball's radius to pt2y and pt3y.
pt2y += (double)radius; pt3y += (double)radius; Note: For the top wall (the ceiling), you would subtract the radius instead of adding it to the y values, effectively moving the ball downward, and for the side walls, add and subtract to and from the x values of the walls. Calculating the balls' post-collision velocity Now we need to find the ball's
post-collision (or resultant) velocity after it hits the wall.
How do we accomplish this?
 What is the new velocity after the collision? To figure this out, we will use
the current (or initial) velocity vector and use some special
information we know about to find the resultant velocity vector.
Specifically, we know that the angle of reflection that the initial
vector makes with the wall's normal vector is equal to the angle of
incidence. Also, the length of the resultant velocity vector is
equal to the length of the incident vector.
 The important vectors for calculating resultant velocity Here's where a little vector math
comes in to save us from getting lost in a sea of angles and
quadrants. We can create the resultant velocity vector by
"projecting" the initial vector onto a vector perpindicular to the wall
normal, and then adding that new vector we get to the initial vector
two times. Examine this diagram to get a better idea of this:
 You can project a vector onto
another by doing the "dot product", and what you get the is component
of the first vector along the direction of the second vector. We
get the wall normal vector by findng a vector perpindicular to the wall
line segment itself. You can find the perpindicular of a vector
like so:
vector1:
<vx, vy>
normal to vector1: <-vy, vx> So put a minus sign in front of one of the terms and switch the x and y terms, and you have a perpindicular vector. Using this wall normal vector, we make it into a unit vector by dividing its x and y components by their length: unit
normal vector1:
<-vy,vx> / sqrt(vy^2 + vx^2)
We now have a unit
vector for the wall normal.unit normal vector1: <-vy / sqrt(vy^2 + vx^2), vx / sqrt(vy^2 + vx^2)> To find the projection vector of
the initial vector to the wall normal, we use this formula:
projection vector = (-I ·
n) * n
Where:
I = initial vector n = the unit wall normal vector The -I · n gives us the dot product of -I and n, which is a scalar value (just a number), that we then multiply to to n vector. This creates the projection vector which we will add to the initial vector twice to get the resultant vector. Here is the code, starting with finding the wall normal vector. Remember that the wall line segment vector was S2x and S2y: double nx, ny; nx = -S2y / ::sqrt(S2y*S2y + S2x*S2x); ny = S2x / ::sqrt(S2y*S2y + S2x*S2x); // npx and npy is the ball's initial velocity vector projected onto the normal // vix and viy are the initial velocity magnitudes in the x and y direction, and // vfx, vfy are the resultant velocity magnitudes. double npx, npy, vix, viy, vfx, vfy; double dotProd; // The minus (-) signs before vix an viy are from the -I in the above formula. // We are finding the projection vector first. dotProd = -vix*nx + -viy*ny; npx = dotProd*nx; npy = dotProd*ny; // We now have the projection vector, so add it twice to the initial vector to get // the resultant vector. vfx = 2*npx + vix; vfy = 2*npy + viy; Whew! This is confusing stuff, but it greatly simplifies finding the resultant velocity. We have now figured out all the quantities we needed to to write our ball to wall collision routine! We have found the collision point, time to the collision, and resultant velocity of the ball. Note that we have not subtracted anything for energy loss, friction, etc., which we leave up to the caller of the function to figure out. A simple way to approximate this energy loss from the collision is just to multiply the resultant velocity vector by some factor less than 1.0, like perhaps 0.9. That means each collision the ball would move only about 90% of its initial speed going into the collision. You can get more technically accurate with this if you like and use coefficients of restitution for objects, but the effect is the same. Part
III: Ball to Ball Collision Detection
Alright! Now let's tackle ball to ball collisions, which will be quite easy since we have already figured out ball to wall collisions. The concepts are the same. There are two main cases for ball to ball collision:
Ball to stationary ball collisions There are two main ways to figure out collisions, and we tried both in Abound:
I did not think that Abound could be solved outright with the mathematical method, but I was proven wrong by one of my friends. I won't go into detail on how to derive these equations, but if you are interested, think about this: You have a ball and stationary ball, and want to know if the ball will ever collide with the stationary ball, given the initial coordinates, velocity, and acceleration of the ball. Okay, so use the distance formula: d = sqrt(x^2 + y^2), and realize the distance you are looking for is the exact distance where a collision occurs between these balls, which is the sum of their radii, r1 + r2. Now, the x in the equation above is the difference between the two x coordinates of the balls, which for the stationary ball is always the same, but for the moving ball changes over time. The y value is similar. So you get this equation: r1 + r2 = sqrt( (x(t) -
xstationary)^2 + (y(t) - ystationary)^2)
Okay, so what are x(t) and
y(t)? They are the Newtonian motion equations we already
described in detail in the ball to wall collision explanation!
Substitute in those equations, square the crazy polynomials and
simplify, and you will be left with a 3rd degree polynomial with only
one variable: t. Then you can go on the internet (or contact us)
and find the equation to solve a 3rd degree polynomial. It's
complex but solved.
Why did we not go with this then? Two reasons:
 These two balls are at the collision point To find out whether the balls are
overlapping, all we have to do is take the two center points of the
balls, (x1, y1) and (x2, y2), and use the distance formula to find the
distance between them. If it is less than the sum of their radii,
r1 + r2, then the balls are overlapping and we have a collision.
If it is greater than the sum of their radii, we have no collision.
Okay, so assuming we have a collision, we have probably moved the ball too far and it is past the actual collision point. We need to find the collision point, and then as before with ball to wall collisions, find the resultant velocity of the ball. How do we find the collision point? Good question. I will describe the method we used, but I doubt it is the best. We had a lot of trouble with this part of the code, which shouldn't have been that difficult, or at least we didn't expect it to. May you have better luck with your implementation! If we detected a collision between the ball and stationary ball after moving the ball forward the full timestep, we would move the ball back to its original position and then move it forward half the full timestep forward. We then test for overlap. If there is no overlap, we realize we need to move it further forward because we pulled back too much, so then we move it half the distance forward again, or 75% of the original timestep. (You can see where this is going.) If we still don't have any overlap, we move it half the distance forward again, 87.5% of the original, etc. Now let's say that we move it forward and we find we are overlapping again. What then? In this case, we step back half the timestep that we just moved forward by. In this way we keep bisecting the timesteps until we get close to the collision point. Since we want to get very close to the exact collision point, we establish an epsilon or tolerance and if the distance between the balls is within +/- epsilon of the sum of their radii, then we say it's good enough and that is the timestep we use.  Full timestep is too far, so use binary movement algorithm to find exact point Okay, so let's say you use this
algorithm or even a different one and find the collision point.
Now how do you find the resultant velocity of the ball after the
collision? Here's the great thing: It's exactly the same as the ball to wall
collision resultant velocity formula, except we replace the normal
vector from the wall with the normal vector of the balls, which is just
the vector from one ball's center to the other ball's center! You obtain this vector by
taking the two center points of the balls and subtracting the x and y
coordinates of one ball from the others'. One other note: the
collision point to use is the center point of the moving ball, just as
before with ball to wall collisions the collision point we use in our
calculations is actually the center of the ball after moving the ball
to where it is just colliding.
Here's a snippet of code I use: // collision found, determine resultant velocity // collision point is the current location of moving ball, obj1 double pt1x, pt1y; result = obj1->GetPosition(&pt1x, &pt1y); assert(SUCCEEDED(result)); (*collisionPtx) = pt1x; (*collisionPty) = pt1y; double nx, ny; // Get vector from obj2's center to obj1's center nx = pt1x - pt2x; ny = pt1y - pt2y; // normalize this vector by dividing x and y component by length double nnx, nny; nnx = nx / ::sqrt(nx*nx + ny*ny); nny = ny / ::sqrt(nx*nx + ny*ny); result = CalcPostCollisionVel(obj1, nnx, nny, velx, vely); And just in case it helps, here is my CalcPostCollisionVel function, which my custom classes and interfaces being used (so you have to edit it for your code): HRESULT CCollisionExpert::CalcPostCollisionVel( ICollidableObject* obj1, double nx, double ny, double* velx, double* vely) { HRESULT result = S_OK; // npx and npy is the obj1 velocity vector projected onto the normal double npx, npy, vix, viy, vfx, vfy; IMobileObject* mobileObj = NULL; result = obj1->QueryInterface(IID_IMobileObject, (void**)&mobileObj); if (SUCCEEDED(result)) { result = mobileObj->GetVelocity(&vix, &viy); assert(SUCCEEDED(result)); double dotProd; // To find projection of incident (velocity) vector to normal, use // np = (-I . n) * n, where I is the velocity vector of obj1, // and n is the normal vector made up of nx and ny, found by // getting the vector from obj1's center to obj2's center dotProd = -vix*nx + -viy*ny; npx = dotProd*nx; npy = dotProd*ny; vfx = 2*npx + vix; vfy = 2*npy + viy; // Now validate that the length of the final velocity vector equals // the length of the initial velocity vector double viLength, vfLength; viLength = ::sqrt(vix*vix + viy*viy); vfLength = ::sqrt(vfx*vfx + vfy*vfy); double difference; if (vfLength >= viLength) { difference = vfLength - viLength; } else { difference = viLength - vfLength; } if (difference > s_CorrectVelocityEpsilon) { // wrong normal passed in, vectors not same length, retry with other normal. result = E_FAIL; } else { *velx = vfx; *vely = vfy; } mobileObj->Release(); } return result; } You've done it! Now we have the timestep required to move the ball to the collision point and the resultant velocity after the collision. Ball to ball collisions Guess what? The algorithm to test for moving ball to moving ball collisions is exactly the same as for moving ball to stationary ball collisions, except now you have to move both balls forward and backward by the current timestep when trying to see if you have a collision. Once you find an overlap, you can do the bisection technique as described above. However, to then determine the resultant velocity, you need to do just a little bit more. I will show the code and then explain the key parts: // collision found, determine resultant velocity // collision point is the current location of obj1 double pt1x, pt1y; result = obj1->GetPosition(&pt1x, &pt1y); assert(SUCCEEDED(result)); double pt2x, pt2y; result = obj2->GetPosition(&pt2x, &pt2y); assert(SUCCEEDED(result)); // Get vector from obj2's center to obj1's center nx = pt1x - pt2x; ny = pt1y - pt2y; (*collisionPtx) = pt1x; (*collisionPty) = pt1y; (*collisionPtx2) = pt2x; (*collisionPty2) = pt2y; double nnx, nny; nnx = nx / ::sqrt(nx*nx + ny*ny); nny = ny / ::sqrt(nx*nx + ny*ny); double* velx; double* vely; double* vex2x; double* vely2; result = CalcPostCollisionVelB2B(obj1, obj2, nnx, nny, velx, vely, velx2, vely2); And now the CalcPostCollisionVelB2B: HRESULT CCollisionExpert::CalcPostCollisionVelB2B( ICollidableObject* obj1, ICollidableObject* obj2, double nx, double ny, double* velx, double* vely, double* velx2, double* vely2) { HRESULT result = S_OK; // Calculate tangent vector, perpindicular to the normal double tx, ty; tx = -ny; ty = nx; // npx and npy is the obj1 velocity vector projected onto the normal double vix, viy, vin, vit, vfnmag, vftmag; double vix2, viy2, vin2, vit2, vfnmag2, vftmag2; IMobileObject* mobileObj = NULL; IMobileObject* mobileObj2 = NULL; result = obj1->QueryInterface(IID_IMobileObject, (void**)&mobileObj); assert(SUCCEEDED(result)); result = obj2->QueryInterface(IID_IMobileObject, (void**)&mobileObj2); assert(SUCCEEDED(result)); // get dot products of the initial velocities of both balls to the // normal and tangent unit vectors, which is the magnitudes of these // velocities in the n and t directions. result = mobileObj->GetVelocity(&vix, &viy); assert(SUCCEEDED(result)); vin = vix*nx + viy*ny; vit = vix*tx + viy*ty; // final velocity in t direction is equal to initial in t direction vftmag = vit; result = mobileObj2->GetVelocity(&vix2, &viy2); assert(SUCCEEDED(result)); vin2 = vix2*nx + viy2*ny; vit2 = vix2*tx + viy2*ty; // final velocity in t direction is equal to initial in t direction vftmag2 = vit2; // Calculate final velocities along the n, t directions // Note that in Abound, all balls have mass of 1.0 and // restitution coefficients of 1.0, just to make things simple. // To be more realistic, bigger balls should have greater mass. double m = 0.0, m2 = 0.0, rc = 0.0, rc2 = 0.0; result = obj1->GetMass(&m); assert(SUCCEEDED(result)); result = obj2->GetMass(&m2); assert(SUCCEEDED(result)); result = obj1->GetRestitutionCoef(&rc); assert(SUCCEEDED(result)); result = obj2->GetRestitutionCoef(&rc2); assert(SUCCEEDED(result)); // vfnmag is the magnitude of ball 1's final velocity in the n direction vfnmag = ((rc2+1.0)*m2*vin2+vin*(m-rc2*m2)) / (m+m2); // vfnmag2 is the magnitude of ball 2's final velocity in the n direction vfnmag2 = ((rc+1.0)*m*vin+vin2*(m-rc2*m2)) / (m+m2); // Find final velocities in x,y direction *velx = nx*vfnmag+tx*vftmag; *vely = ny*vfnmag+ty*vftmag; *velx2 = nx*vfnmag2+tx*vftmag2; *vely2 = ny*vfnmag2+ty*vftmag2; mobileObj2->Release(); mobileObj->Release(); return result; } What this code is doing is finding the velocity component of both balls in the n,t coordinate system, where n is the vector from one ball's center to the other's, and the t vector is perpindicular to the n vector:  Two moving balls colliding, first we find n,t coordinate system velocities Once we
have the initial velocity
of the balls in the n,t coordinate system, we get the mass and
restitution coefficients of the balls, then use some formulas I found
in a book to get the final velocities. The mass is important
because, due to the law of conservation of momentum, a ball with more
mass has more momentum (since momentum p = mass * velocity), and so is
affected less in a collision with a less massive object. The
restitution coefficient is how much "bounce" the ball has. A
coefficient of 1.0 is a perfectly elastic ball. I use this for
Abound because I simulate the "damping" or frictional force causing
loss of energy in a different way (just by reducing the velocity after
the collision manually).
Now then, we use some more formulas to translate the n,t final velocities back into our familiar x,y cartesian coordinate system. And we're done! If you are interested in how these formulas are derived, I suggest you study the code in depth and discern the vector equations from it, or check out Andre Lamothe's excellent book on game programming. That's it! You now have the ability to create the Abound screensaver! Wait a second. Why did I just tell you all this? :) Well, I want to share this knowledge and experience with you that you might be able to make cool programs more easily and have less headache than me! I hope this helps you in your programming! |
| 2004 Heroic Virtue Creations. All rights reserved. Contact us, Privacy Policy |