How to handle multiple simultaneous elastic collisions?

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.