1[CODE] 2Calculating a ricochet turns out to be a lot trickier problem than it 3first appears. For those of us who are a decade or more away from our 4last practice with algebra and trigonometry it requires some patience 5and perseverance. 6 7First we're going to concentrate on the collision of two balls. Later 8we'll expand that to the collision of a ball against a wall. Our 9discussion will include mass and elasticity. At the end we'll discuss 10some of our ideas on how we might handle simultaneous collisions 11between multiple objects. 12 13First, two balls. 14 15There are six parts to the calculation, with a couple of subparts. 16 17 1) Gross collision detection 18 2) Calculate accurate positions at time of collision 19 3) Calculate the angle of collision vs the velocity vector 20 4) Calculate portion of velocity vector that applies to collision 21 5) Calculate final velocities along collision vector 22 6) Apply final velocities back to the object 23 24--------------------------------------------------------------------- 25 1) Gross collision detection. 26 27The purpose of this step is to determine in as few instructions as 28possible whether the objects are close enough together to warrant more 29expensive calculations. There are many ways to accomplish this. The 30one we chose was the simple bounding box (See figures 1a through 1c). 31 32The quickest way to find out if two bounding boxes overlap is to test 33to see if the bounding boxes DON'T overlap. It only takes four tests 34to show that box A is to the right of, left of, above, or below box B. 35 36// Use this macro in an if statement. Ex. 37// if (bounding_box_test(ibx, ibx1, iby, iby1, jbx, jbx1, jby, jby1)) 38// DoSomething(); 39// else 40// DoSomethingElse(); 41#define bounding_box_test(ibx, ibx1, iby, iby1, jbx, jbx1, jby, jby1) \ 42 (!((ibx > jbx1) || (ibx1 < jbx) || (iby > jby1) || (iby1 < jby))) 43 44You'll need to extend the bounding boxes to include both the beginning 45and ending positions of each object. Otherwise, the objects could 46become overlapped before you detect a collision. 47 48--------------------------------------------------------------------- 49 2) Calculate accurate positions at time of collision. 50 51The central trick for this step is the Quadratic equation. 52 53Let's take a moment to define our terms. (See figure 2a) 54 55 Stuff we know: 56 x1,y1 and x2,y2 - The initial positions of the centers of the two objects 57 dx1,dy1 and dx2,dy2 - The distances the objects moved this frame 58 r1, r2 - radii of the two objects 59 60 Stuff we calculate: 61 t - Time of collision 62 cx1,cy1 and cx2,cy2 - The centers at time of impact 63 64What we're trying to find is when the centers of the two objects are 65the same distance apart as the sum of their radii. The distance 66formula is sqrt([cx1-cx2]^2 + [cy1-cy2]^2). Therefore, we're looking 67for the time (t) when 68 (r1+r2)=sqrt([cx1-cx2]^2 + [cy1-cy2]^2). 69 70How do we know where will a ball be at any given time (t)? Here are 71functions which describe the paths of the centers of the balls over 72time: 73 74 cx1 = x1 + tdx1 cx2 = x2 + tdx2 75 cy1 = y1 + tdy1 cy2 = y2 + tdy2 76 77The t's relate all the forumlas to each other. Replacing the cx's and 78cy's in the distance forumla with these equations and we end up with: 79 80 r1+r2 = sqrt(((x2 + tdx2)-(x1 + tdx1))^2 + ((y2 + tdy2)-(y1 + tdy1))^2) 81 82Multiply everything out then rearrange and simplify and you end up 83with: 84 85 0 = [(dx2-dx1)^2 + (dy2-dy1)^2] t^2 86 + [2(x2-x1)(dx2-dx1) + 2(y2-y1)(dy2-dy1)] t 87 + [(x2-x1)^2 + (y2-y1)^2 - (r1+r2)^2] 88 89This is a polynomial in the form 0=ax^2+bx+c. We can use the Quadratic 90equation (-b(+|-)sqrt(b^2-4ac))/2a to solve for the variable. The a, b 91and c are all spelled out above. You could plug a, b and c into that 92monster equation, but it turns out you want to calculate it in pieces. 93 94The Quadratic equation will give two answers, call them t1 and t2. One 95for each the plus and minus of the square root portion. There are some 96special cases to check before solving the equation, and some special 97cases that result from the equation. (See figure 2, cases 1-6) 98 99 1) If a=0 the equation goes infinite. Notice that "a" consists of the 100 square of the difference between the direction vectors. 101 Therefore, a=0 if and only if the balls are moving the same 102 direction and the same speed. 103 104 2) If 4ac > b^2 then you end up trying to take the square root of a 105 negative number. In other words, there's no solution. It turns 106 out that this happens if and only if the balls never pass within 107 r1+r2 of each other. Even though the paths may cross, the balls 108 are far enough apart in time that they don't approach close 109 enough to each other to ever actually touch. 110 111 3) If both t's are negative then the balls are receding from each 112 other. 113 114 4) If one t is negative and the other t is positive then the balls 115 began the frame already overlapped. 116 117 5) If both t's are positive then the smaller of the two is when they 118 first reach r1+r2 from each other. 119 120 6) If both t's are greater than 1.0 then the balls do not collide 121 this frame. 122 123Condition 5 is the only valid collision and you continue with the rest 124of the calculations. 125 126Conditions 1, 2, 3 and 6 indicate that there is not a valid collision 127this frame and you therefore can abort before performing the rest of 128the calculations. In effect, you discard this pair of objects since a 129collision didn't take place. 130 131Ideally, condition 4 should not occur. Whether or not it does occur 132depends on whether or not you handle multiple collisions in one frame. 133If you don't test for condition 4 then the rest of the math works out 134that the balls will remain locked together "arm-in-arm" so to speak. 135 136--------------------------------------------------------------------- 137 3) Calculate the angle of collision vs the velocity vector 138 139In order to calculate the momentum transfer later on we need to perform 140the remainder of these steps on both objects. 141 142At first glance it appears that you simply take the angle between the 143paths of the balls. That doesn't work. Let's take the example of two 144balls headed in the same direction and one ball is catching up on the 145other. If their centers lie on the same line then it's a simple 1D 146collision. But if the center of one ball is offset a little to one 147side then the momentum transfer occurs at an angle even though the 148motion paths are parallel. (See figures 3a and 3b) 149 150What we need to find is the angle formed by the velocity vector and the 151line connecting the centers. We need this angle in order to calculate 152how much of the velocity vector to apply to the collision. In other 153words, if the balls hit head-on, as in figure 3a, then the entire 154velocity vector is applied to the collision. If the balls just nick 155each other, as in figure 3b, then less momentum is transfered between 156the balls. 157 158The mathmatical tool for this problem is the Law of Cosines. 159 a^2 = b^2 + c^2 - 2bc cos(A). 160As written, it's intended for finding the length of a side when an 161angle is known, but we can flip it around: 162 cos(A) = ( a^2 - b^2 - c^2 ) / (-2bc) 163 164 Thus the angle is: A = acos( ( a^2 - b^2 - c^2 ) / (-2bc) ) 165 166Note that we can't use "simple" trig since we're not guaranteed of 167having a right angle. (See figure 3c and 3d) This way you won't have 168to transform coords to some artificial origin. 169 170(-2bc) approaches 0 if and only if the radii of both objects approach 1710. That's a pretty obvious should-not-occur situation. 172 173--------------------------------------------------------------------- 174 4) Calculate portion of velocity vector that applies to collision 175 176Once we have angle A this part turns out to be trivial. The piece of 177the total velocity vector that points toward Ball 2 is: 178 vi=cos(A)*sqrt(dx1^2+dy1^2) 179 180One obvious optimization is to save and use cos(A) above, rather than 181find A only to immediately take its cos() again. 182 183--------------------------------------------------------------------- 184 5) Calculate final velocities along collision vector 185 186At this point we can treat the this as a 1D collision along the line 187connecting the centers. You can find the momentum transfer equations 188in most first-year college physics texts. 189 190 vf1=(((m1-m2)*vi1)+(((1.0+(e1*e2))*m2)*vi2))/(m1+m2); 191 vf2=((((1.0+(e1*e2))*m1)*vi1)+((m2-m1)*vi2))/(m1+m2); 192 193Where: vf1, vf2 - final velocities along collision vector 194 vi1, vi2 - initial velocities along collision vector 195 m1, m2 - mass of each ball 196 e1, e2 - elasticity of each ball 197 198--------------------------------------------------------------------- 199 6) Apply final velocities back to the object 200 201Now we need to subtract the off old velocity vector and add on the new 202one. That will leave us with an object that's moving at the new, 203adjusted speed after ricochet. 204 205 angle=atan2(dcy,dcx); // angle of the line connecting the centers 206 sina=sin(angle); cosa=cos(angle); 207 odx=cosa*vi; // subtract off old velocity vector 208 ody=sina*vi; 209 ndx=cosa*vf1; // add on new velocity vector 210 ndy=sina*vf1; 211 dx+=odx-ndx; // signs look reversed but are correct 212 dy+=ody-ndy; 213 214--------------------------------------------------------------------- 215 So, that's a ricochet 216 217So, that's how you ricochet two balls. Whew! It seems like a lot of 218work, but there's no magic involved. Just break the problem into 219pieces and use the appropriate tool for each piece. 220 221We haven't discussed optimizations, yet. It turns out, collisions 222happen rarely enough that even using floating point and transcendental 223functions like sin and cos don't slow things down noticable. For 224example, an Asteroids clone with 30-40 rocks bouncing around spends 225almost all its time blting the sprites to the screen. The time to 226calculate ricochets is completely swamped. Still, for maximum speed 227you'll want to use a fixed-point representation and lookup tables for 228the transcendentals. 229 230But my advice is to live with floats while you build your prototype. 231The first rule of optimization: Make it right before you make it faster. 232 233Our implementation uses a dx, dy method to move the balls. An 234angle/norm implementation would perform the same work, it's just 235arranged a little different. See CBENCH.ZIP for a dx/dy implementation 236by David Bollinger and CAROM.ZIP for an angle/norm implementation by 237Csaba Markus. 238 239--------------------------------------------------------------------- 240 Wall collisions 241 242At the time of this writing, we haven't completed the implementation of 243wall collisions. 244 245Our first pass implies that the trick to finding the collision point is 246to calculate a "shadow wall" one radius distance to each side of the 247wall. Then, simply find the intersection of the path of the center of 248the ball with each shadow wall (see figure 4a). Find which is closer to 249the original location of the ball. 250 251That gives you a possible collision. Next, you need to decide if the 252ball actually hit the wall face, or if it passed beyond the end of the 253wall and possibly hit the endpoint. 254 255To find if the ball hit a wall face, find the distance from the center 256of the ball to each endpoint of the shadow wall. If either distance is 257greater that the distance from one endpoint to the other then the 258center missed the wall face. 259 260To find if the ball hit the endpoint of a wall, treat the wall endpoint 261as an infinitely massive ball of zero size and go through the ball 262collision above (see figure 4b). 263 264--------------------------------------------------------------------- 265 Simultaneous collisions 266 267Again, we haven't implemented this yet. There are two likely 268candidates for this. 269 270First, go through each pair of objects and find the pair lowest time of 271collision. Perform that collision and then find the next lowest time, 272taking into account the new velocities of the objects. 273 274Or, sort the times and step through them in that order. Resort all 275objects that are close enough to be affected by each collision as they 276happen. 277 278--------------------------------------------------------------------- 279 Wrapping it up 280 281I hope you found this description useful. I realize it's ended up a bit 282on the terse side. Hopefully the PCX files will help you visualize what 283I'm trying to describe. If anyone has questions, feedback, suggestions or 284critique please feel free to contact me, Drake Christensen 71251,433. 285 286This file owes its existence to David Bollinger 72510,3623. He and I 287spent over a month brainstorming this surprizingly obscure problem in the 288GAMDEV forum on Compuserve. His CBENCH example is available in GAMDEV. 289Obviously, any mistakes or obfuscation in this text are entirely my fault. 290 291Another who provided needed assistance is Csaba Markus (E-mail: 292ethcms@duna.ericsson.se). We found his CAROM simulator at just the right 293time to convince ourselves that we were heading down (one of) the right 294path. 295 296I can't give a specific bibliography, but if you want to research this in 297texts, my suggestion is to visit a local college library and look for 298mechanics and physics texts circa 1910 or so. I was unable to find 299anything more recent than those. Apparently, the academic community 300doesn't consider this an interesting subject anymore. :-) 301 302Related files: 303 CBENCH.ZIP - Collision test bench by David Bollinger 72510,3623 304 CAROM.ZIP - Carom simulator by Csaba Markus ethcms@duna.ericsson.se 305 CLDTHD.ZIP - Thread on collision physics by (mostly) David Bollinger 306 and Drake Christensen