Guys, You probably get this question a lot on here, so I apologise. I also note a couple of related questions in the forum at the moment, anyway. Through experience, which method for integrating the eqn''s of motion have people found to be most optimal (by way of speed and accuracy)? I am aware of the most popular, i.e. Euler method where we take f = ma V_new = V_old + (f/m)*dt and then integrate again to get position... P_new = P_old + (V_new * dt) in a sort of way. My game dev physics book discusses use of an "advanced Euler", in which two terms of the polynomial are used (of the Taylor expansion), or the Runge-Kutta method. However, even though I studied both in my degree, I can''t for the life of me understand the book. (His example doesn''t explain two well the equations to use, and how to implement for other examples). So I guess, whichever method is best, I would need a good article on the matter also, if possible. (or someone to explain with reference to spring mechanisms (i.e. f = -k*x)). Cheers Matt

As you can imagine, the answer to your question could fill a small library! I have several books in my personal library that discuss the pros and cons of different integrations schemes.

The answer boils down to something very disastifying: the best choice depends on the situation. Helpful, eh?

Stability is as important, if not more so, than speed. And achievable speed is usually a function of the stability of a method. Two-step methods such as "simple" explicit Euler (which is the type of Euler integration seen most often in basic integration of the equations of motions) are always the fastest for explicit integration. But for some problems, implicit, semi-implicit, or predictor-corrector methods (which are more complex and much more difficult to implement) may actually end up being faster because you can use larger time steps while achieve stable integration.

I actually recommend that you never use explicit Euler integration---it has severe stability constraints that often require very small time steps to avoid calcs that eventually blow up. Its mainly good for getting a system up and running initially. (But it should actually work fine for simple projectile motion with occasional collisions and no rotations.) Beyond that, it won''t work at all if you have springs in your system, unless you artificially add damping. The leapfrog method is a two-step method that requires that you uses the results from 2 frames back to calculate the next frame. It leapfrogs the previous result and strangely the stability characteristics change entirely. The method is just as simple as explicit Euler, but doesn''t require damping for problems with springs. It does still have stability constraints. Verlet methods are a variation on the leapfrog method that are a bit more flexible, but still quite simple and fast. The Runge-Kutta methods are possibly the most robust explicit methods for doing time integration. They do have stability constraints, but allow somewhat larger time steps than Euler and leapfrog methods. But Runge Kutta methods aren''t going to work everywhere. Time step limits in the presence of moderately stiff springs and moderately high oscillations must be small, slowing things down.

Implicit methods, which are quite difficult indeed to implement, are the most flexible in terms of stability and time step. There is a class of implicit methods known as "A-Stable" methods that are unconditionally stable for problems that are physically stable. What that means is that, if the physical problem you''re trying to simulate is itself stable, you can use any time step size and it will work without problem. Some A-Stable methods can even simulate unstable physical situations without problems, though in that case there are stability constraints on time step.

That''s a ramble. You might learn something if you read my Game Developer''s Conference 2001 paper and presentation, available for free download here:

http://www.gdconf.com/archives/2001/index.htm

Look for the programming track proceedings, a paper called "Stable Rigid-Body Physics"

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Thankyou Graham,

I know about stability since I studied Control Engineering (I am aware of Stability, instability and critical stability etc).

Your methods look interesting, and will read your paper, thanks again

Matt

Hope it helps!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Graham,

I read your paper, I think it must be quite heavy reading for someone who hasn''t done a control theory degree! Thankfully I have...

Do you know of any good tutorials on implementing the Advanced Euler, Runge-Kutta or A-Stable method for the equations of motion. I know this should be simple, but I don''t seem to be understanding this.

Cheers

Matt

It could be good to start with integrating a one-variable differential function (y''=f(x), where x,y are scalars), and only after that advance to general systems.

Siggraph course notes by Baraff, Witkin and Kass (google for "baraff physically based modeling" show pretty well how to integrate a system forwards in time. First we transform the 2nd order ODE usually seen in physics to a 1nd order problem. Then we use "universal routines" that gather around vectors of states and derivatives to build the algorithms. But check out the papers, and most of all, good luck.

- Mikko Kauppila