# Physics Simulation Forum

 Page 1 of 1 [ 9 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Lagrange multipliersPosted: Sun Jul 08, 2012 11:48 am

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 !

Top

 Post subject: Re: Lagrange multipliersPosted: Mon Jul 09, 2012 4:23 pm

Joined: Tue Feb 20, 2007 4:56 pm
Posts: 190
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.)

Top

 Post subject: Re: Lagrange multipliersPosted: Mon Jul 09, 2012 5:17 pm

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 773
Location: Bellevue, WA
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.

Top

 Post subject: Re: Lagrange multipliersPosted: Mon Jul 09, 2012 9:09 pm

Joined: Sat Oct 08, 2005 1:16 am
Posts: 56
Location: Itinerant
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

Top

 Post subject: Re: Lagrange multipliersPosted: Wed Jul 11, 2012 11:37 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
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:

Top

 Post subject: Re: Lagrange multipliersPosted: Thu Jul 12, 2012 5:59 pm

Joined: Sat Oct 08, 2005 1:16 am
Posts: 56
Location: Itinerant
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

Top

 Post subject: Re: Lagrange multipliersPosted: Thu Jul 12, 2012 11:53 pm

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
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

Top

 Post subject: Re: Lagrange multipliersPosted: Fri Jul 13, 2012 12:22 am

Joined: Sat Oct 08, 2005 1:16 am
Posts: 56
Location: Itinerant
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

Top

 Post subject: Re: Lagrange multipliersPosted: Fri Jul 13, 2012 12:23 am

Joined: Sat Oct 08, 2005 1:16 am
Posts: 56
Location: Itinerant
Thanks Erwin, and pass on my Thanks to Kenny!

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 9 posts ]

#### Who is online

Users browsing this forum: No registered users and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities