Take the 2-minute tour ×

I'm computing the result by colliding pairs of 2D convex objects (without rotation), using the basic equations on wikipedia. However, when there are dependencies, like two objects hitting another object at the same time:

enter image description here

Such as here, with objects 1 and 2 hitting 3 at the exact same time, the pair-wise approach fails. Depending on the order I compute the collisions (1-3 first or 2-3 first), I will get different results. Repeated iteration through the collisions will still give order dependent results.

I already have it setup so I can figure out what objects are in contact with each other, so my code will know when computing one of these pairs that object 3 is colliding with another object at that moment (so the 1-3 collision will know about the 2-3 collision, and vice versa). I'll know what edges/corners are in contact with what, as well.

Whatever solution needs to be robust... For instance, if the setup is made more complicated like these 2 examples:

enter image description here

The process needs to be able to handle that and worse. Any possible chain of simultaneous contacts/collisions. I'll have all the data on hand describing them, so I "only" need to know how to resolve the general case of these systems. I'm not doing anything with rotation currently, which simplifies things.

It seems like it would involve grouping objects together, but the interference caused by edges that aren't orthogonal (see that last example with a hexagon) would seem to make that approach fail.

I saw a similar question that was asked before, but the answer given was never checked (dead end?). I'm not sure how shock propagation would resolve my first example, either, as C is moving away after the first collision... so what shock is there to propagate? edit: Ok, I see now that simultaneous collisions and shock propagation are two different ideas, that's why it didn't seem useful.

share|improve this question
There actually is an answer to the question you link to, and that may be what you're looking for. –  Alex Szatmary May 7 '13 at 16:23
@AlexSzatmary I'm not sure how that approach is applicable to my first example. Once one collision occurs, C will be moving away... There's no shock to propagate when dealing with the second collision. –  user173342 May 7 '13 at 16:27

3 Answers 3

up vote 4 down vote accepted

This kind of dynamic simulation of multi-contact physics gives rise to a linear complementarity problem. There are algorithms available to solve this kind of problem; the math is related to that used for linear programming problems.

The need for solving this kind of problem is more common than you might think. Any kind of vaguely realistic simulation (i.e., with gravity, ground, and inelastic collisions) will soon end up with objects resting on each other; accurately and robustly handling the transition from dynamic collisions in space, to sliding and rolling objects, to "block-stacking" configurations, can be technically challenging.

I recommend looking for books or other resources on the subject. Exactly which techniques you actually need will depend on your specific application, but you may be able to find some libraries that will help.

share|improve this answer


That is correct. This is due to how the physics of collisions work. Consider this simple example, using your first figure:

m_1 = m_2 = m_3
u_1 = u_2
u_3 = 0
x_1 = x_2 + d

The only difference between 1 and 2 is that 1 is closer to 3 by d. 1 hits 3 first, stops, and v_3 becomes u_1 (u is initial and v is final velocity). Because u_2 and the new v_3 are the same, both objects 2 and 3 will proceed to the right at constant velocity with a constant distance, d, between them; they will never touch. If 1 and 2 are swapped, that is, if x_2 = x_1 + d, then 2 hits 3 and stops, and 1 trails after 3 by d.

The order of the collisions matters, and treating simultaneous collisions like two successive instantaneous collisions will give conflicting results depending on the order in which the collisions are processed.

Collisions occurring truly simultaneously is often a pathological case (mathematically) and is probably not necessary to resolve correctly for a game, or even for many scientific models.

If it really is important to correctly resolve multiple elastic collisions, the math for that can be worked out, but you would need to add additional assumptions. The elastic collision of two bodies is given by conservation of momentum:

m_1 u_1 + m_2 u_2 = m_1 v_1 + m_2 v_2

and conservation of energy:

(1/2) * m_1 u_1^2 + (1/2) * m_2 u_2^2 = (1/2) * m_1 v_1^2 + (1/2) * m_2 v_2^2

Given the initial velocities of the objects, the velocities of the two objects post-collision could be found. If you wanted to modify these equations to account for a third object,

m_1 u_1 + m_2 u_2 + m_3 u_3 = m_1 v_1 + m_2 v_2 + m_3 v_3
(1/2) * m_1 u_1^2 + (1/2) * m_2 u_2^2 + (1/2) * m_3 u_3^2 = (1/2) * m_1 v_1^2 + (1/2) * m_2 v_2^2 + (1/2) * m_3 u_3^2

a third independent equation would have to be introduced. A simple constraint could be that the momentum transfers of objects 1 and 2 should be proportional to their masses:

m_1^2 (v_1 - u_1) = m_2^2 (v_2 - u_2)

This would be nice for the situation depicted in figure 1: intuitively, I would expect 1 and 2 to have the same final velocity, and this constraint would give you that. Be warned, this equation doesn't have a clear physical basis and may give strange results in other scenarios. Experiment and see what looks right.

The equations you mention on Wikipedia (the standard, quite useful, textbook equations) assume that there is an instantaneous transfer of momentum between the two objects. This is not really true for anything in real life. When one billiard ball hits another, the balls deform very slightly, and this deformation takes time; this time is on the scale of milliseconds or less and is typically negligible.

share|improve this answer
All of this is very true, but my simulation is much simpler than reality. Time has discrete steps, and objects are rigid. So while a truly simultaneous case may be pathological, I have the unfortunate need to have to handle it since it is an unavoidable possibility in my simulation. And I need to handle it in a deterministic way, or else there will be desyncs between different clients... Anyway, what would be the assumptions for dealing with this? –  user173342 May 7 '13 at 16:45
user173342, are you trying to model what really happens, or merely something plausible (eg for a game)? Very different. Real life simulations adjust the step size depending on the configuration (distance between objects and speed). While your program may be deterministic and always produce the same output, in real life what happens when you do the opening break in billiards is not. If you want it to produce plausible, realistic results you will probably have to introduce random noise as happens in real life. Making this an authentic simulation is hard. Merely plausible is easier. –  Peter Webb May 8 '13 at 9:47

Do the individual collisions one-by-one, but always use the initial velocity of each object. When done, add up the velocity-changes for each object.

(v1_1,v3_1) = collide(u1,u3,m1,m3)
(v2_2,v3_2) = collide(u2,u3,m2,m3)
v1 = u1 + (v1_1 - u1) = v1_1
v2 = u2 + (v2_2 - u2) = u2_2
v3 = u3 + (v3_1 - u3) + (v3_2 - u3) = v3_1 + v3_2 - u3

This way, it will not be order-sensitive.

share|improve this answer

Your Answer


