Hi, I've implemented rigid body simulation using sequential impulse, so far everything is working well

There's something I don't understand about the math behind, though

In Richard Tonge's pdf "iterative rigid body solver" in GDC 2013, he stated that the reason we use sequential impulse is that linear system would eliminate velocity at all contacts (with "attracting impulse"), causing contact that should break not breaking.

[attachment=32642:RIchard.PNG]

Does that mean no global solver would work? Since I read this on Erin Catto's "understanding constraint" in GDC 2014:

[attachment=32645:Erin.PNG]

implying we can use global solver. I think I got things mixed up somewhere.

Inequality constraints and limits are what bring about the complementary conditions, if I'm not mistaken. Without these physics simulation could just be a familiar system of linear equations. In Tonge's example we have a contact constraint (inequality constraint), the LCP says that if the bodies were to separate (perhaps gravity got flipped upward, or it slide off the table) we don't enforce it. But if the bodies are going to interpenetrate, we enforce the constraint. We need this condition because otherwise the constraint would just strip away all velocity along the contact surface's normal all the time no matter what.

If you look into the formulation of the LCP you see the complementary condition states exactly this, by forcing one of two terms to always be zero.

Global LCP solvers can work, but not global linear solvers, if LCPs are mixed into the system. A mixed-linear complementary problem (MLCP) is a system of both linear and complementary problems.

Sequential Impulses implements a solver capable of handling the LCPs mixed into the system, allowing for a Gauss-Seidel-alike iterative solution to be achieved.

No, it means by linearizing an LCP you don't account for vanishing contact points, giving birth to an unplausable and unrealistic simulation.

http://www.cs.cmu.edu/~baraff/papers/sig89.pdf. 227, Section 5.3. (Warning: Predated literature. Still good and valid though.)

In addition, local/iterative solvers and integrators linearize or skip over non-linearities present in some constraints or forces (e.g. "quadratic" friction, air resistency, etc.) but still give sufficient results for the purpose of game physics. They can handle redundant solutions very nicely as well (e.g. a table with 4 legs on a plane).

Think of a ball resting on the ground. The contact point is only active if the ball is accelerating downwards. In the moment you pick it up there is no contact force.

I think the confusion here is about the term linear system. Richard means a system of linear equality equations. You cannot model contact with equality constraints. You model contacts using the Signorini conditions (should also be in the citied paper) which makes the problem an LCP. The LCP is still linear, but with inequalities and the complimetary condition. If you would use a linear condition you would get sticky contacts.

The complimentary condition is what is essential for modeling contacts. If the relative acceleration is larger zero the contact force is zero. Or the contact force is active and removes all relative acceleration.

A good excersise is to solve a 1d LCP and then translate the meaning to the contact problem.

So yes, global LCP solvers can indeed solve this as well. There is a whole lot of problems with overconstrained systems. The four leg table is a good example. The solver can give you mg/2 in two diagonal legs and you would get the correct dynamic response. All variations that create equilibrium are feasible, but we know that we have in each leg a force of mg/4. I think Mirtichs PhD talks a bit about these problems.

Inequality constraints and limits are what bring about the complementary conditions, if I'm not mistaken. Without these physics simulation could just be a familiar system of linear equations. In Tonge's example we have a contact constraint (inequality constraint), the LCP says that if the bodies were to separate (perhaps gravity got flipped upward, or it slide off the table) we don't enforce it. But if the bodies are going to interpenetrate, we enforce the constraint. We need this condition because otherwise the constraint would just strip away all velocity along the contact surface's normal all the time no matter what.

If you look into the formulation of the LCP you see the complementary condition states exactly this, by forcing one of two terms to always be zero.

Global LCP solvers can work, but not global linear solvers, if LCPs are mixed into the system. A mixed-linear complementary problem (MLCP) is a system of both linear and complementary problems.

Sequential Impulses implements a solver capable of handling the LCPs mixed into the system, allowing for a Gauss-Seidel-alike iterative solution to be achieved.

No, it means by linearizing an LCP you don't account for vanishing contact points, giving birth to an unplausable and unrealistic simulation.

http://www.cs.cmu.edu/~baraff/papers/sig89.pdf. 227, Section 5.3. (Warning: Predated literature. Still good and valid though.)

In addition, local/iterative solvers and integrators linearize or skip over non-linearities present in some constraints or forces (e.g. "quadratic" friction, air resistency, etc.) but still give sufficient results for the purpose of game physics. They can handle redundant solutions very nicely as well (e.g. a table with 4 legs on a plane).

Think of a ball resting on the ground. The contact point is only active if the ball is accelerating downwards. In the moment you pick it up there is no contact force.

I think the confusion here is about the term linear system. Richard means a system of linear equality equations. You cannot model contact with equality constraints. You model contacts using the Signorini conditions (should also be in the citied paper) which makes the problem an LCP. The LCP is still linear, but with inequalities and the complimetary condition. If you would use a linear condition you would get sticky contacts.

The complimentary condition is what is essential for modeling contacts. If the relative acceleration is larger zero the contact force is zero. Or the contact force is active and removes all relative acceleration.

A good excersise is to solve a 1d LCP and then translate the meaning to the contact problem.

So yes, global LCP solvers can indeed solve this as well. There is a whole lot of problems with overconstrained systems. The four leg table is a good example. The solver can give you mg/2 in two diagonal legs and you would get the correct dynamic response. All variations that create equilibrium are feasible, but we know that we have in each leg a force of mg/4. I think Mirtichs PhD talks a bit about these problems.

@DirkGregorius @IrlanRobson @RandyGaul

Hi guys, thank you for your responses :D

I think this is a bit too much for me :wacko: , what you guys said get mixed up with things in my head (I'm at the point where I don't really know what I understand or not understand anymore lol).

I've been doing some reading and I think these are my confusions

Right now, this is my current understanding / misunderstanding (please correct me if I'm wrong):

• LCP only exist in case of multiple contacts
• LCP is linear inequalities (since there may be more than one correct magnitudes) with some extra conditions (if relative velocity > 0, then magnitude = 0, because no impulse applied anymore)
• This LCP Mz+q >= 0 (and their extra conditions),is a constraint function that is applied when we're trying to compute magnitude of impulse
• We need to find impulse magnitude that a) is more than 0 b) after applied, sets relative velocity at contact point >= 0 for all contacts
• These magnitudes are different for each contact points

And this is the questions in my head:

• It says LCP is inequality Mz + q >= 0 where size of the matrix depends on how many contacts we have, how do we put into that inequalities so we can find magnitude for each contact point? Like, what is M, z, and q? which one is impulse magnitude, etc?
• In Baraff's course notes, he stated that we need to relate to force in case of multiple contact points (the paper Irlan posted also mentioned this). There's a youtube lecture video that use that course notes (I failed to understand it though), but he said it's the same linear complementarity problems (in the paper itself, it only says quadratic programming problem). Why do we need to relate to force?
• I still don't understand how the case of multiple contact point without vanishing contact is also LCP (for example, stacking box in one dimension in Erin's "Understanding Constraint").

LCP only exist in case of multiple contacts

Nope, this is wrong. The LCP exist even for a single contact point. We need an LCP to model contacts properly, not to handle many contacts.

I should have not posted that paper as Baraff solves for forces globally, sorry. You don't need to relate to force using the SI/PGS if you want.

Thus, the relationship between a force F and an impulse P is simply: P = integral( F dt ) from t1-t2 or P = m * ( v(t2) - v(t1) ) or P ~= F * dt, that is, the change in velocity.

Kenny Erleben PhD thesis talks about the e/in-equalities your asking.

I should have not posted that paper as Baraff solves for forces globally, sorry. You don't need to relate to force using the SI/PGS if you want.

Thus, the relationship between a force F and an impulse P is simply: P = integral( F dt ) from t1-t2 or P = m * ( v(t2) - v(t1) ) or P ~= F * dt, that is, the change in velocity.

Kenny Erleben PhD thesis talks about the e/in-equalities your asking.

it's cool, it's cool :D

I'm taking a look at that, thank you

Nope, this is wrong. The LCP exist even for a single contact point. We need an LCP to model contacts properly, not to handle many contacts.

Ah, I guess you're right. So, for single contact case

I just look at Baraff's paper again, since he said relative velocity at contact after collision Vrel = n • ((Pa + (jn/mass a)) - (Pb + (jn/mass b)))

where j is magnitude, n is contact normal, Pa and Pb is linear + angular velocity at contact before collision, one from each body

I guess we can express magnitude j as linear function j = c Vrel + d ? is this what LCP on single contact case looks like? setting j or vrel > 0 ?

you guys seem really good at this, better than lecturer at my univ :wacko: :D

You must simply *clamp* j to [0, infinity] to disallow the contact to suck the body. By doing this you've satisfied the contact LCP.

You can *assert* that dot(vrel, normal) >= 0 after solving a *single* contact if you think there is something wrong with your equations. That's another advantage of the SI, in that it allow us to do this cheaply, right after applying the impulses that bring the relative velocities to zero.

You must simply *clamp* j to [0, infinity] to disallow the contact to suck the body. By doing this you've satisfied the contact LCP.

You can *assert* that vrel >= 0 after solving a *single* contact.

Hi Irlan :D

Yes, I think I understand the algorithm itself. I make my accumulated J to 0 if it's less than 0 after current iteration, that way my impulse will only push or do nothing at all.

I just can't seem to understand the underlying LCP problem, the math things I mentioned above.