SV: [ODE] Iterative solution

[david@csworkbench.com]

Yeah, I realized last night that I could do better.  I'm mid-debugging an
even tighter version that doesn't move bodies so much.... I'm not sure if
this is basically one of the algorithms you proposed or not, but here it
is:

accumulate gravity and inertia for all bodies
calculate J for all joints
calculate A for all joints
for i = 0 to maxIterations
 recalculate rhs
 solve LCP
 accumulate forces
next i
move bodies

If this works, it moves 40% of my processing time (calculating A and
moving bodies) out of the inner loop.... so there should be yet another
impressive speedup.  I'm not even sure if this is theoretically correct,
but it makes all the comments I've heard on the list make a lot more
sense.  It also makes possible summing the forces added in the accumulate
forces step, and cutting out when that is lower than a specified
percentage.  If it works.

To the best of my understanding, rhs is a vector that predicts where the
bodies will be next step, and the job of the LCP is to figure out what
forces need to be added to bring the system to a state consistent with the
constraints.  rhs uses the force and torque accumulators of the bodies in
it's calculation, so convergence should ensue..... quickly and correctly
is another question.....

Is this more in line with what you guys were thinking?  Did I stumble on
one of the algorithms you mentioned, or am I way off base?  I'm still
working on developing a good working mathematical model for how all this
works...

This is almost a drop in replacement for ODE's solver.  It could be easily
implemented as such if you wanted to leave out some options.  Right now,
the convention is to just call:
dWorldStepFast(world, stepsize, maxIterations);
as opposed to the normal dWorldStep.  That way you can switch back and
forth between the old and new algorithms based on some heuristic, since
it's still a little shakier than the old algorithm until you give it
enough iterations that it becomes slightly slower than the old algorithm
in the case where there's lots of small islands.  Of course, if I get this
new version working, it may be faster in all cases, but you might still
want to use the old dWorldStep for accuracy.

Let me know your thoughts,
David Whittaker

>
> hi,
>
> i'm curious about your algorithm. you stated it like this (in summary):
>
>> for i = 0 to maxIterations
>>  ...
>>  foreach joint
>>   solve LCP problem for this joint
>>   add resulting forces to each body's accumulators
>>  next joint
>>  foreach body
>>   adjust velocity by force and torque accumulators
>>   adjust body's position by velocity
>>   reset force and torque accumulators to 0
>>  next body
>> next i
>
> so it seems that the body position drifts during the solution process?
> why not keep the position constant and just adjust the velocity? -
> because the constraints are (mostly) velocity constraints.
>
> your algorithm seems like a form of block-jacobi iteration for solving
> the system matrix. i'm curious if this could be improved by converting
> it to block-gauss-siedel or block-SOR. i'm also wondering what the
> trade-off is between the blocking and non-blocking iterative matrix
> schemes ... in the blocking scheme it seems like the maximum convergence
> eigenvalue is lower (so convergence is faster) but you have so do the
> extra work of the mini-LCP's at each step ... hmmmm, this is a
> worthwhile subject of study. does anyone know if there are any existing
> papers on this subject?
>
> is your code a plug-in replacement for ODE's existing solver? i'm
> looking forward to seeing it...
>
> russ.
>
> --
> Russell Smith
> http://www.q12.org
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode