Simultaneous inelastic collision response

[jedediah]

I'm trying to figure out how to calculate collision response in a simulation I'm working on. Here are the details:

• 2D
• Objects are made of axis-aligned edges and do not rotate
• Object masses are whole numbers
• Collisions are completely inelastic
• No friction
• Collision/separation times are calculated exactly
• Entirely possible for objects to have equal velocity and this is explicitly tracked
• Complex simultaneous collisions are possible

The goal of the simulation is to be very precise. The simulation groups objects into shared inertial frames, independently on each axis. Collisions can happen when objects in two different inertial frames have aligned edges. Many objects can be involved in a collision, but only two inertial frames and one axis.

I can already find all the contacts and their normals (which are either 1 or -1). Some pairs of objects may be interlocked and thus have both 1 and -1 contacts. There may be cycles in the contact graph.

What I'm trying to figure out is how to calculate new velocities for all the objects. For only two objects, their shared velocity after colliding will be the sum of their prior velocities weighted by their masses. But with a network of simultaneous contacts, it seems to be more complicated.

Here is a simple example. After this collision, all objects should have velocity 2/3. But if I handle the collisions sequentially, one of the yellow objects will end up with a different velocity than the other two.

I feel like there should be a way to solve this in general, but after much tinkering it still escapes me.

 

[AlephZero]

Here is a simple example. After this collision, all objects should have velocity 2/3. But if I handle the collisions sequentially, one of the yellow objects will end up with a different velocity than the other two.

Why do you think that?

Use conservation of momentum = mass x velocity, which is the same as as your "sum of the prior velocities weighted by their masses".

If the top two collide first:
Momentum before = 7x1 + 5x0 = 7
Velocity after = 7/(7+5) = 7/12
Then for the second collision
Momentum before = 3x1 + 12x(7/12) = 10
Velocity after = 10/(3+12) = 2/3.

You get the same final result if the collisions occur in the reverse order
Momentum before first collison = 3x1 + 5x0 = 3
Velocity after = 3/(3+5) = 3/8
Momentum before second collision = 7x1 + 8x(3/8) + 10
Velocity after = 10/(7+8) = 2/3

If the collisions are simultaneous,
Momentum before = 7x1 + 5x0 + 3x1 = 10
Velocity after = 10/(7+5+3) = 2/3.

 

[jedediah]

Ok, but doesn't that treat all the objects as if they are glued together? The yellow objects can't pull each other. It doesn't make a difference in this case, but in other cases there might be separations. That's really my problem: figuring out which objects have the same velocities after the collision.

For example, I'm pretty sure that the correct outcome of this is that the top two blocks have velocity 1/3 and the bottom two have velocity 2/3 (given yellow initially v=1 and blue v=0). So the two small blocks collide and then instantly separate. This can be calculated by doing the top and bottom collisions first, then seeing that the middle contact isn't a collision. But if I were to look at the middle contact first, it would look like a collision. Generally speaking, how do I figure out how to group the objects?

 

[jedediah]

For anyone who is interested, I've been researching this problem for the last few days and discovered that it's more complicated than a single calculation. It's a system of equations, but some of them are inequalities, e.g. the non-penetration constraints, and may or may not bound the solution. Apparently a general solution involves solving a "linear program", which is a new subject for me.

As I understand this linear programming thing, each equation defines a hyperplane boundary of a convex n-dimensional polytope, where n is the number of variables in the equations. The polytope contains the "feasible" solutions and each vertex is where some particular subset of equations binds the solution. Finding the actual correct solution involves "pivoting" equations in and out of the binding set until the particular set is found that maximizes/minimizes some "objective function". This is equivalent to hopping from vertex to vertex of the polytope, towards the direction defined by the objective function, until the extreme vertex in that direction is found. But first, the entire system of equations needs to be "normalized" by introducing extra variables, so that the inequalities become equalities and all variables are >= 0. Also, a starting vertex needs to be found by introducing "artificial variables" and solving a different linear program to minimize them. If they can be minimized to zero, then they are removed and the original problem can then be solved. Otherwise, the original problem has no solution.

I am still digesting this topic, particularly the parts about normalization and artifical variables. I would like to be able to visualize these steps, but none of the material I've read takes the geometric interpretation that far.

But I am even more confused about how to apply linear programming to my collision response problem. The constraints for my problem, as far as I know, are these:

• conserve momentum -- total (mass $\times$ velocity) is constant
• no penetration -- (outgoing relative velocity) $\cdot$ normal $\geq$ 0
• no pulling -- (collision impulse) $\cdot$ normal $\geq$ 0
• inelastic collisions -- (outgoing relative velocity) $\cdot$ (collision impulse) = 0

The last one is interesting: it asserts is that if two objects separate after the collision then they didn't exchange any momentum with each other. I'm pretty sure that's implied by perfectly inelastic collisions, but not certain.

But how do these constraints fit into the linear program? What am I minimizing/maximizing?

 

[AlephZero]

You are using a different definition of "inelastic collision" from the standard one, where (by definition) the objects always stick together when they collide.

The last one is interesting: it asserts is that if two objects separate after the collision then they didn't exchange any momentum with each other. I'm pretty sure that's implied by perfectly inelastic collisions, but not certain.

That makes no sense to me. If the objects don't "exchange" momentum, the momentum of each object doesn't change. Therefore the velocities don't change. That is impossible unless the objects never collide at all.

You seem to be trying to make a model where the collision is sometimes perfectly inelastic, and sometimes partially inelastic, depending how hard the objects "try to bounce apart". If you start with just 2 objects, you can probably sort out your thinking by working in a reference frame fixed to the combined CG of the two objects. Since the actions and reactions are equal and opposite, this is an inertial reference frame. If the CG doesn't move before the collision, it doesn't move after it.

So I think you want to model a situation where if the relative velocity of the objects before the collision is "small" they stick together, but if it is "big" they bounce off each other. (I'm not quite sure how you are trying to define "big" and "small".)

Even if it my interpretation of what you mean is wrong, it might help to sort out your own thinking!

 

[jedediah]

You are using a different definition of "inelastic collision" from the standard one, where (by definition) the objects always stick together when they collide.

That makes no sense to me. If the objects don't "exchange" momentum, the momentum of each object doesn't change. Therefore the velocities don't change. That is impossible unless the objects never collide at all.

Exactly.. if they didn't stick together then they didn't collide, because they were pulled apart by other collisions at the instant in question. And this can happen even if they had negative relative velocity before the contact, as in my second example image. The two small pieces are in contact for zero time and thus exchange zero momentum with each other.

But more often it will happen when two objects are already in contact and a third breaks them apart. Consider my first example but make the velocity of the bottom piece 0. Then it's obvious that its momentum doesn't change, but the entire system still has to be solved to know that, generally speaking.

My intuition is that in no case can two pieces exchange momentum and be pulled apart by other collisions at the same instant, but I don't know how to prove that.

In other news, I discovered that this is not actually a linear programming problem, but a "linear complementarity problem", which is similar and can be solved in similar ways. It looks like I will need to test particular combinations of the contacts colliding to see if the non-penetration and non-pulling constraints hold. And there is some way to choose new combinations that is guaranteed to get me closer to the solution.

http://en.wikipedia.org/wiki/Linear_complementarity_problem