Computer Science Canada

Circle-Circle Collisions - Clipping problem
Author:  Martin [ Fri Sep 09, 2005 2:08 am ]
Post subject:  Circle-Circle Collisions - Clipping problem
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.

Posted Image, might have been reduced in size. Click Image to view fullscreen.

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.
Author:  wtd [ Fri Sep 09, 2005 2:36 am ]
Post subject: 
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.
Author:  bugzpodder [ Fri Sep 09, 2005 9:45 am ]
Post subject: 
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.
Author:  zylum [ Sat Sep 10, 2005 8:07 pm ]
Post subject: 
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
Author:  [Gandalf] [ Sat Sep 10, 2005 8:59 pm ]
Post subject: 
The above code doesn't work since you have the for loop increase j, which is already a parameter of your function.
Author:  bugzpodder [ Sat Sep 10, 2005 10:14 pm ]
Post subject: 
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. Wink

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
Author:  zylum [ Sun Sep 11, 2005 10:34 am ]
Post subject: 
[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 Confused

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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy