Rigid Body Techniques

[bronxbomber92]

Hi,

I'm looking to implement my first rigid body engine, and I'm undecided which technique to use. The one's I'm considering are the approaches presented in:

Advance Character Physics, by Thomas Jakobsen
Verlet Integration and Constraints in a Six Degree of Freedom
Rigid Body Physics Simulation, by Rick Baltman and Ron Radeztsky Jr. - which seems to be an expansions of Advance Character Physics
Impluse-based Dynamic Simulation of Rigid Body Systems, by Brian Vincent Mirtich
Rigid Body Simulation, by David Baraff from Siggraph 2001

To be honest, I'm not sure what technique David Baraff uses in his paper. I'd be helpful to know! I'm not to hot on using Jakobsen's approach because it seems like it could be a hassle to represent the rigid body by several points/particles. I'm not sure of the the advantages and disadvantages of each approach though, and any other alternatives there are. Could someone help me out here?

Thanks,
Jedd

[Dirk Gregorius]

None of them. I would use Sequential Impulse as described by Erin Catto. This is implemented in Box2D and the 3D version in Bullet. Personally I would argue that you can forget about the Verlet stuff. The Mirtich stuff is quite similar to Sequential Impulse, but differences in the clamping of the contact impulse and the implementation of constraints. The Baraff solver works on the acceleration level. It is good to read this though, since this is a classic approach used in CAD I guess. It suffers from infinite friction forces and it should be significantly slower.

Note that Sequential Impulse is a velocity based method, equivalent to the iterative LCP solving method known as projected gauss seidel (PGS).

http://www.gphysics.com

Note that there are two implementation. Box2D_Lite might be easier to understand in the beginning...

[bronxbomber92]

Thanks! So I guess the paper to read is the one Erin Catto wrote in 2005: Iterative Dynamics with Temporal Coherence.

Just out of curiosity, what's wrong with the Verlet technique presented by Rick Baltman and Ron Radeztsky Jr.?

[Dirk Gregorius]

Thanks! So I guess the paper to read is the one Erin Catto wrote in 2005: Iterative Dynamics with Temporal Coherence.

This is a description of an iterative PGS method for an MLCP. The later presentations present the PGS in terms of sequential impulses. Both are mathematically equivalent, but differ in the implementation. Another good resource might be the PhD of Kenny Erleben. Basically the ODE is an example of the former and Bullet (and also Box2D) an example of the later.

You need to understand the following. Basically in constrained rigid body dynamics you solve what is called a system of differential and algebraic equations (DAE). This looks like this:

dv/dt = M^-1 * (f_ext + f_c)
dx/dt = v

C(x,q) = 0

The first two are the Newton-Euler equations. The last equation is a system of non-linear algebraic equations (this means C is a vector). C imposes some geometric constraints onto the system, e.g. for a ball-socket joint that a point p1 of the first body is coincident with a point p2 on the second body. When you think about this a little you quickly realize that this also imposes a velocity restrcition onto system. In the above example the two points only remain coincident if the relative velocity at both points vanishes. Formal the velocity restrictions can be found through building the time-derivative of the constraint equations C. In order to build the formal derivative you use the total derivative (http://en.wikipedia.org/wiki/Total_derivative). The result is:

del_C/del_t = del_C/del_x * dx/dt + del_C/del_t = J * v + del_C/del_t

The del operator stands for partial derivative and J is the famous Jacobian matrix ( http://en.wikipedia.org/wiki/Jacobian ). Of course there is also an acceleration constraint which is the second derivative of the constraint equations C w.r.t time, but I leave this out for now. Maybe I should note that the velocity and acceleration constraints are sometimes refered to as the hidden constraints. Think about it practically and not mathematically, like in the above example. This should be easier to grasp in the beginning. So the methods you mentioned differ which constraints the try to satisfy.

The Jacobsen (Verlet) method works on the position level. You discretize the Newton-Euler euqation and plug this into the constraint equations (details ommitted - I name references later)
The Projected Gauss Seidel (PGS) or Sequential Impulse (SI) solve on the velocity level. Again you discretize and plug the result into the velocity constraint equation

One gotcha when solving on the velocity level is that there will be some position error (called drift sometimes). This is because of numerical errors, but more likely because the iterative solution is not fully correct, but only an approximation. In order to work against this drift we "stabilize" the system. A common used stabilizaion is "Baumgarte" stabilization.

The Baraff method works on the acceleration level. I leave this out since it is not relevant for game development. So if you want to get into this I recommend reading the PhD of Kenny Erleben and all presentations of Erin Catto. For an example on solving on position level (though in the context of particles) look at the paper by Muller "Position Based Dynamics". All references can easily be found using Google or here on the forum...

ust out of curiosity, what's wrong with the Verlet technique presented by Rick Baltman and Ron Radeztsky Jr.?

There is nothing wrong with this method. But from my experience PGS and SI work better and faster than the Verlet methods...


HTH,
-Dirk

[ewjordan]

Practically speaking, Verlet-based simulation is easy to understand, which makes it initially attractive, and there is something nice about having velocity-free representations (if you've ever done PDE simulations, wave equations or something like that, you'll know how much easier these can be to work with, since often a naive translation of the PDE will give you higher order accuracy "for free," along with better stability properties), but when you start trying to really make your engine do everything that a real physics engine should do, it becomes cumbersome. It's one thing to avoid interpenetration using projection, since the simulation method handles it all very easily, but it's another thing altogether to try and make things realistic with friction, restitution, joints, etc. Anything that involves velocity becomes a major hassle, and you lose all of the nice properties that pure even-order discretization gives you. You start going through it all and you ultimately realize that it would have been less work just to go with a less clever method of integration in the first place.

Can't speak to the speed difference, though, since it's such a major annoyance to get functionality to be identical between a Verlet simulator and a "normal" one that I've never tested them side by side.

[bronxbomber92]

Thanks for the input, it's really appreciated!

So, Impulse based dynamics it is. Besides Erin Catto's slides (which I can't view properly because I'm on a Mac, and NeoOffice doesn't display the power point slides correctly) are there any papers on SI? If not, I guess I'll just follow Iterative Dynamics with Temporal Coherence or Mirtich's PhD thesis (which I don't think uses SI?).

[bronxbomber92]

How do the methods of Jan Bender compare to Erin Catto's SI method? Are there any obvious advantages or disadvantages between the two?

[kkw]

Verlet Integration and Constraints in a Six Degree of Freedom
Rigid Body Physics Simulation, by Rick Baltman and Ron Radeztsky Jr. - which seems to be an expansions of Advance Character Physics
...
I'm not to hot on using Jakobsen's approach because it seems like it could be a hassle to represent the rigid body by several points/particles.

I have implemented a working 3D ragdoll a few months back with Jacobsen's method. Though it is quite easy to make it work on the simulation part, but when you try to apply your ragdoll particles to your mesh, then a lot of assumptions must be made to derive the 'orientations' for your skeleton joints. This is ok if your game only has characters with a single skeleton settings, but when you have animals, aliens, or other non-standard skeletons mixed in, then your assumptions on one skeleton setting won't work on other settings.

Then I tried the Baltman's paper, which allows you to represent rigid body with just a single particle, this is because the paper introduce orientation to the original jacobsen's method (which was purely positional). Calculating orientations for skeleton joints is much more straight forward, just set the orientation of the particle to the joint. Velocity is used, instead of previous position for the integration part. But I found few typos with the paper, when something goes wrong, I'm not sure whether it is my mistake or the paper's typo, though I managed to get things working in the end (with lots of guessing).

Now, I'm trying SI by looking at Box2D and Bullet source, and I must say that I'm having quite a lot of fun with SI .