Question about impulse-based dynamics and collision/contact

[balthazar]

Hey

I'm trying to make a physics engine for a game, and I've lately been considering making it (at least partly) impulse-based. The only problem is that the game will have many situations with fairly complex configurations of simultaneous collisions/contacts. So I've been looking at Jan Bender's paper on how to do this efficiently and accurately.

Anyway, a super simple outline of the algorithm is as follows (I have edited this after I posted it to make it clearer):

Perform collision detection( detect contact points and normals );
while( collision occcured = ( u[rel]*n <= -sqrt(2g*ec) ) ) compute collision responses;
Perform simulation step with contact handling;

Where u[rel]*n is the relative velocity of the contact points dot producted with the contact normal, for each contact detected. g is the acceleration of gravity, and ec is the tolerance for the collision detection. So when I write:

collision occcured = ( u[rel]*n <= -sqrt(2g*ec) )

It means that each pair of contact points is checked, to see if the relative velocity by which the contact points move TOWARDS each others (or towards more penetration) >= sqrt(2g*ec). Hope this is not completely incomprehensible.

The idea of the collision loop is to let the collisions correctly propagate before the simulation step is performed. So, in the instance of the office toy with five balls hanging adjacent to each others, if you pull out one ball and let it hit the others, the collisions will correctly propagate through the chain of balls. My question is whether this could cause infinite loops? If the colliding bodies are "locked in" between static bodies, then perhaps the collisions might just propagate forever? Jan Bender says nothing about this in his paper. I have been trying to think of situations when it could happen during "natural simulation" (with no impulses imposed on the bodies by the user of the physics engine, and no bodies' positions being explicitly moved by the user), but haven't come up with anything yet. Whatever forces are applied to the bodies, like friction caused by resting contact, is not considered during the collision loop. So, if the bodies have a relative velocity when they hit each others, they must be coming from somewhere, and I believe there will eventually be a "way out" for the propagating impulses. Please tell me if this is correct.

But consider a row of balls (for 2D), locked in between two static bodies, and the user artificially imposes an impulse on one of the balls, making it collide with the next ball? Then I believe the impulses would just go on forever propagating back and forth. At least if the coefficient of restitution is 1. If it is less than 1, still, an unnecessary number of iterations will take before the collisions are damped enough to consider it "static contact" rather than collisions.

So my questions are:
1) Have anyone tried to implement Jan Bender's algorithm?
2) Have you tried to come up with a way to detect possible infinite loops during the collision resolution (or have some good ideas)?
3) May I trust that this type of situation would not happen if there is no "external" application of impulses/moving of bodies by the user?

[Jan Bender]

Hi,

The idea of the collision loop is to let the collisions correctly propagate before the simulation step is performed. So, in the instance of the office toy with five balls hanging adjacent to each others, if you pull out one ball and let it hit the others, the collisions will correctly propagate through the chain of balls. My question is whether this could cause infinite loops? If the colliding bodies are "locked in" between static bodies, then perhaps the collisions might just propagate forever? Jan Bender says nothing about this in his paper. I have been trying to think of situations when it could happen during "natural simulation" (with no impulses imposed on the bodies by the user of the physics engine, and no bodies' positions being explicitly moved by the user), but haven't come up with anything yet. Whatever forces are applied to the bodies, like friction caused by resting contact, is not considered during the collision loop. So, if the bodies have a relative velocity when they hit each others, they must be coming from somewhere, and I believe there will eventually be a "way out" for the propagating impulses. Please tell me if this is correct.

In my impulse-based method friction is simulated by impulses and not by using forces. So friction is considered in the collision loop. Take a look at my paper:

http://www.impulse-based.de/index.php?v ... t&Itemid=9

But consider a row of balls (for 2D), locked in between two static bodies, and the user artificially imposes an impulse on one of the balls, making it collide with the next ball? Then I believe the impulses would just go on forever propagating back and forth. At least if the coefficient of restitution is 1. If it is less than 1, still, an unnecessary number of iterations will take before the collisions are damped enough to consider it "static contact" rather than collisions.

These situations can be resolved by using a shock propagation algorithm. Take a look at my PhD or read the paper "Nonconvex Rigid Bodies with Stacking" from Eran Guendelman to get more information about this.

1) Have anyone tried to implement Jan Bender's algorithm?

Yes, me

2) Have you tried to come up with a way to detect possible infinite loops during the collision resolution (or have some good ideas)?

Try the shock propagation algorihm.

3) May I trust that this type of situation would not happen if there is no "external" application of impulses/moving of bodies by the user?

I think the situations you mentioned will propably never occur during the simulation.

Hope that helps,

Jan

[balthazar]

Thanks a lot for your reply.

In my impulse-based method friction is simulated by impulses and not by using forces. So friction is considered in the collision loop. Take a look at my paper:

http://www.impulse-based.de/index.php?v ... t&Itemid=9

Yes, I understand that. I didn't make myself clear. Friction related to the collisions themselves is definately considered during the collision loop. What I meant was that friction, or external forces not releated to the collisions is not considered. I believe this is physically correct too, since the bodies are rigid. I just mentioned it because in all my mental scenarios where the collision loop might fail, there was always some large external force involved, preventing the bodies from escaping. But this would not cause a real problem because the collisions and the velocity changes happen in 0 time, so these forces would not have any impact.

These situations can be resolved by using a shock propagation algorithm. Take a look at my PhD or read the paper "Nonconvex Rigid Bodies with Stacking" from Eran Guendelman to get more information about this.

Thanks a lot, I will check it out. Thanks for your papers, I'm looking forward to trying out your solutions...