FWD: [ODE] Performance with multiple cars

[Adam D. Moss]

whitt013 wrote:
> Ok, I'll bite.  I've begun working on a high level implementation of the 
> iterative algorithm. 

Cool.

 > My approach right now is to replace the functionality of
> dProcessIslands with a function that simply iterates through all the joints 
> and calls a slightly modified dInternalStep on the joint and each body it's 
> connected to.  The modifications needed were to add cforce back to the facc 
> and tacc vectors and not actually move any bodies until all the iterations 
> were complete.  The plan is to just perform one small step and let the end 
> user lower their stepsize and do the collision and call dWorldStep multiple 
> times per frame. 

Sounds reasonable to me.

 > So far, it looks quite good for all the test_* programs with
> as little as 5 iterations (timestep = .01) per frame.  But it gets really 
> sloppy (looks like the CFM is too high, even if CFM is 0, even with 100 
> iterations) with more articulated systems (I've got a train of 50 spheres with 
> wheel spheres on either side of every other body sphere to make a really long 
> "car" with 25 pairs of wheels).
> 
> I'll play with it some more over the weekend, maybe even get up enough courage 
> to dive into dInternalStep, but feel free to shoot holes in this method if you 
> know why it isn't working as well as expected.

I'm not going to shoot holes -- for one, I don't know enough about
how ODE currently represents and resolves its constraints internally.

However, I implemented an iterative large-system constraint-solver
for another project recently -- although it has to solve a lot of
the same sorts of problems that ODE's simulation steps do, the
details are probably radically different enough that I couldn't
advise on the specifics.

But I can offer a few insights into general gotchas and tips
with iterative solvers:

* The order in which the constraints are solved can radically
change the accuracy of the solution for good or ill.  I randomize
the order of solving in each iteration, which really helps
convergence.  I don't know if that's easily applicable to ODE's
island traversal.

* Split any correction required to fulfil a constraint evenly across
as many of the participating elements of that constraint as possible.

* It seems that the majority rules an iteratively-solved constraint
system -- if there are very many constraints fighting a very few,
the few will tend to really suffer while the majority get good
solutions even when there exist some 'perfect' solutions that
could please all.  I'm sure that there are many tricks that
can be borrowed from N-dimensional hill-climbing (which I
think that iterative constraint solving strongly resembles) to
improve the chances of finding global maxima though.

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