Getting starting programming an implicit "lcp" solver?

[jeremiah]

I've been trying to search the net for how to figure out the basics of programming my own physics engine.

When I say physics engine I'm thinking of implicit, contraints, "solvers", etc. My ignorance shows I'm sure.

I've already programming a basic verlet explicit physics engine, and I was pleased with the results. I've heard programming this other type is much harder, but I would like to give it a go. I just need some tutorial that explains how to actually code one! Is there something like this online?

I know I could go look at the code of an engine, but I'm afraid even if I looked at the code, I still wouldn't understand what's going on.

Thanks,

[oztune]

I'm in the process of moving on from the jakobsen scheme as well, and would suggest:
Box2d source and slides(created by Erin Catto, one of the mods here. He's always ready to answer questions which is very helpful)
Chris Hecker's tutorials - http://chrishecker.com/Rigid_Body_Dynamics
Oliver's rigid body tutorials (with source too) - http://members.lycos.co.uk/olivierrenault/

[Erwin Coumans]

Have you already checked the Physics engine list, books, PhD thesis, on-line resources? It has most of the links, books that you need.

In particular these two online books/thesis are recommended:

Helmut Garstenauer, A Unified Framework for Rigid Body Dynamics
Kenny Erleben, "Stable, Robust, and Versatile Multibody Dynamics Animation", ftp://ftp.diku.dk/diku/image/publicatio ... 050401.pdf

Hope this helps,
Erwin

[Dirk Gregorius]

Erwin, you might want to add the Shabana book. It has the best description how to model joints in my opinion:

http://www.amazon.com/Computational-Dyn ... 569&sr=8-3

[jeremiah]

Thanks for the links, I'll check out the PDFs and see how far they can get me.

[jeremiah]

I read "A Unified Framework for Rigid Body Dynamics" and it was a great read. It referenced David Baraff's SIGGRAPH '97 course notes http://www.cs.cmu.edu/~baraff/sigcourse/index.html , of which had a nice article about implicit euler (backwards euler) here: http://www.cs.cmu.edu/~baraff/sigcourse/notese.pdf.

I'm trying to ease my way into this stuff, so I'm trying to understand the backward euler math. I generally feel that I understood all the steps, but I just wanted to clarify here.

For explicit Euler. Let's say I have two mass points connected by a spring. I figure out the distance between the points, calculate the difference between the actual distance and the relaxed distance. The force I apply to both mass points is -k t d (each would get half of course), where k is the spring "value", t is the timestep value (1/30 for 30 fps?) and d is the difference between the actual distance and the relaxed distance.

From what I can tell, the implicit "backwards euler" method substitutes the "-k t" for "(-k t) / (1 + k t)".

Of course, depending on how you come up with your "k", you could do away with the "t" altogether. In that case the explicit euler force is "-k d" and the backwards euler force is "((-k) / (1 + k)) d" right?

Is my understanding correct? Perhaps there are other formulas? From what I gather from "notese.pdf" above, Baraff approximated "f( y0 + changeInY )" with "f(y0) + f'(y0)changeInY". Perhaps if you approximate differently you'll get a different formula?

I'm just looking for a quick "yeah, that is right", or "no, you're wrong/confused because of XYZ".

Thanks,

[bone]

The force I apply to both mass points is -k t d (each would get half of course), where k is the spring "value",

Sorry I'm not answering the question you want answered, but I am not sure about that anyway.

Regarding your "each would get half of course" clause above, I disagree. I thought that at one time, but I believe the convention for specifying a spring's rate means that both sides get the full force. For example, a 200 N/m spring deflected 0.1m would apply a 20N force on one mass and an (equal and opposite) 20N force on the other mass, not half of that on each.

[eddybox]

Jeremiah,

You're confusing your physical model and your time integration scheme. Generally, you don't want your force be a function of your time step. Instead, compute your force as a function of the state (positions, velocities, etc.) of your system.

Once that's clear, explicit Euler is just a scheme to time-step your given model/system.
a = f/m,
v2 = v1 + a*dt,
x2 = x1 + v1*dt
where (x1, v1) is your current state vector, dt is your time step, f is a function of x1 and v1, and (x2, v2) is the state at the end of your time step. (note: when computing x2, you can replace v1 with v2 to get a (better) "verlet style" method.)

For backward Euler, f is instead a function of x2 and v2. But the hitch is that now x2 and v2 are dependent on f, which is in turn dependent on x2 and v2. What to do? Well, for a simple case, like the simple mass-spring in Baraff's course notes, you can analytically eliminate f from your update equation. But in the case of a more complex system, like a cloth mass-spring network, you need to solve a system of non-linear equations (or do what Baraff does in his '98 paper, and approximate it as a linear system, compute the jacobians, and solve a big, sparse matrix at each step). fun, eh? For now, drop the implicit/backward time integration - I doubt you want to code a general physics engine based on them. There are plenty of other challenges for you to tackle.

Have a look at the great references mentioned above...

Cheers,
Eddy