Hard math problem regarding circle collisions

26 posts

Flag Post

I’m making this physics library… Got an idea of how to make collision solving perfect, considering everything that happens between two frames. So when I see two circles overlapping, I first need to place them in time where they had just collided. To make this perfect I need to consider the speed.

Say the step in time is 1/30 seconds (this is not really relevant). I would want to find n, a number between 0 and 1.
1 means last frame and 0 means current frame. Because circleposition – circlevelocity * 1 is the position the circle was at last frame, and circleposition – circlevelocoty * 0 is the position it’s currently at obviously. (if the step is always the same)

<tldr>
So here’s the algebra I figured out. c1 and c2 being the circles’ position vectors and v1 and v2 being the circles’ velocity vectors. r1 and r2 being the radii of the circles.

|c2 - v2 * n - (c1 - v1 * n)| = r1 + r2

I’ve been trying for a long time to find n but can’t figure it out. There is only one answer so this should be possible. So what I’m asking is how to find n here.

</tldr>

Just in case, || means absolute value (length) of vector.

PS: Someone from 1GAM did persuade me to KISS (keep it stupidly simple) in my game, but I just can’t throw this away without solving it first :P

Edit: I will show you the next step I did, the rest is just a mess where I can’t find the solution

Saying c = c2 - c1 (delta s), and appending _x and _y for x and y values of the vectors.

(c + n(v1_x - v2_x))^2 + (c + n(v1_y - v2_y))^2 = (r1 + r2)^2
 
Flag Post

http://archive.ncsa.illinois.edu/Classes/MATH198/townsend/math.html

Equation

To simplify the problem, treat the cases (c2 - v2 * n) > (c1 - v1 * n) and (c2 - v2 * n) < (c1 - v1 * n) separately.
(c2 - v2 * n) > (c1 - v1 * n):
(c2 - v2 * n) - (c1 - v1 * n) = r1 + r2
(v2 * n) - (v1 * n) = r1 + r2 - c2 + c1
n(v2 - v1) = r1 + r2 - c2 + c1
n = (r1 + r2 - c2 + c1) / (v2 - v1)

Alternatively:

|(c2 - v2 * n) - (c1 - v1 * n)| = r1 + r2
((c2 - v2 * n) - (c1 - v1 * n))^2 = (r1 + r2)^2
(c2 - v2 * n)^2 - 2(c2 - v2 * n)(c1 - v1 * n) + (c1 - v1 * n)^2 = (r1 + r2)^2
[c2^2 - 2(c2 * v2)n + (v2^2)n^2] - ... = (r1 + r2)^2
...

 
Flag Post

Step 14 is what you’re trying to do?

 
Flag Post
Originally posted by ErlendHL:

. There is only one answer

That’s not true. Two touching balls with equal velocities will stay in touch, producing many solutions for n.
Two non-touching balls with parallel velocities will never touch, so there will be no n satisfying the equation.

 
Flag Post

NineFiveThree: Ah, that’s right, sorry.

Dealmaster13: When you found n, you weren’t using vectors so I’m not sure how this would help me. Maybe there’s something I don’t understand.

What I also think this equation can help me with, is to find out if two circles have collided without overlapping in the current frame (when they have so big velocity they pass each other in one frame). Like, if n has an answer between 0 and 1, it means they have collided.

 
Flag Post

assuming c1 and c2 to be the positions before the collision happend:

|c1 + n*v1 - c2 - n*v2| = r1 + r2
|c1 - c2 + n*(v1 - v2) | = r1 + r2

apply length calculation:
(c1_x - c2_x + n*(v1_x - v2_x))² + (c1_y - c2_y + n*(v1_y - v2_y))² = (r1 + r2)²

expand (first term shown):
c1_x^2-2 c1_x c2_x+2 c1_x n v1_x-2 c1_x n v2_x+c2_x^2-2 c2_x n v1_x+2 c2_x n v2_x+n^2 v1_x^2-2 n^2 v1_x v2_x+n^2 v2_x^2 + ... = (r1 + r2)^2

solve the equation.

 
Flag Post
Originally posted by ErlendHL:

Dealmaster13: When you found n, you weren’t using vectors so I’m not sure how this would help me. Maybe there’s something I don’t understand.

Sorry, completely my bad; it was late at night

Simplify your problem by storing a, b and c values as they have done here
The scalar (dot) product of a vector with itself is the square of its magnitude: v.v = |v|2. You will also need to recall that the scalar product is distributive over vector addition: v1.(v2 + v3) = v1.v2 + v1.v3. Scalar multiplication: (c1v1).(c2v2) = (c1c2)(v1.v2).

First few All of the steps (note ci + vit makes more sense to me personally, depending on the definition of vectors c and v of course):
|(c1 + v1t) – (c2 + v2t)| = r1 + r2
|(c1c2) + (v1v2)t| = r1 + r2
((c1c2) + (v1v2)t).((c1c2) + (v1v2)t) = (r1 + r2)2
… (simple vector algebra) …
(c1c2).(c1c2) + 2(c1c2).(v1v2)t + (v1v2).(v1v2)t2 = (r1 + r2)2
k1 = (c1c2).(c1c2) (this is a)
k2 = (c1c2).(v1v2) (this is b)
k3 = (v1v2).(v1v2) (this is c)
k1 + 2k2t + k3t2 = (r1 + r2)2
k1/k3 + 2k2t/k3 + t2 = (r1 + r2)2/k3
(t – k2/k3)2 – (k2/k3)2 + k1/k3 = (r1 + r2)2/k3 (‘completing the square’)
… (simple algebra) …
t = (+/-)((r1 + r2)2/k3 + (k2/k3)2 – k1/k3)1/2 + k2/k3

 
Flag Post

I don’t want to be a dick, but why are you building your own physics library. There are already many great ones out there.
Too many game developers get caught up trying to develop their “game engine” before developing their actual game and never get their feet off the ground.

If you’re doing it purely for learning purposes, then feel free to ignore this, but try not to get too caught up in building everything yourself from scratch.

 
Flag Post

Thanks for the replies!

Writing a reply, I went to eat without posting and when I came back there were two more replies. Just posting what I wrote anyway (it’s not as relevant anymore)

I made a delta v and delta c to use instead of v1_x - v2_x, v1_y - v2_y, c1_x - c2_x and c1_y - c2_y.
Here, 1 at the end of v and c means the x value of the vector and 2 means y value.

I don’t know anything about imaginary numbers yet. Looking at the answers, it seems like this task would be way too performance heavy for a game.

Dealmaster13: Thanks a ton! That makes sense. t has two answers then right? Do you think this could be efficient enough to implement into a game?


Originally posted by ArreatsChozen:

I don’t want to be a dick, but why are you building your own physics library. There are already many great ones out there.
Too many game developers get caught up trying to develop their “game engine” before developing their actual game and never get their feet off the ground.

If you’re doing it purely for learning purposes, then feel free to ignore this, but try not to get too caught up in building everything yourself from scratch.

You are totally right about that. I do it for my game, but also for learning, because I’m very interested in this. So I learn math and physics and get some practice in structuring a library. Also, the way physics libraries like Box2D are structured does not fit me very well so I also make things from scratch to make it perfect for myself. And I think it’s funny and interesting to do such.

(E) Right now I’ve spent so much time writing libraries in January that I’ll just make a simple Text RPG game in Python as my One game a month entry.

 
Flag Post
Originally posted by ErlendHL:

Dealmaster13: Thanks a ton! That makes sense. t has two answers then right? Do you think this could be efficient enough to implement into a game?


t has zero, one, two, or infinitely many real solutions.

t has no real solutions if (r1 + r2)2/k3 + (k2/k3)2 – k1/k3 is negative (or k3 = 0 and |c1 + c2| =/= (r1 + r2)2), one if it equals 0, two if it is positive, and infinitely many if k3 = 0 and |c1 + c2| = (r1 + r2)2

t has no real solutions if the balls never collide (most common case)
t has one real solution if the balls glance? once
t has two real solutions if the balls collide without glancing, thus touching twice (once on the ‘entry’ of one ball and once on its ‘exit’)
t has infinitely many real solutions when the balls are always touching because they share the same velocity and are initially touching
t has a negative solution if the balls (would) have collided in the past

This collision detection can be efficiently implemented:
1. Initialise the system by performing collision checks on every pair of balls (O(n2) in number of balls), taking into account world boundary collisions if necessary
2. Keep a sorted queue of the collisions in order of ascending t value (ignoring ‘erroneous’ negative values of course)
3. Perform the next collision by moving the two balls such that they are touching (graphically or otherwise) when appropriate (i.e. during the frame at which t <= 1 where t is in frames)
4. Move the rest of the balls making use of the value t
5. Recalculate the collided balls’ velocities
6. Assert that the collision queue does not contain details about collisions concerning either of the two balls that just collided – as this information is now defunct
7. Perform collision checks between the two balls that just collided and every other ball (O(n)), taking into account world boundary collisions if necessary, adding to the sorted queue appropriately
8. Perform the next collision if it is due to occur within the current frame, taking account the time that has already passed in the value of t
9. Move all of the balls such that we are in the next frame (if we are presenting the collisions graphically on a frame-by-frame basis where each frame has a fixed duration of time)
10. Return to step 3

So after initialisation, the cost of each collision is O(n) in checking for new collisions

Minor point: if the next collision will be between ball1 and ball2 then ball1 and ball2 need not store information about any collisions between them and the other balls (as this information would become irrelevant by the time the collision between ball1 and ball2 takes place)

It is debatable as to whether most physics libraries take into account this system of precise collisions between objects; if not, they really should, at least for low (<100) particle systems

In work environments, it is a good idea to use public libraries to improve efficiency, however for most other purposes writing your own hopefully somewhat generic libraries is a great way to go about things; at the very least for the educational and training aspect

 
Flag Post
Originally posted by feartehstickman:

Step 14 is what you’re trying to do?

There is severe tunneling in the example, a very undesirable no-sweep method.

 
Flag Post

Thanks again, Dealmaster! I really appreciate your deeply informative texts.

Before settling into your latest post, I just gotta clear this up.

I don’t understand what you do after this

k1 + 2k2t + k3t2 = (r1 + r2)2

to find the answer.

I redid what you did because I want to fully understand it all. I use a,b and c instead of k1, k2 and k3.
This is where I arrived:

a + 2bt + ct2 = (r1 + r2)2
c * t2 + 2b * t + a – (r1 + r2)2 = 0

t = (-2b (+/-) (4b2 – 4c(a – (r1 + r2))2)0.5) / 2c

 
Flag Post

he devides k3, making the coefficient of t² equal to one.

Then he adds -(k2/k3)² + (k2/k3)² not changing anything. (staying equivalent)
This allows to use the binomial formula to get rid of the t² leaving you with just t.

http://en.wikipedia.org/wiki/Quadratic_equation#By_completing_the_square

You want to write a physics library (!) but do your calculations by hand, if that’s not irony, I don’t know.

 
Flag Post
Originally posted by NineFiveThree:

You want to write a physics library (!) but do your calculations by hand, if that’s not irony, I don’t know.

What’s wrong with that?

We’re just finding an expression for t

Here’s a video on completing the square (haven’t watched it, but highly rated): http://www.youtube.com/watch?v=xGOQYTo9AKY
The basic standard for completing the square is to have an equation of the form x2 + bx + c = 0:
x2 + 2(1/2)bx + ((1/2)b)2 – ((1/2)b)2 + c = 0
(x + (1/2)b)2 – (1/4)b2 + c = 0
(x + (1/2)b)2 = (1/4)b2 – c
x + (1/2)b = (+/-)((1/4)b2 – c)1/2
x = -(1/2)b (+/-)((1/4)b2 – c)1/2

x → t
b → -2k2/k3
c → k1/k3 – (r1 + r2)2/k3

t = (+/-)((r1 + r2)2/k3 + (k2/k3)2 – k1/k3)1/2 + k2/k3

There are a lot of equations here, so there’s a slight chance that I’ve made a mistake somewhere if my equations do not match the equations in the link that I provided earlier on collisions in billiards

 
Flag Post
Originally posted by Dealmaster13:
Originally posted by NineFiveThree:

You want to write a physics library (!) but do your calculations by hand, if that’s not irony, I don’t know.

What’s wrong with that?

Nothing wrong, just ironic.

Originally posted by Dealmaster13:
x2 + bx + c = 0

There are a lot of equations here, so there’s a slight chance that I’ve made a mistake somewhere

I actually never used/heard of this method before this thread.
I always applied the formula that gives the solution directly, given your quadratic equation above (in that form):
x 1/2 = – b/2 (+/-) sqrt((b/2)² – c)

Of course, both ways give the same solutions, but this way, there aren’t “a lot of equations” so you (@Erlend) might find that easier to grasp.

 
Flag Post

Completing the square is a means of solving the quadratic equation using simple, sound algebraic steps rather than by just using a formula that skips a number of the elementary algebraic steps

I have the impression that Erlend is the type of guy that wants to know why something works rather than the type of guy that wants a quick and easy solution to a problem

 
Flag Post
Originally posted by Dealmaster13:

Completing the square is a means of solving the quadratic equation using simple, sound algebraic steps rather than by just using a formula that skips a number of the elementary algebraic steps

I have the impression that Erlend is the type of guy that wants to know why something works rather than the type of guy that wants a quick and easy solution to a problem

Hence my link to wikipedia where the formula is derived in algebraic steps with the same variable names that Erlend used.
I don’t think it makes sense to reevaluate this solution again and again. As you stated yourself, a lot of equations hold the slight chance of mistakes.

Don’t get this wrong, your effort is appreciated. I just wanted to provide a different way to get to the solution.

 
Flag Post

But I don’t quite see your point, as all of the mathematical equations above bar the final line are not to be coded, which is the whole point of these calculations

You can state the quadratic formula, but it won’t directly help you understand how to derive it

I do appreciate you pointing out that such a formula is used in practice, though, at the very least to provide further insight into quadratic equations

 
Flag Post
Originally posted by Dealmaster13:

it won’t directly help you understand how to derive it

The wikipedia link does that.
It starts from a quadratic equation and ends with the formula.

 
Flag Post

That’s good to know

 
Flag Post

@Dealmaster13: Some good stuff in this thread, thanks for the educational reading ;-). I have two questions about implementing this type of thing (and before someone jumps in, it is for my own education, I find making my own implementations fun):

- The derivations here are all for sphere-sphere collisions, which have an easy algebraic representation. Can similar things be done for other collision hulls, particularly OBBs (and objects with angular momentum)? I currently have an instantaneous collision model (i.e. are the hulls overlapping right now), and was thinking of backtracking to work out collision times.

- How do you deal with the situation where two objects are in continual contact, but other collisions are still possible, e.g. a pool ball rolling along a table? The time of collision with the table is always 0 and will result in timeslicing to 0 and infinite loops if you don’t watch it.

 
Flag Post

You raise some very good points.

The main theory is based on sphere-sphere or circle-circle, but obviously we’ve also mentioned what would be sphere-line; so that would be fine as well.

Collision hulls (irregular polygons; curved surfaces potentially require a lot of work) are definitely workable, with OBBs (or perhaps more appropriately, initially bounding spheres) becoming a necessary feature for collision detection, as high vertex (and side) counts will cause computation requirements to balloon.
When you factor in angular momentum, things start getting tricky, but again, it’s workable by considering the appropriate bounding sphere for efficiency and then encoding the geometry of each polygon side as a complex expression of time (perhaps Newton Raphson, which obviously can be extremely accurate, would be a more suitable approach if finding an expression for time is indeterminable). I suppose it’s easier said than done, and attempting the implementation may raise issues that weren’t immediately obvious.

I was first sceptical about the idea, but I think that changing velocities is even permissible, given that velocity can be expressed as a function of time in a reasonable manner. Again, it’s the process of implementing a potential solution which will best determine the plausibility of the algorithm employed.

Concerning the continual contact, I am assuming that you are referring to a ball rolling along the side of a table – a very important side case that needs to be dealt with, as you’ve discovered. One solution is to completely ignore glancing blows between two balls, and the brushing of a ball against a surface, while ensuring for the latter that while the ball is in contact (which would be until its next collision) the ball’s velocity is affected appropriately (i.e. friction). Care needs to be taken to ensure that collisions that have just been dealt with (and thus have t = 0) are removed from the queue.

 
Flag Post

I’ve been very busy lately so couldn’t reply.

Thank you all for helpful input!

@ 2 latest post:

I don’t understand all the words (Collision hull?) but anyway, I’ve wondered myself also: When I start dealing with irregular polygons, will this way of finding out if they have collided still be ideal? I guess you take each pair of vectors and make an expression for t when those two vectors initially touch in time, considering the rotation momentum as well.

Originally posted by Dealmaster13:

This collision detection can be efficiently implemented:
1. Initialise the system by performing collision checks on every pair of balls (O(n2) in number of balls), taking into account world boundary collisions if necessary
[…]

I think I understand this! Is step 10 next frame or iterations in the same frame? Steps 1-9 are all in the same frame right? This is so much better and accurate than what I had in mind: iterate and solve all collisions in no particular order until there are no collisions left or limit is reached.

I’ll have to start coding this when I get the time. (Then I bet more questions will arise..)

I’m a newcomer when it comes to physics (I don’t get to take it at school either) so hope you have patience with me :P

 
Flag Post
Originally posted by ErlendHL:

Is step 10 next frame or iterations in the same frame? Steps 1-9 are all in the same frame right?

Steps 1-9 are in the same frame, while step 10 represents the transition to the next frame, at which point either you decide to perform the tests and move everything by one frame’s movement regardless of whether collisions took place (what is typically done, as this way time passing is evident), or alternatively thanks to the beauty of the method, you can fast-forward to the next collision and take it from there (another interesting observation is that by reversing all velocities, you can accurately rewind time as well, most importantly without the need of any kind of time-stepping – i.e. how collisions are determined in most programs)
You’ll want to review BobJanova’s post and my previous one

 
Flag Post

Ah okay!
Still very busy so things are not rolling superfast over here.

One things I’ve been thinking about (algorithm, like the 10 steps you mentioned):


Have a variable frameProgress = 0 on frame init

1. Do the t-test on every pair of circles. Get the pair with the lowest positive t value. Appropriate values of t here should be between 0 and (1 – frameProgress)

2. Add t to frameProgress (frameProgress += t)

3. Recalculate the two circles’ velocities. Move all circles based on that value of t (i.e. move them with their respective xSpeed and ySpeed divided by t found in step 1.)

4. Go back to 1. Break loop if no appropriate t values are found. Also, frameProgress should never exceed 1.


To me this sounds like a good idea, at least when I visualized it in my head. Hope you understand my way of thinking/explaining.

I’m not sure if this is better or worse than the way you explained, but I can’t think of any issues atm.