Lagrange multipliers

c0der · **Joined:** Sun Jul 08, 2012 11:32 am **Posts:** 59

Is it necessary to learn this topic to model constraints? I have successfully modelled joints from Erin Catto's presentation (2006). Also, why would you model a penetration/friction constraint when I simply used SAT and normal/tangential impulses with sleeping rigid body state to model stacked boxes?

Thanks !

bone · **Joined:** Tue Feb 20, 2007 4:56 pm **Posts:** 179

Erin Catto's demonstration uses velocity-based constraints; I usually think of Lagrange multipliers as used with acceleration-based constraints, but I'm not sure of the exact definition and it could be the same thing. I think if you've modeled constraints, you've either used Lagrange multipliers without knowing it or something very similar.

As for using contact constraints, I think it certainly becomes necessary when you are using articulated bodies that collide with each other. Not everything is stacking boxes! (Although admittedly that is one decent test of a physics system.)

Dirk Gregorius · **Posted:** Mon Jul 09, 2012 5:17 pm

Here is a great introduction into Lagrange multipliers: http://www.slimy.com/~steuard/teaching/ ... range.html

I don't think it is necessary to understand this method to model constraints. To be honest I worked through this some years back and forgot at the moment again how they are related though I model constraints all the time

. Erin's presentations is great. He introduced the common approach to model constraints from computational dynamics to the game physics community. Start with a position constraint, build the time derivative and identify the Jacobian by inspection. Don't start with a velocity condition and try to guess a stabilization term. This doesn't work so great in practice from my experience. If you follow this advice you safe yourself a lot of problems.

mewert · **Posted:** Mon Jul 09, 2012 9:09 pm

I also have written physics engines without knowing how Lagrange multipliers work. If you view the constraints geometrically and directly apply the principle of virtual work, you don't even need to know calculus.

However, now I'm attempting to do some research into extending a "solver" to work with Space-Time constraints. The Witkin/Kass paper is great, but I need something orders of magnitude more efficient.

Anyways I'm going back and trying to figure out how to get J M^-1 J^t lambda = c from Lagrange Multipliers. The papers I've seen appear to be making some kind of implicit assumptions and skipping a step or two, the result being that I can't figure out what the original equations where.

So:
Lagrange Multipliers.
Minimize f(x) subject to the constraints g(x) = c

Put into lagrange mult form.
f(x) - lambda(g(x)-c) = 0

The solutions for lambda will be found where the gradient of that equation = 0.

So... what are f(x) and g(x) used to arrive at the familiar JMJt formula?

- Michael Alexander Ewert

Erwin Coumans · **Posted:** Wed Jul 11, 2012 11:37 pm

Hi Michael,

Good to see you again!

You can use Newton's second law f=m*a and the constraint equations C(q)=0 to get to the Lagrange Multipliers JMJt formulation,
see the "Constrained Dynamics in 4 Easy Steps" from Chris Hecker in the Math section:

http://chrishecker.com/How_to_Simulate_a_Ponytail

There are a lot more details in our Eurographics 2012 paper "Interactive Simulation of Rigid Body Dynamics in Computer Graphics", the PDF is here:
http://code.google.com/p/bullet/downloa ... akechanges

mewert · **Posted:** Thu Jul 12, 2012 5:59 pm

Thanks Erwin, good to be back.

Both those papers use the same trick as Baraff's "Linear Time Dynamics Using Lagrange Multipliers". Which skips an important step. The objective function isn't stated anywhere. I don't know what is being minimized.

This is the Lagrange Multiplier Method:
1) problem statement
Minimize f(x) subject to the constraints g(x) = c

2) Lagrange equation form
L = f(x) - lambda(g(x)-c) = 0

3) Calculate Jacobians
Find the gradient of L w.r.t x and lambda. Set that to 0.

4) Do some algebra
Solve for lamdba.

The Baraff formulation includes lambda in the problem statement. Lambda is defined from the outset as the constraint force. It starts closer to step 4. I need to see what steps 1 and 2 are, so I can get some deeper insight into how to extend this problem into the 4th dimension ( time ).

I suspect the objective function might be the back-euler integration step of the kinematic equations.

- Michael Alexander Ewert

Erwin Coumans · **Posted:** Thu Jul 12, 2012 11:53 pm

Hi Michael,

I asked Kenny Erleben for advise on f(x) and g(x) and here is some of his response:

Kenny wrote:

f(x)

would be the free energy of the system that is the kinetic energy minus the potential energy

and

g(x) = c

would be a holonomic scleronomic constraint function

So how do you get from those f(x) and g(x) to our JMJt?

Kenny wrote:

Oh, pain:-) Define

L(t,x,v) = 1/2 m v(t)^T v(t) + 1/2 w(t)^T I(x(t)) w - m g h(x(t))

Solve the variational problem (Hamiltons principle)

delta S(t,x,v) = 0 subject to C(x(t)) = 0

where the total "free" energy is given as

S = int_0^T L(t,x,v) dt

and the scleronomic constraint is defined as

C(x) = h(x)

Using Lagrange multipliers we now solve for

delta S^prime = 0

where

S^prime = int_0^T L(t,x,v) - lambda C(x) dt

and we have

L^prime(x,v) = L(t,x,v) - lambda C(x)

Then the Euler-Lagrange equations are given by (this is hairy so trust me on this)

d_x L^prime - d_t ( d_v L^prime ) = 0

where d_x and d_v and d_t are partial derivatives wrt. x, v and t respectively. Any solution to the EL equations will be a first order minimizer to the functional S^\prime and that is all what you care about in physics, If you do the calculus and work the algebra you should get the formula answer you are looking for.

The first text book example is often to throw a single unconstrained particle through this machinery and then one will rederive Newtons second law of motion.

Kenny wrote:

The best source for it that I ever have read is the book variational mechanics by Cornelius Lanczos. If you don't not care about non-holonomic constraints then you can pick up a physics book such as Goldstein's analytical mechanics that will explain the ideas too. In our STAR paper we took a different approach (vectorial mechanics instead of variational mechanics) in deriving all this.
If you are not scared of math you can dig into some of the papers by Claude Lacoursiere, his PhD thesis might be a good place to start. I seem to remember that Claude explains these details quite well and detailed.

Does that help?
Erwin

mewert · **Posted:** Fri Jul 13, 2012 12:22 am

Awesome. Very helpful. That's makes sense to me now. It matches up well with the Witkin/Kass Space-Time Constraints paper.

Still a lot of work to do though!

Basically I'd like to see if some of the tricks we use to reduce the computational complexity of the Rigid Body Dynamic Solvers we all know and love can be applied to a Space-Time RB solver. Since a retreat back to a O(n^2) solver for each time-slice wont be practical in my life-time

I figure that if the next-gen consoles are an order of magnitude faster than current-gen, it might be feasible to use a Space Time Constraints solver for some simple scenarios.

- Michael Alexander Ewert

mewert · **Posted:** Fri Jul 13, 2012 12:23 am

Thanks Erwin, and pass on my Thanks to Kenny!

Physics Simulation Forum

Lagrange multipliers

Who is online