pre-calculation of circle collision

pre-calculation of circle collision

Martin Kalbfuß

Member #9,131

October 2007

Hi,

I try to calculate the time of collision of two circles. After thinking a while about it I got the following equation:

r1 + r2 = |(s1 + v1 * dt) - (s2 + v2 * dt)|;

where

r1, r2 => radius
s1, s2 => starting position
v2, v2 => velocity
dt => time of collision

I have to solve for dt. But I'm not sure how to handle the absolute value. I never
had to do this for an equation like this.

Thanks for any help.

http://remote-lisp.spdns.de -- my server side lisp interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

Matthew Leverton

Supreme Loser

January 1999

Just split it up into two separate equations:

$<math>r1 + r2 = (s1 + v1 * dt) - (s2 + v2 * dt)</math>$

$<math>r1 + r2 = -((s1 + v1 * dt) - (s2 + v2 * dt))</math>$

Then solve each independently for dt.

--
RTFM | Follow Me on Google+ | I know 10 people

Myrdos

Member #1,772

December 2001

[EDIT] Whoops, didn't read your question carefully enough.

__________________________________________________

Oscar Giner

Member #2,207

April 2002

You just handle 2 equations, one where it's positive:

r1 + r2 = (s1 + v1 * dt) - (s2 + v2 * dt)

and another when it's negative:

r1 + r2 = -((s1 + v1 * dt) - (s2 + v2 * dt))

That is, you get 2 solutions. You need to check which of the 2 is the one you want (you probably want the smaller dt which is >= 0).

--
[Website | e-mail]
[Tetris Unlimited] [AllegAVI | AlText]

Arthur Kalliokoski

Second in Command

February 2005

Un-removed due to double stupidity (the first one seemed to only work if circle center was tangental to circle 2)

The way I'd do it:

Find the closest the center of circle 2 will get to circle 1

http://math.ucsd.edu/~wgarner/math4c/derivations/distance/distptline.htm

Then the hypotenuse is the sum of the radii.Use trigonometric identities to find how far circle 2 has progressed.

{"name":"604390","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/8\/08f4c24026f741f06187590d6e4d7c22.png","w":584,"h":360,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/8\/08f4c24026f741f06187590d6e4d7c22"}

They all watch too much MSNBC... they get ideas.

Martin Kalbfuß

Member #9,131

October 2007

Sorry guys. I've made a mistake.

It's the absolute value of a vector not a scalar. I'm not sure if I used the correct words and symbols to represent this.

I forgot what I've learned in school.

$<math>r_1 + r_2 = \sqrt{((x_1 + v_{x1} * d_t)-(x_2 + v_{x2} * d_t))^2 + ((y_1 + v_{y1} * d_t)-(y_2 + v_{y2} * d_t))^2}</math>$

$<math>(r_1 + r_2)^2 = ((x_1 + v_{x1} * d_t)-(x_2 + v_{x2} * d_t))^2 + ((y_1 + v_{y1} * d_t)-(y_2 + v_{y2} * d_t))^2</math>$

I assume that's the correct solution. I will write a small simulation in the end.

Thanks for your answers. What do you think about it? Both balls are moving.
I need $<math>dt</math>$ to know when to change the moving directions of the two circles(balls).

http://remote-lisp.spdns.de -- my server side lisp interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

Arthur Kalliokoski

Second in Command

February 2005

I think my idea would still work if you simply took circle 1 to be stationary and subtracted the circle 1 vector to circle 2 trajectory. I'll make an allegro 4 program to demonstrate if you can compile an allegro 4 program.

They all watch too much MSNBC... they get ideas.

Edgar Reynaldo

Major Reynaldo

May 2007

I did this some time ago, and solved it using intercept times. The code is kind of old, and a little messy, but you should get the picture anyway.

PhysicsTest4.7z (src, exe, A44 dll)
Use the arrow keys to accelerate, space to stop, - and = to decelerate and accelerate and escape to quit.

{"name":"604394","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/7\/e7d3d1cfce2f9a891e2af6f4a85bd2d4.png","w":812,"h":632,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/7\/e7d3d1cfce2f9a891e2af6f4a85bd2d4"}

Arthur's approach might be simpler, but his diagram is misleading. The point where the trajectory of the first circle is closest to the center of the second circle is not always on the edge of the first circle, so you can't mark the distance from there to the center of the first circle after it moves as being equal to the radius of the first circle.

To use Arthur's method, I would :
1) Find the relative velocity of circle 1 to circle 2. We'll consider circle one as moving and circle 2 as stationary.
2) Create a line equation using the ray created by the relative velocities (cx1,cy1)->(cxvel1,cyvel1). The magnitude of the relative velocity must be non zero or they can't collide.
3) Find the point on the line closest to the center of circle 2.
4) Find the distance from the point in 3 to the center of circle 2. This distance must be less than or equal to the sum of the radii or they will never collide.
5) The distance from 3 to the center of circle 1 is the square root of ((sum of radii) squared minus the distance in 4 squared).
6) Find the distance from the point in 3 to the center of circle 1.
7) The distance traveled by circle 1 is the distance in 6 plus and minus the distance in 5.
8) Divide the distance traveled by the relative speed of circle 1 to find the time of intercept.

Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide
King Piccolo will make it so Then I could just flip it with some sweet, sweet matrix math. In either case, I’ll ride this wagon until the wheels fall off. Thanks to those that keep it running

Arthur Kalliokoski

Second in Command

February 2005

Edgar Reynaldo said:

The point where the trajectory of the first circle is closest to the center of the second circle is not always on the edge of the first circle.

That was a second attempt, and still too hurried. The fact is that it doesn't depend on the tangent of either the first circle (first attempt) or second circle (second attempt). It just needs to check that the sum of the radii is greater than the closest distance.

Here's a third attempt

{"name":"604398","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/4\/94d9f8b157f3f26893eeb8f9707cd3e1.png","w":466,"h":279,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/4\/94d9f8b157f3f26893eeb8f9707cd3e1"}

They all watch too much MSNBC... they get ideas.

Martin Kalbfuß

Member #9,131

October 2007

I have problems,because of its complexity.
Currently I translate the coordinate-system before to eleminat $<math>s_b</math>$ .

{"name":"604403","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/4\/347d4bf6af32bd7d7201f8b5b1a0b306.png","w":794,"h":1123,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/4\/347d4bf6af32bd7d7201f8b5b1a0b306"}

This way $<math>s_b</math>$ is eleminated.

$<math>\vec s_a = - \vec s_b</math>$ translation
$<math>r_1 = r_2</math>$ equal sized balls

$<math>r_1 + r_2 = |\vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{s_b} - \vec{v_b} \cdot \Delta t|</math>$

$<math>2 \cdot r_1 = |\vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{s_b} - \vec{v_b} \cdot \Delta t|</math>$

$<math>d_1 = |\vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{s_b} - \vec{v_b} \cdot \Delta t|</math>$

$<math>d_1 = |\vec{s_a} + \vec{v_a} \cdot \Delta t + \vec{s_a} - \vec{v_b} \cdot \Delta t|</math>$

$<math>d_1 = |2 \cdot \vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{v_b} \cdot \Delta t|</math>$

$<math>d_1 = |2 \cdot \vec{s_a} + \Delta t (\vec{v_a}- \vec{v_b})|</math>$

$<math>d_1 = \sqrt{(2 \cdot s_{a,x} + \Delta t (v_{a,x} - v_{b,x}))^2 + (2 \cdot s_{a,y} + \Delta t (v_{a,y}- v_{b,y}))^2}</math>$

$<math>d_1^2 = (2 \cdot s_{a,x} + \Delta t (v_{a,x} - v_{b,x}))^2 + (2 \cdot s_{a,y} + \Delta t (v_{a,y}- v_{b,y}))^2</math>$

I'm not able to solve for $<math>\Delta t</math>$

Any Idea? Thanks.

Edit: I can eleminate $<math>s_{a,y}</math>$ , translating the coordinate system. But there's still $<math>s_{a,x}</math>$ which is the main problem.

Edit: Some words about the equation. $<math>\Delta t</math>$ is the time when the absolute value of the distance is equal to the added radi. This is the time, when both circles collide. I'm still not sure, if this is correct.

Edit: Oh! I have two unkown variables. $<math>\Delta t_1</math>$ and $<math>\Delta t_2</math>$ . They're only equal for a collision. But they don't have to be even if their paths are crossing.

http://remote-lisp.spdns.de -- my server side lisp interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

dejaime

Member #12,984

June 2011

I made a game (some kind of different space shooter) and used something different there for my circular collision pre-detection.
I used some resources to simplify that, it's not too hard to understand.
You simplify the problem from 2 positions, 2 radius and 2 speeds
to 2 positions, 1 radius and 1 speed or even 1 position, 1 radius and 1 speed if you consider one in the origin (0,0) and use the second as (dX, dY).
All you have to is check if the distance between the 2 positions is < (or<=) than the radius.

1: Consider object 1 as if it was a point and object 2 as a circle with diameter = (Obj1 diameter + Obj2 diameter)
This way, you check if the "point" is inside the circle with the added radius of both objects

2: Use one of the objects in the center (witch of them you choose will affect calculations, but it's really simple).

3: Use both speed vectors as one. You'll need to subtract them (not sum!)
Imagine that one circle is fleeing from the other, so, it's "escaping speed" is it's speed minus the other circle's.
So, you consider Obj 1 as the origin and make the calculations for obj 2, creating a new scheme of origin and a third obj (Obj3). (see the attached images, they'll help)
So, Obj3 has the following characteristics:
radius = Obj 1 radius + Obj 2 radius
Position = dPos = Pos2 - Pos1
Speed = dSpeed = v2 - v1
and then you look at witch time Obj 3 touches the origin (IF, it may not touch at all what means no collision).
PS: If you choose to bring Obj2 to the center, the position and speed calcs are different:
Pos = Pos1 - Pos2
Speed = v1 - v2
The circle in the center is always the negative one.

This way, you'll have only one single circle obj moving "for both", and all you have to test is if the obj is colliding with the origin.
Actually, in my game, I didn't bring any of the circular obj to the center, just used its real position and the other one's real position too, checking the dt with a different radius and speed vector...

{"name":"604406","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/1\/e10e0570bd5039387bba840e7e95eaad.png","w":271,"h":355,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/1\/e10e0570bd5039387bba840e7e95eaad"} {"name":"604407","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/4\/64e672f3300916d94ff7e5288202d20a.png","w":549,"h":389,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/4\/64e672f3300916d94ff7e5288202d20a"}

Take a moment to consider if this can be applied to your situation, it fitted like a glove in my project.

If I find that old code I'll bring it to ya, but can't promise...
ps: keep the third object allocated, you wouldn't want to create a new object every time.

Edgar Reynaldo

Major Reynaldo

May 2007

Martin Kalbfub said:

I'm not able to solve for $<math>\Delta t</math>$

Sure you can, you just have to multiply everything out and then sort the coefficients on the powers of time.

Dejaime has the right idea, but he didn't go fully into the equations involved, so I will.

First, you have circle one and circle two. Consider circle two as the leader circle. All positions and velocities will be relative to circle ~~two~~ one. That means circle one is effectively stationary and centered on the origin.

Find the relative position of the leader circle :
$<math>Lx = Cx_2 - Cx_1</math>$
$<math>Ly = Cy_2 - Cy_1</math>$

Find the relative velocity of the leader circle :
$<math>Lvx = Cvx_2 - Cvx_1</math>$
$<math>Lvy = Cvy_2 - Cvy_1</math>$

Write the equations for the x and y position of the leader circle at time t :
$<math>xpos(t) = Lx + Lvx*t</math>$
$<math>ypos(t) = Ly + Lvy*t</math>$

Write the equation for the distance from the origin squared at time t (this should be set equal to the squared sum of the radii) :
$<math>dist(t)^2 = xpos(t)^2 + ypos(t)^2 = (Cr_1 + Cr_2)^2</math>$

Substitute in the equations for xpos(t) and ypos(t) :
$<math>Lx^2 + 2*Lx*Lvx*t + Lvx^2*t^2 + Ly^2 + 2*Ly*Lvy*t + Lvy^2*t^2 - Cr_1^2 - 2*Cr_1*Cr_2 - Cr_2^2 = 0</math>$

Sort the factors according to powers of t :
$<math>(Lvx^2 + Lvy^2)*t^2 + (2*Lx*Lvx + 2*Ly*Lvy)*t + (Lx^2 + Ly^2 - Cr_1^2 - 2*Cr_1*Cr_2 - Cr_2^2)*t^0 = 0</math>$

So now you have a quadratic equation :
$<math>A*t^2 + B*t + C = 0</math>$

Use the quadratic formula :
$<math>t = \frac{-B \pm \sqrt{B^2 - 4*A*C}}{2*A}</math>$

With these as A, B, and C :
$<math>A = Lvx^2 + Lvy^2</math>$
$<math>B = 2*Lx*Lvx + 2*Ly*Lvy</math>$
$<math>C = Lx^2 + Ly^2 - Cr_1^2 - 2*Cr_1*Cr_2 - Cr_2^2</math>$

That gives you the times of intercept.

If the discriminant^[1] of the quadratic formula is negative or if A is zero then there are no real solutions. If the discriminant is zero, there is one solution and the circles glance off of each other. If the discriminant is positive, then there are two real solutions. To indicate a collision, one of the solutions must be positive. If both are positive, use the smallest one, as that is the earliest collision.

Once you get that method to work, you should try out Arthur's solution. You have to know how to use a general first degree equation of a line, but that's not too hard. His solution really is simpler.

References

The difference of B squared and 4 A C

Martin Kalbfuß

Member #9,131

October 2007

Edgar Reynaldo said:

So now you have a quadratic equation :
$<math>A*t^2 + B*t + C = 0</math>$
Use the quadratic formula :
$<math>t = \frac{-B \pm \sqrt{B^2 - 4*A*C}}{2*A}</math>$

Thank you very much. I completely forgot about the quadratic formula to solve a quadratic equation.

http://remote-lisp.spdns.de -- my server side lisp interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

dejaime

Member #12,984

June 2011

Edgar Reynaldo said:

Dejaime has the right idea, but he didn't go fully into the equations involved, so I will.

Thank you for the math, I find that part boring... [:

If you happen to test and one root is Zero that means the objects are "touching but not colliding", if you get me. So, the second root (probably not equal to zero unless both objects are points or other situations regarding parallel movement directions) will tell you if they are going to collide shortly (positive root) or they are not going to collide (negative root).

If you have a negative and a positive root that means the objects are already colliding.

If anyone can confirm this, I'm feeling kinda dumb 2day, anything can happen!

@edit: I needed this coz there were some different interactions on collisions in my design, some kind of ethereal state, where some objects could go through other while applying an abnormal effect... Something like Physical + Physical or Ether + Ether = normal Collision, Physical + Ether = no collision, but I still needed to know if they were "sharing space" so I could apply the secondary effects. If you have no need for this, it'll be even simpler!