[ODE] Speed of ODE's constraint method

[Richard Tonge]

Hello

>Is the LCP / Lagrange multiplier method used in ODE
>fast enough for interactive frame rates (> 30 fps)
>for a minimal number of constraints/contacts?

The short answer is yes. The long answer is maybe :o)

The short answer is yes because there are a number of
games on the shelves (and the top 10) that use an LCP
method. Although the actual LCP method used in those
games is different, it has similar characteristics to
the one used in ODE.

Brace yourselves for the long answer lads...

Direct LCP methods (as used in ODE) have properties
that are acceptable for some games/platforms and not
others. In particular, memory usage, cpu usage and
memory bandwidth usage can scale quite badly as the
size of the system increases. 

Memory
Direct methods require the storage of one or more
large matrices. The size of the matrix can fluctuate
quite a bit depending on what is happening in the
game.

For example, take a game where animated characters
turn into physical ragdolls when they die. Suppose
each one has 9 joints which each constrain 6 relative
degrees of freedom. 

If a ragdoll is flying through the air then the number
of matrix rows is 9*6=54. In this system, there is one
matrix of size 54*54, which takes about 12k. Not too
bad.
Suppose the ragdoll hits the floor. This might add 2
friction contacts,each constraining 3 dof for each of
the 10 bodies, giving 9*6+3*10*2=114 rows in total.
This brings the matrix size to 114*114 which takes
52k.

Suppose you have 10 ragdolls flying through the air.
You get 10 matrices of size 54, which takes
12k*10=120k.
Suppose that they fall in a pile on the floor. As they
are all touching they have to all go in the smae
matrix. There might be 3*10*2=60 rows due to the
contacts between 9 ragdoll-ragdoll pairs, and
3*10*2=60 rows between the bottom ragdoll and the
ground. Each ragdoll still has 54 rows holding it
together. This gives a grand total of
9*60+60+54*10=1140 rows. A 1140*1140 matrix takes
about 5 megs!
Unlike graphics, the cost of (direct LCP) physics is
not per object, it is per interaction, and it can get
quite big.

Of course, in real games which use these methods,
there are hacks to make sure that people dont die in
the same spot, or that only a small number of cars can
be involved in a crash. James Golding did a GDC 2002
talk  about how this is done in MathEngine Karma.
However, big piles of dying people, big walls of
falling blocks or big car crashes might be a vital
part of the game, and in these cases other methods are
better.

There is a similar story with cpu time. Ill have to
talk generally here because the direct LCP method I
have experience with is different to the one used in
ODE. Typically what happens is that a number of
'iterations' (in the for-loop sense, not the iterative
algorithm sense) are performed. Each one takes some
subset of the data in the matrix and performs some
O(n^3) or O(n^2) matrix operations on it. The number
of 'iterations' is variable and depends on things like
the number of separating contacts. In theory, the
maximum number of iterations is O(2^n) or O(3^n),
which is an argument often wheeled out by anti-LCP
people. There are problems but this is the least of
your worries. The reason is that you can stop the an
LCP after a constant number of iterations, and the
physical artefacts are not too bad.
The real problem is that the size of the matrix, n
fluctuates quite a bit (as discussed above). This
wouldnt be too bad if you were doing a linear amount
of work on the matrix. However, you are doing O(n^3)
work, so any fluctuations in n give large fluctuations
in the cpu time. 

I should say though that LCP methods are very stable,
and once Russ sorts out box-box, ODE is going to be
rock solid. The reason that there are direct LCP games
in the top 20 at the moment despite the above hurdles
is because the stability is so good.

>Also - is there any drawback to using the LCP method
>on consoles?

On PC, the above concerns arent too much of a problem.
PC games machines have lots more ram than consoles,
and if the game is good enough they will buy more.
CPUs are a lot faster and have more cache. This makes
the constant factors in execution time very small.
Simple gameplay and AI hacks can prevent physical
systems getting too big. For this reason, I believe
that direct LCP based physics engines such as ODE are
a very good choice for the PC. Our tests have also
shown that they are a very good choice on the gamecube
and xbox due to the easily accessible memory bandwitdh
on those platforms.

However, on the PS2 it is not quite as clear. Many
people are releasing games based on a direct LCP
solver on PS2, but they have had to make some
compromises. The PS2 does have masses of memory
bandwidth and floating point performance, but
unoptimised C code doesnt have access to it. If you
are going to port ODE to the PS2 I would suggest
double buffering all your data through the scratchpad,
microcoding all your inner loops and staying away from
vif0. Taking advantage of matrix sparsity is a good
idea too.
In my experience, iterative (as opposed to direct) LCP
methods work much better on PS2. With these methods it
is possible to keep all the data of a reasonably sized
scene in spr or vumem0 at once. This gives you far
more gigaflops, because you are not hanging around
waiting for main memory all the time. With these
algorithms, you can even out run a PC!

<Marketing hat on>
MathEngine Karma 1.3 comes with a direct LCP solver
Kea, and an iterative LCP solver Arthur, so that you
can select the best solution for your platform/game.
<Marketing hat off>

Sorry about that...

Of course, there are non LCP routes you could look at
as well. In particular Thomas Jacobsen's constraint
relaxation with verlet integration is probably worth a
look.

Good luck with your simulations!

Richard Tonge
PS2 Optimisation Engineer
MathEngine

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com