[ODE] Linear-Time Dynamics using Lagrange Multipliers

[Richard Tonge]

Hello

> Has anybody tried to implement the sparse solution
> method proposed in David
> Baraff's paper "Linear-Time Dynamics using Lagrange
> Multipliers" 

Ive not personally implemented this technique, but I
have implemented more general direct LCP methods on
the PS2 that exploit sparsity. Although I didnt do the
analysis myself, I vaguely recall that Baraff's linear
method is equivalent to a more general algorithm, LU
solve without pivoting.

> Moreover, such low space
> requirements enable fast solver implementation on
> PS2's VU.

Yeah, a few years ago we were in the position you are
in now. At that time we thought that sparse LCP was
the way to go.

Bear in mind that with the VU, you can only easily
manipulate 4*4 blocks, so you can only take advantage
of block sparsity. Although JMJT is often quite
sparse, a lot of the sparsity is destroyed if you
factor JMJT. It is possible that even if you implement
a sparse solver, you still wont be able to fit your
system into vumem. We implemented a sparse LCP that
paged in vumem sized chunks of sparse blocks to get
round this problem, but the data paths to vumem are
quite slow and there is a lot of overhead.

After trying a lot of different ways of implementing
sparse algorithms on the PS2, we did find a reasonably
good solution, and this is used in a number of PS2
games such as Bart Simpson's Skateboarding, Downforce
and Big Mutha Truckers. 

However, we now think that even with sparsity and lots
of optimisation tricks, direct LCP has fundamental
problems. We now use an iterative method that doesnt
use a matrix at all and use a linear amount of data.
This makes microcode implementation tons easier.

Writing an LCP based physics engine from scratch on
the PC is very hard, and Russ has done an amazing job.
Taking such an engine and optimising it for the PS2 is
also quite hard.

If you do want to continue down this route, then might
want to look up my SCEE and SCEA devcon presentations
on the subject.

Despite all the problems, this sort of thing is very
interesting and I wish you good luck :o)

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