Iterative solver (again) [Was: Re: [ODE] Russ' plans for ODE?]

[Alen Ladavac]

>     Hmm... They told us and I made my guess also. I remember Pierre
>     has stated that they use a technique which is similar to ODE's
>     StepFast.

But they didn't actually tell it is that one, just that it is similar. :)
They don't build a huge matrix, that's for sure. Huge matrix method cannot
theoretically be the right way to go, since the matrix itself is NxN, so
even building it is O(n^2) in the start. But this still doesn't mean that
they keep the first approximation of per-joint forces as the solution.

> AL> I believe that. But I wouldn't jump to conclusions that it is enough.
> AL> Could it be that the "better designed iterative solver" is somewhat
similar to
> AL> what was hinted by Richard Tonge a few years ago on this list?
>      You mean this one?
>       http://q12.org/pipermail/ode/2002-October/006141.html

Yes, that's the one. But, now that I've re-read some of the Adam's and
Pierre's mails, seems like they might be more into using positional
correction to cover up for approximation errors in main LCP
(force-velocity). Guess we'll never know for sure unless they tell us. :)
Interesting enough, seems like someone actually told Pierre to go away (!),
during the last discussion, and that's where the thread ends. Perhaps they
might come back and correct our straying minds... ;)

>     Wait a minute! So you mean that solver will take in the huge
>     matrix of original step and then solve it iteratively? Or still
>     iterative through a list of joints like StepFast?

It takes the original J and M matrices in their very sparse form (actually
recorded as 6xN and 6xM matrices) and uses that for an O(n) solution. But
generally, this method doesn't require any changes to the way that joints
are formulated - it is merely a faster way to solve (or rather - approximate
solution to) the LCP.

>     And, if it's feasible,would you please describe your experiments?

It is still too early to tell that it is _the_ solution, so I wouldn't get
overly excited. In short, I would best describe it as projection method,
similar to Gauss-Seidel, done per-constraint, not per joint as in StepFast1.
I just started this because I was interested in whether someone already
tried something like this.

> AL> Timestep in a simulator can never be too small. :)
>     Hmm.. then let say like this situation: a box is in very deep
>     penetrate with a sphere. The collider give us a depth. The
>     dynamics part know that it should pull the box separate from
>     sphere but in very tiny time step, the box can just be moved a
>     tiny distance. Could it happen? It sounds a little stupid but if
>     this scenario happens, we don't use our time step efficiently.

First of all, if the timestep is small, ball's velocity would need to be
much higher in order to penetrate deep into the box. So, for small timestep,
the problem is less likely to occur in the first place. Second, at lower
timesteps the error correction actually works better. Have you noticed the
fact that as fps goes down, heavy objects sink into the ground? It is
inherent to timestepping schemes, where you have to allow for some error, to
prevent instability - and if timestep is larger, allowed error is greater,
so you correct more slowly. My knowledge might be a bit limited in this
part, but that's as far as I can read the error*fps^2 term in the right hand
side of the joint equation.

Anyway, smaller timesteps will always cover up for numerical problems, but
that is not the way I'd like to have that solved. Direct LCP solver works
correctly even for timesteps of 1/10 of second. An iterative method might be
able to find a similarly stable solution for same timestep, and that is what
I'm seeking. I see the problem primarily in solving the (in)equation system
faster, not reformulating the problem, as the current formulation has proved
stable. But who knows...

>      For demonstration, I'll put a demo with that technique and use a
>      quite "polished" collider. These day, I tried to make your
>      sphere-cylinder collider code more robust :).

Great. I'd like to see it for comparisons with direct solver.

Cheers,
Alen