How to handle multiple simultaneous elastic collis

Question

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:

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:

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.

Answer 1

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.

Answer 2

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.

Answer 3

Depending on the order I compute the collisions (1-3 first or 2-3 first), I will get different results.

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.