PhD thesis on numerical methods for rigid bodies

Post Reply
User avatar
Erwin Coumans
Site Admin
Posts: 4235
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

PhD thesis on numerical methods for rigid bodies

Post by Erwin Coumans »

Ghosts and machines: regularized variational methods for interactive simulations of multibodies with dry frictional contacts

Lacoursière, Claude (2007). Ghosts and machines: regularized variational methods for interactive simulations of multibodies with dry frictional contacts.

http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-1143
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

This is a huge piece of work... :-)
KenB
Posts: 53
Joined: Sun Dec 03, 2006 12:40 am

Defence June 13

Post by KenB »

Claude defends his thesis on June 13 at 10.00 at Umeå university, Sweden.

If someone would feel like popping by, you're of course most welcome, and don't hesitate to contact Claude or myself about travelling, accomodation etc.

/Kenneth
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Are there any chance that we see at least some demos of SPOOK where it handles some test scenes and we get an impression its speed?
KenB
Posts: 53
Joined: Sun Dec 03, 2006 12:40 am

Post by KenB »

Dirk Gregorius wrote:Are there any chance that we see at least some demos of SPOOK where it handles some test scenes and we get an impression its speed?
Yes, guess if we're busy...

The situation is a bit special since much about the methods is covered in the monograph, while case studies/tests are still being developed. So we risk seeing someone implementing the methods, publishing them, and actually getting more academic credit for them than what goes to Claude for his monography. This is a peculiarity of the current publishing tradition in academia.

So, if someone is very keen on testing/validating/adapting the methods in various areas and go for scientific publishing, we're open for active collaboration on this - rather than competition!

My students have implemented the methods for rigid body stacks and cloth, but more analysis is needed.

If one chooses to go for stationary relaxational solvers aka projected Gauss-Seidel, the overall computational complexity is in practise very similar to what you see in e.g. Catto's GDC papers (which also is inspired by Claude's previous work).
However, the regularized/stabilized methods rely on physical and structure preserving principles (which isn't really the case of Baumgarte, nor the zero-right-hand-side-method+projections of Guendelman, Bridson & Fedkiw) since they are derived from variational principles, and therefore the behaviour is almost always better. Therefore the method is likely to be faster and more stable in most cases I can think of.
Of course the generic problems of projected G-S cannot be totally or trivially overcome.

/Kenneth
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

e.g. Catto's GDC papers (which also is inspired by Claude's previous work).
May I ask which work you mean in particular?

nor the zero-right-hand-side-method+projections of Guendelman, Bridson & Fedkiw
What do you mean by the "zero-right-hand-side-method" and to what kind projection do you refer in GBF paper - velocity or position projection?

Of course the generic problems of projected G-S cannot be totally or trivially overcome.
What do you mean by generic problems?



BTW, I think there are open questions to you in two other threads on this forum. I think it would be really appreciated if you would answer those as well.

http://www.continuousphysics.com/Bullet ... php?t=1033
http://www.continuousphysics.com/Bullet ... php?t=1124

Sorry, but I have sometimes a hard time to follow you...



Cheers,
-Dirk
Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

Dirk, I'll take a shot at answering your questions and KenB can correct me if I'm wrong.
e.g. Catto's GDC papers (which also is inspired by Claude's previous work).
Claude's paper http://www.ep.liu.se/ecp/010/004/ecp01004.pdf said this:
Pairwise impulse based models amount to Gauss-Seidel iterative processes and we will provide data on such methods below.
From that and other sources (namely Gary Snethen and an ETHZ 2005), I was inspired to develop an impulse method that is equivalent to PGS. Thus I developed the Sequential Impulse algorithm. No aspect of SI was inspired by Claude's algorithms.
nor the zero-right-hand-side-method+projections of Guendelman, Bridson & Fedkiw
With this I think KenB is referring to the absence of a Baumgarte term. I think KenB is saying that Claude's algorithm is better at preserving things like momentum and/or energy.
Of course the generic problems of projected G-S cannot be totally or trivially overcome.
The problem PGS has is that it has poor convergence in some cases (heavy object on top of a light object).
KenB
Posts: 53
Joined: Sun Dec 03, 2006 12:40 am

Post by KenB »

Yes, you are perfectly right Erin.

In the GBF paper, in their "simplified method", they have a second iteration stage where they look for zero velocities by going from restitution -1 to 0. Of course this means that the existing energy/momentum will not be used to resolve penetrations. Penetrations are instead resolved using position projections, and this is a pretty much uncontrolled operation from a physical perspective. However, I do also think that their method has some beuaty to it, since it is incredibly easy to grasp and implement.
I think it might be possible to derive their method as a special case/limit of the variational/stabilized solvers that Claude has developed.

With Baumgarte stabilization you add the penetration size and velocity to the right hand side of the equation for the langrange multiplier, but the choice of parameters is quite arbitrary, and it isn't overly stable.

In the derivation of the regularized/stabilized solver you can actually derive the "Baumgarte parameters" from physical principles, and you can also guarantee that the solver doesn't overshoot, thanks to the regularization (I believe this has been called "lambda relaxation" in some of the forums here, but I don't think it has been formally derived from the physics before).
KenB
Posts: 53
Joined: Sun Dec 03, 2006 12:40 am

Post by KenB »

Well, it takes a bit too much time to explain things in a forum without using proper math, so I think I'll just refer to Claude's thesis.
The discussion about rotational integration is pretty much covered there, so I suggest you read that chapter.

When it comes to the other "open question", I'm not sure what was really the open question.
Dirk Gregorius wrote:

BTW, I think there are open questions to you in two other threads on this forum. I think it would be really appreciated if you would answer those as well.

http://www.continuousphysics.com/Bullet ... php?t=1033
http://www.continuousphysics.com/Bullet ... php?t=1124

Sorry, but I have sometimes a hard time to follow you...



Cheers,
-Dirk
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

With Baumgarte stabilization you add the penetration size and velocity to the right hand side of the equation for the langrange multiplier, but the choice of parameters is quite arbitrary, and it isn't overly stable.

In the derivation of the regularized/stabilized solver you can actually derive the "Baumgarte parameters" from physical principles, and you can also guarantee that the solver doesn't overshoot, thanks to the regularization (I believe this has been called "lambda relaxation" in some of the forums here, but I don't think it has been formally derived from the physics before).
Choosing Baumgarte parameters is indeed tricky, but don't we actually linearize the problem here, so I always though that this is the main reason for instability. Take for example a ball socket joint. Even when you have perfectly satisfied velocity constraints, you can still end up with large positional errors, due to high angular velocities after integrating the positions. The problem is that Baumgarte tries to compensate for the error of the last frame not the current one (at least in the form we use it). So I liked what U. Asher wrote in one of his papers. "Baumgarte stabilizes the system, but not necessarily using the best trajectory." We linearize the non-linear position constraints, so of course there will be instabilities. GS has limitations, but warm-starting helps a lot since you amortize the iteration count over several frames. Dealing with the non-linear system in much more difficult imo...
Antonio Martini
Posts: 135
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

KenB wrote: The discussion about rotational integration is pretty much covered there, so I suggest you read that chapter.
could you please mention where in the Claude's Phd(it's really big) i can find a discussion of the rotational motion integration using methods of molecular dynamics and also a discussion of the inertia related problem linked to the exponential map you mentioned in the other post?

it's true that it is both difficult and time consuming writing proper maths on here, however mentioning other people work and a page-equations number should be something possible.

that would be very helpful, thanks in advance,
Antonio
Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

I haven't read Claude's dissertation yet, but I wonder if his regularization is similar to using softness and Baumgarte together. There are some nice formulas that let you specify softness and Baumgarte in terms of stiffness and damping coefficients. This makes softness and Baumgarte much more physically plausible. I believe the formulas also guarantee stability, i.e., unstable values of the Baumgarte parameter would imply a negative damping and/or stiffness value. With softness/Baumgarte selected from the damping/stiffness values, we get guaranteed stability because PGS is acting like an implicit integrator.

Further, if you have an approximate mass value, you can use a damping ratio and undamped natural frequency to determine the softness and Baumgarte. I used this for a vehicle suspension constraint.
KenB
Posts: 53
Joined: Sun Dec 03, 2006 12:40 am

Post by KenB »

Erin Catto wrote:I haven't read Claude's dissertation yet, but I wonder if his regularization is similar to using softness and Baumgarte together. There are some nice formulas that let you specify softness and Baumgarte in terms of stiffness and damping coefficients. This makes softness and Baumgarte much more physically plausible. I believe the formulas also guarantee stability, i.e., unstable values of the Baumgarte parameter would imply a negative damping and/or stiffness value. With softness/Baumgarte selected from the damping/stiffness values, we get guaranteed stability because PGS is acting like an implicit integrator.

Further, if you have an approximate mass value, you can use a damping ratio and undamped natural frequency to determine the softness and Baumgarte. I used this for a vehicle suspension constraint.
Yes, it is similar, but a major difference is that "Baumgarte with softness" can actually be derived from a discrete variational principle in Claude's framework - as a special case (not necessarily the best case..). The time stepping method falls out of the same derivation, as well as information on how to choose the "Baumgarte and softness" parameters, and not to forget: a way to understand what the parameters mean for the physics of the system. These parameters actually have real physical meanings and can be used for modeling of the real physics.

The regularization allows you to solve for a slightly different physical system, but still indeed a real and valid physical system. Another encouraging result is that the regularized system typically is a _better_ model of the empirical system you try to model - and still easier to solve than the idealized mathematical system.
Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: PhD thesis on numerical methods for rigid bodies

Post by Erin Catto »

I'm interested in using the quaternion-based constraints that Claude outlines in his dissertation. Some of it is a bit confusing (he defines an attachment frame twice, etc). And some of the details are spread across the chapters, tucked away in long chains of proofs.

Does anyone on this forum have experience with such constraints? Are there any other references I should look at?
KenB
Posts: 53
Joined: Sun Dec 03, 2006 12:40 am

Re: PhD thesis on numerical methods for rigid bodies

Post by KenB »

Erin Catto wrote:I'm interested in using the quaternion-based constraints that Claude outlines in his dissertation. Some of it is a bit confusing (he defines an attachment frame twice, etc). And some of the details are spread across the chapters, tucked away in long chains of proofs.

Does anyone on this forum have experience with such constraints? Are there any other references I should look at?
Sorry for the slow response time here. I've been trying to cut down on communication lately to get some work done. Anyway, a paper on the quaternion constraints is planned this fall/winter. We'll keep you updated.
Post Reply