Circle-Circle Collisions - Clipping problem

[Martin]

I've been playing around with some physics in flash, and I have a problem.

All of the balls have diameter 1. Ball A is heading towards ball B, which is stationary, at 5 units per frame. Frame 1, distance is 7. Frame 2, distance is 2. Frame 3, distance is -3 ... ie, it passes through the stationary ball B.

Now, to fix this, I just checked a ray along the path that the ball would be travelling along if it were real life. However, now, I have another problem that I'm not sure how to solve (or if it's even solveable).

Here's a diagram.



If the black line represents the distance travelled in a frame at constant velocity, it's obvious that the balls do not collide. However, their trajectories intersect, so my current model detects that as a collision. This gets even more confusing with more balls. So, does anyone know of a better way to do this? I think I'm going to try mapping the paths of the balls as a function of time and see how that works, but otherwise, I'm out of ideas.

Thanks in advance.

[wtd]

How about mapping the distance between the centers of the circles with respect to time? If at any point that distance becomes les than or equal to the sum of their radii, then you have collision.

[bugzpodder]

what you do is find the time of intersection and check if they are equal. however, we are dealing with circles, so a simple ray is not enough. we may have the ray not intersecting, but the circles intersecting a little bit.

suppose you have two point A and B moving at vA and vB. then we can compute the relative point A-B and velocity vA-vB as to assme B is stationary at the origin. for the circles with radii rA and rB, this simply reduces to whether a line intersects at a circle. you should find two roots. do some case checking to find the exact time of collison. always take the smaller root.

actually i've done this on the last day of my coop lol.

[zylum]

yeah, you can isolate the system so that one of the balls is moving and check if it will collide with the other now stationary ball. you have to find the amount of time until the collision. if the time is less than 1 and greater or equal to 0 then a collision will occure between the current frame and next frame. since the balls will collide in 2 spots (at their leading edges and trailing edges) there will be two roots. you take the smaller of the two.. if a collision occures, you can update the balls by increasing their position by velocity*time to collision. anyhoo heres the turing code:

code:

fcn timeToCollision (i, j : int) : real     var t : array 1 .. 2 of real     var x1 := ball (i)._x     var y1 := ball (i)._y     for j : 1 .. upper (ball)         if i ~= j then             var dx := ball (j)._x             var dy := ball (j)._y             var vx := ball (i)._vx - ball (j)._vx             var vy := ball (i)._vy - ball (j)._vy             var R := ball (i)._radius + ball (j)._radius             var a := 2 * vx * x1 - 2 * vx * dx + 2 * vy * y1 - 2 * vy * dy             var b := -2 * vx * x1 + 2 * vx * dx - 2 * vy * y1 + 2 * vy * dy             var c := -vy ** 2 - vx ** 2             var d := R ** 2 - x1 ** 2 - dx ** 2 - y1 ** 2 - dy ** 2 + 2 * x1 * dx + 2 * y1 * dy             var e := -vy ** 2 - vx ** 2             var f := sqrt (b ** 2 - 4 * c * d)             t (1) := (a + f) / (2 * e + 1e-10)             t (2) := (a - f) / (2 * e + 1e-10)             if t (1) >= 0 and t (1) < 1 and t (2) >= 0 and t (2) < 1 then                 result min (t (1), t (2))             elsif t (1) >= 0 and t (1) < 1 then                 result t (1)             elsif t (2) >= 0 and t (2) < 1 then                 result t (2)             end if         end if     end for     result 1 end timeToCollision

[[Gandalf]]

The above code doesn't work since you have the for loop increase j, which is already a parameter of your function.

[bugzpodder]

a few thoughts on zylums code:

if discriminant is less than 0 then they wont intersect (ever). i won't take the sqrt of that if i were you.

the roots need to be sorted so t(1)<=t(2) so the earlier one is returned

if t(2)<0 then no collision
if t(1)<=0<=t(2) then the balls are overlapping at the start of the timestep
if 0<=t(1)<=1 then t(1) would be what you want
if 1<t(1) then no intersection at this timestep

[zylum]

[Gandalf] wrote:

The above code doesn't work since you have the for loop increase j, which is already a parameter of your function.

bah i always seem to change code righte before i post it without testing

i originally had it so that you check if ball i collides with any of the balls.. heres the original code plus checking if discriminant is less than 0 plus example code:

code:

type BallData :     record         _x, _y, _radius, _vx, _vy, _mass : real     end record var ball : array 1 .. 2 of BallData fcn timeToCollision (i : int) : real     var t : array 1 .. 2 of real     var x1 := ball (i)._x     var y1 := ball (i)._y     for j : 1 .. upper (ball)         if i ~= j then             var dx := ball (j)._x             var dy := ball (j)._y             var vx := ball (i)._vx - ball (j)._vx             var vy := ball (i)._vy - ball (j)._vy             var R := ball (i)._radius + ball (j)._radius             var a := 2 * vx * x1 - 2 * vx * dx + 2 * vy * y1 - 2 * vy * dy             var b := -2 * vx * x1 + 2 * vx * dx - 2 * vy * y1 + 2 * vy * dy             var c := -vy ** 2 - vx ** 2             var d := R ** 2 - x1 ** 2 - dx ** 2 - y1 ** 2 - dy ** 2 + 2 * x1 * dx + 2 * y1 * dy             var e := -vy ** 2 - vx ** 2             if b ** 2 - 4 * c * d < 0 then                 result 1             end if             var f := sqrt (b ** 2 - 4 * c * d)             t (1) := (a + f) / (2 * e + 1e-10)             t (2) := (a - f) / (2 * e + 1e-10)             if t (1) >= 0 and t (1) < 1 and t (2) >= 0 and t (2) < 1 then                 result min (t (1), t (2))             elsif t (1) >= 0 and t (1) < 1 then                 result t (1)             elsif t (2) >= 0 and t (2) < 1 then                 result t (2)             end if         end if     end for     result 1 end timeToCollision proc collide (i, j : int, t : real)     ball (i)._x += round (ball (i)._vx * t)     ball (i)._y += round (ball (i)._vy * t)     ball (j)._x += round (ball (j)._vx * t)     ball (j)._y += round (ball (j)._vy * t) end collide proc drawBalls     for i : 1 .. upper (ball)         Draw.Oval (round (ball (i)._x), round (ball (i)._y), round (ball (i)._radius), round (ball (i)._radius), 7)     end for end drawBalls proc moveBalls     for i : 1 .. upper (ball)         ball (i)._x += ball (i)._vx         ball (i)._y += ball (i)._vy     end for end moveBalls ball (1)._x := 100 ball (1)._y := 200 ball (1)._vx := 5 ball (1)._vy := 1 ball (1)._radius := 20 ball (1)._mass := 1 ball (2)._x := 200 ball (2)._y := 200 ball (2)._vx := -3 ball (2)._vy := 2 ball (2)._radius := 20 ball (2)._mass := 1 var t : real loop     drawBalls     delay (100)     moveBalls     t := timeToCollision (1)     exit when t < 1     cls end loop delay (1000) cls collide (1, 2, t) drawBalls

the timeToCollision function returns 1 if the collision wont occure between the current frame and the next frame and a value less than one and greater or equal to 0 if it will occure... if more than one collision will occure between frames, it will return the time for the one that will occure first.