[ODE] stepfast beta 2

[David Whittaker]

Documentation is coming soon, but the primary purpose of the solver is
to simultaneously reduce both the time and space required for a step, at
the expense of accuracy.  The limiting factor in the current step
function's speed equation is O(m^3), where m is the number of degrees of
freedom removed from the system (a single island), and it's O(m^2) space. 
In the stepfast function, speed is roughly O(m*i), where i is the number
of iterations per step, and space is O(m).

If you aren't familiar with big-O notation, here's the what it means: 
lets establish a base case as the amount of time it takes for a solver to
solve a single constraint.  This will be different for the two solvers (in
fact, the fast solver will take longer in this simple case).  Now let's
see how long it would take to simulate 100 constraints.  The worldstep
solver would take 100^3 = 1,000,000 times as long as it's base case of a
single constraint.  On the other hand, the stepfast solver, even at 10
iterations, is going to take 100 * 10 = 1,000 times as long as it's base
case.  Keep in mind that there are other parts to the theoretical equation
that determines how fast a given program will run (even hidden constants
in the big-O notation), so you won't be able to verify these results
experimentally.  The point is that stepfast is a good bit more scalable
than worldstep.

So what do you give up for these gains in speed and space?  Accuracy and
Robustness (hmmm, might have to look that one up).  When the worldstep
solver looks perfectly solid on a particular scene, you may be able to get
close to an object and detect a little jitter in the stepfast solver. 
When the worldstep solver can take a fairly large range of masses, the
stepfast solver has trouble making things look good with masses that
differ by more than a factor of 10 without increasing iterations (and
slowing it down).  Say you build a wall out of blocks connected by fixed
joints.  The worldstep solver will reject anything that runs into the wall
without moving the wall at all, while the stepfast solver might make the
wall sway or even fall over if there is enough force.  However, most of
these effects can be mitigated or removed by a combination of the
auto-disabling/enabling code I'm working on putting directly in the
source, and a little extra care in setting up your simulation parameters,
especially mass, fmax, and iterations.

On the other hand, you get better control over the accuracy/speed
trade-off than the worldstep function... to a point.  By increasing or
decreasing iterations, you can control just how much time you want to
spend on trying to find a good solution.  Big car pile-ups and other
simulations which send the worldstep solver out to lunch are only slightly
slower (due to the increased contact count) in the stepfast solver.  So it
is a big tradeoff.  You have to decide whether speed or accuracy is more
important to you... and most game developers say speed if it's accurate
"enough".

David

P.S.  When I move the randomizing code into the source and seed it to the
same number at the start of every simulation, it will be just as
deterministic as the worldstep solver.  And you have full access to all of
the rest of ODE's api, so you can set body position, rotation, and other
parameters at will to bring it back into sync if you get behind (through
dBodySetPosition/Rotation/LinearVel/AngularVel).

> What exactly does stepfast solve?  I've been playing with test_crash
> and you can hit f to "toggle fast step mode" which appears to use your
> dWorldStepFast() over the default ODE dWorldStep() call.  I assume
> this is an optimization modification, because when I try to turn off
> fast step mode, my CPU spikes all the way up (P4 2.8ghz w/ 1GB of RAM)
> and I get maybe 1 frame every 15-20 seconds.

Heh, nice system...  the original solver wasn't really designed for a
system this large.

> I guess the reason why I'm asking is that there's been a lot of
> technical/math talk about your modification, but there's not one place
> to look for the pros/cons of using it.  I'm interested in using ODE in
> a client/server environment and was wondering how well it would fit.
> How do I keep the server and the client's simulation in relative sync,
> as well as correct the client when it gets out of sync?
>
> Ted