circle-circle collision detection

Recommended Posts

uncle_rico    415
Ok, so I'm designing a circle-circle collision test. I figure that this will be one of the easier types of tests, because the distance between the circles' centers at the time of a collision will always be the exact sum of their radii. So, suppose I have two balls bouncing around the screen. Each frame, I will record the path of each ball over the course of that frame. Then, I have to figure out if the two balls ever came close enough to touch during that time. Now, just because the two balls' paths intersect, that does not mean there was a collision. It's possible that one ball was able to move out of the way of the other before the other one crossed it's path. So timing is an important issue. Also, even if the two paths don't intersect, that does not mean there wasn't a collision. Since I'm just measuring the paths of the balls' centers, I need to find out not only if the paths have intersected, but also find out if there was an instance at which the two centers got closer to each other than the sum of the circles' radii. And therein lies the problem, because at first I thought it would be a simple matter of creating a line segment for each of the balls' paths, and finding where those two segments intersect. However, as I began to work the problem out it obviously got a bit more complicated. So, since timing is important, I've come up with a simple formula for measuring where the balls' centers are at any given time. If you have a line segment that represents a ball's path over the course of a single frame, and you know the veolocity is constant (which you do in my case), and you see the "time" element as just a fraction of 1, then I know you can simply: 1) Find the total change in x by x2 - x1. 2) Multiply the time by the change in x. 3) Add the result to x1. 4) Obtain the correct value of y based on the line's formula. So there it is. Also, I've found that determining the distance between the center of any two balls is trivial. Simply do this: sqrt((x2 - x1)^2 + (y2-y1)^2) But what I need to know is, at what time did the distance between the two centers equal the sum of their radii? I don't need to calculate the distance because I already have it -- if each circle has a radius of 5, then a collision will happen whenever the distance between the two distances equal 10. So, I plug it in: sqrt((x2 - x1)^2 + (y2-y1)^2) = 10 -OR- (x2 - x1)^2 + (y2-y1)^2 = 10^2 Which simplifies to what? Something like this? x2^2 - 2x1x2 + x1^2 + y2^2 - 2y1y2 + y1^2 - 100 = 0 What a mess! I'm so math impaired. I haven't even attempted it, but I imagine that this would yield an infinite number of possibilities for x1,x2,y1, and y2. Not all of these possibilities would work, though, when I put the timing into the equation. So, this won't work it seem. I can find the ball's center's position given any specific time, and I can find the distances between two centers given any specific positions, however it seems that the only way to figure out the precise time given the distance isn't possible. At least, not with my crappy math skills.

Share on other sites
smitty1276    560
I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.

Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.

Share on other sites
jyk    2094
Quote:
 So, this won't work it seem. I can find the ball's center's position given any specific time, and I can find the distances between two centers given any specific positions, however it seems that the only way to figure out the precise time given the distance isn't possible. At least, not with my crappy math skills.
It's perfectly possible, it just requires a different approach. You need to represent the path of each circle parametrically:
C+tV
Where C is the circle center at its starting position, V is the circle velocity/displacement vector, and t is time. The squared distance between the two circles at time t is then:
f(t) = |C0+tV0-(C1+tV1)|^2 = (C0+tV0-(C1+tV1)).(C0+tV0-(C1+tV1))
Where '.' is the dot product. You then have to find the solution to the quadratic equation:
(C0+tV0-(C1+tV1)).(C0+tV0-(C1+tV1)) = (r0+r1)^2
To work through that, it may help to know that in this context the dot product with vectors can be treated much like multiplication with scalars.

If that doesn't give you enough to go on, I can try to provide some more info.

Share on other sites
uncle_rico    415
Quote:
 Original post by smitty1276I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.

Thanks! Is this the sort of thing you are referring to?

Px(t) = t(x1 - x2) + x1
Py(t) = t(x1 - x2) + x1

Where Px is the position of the center's x at any given time, and Py is the position of the center's y?

Share on other sites
Sir Sapo    769
EDIT: Nevermind, I didn't read the whole question[grin]

This might be simpler than what you want, but can't you just check to see if the distance between the two centers is less than the radii of either of the circles?

That's what I always do for my collision circles.

Share on other sites
jyk    2094
Quote:
Original post by uncle_rico
Quote:
 Original post by smitty1276I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.

Thanks! Is this the sort of thing you are referring to?

Px(t) = t(x1 - x2) + x1
Py(t) = t(x1 - x2) + x1

Where Px is the position of the center's x at any given time, and Py is the position of the center's y?
Pretty close. I think you just mistyped the second line (the x's should by y's). Also, it should be x2-x1 rather than x1-x2. And finally, it'll all be easier to manage if you wrap it up in vector notation, i.e. P(t) = C+tV, where P = (Px,Py), C = (x1,y1), and V = (x2-x1,y2-y1).

Share on other sites
uncle_rico    415
Quote:
Original post by jyk
Quote:
Original post by uncle_rico
Quote:
 Original post by smitty1276I'm sure you'll get some good answers on this one, but I would recommend parameterizing their positions as a function of t then using those positions to find the t at which they breech the collision distance.Also, you can leave out the sqrt and check everything in terms of distance squared in many or most cases... square roots should be avoided if possible.

Thanks! Is this the sort of thing you are referring to?

Px(t) = t(x1 - x2) + x1
Py(t) = t(x1 - x2) + x1

Where Px is the position of the center's x at any given time, and Py is the position of the center's y?
Pretty close. I think you just mistyped the second line (the x's should by y's). Also, it should be x2-x1 rather than x1-x2. And finally, it'll all be easier to manage if you wrap it up in vector notation, i.e. P(t) = C+tV, where P = (Px,Py), C = (x1,y1), and V = (x2-x1,y2-y1).

Excellent, thank you. Yeah, I copied and pasted the Py(t) function without changing all the x's. Hah. This is the part of the game where I stare at your explanation for an hour or so, attempting to wrap my mind around it. I'll let you know how I do. I think you provided enough information though, thanks!

Share on other sites
smitty1276    560
I'll have to make this brief so I apologize if it is confusing, but I'll try to be clear.

Assume both circles have a radius R.

Circle0 and circle1 have center points at C0 and C1 respectively, and are moving at velocities v0 and v1 respectively (where velocity is a vector of how ever many dimensions you are operating in here).

The the positions, P0 and P1, and any given time, t, are:
P0 = C0 + t*v0
P1 = C1 + t*v0

The square of the distance between the center points at any given t is
distSquared = P0*P0 + P1*P1

If distSquared < 4*R*R they have collided. (4*R*R is 2 times the radius, squared)

So you basically need to solve for the maximun t in which that condition is true and you will have the exact time of the collision. Then the time t can be used to calculate the actual positions.

OOPS... the distance squared not correct, but you probably noticed that.

(P1.x-P0.x)^2 + etc...

Share on other sites
uncle_rico    415
Why is the first step to find the square of the distance between C1 and C0? Why not just find the distance itself? Is that just to avoid havihg to do a sqrt later?

Share on other sites
smitty1276    560
Yeah, you can take the sqrt if you want. I've just been conditioned to avoid them. It won't even be noticable most of the time, I'm sure.

Share on other sites
uncle_rico    415
Quote:
 Original post by smitty1276Yeah, you can take the sqrt if you want. I've just been conditioned to avoid them. It won't even be noticable most of the time, I'm sure.

Oh no, I'm totally cool avoiding the sqrt, I just wanted to make sure. Thanks for clearing that up!

Share on other sites
uncle_rico    415
Just a quick question. In this formula:

f(t) = |C0+tV0-(C1+tV1)|^2 = (C0+tV0-(C1+tV1)).(C0+tV0-(C1+tV1))

Does "||" refer to absolute value or length of the resulting vector? I took it to mean abs however I think I'm wrong because that C0+tV0-(C1+tV1), IIRC, will result in an ordered pair, which to my knowledge could either represent a vector or a point (is it possible to have an absolute value of a vector or a point?). I guess I could then use that point as the magnitude of the vector, with its origin being at 0,0, and then measure the length using the Pythagorean theorem and then square it. So, if the ordered pair is 3,5 I could calculate the length like 9+25=34 and just leave it at that (after all, why sqrt the 34 only to square it again).

I haven't tried the equivilent equation on the far right. Why should I use it instead? Is it less computationally-expensive? I hope I haven't obfuscated thigns too much.

Share on other sites
smitty1276    560
The stuff inside of the bars is a vector. When you have a vector inside of bars, it denotes magnitude (which, coincidentally, is the vector corollary to the scalar absolute value... that is, it is the same for the positive or negative value of the vector).

Oh, BTW, the magnitude of the vector is its length. Treat it like the distance forumala for points.

And in answer to your second question... what you have there (in the second equation) is the dot product of the vector from P1 to P0 onto itself, which will give you the magnitude squared.

Should you use it? It doesn't matter. They are computationally (and mathematically) identical. Each is calculated V.x*V.x + V.y*V.y, where V = C0+tV0-(C1+tV1).

Share on other sites
uncle_rico    415
Quote:
 Original post by smitty1276The stuff inside of the bars is a vector. When you have a vector inside of bars, it denotes magnitude (which, coincidentally, is the vector corollary to the scalar absolute value... that is, it is the same for the positive or negative value of the vector).

Very interesting! I did not know that, but it makes perfect sense.

Quote:
 Original post by smitty1276Oh, BTW, the magnitude of the vector is its length. Treat it like the distance forumala for points.And in answer to your second question... what you have there (in the second equation) is the dot product of the vector from P1 to P0 onto itself, which will give you the magnitude squared.Should you use it? It doesn't matter. They are computationally (and mathematically) identical. Each is calculated V.x*V.x + V.y*V.y, where V = C0+tV0-(C1+tV1).

Awesome. I really appreciate this. Now I just have to wrap my mind around that quadratic and I'm all set.

Share on other sites
uncle_rico    415
Hey guys, me again.

I'm having trouble getting this equation:

(C0+tV0-(C1+tV1)).(C0+tV0-(C1+tV1)) = (r0+r1)^2

into a form that I can use the Quadratic formula. I am able to simplify it a little bit by distributing the negative:

(C0+tV0-C1-tV1)).(C0+tV0-C1-tV1)) = (r0+r1)^2

and then I figured this might work as well, since C0-C1 will give me the distance between them:

(|C0C1|+tV0-tV1)).(|C0C1|+tV0-tV1)) = (r0+r1)^2

but there is where I get stuck. Can I foil this thing? I don't think I can, but it's the only thing I can think of.

Share on other sites
jyk    2094
Quote:
 Original post by uncle_rico (C0+tV0-C1-tV1)).(C0+tV0-C1-tV1)) = (r0+r1)^2
Don't have time to do the whole thing right now, but here are a couple of hints:

1. Make C0-C1 and V0-V1 single variables (factor out the t for the latter)
2. Express the left hand side as (...)^2 rather than (...).(...)
3. Perform the square just as if the known terms were single scalars rather than vectors
4. You should get as a result a quadratic in t
5. Finally, remember that the mults are in fact dot products

This should give you the final form of the quadratic to be solved.

Share on other sites
JohnBolton    1372
First, two spheres (or circles) collide when the distance between their centers is less than the sum of their radii. Next, to simplify the motion, just make the motion of one ball relative to the other:

Given two balls with radii r0 and r1 at postions P0 and P1 with velocities V0 and V1:
    r' = r0+r1    V' = V1-V0    P'(t) = P1 + V't, t = [a,b]
If the distance from P0 to the line segment P'(a)P'(b) is less than r', then the balls collided at some point between a and b.

Now, if you want to now when and where they collided, you will have to find the values of t at the intersections between the line segment P'(a)P'(b) and a sphere (circle) at P0 with radius r', which is what is being described above.

[Edited by - JohnBolton on December 8, 2005 8:10:46 PM]