[ODE] Iterative solution

[Adam D. Moss]

david@csworkbench.com wrote:
> I've gotten to a decent level of functionality with the algorithm in
> place. 

Very cool.

 > Right now, I'm running at 5 iterations and simulating everything
> believably.  The iterated algorithm is actually a bit slower (due to the 5
> iterations) in the common case where you have lots of small islands of
> bodies....

That's interesting.  Perhaps the number of iterations for an
island should be related to the log of the number of bodies
in the island (I'm not sure mathematically how the worst-case
rate of convergance relates to the number of bodies, logarithmic
is just a guess).  But still, I'll happily take a bit of a hit
for the simple case to avoid the complex case's death-by-drowning-
in-molasses-and-then-being-set-fire-to.

There are probably relatively easy early-escapes to avoid killing
the simple cases too badly.  Not so important right now.

 > like 20 separate cars.  However, if those 20 cars all get in a
> pileup, the iterated solution trucks along at the same speed

Lovely.

> My next task is to optimize the dInternalStep routine with the knowledge
> that it will always get 1 joint and either 1 or 2 bodies.  Here's the
> question for the math/physics gurus:  Is the LCP solver even necessary if
> you know beforehand that there is only one joint (up to 6 constraints, 1
> per DOF I believe) in effect? 

I'm not a math/physics guru.  I do recall that when this subject was
discussed a month or so ago, the consensus was that the 6 DOF constraint
solving still be done with the LCP solver, but that the LCP solver
can be optimized to death when there are just a fixed and small number
of constraints (6) to solve.

There was also a consensus that the whole idea of island-finding is
pretty much obsolete with a global iterative solver.

> Another thing that's probably slowing it down a good bit is the fact that
> collision detection has to be run before every iteration. 

Does it really though?  I can't see why you should need to re-run
the collision detection every iteration -- your simulation steps
are 1/5 as long and run 5x as often, but the chances of an object
moving through another incorrectly don't seem changed.

Actually, altering your constraints while iteratively solving those
constraints potentially invites non-convergance.

I think the temptation is to re-collide every iteration to
re-evaluate penetration depths and spot new colliders, but I
don't see why at least the latter shouldn't really wait until
the simulation is smoothed out.

> I'll start profiling after I put in the obvious optimizations tomorrow. 
> Hopefully, with enough optimization, this algorithm will be the fastest
> option in all but the most trivial cases.  If not, it's still possible to
> run in normal mode most of the simulation, and only drop into iterated
> mode for example when more than a set limit of contacts were generated.

It's interesting that the new and old solvers can be run alternately
at will.  Personally I'm more interested in committing to using the
new solver and #ifdef away the old code for reasons of footprint
and least-surprises, but it's a nice luxury to be able to test
against either solver easily.

> One simulation I ran kind of surprised me.  There's a 20x20x20 block
> falling out of the sky, and 25 four-wheeled cars (modified test_buggies)
> arranged in a 5x5 grid, all just touching.  If the block hits the ground,
> then the cars move forward in a group and run into the block, everything's
> fine.  The iterated solution sails along, and the old solution craps as
> expected.  However, if the cars move forward and get under the block
> before it touches down, even the iterated solution slows down by a factor
> of 10 or more (the old solution still craps).  I thought the iterated
> solution shouldn't have this problem.

That's odd, unless:
1) There are 10x as many contacts generated overall when the block
lands on the cars, compared with when they just pile into it, or
2) It's something to do with collision detection, which still has
a worst-case O(n^2) even for hash-spaces (I don't see
why it would be specific to that particular configuration of box
and cars, but I suppose there are lots of variables involved
in how the hashspace will perform).

Profiling the two cases should yield enormous clues in any case!

Regards,
--Adam
-- 
Adam D. Moss   . ,,^^   adam@gimp.org   http://www.foxbox.org/   co:3
busting makes me feel good
kthx bye