[ODE] Speed of ODE's constraint method

[gl]

I personally can't help with the algorithm (it's a bit beyond me I'm
afraid).  However, I think apart from the performance issue, another issue
is the amount of stack space ODE currently requires.

In my test scene, I continually throw out shapes (similar to boxstack).  I
found that I need to reserve a minimum of 16meg (this is on Windows) to stop
getting stack overflow problems, and even then a particluarly complex frame,
with lots of things touching, can still cause and overflow.

I also followed the discussion between Russ and Richard Tonge in the
archives about the different approaches to the problem, and if I understand
it correctly, an iterative solver would also significantly reduce the memory
requirements in complex environments.

Now I don't know what the primary cause of the stack usage is in ODE
(probably recursion contributes to this), but if ODE were used in a console
game, a 16meg stack space is out of the question, right?  That's half the
available memory of an X-Box (and some of that is going to be tied up with
framebuffers, so you start with significantly less).

So yes, it'd be great to have an iterative solver one day : ).
--
gl

----- Original Message -----
From: "Sergio Valverde" <svalverde@barcelona.ubisoft.es>
To: <ode@q12.org>
Sent: Monday, January 20, 2003 4:11 PM
Subject: RE: [ODE] Speed of ODE's constraint method


> Is there anybody interested in implementation of such iterative
> methods in ODE? I will be glad to share thoughts and ideas on
> the subject with other people in this list.
>
> Sergi
>
> -----Original Message-----
> From: Russ Smith [mailto:russ@q12.org]
> Sent: lunes, 28 de octubre de 2002 3:21
> To: Richard Tonge
> Cc: ode@q12.org
> Subject: Re: [ODE] Speed of ODE's constraint method
>
>
>
> > A good reference on iterative LCP methods is chapter 9
> > of Murty's book
>
> interesting. i read chapter 9 and implemented some of the methods there
> in matlab. the sparsity-preserving SOR (successive over-relaxation)
> method described on p378 seems to be the closest to what you describe,
> as its main computational step is multiplying M by some vector. in ODE
> 'M' is J*inv(M)*J', which boils down to a bunch of 6xN matrix operations
> as you described.
>
> for the random PD matrices i was testing with i found that the SOR
> method scaled as O(n^3), the same as the direct method. i found that if
> a 0.1% error was the termination condition then SOR was 3-4 times less
> flop count than ODE's direct solver for 100*100 matrices (the crossover
> point below which the direct method was faster was about 20*20).
> however! --> typical rigid body system matrices have a much more useful
> spectrum than my random matrices, so i suspect that if ODE had an SOR it
> would (a) be much faster than direct LCP, and (b) scale O(n) or O(n^2)
> depending on the structure of the RB system. i will investigate this
> later. SOR would not be too hard to implement in ODE at all (it would be
> an optional method). chosing the parameter values (e.g. w) presents a
> problem.
>
> > Although this should give you an idea about what I
> > mean by iterative LCP, I should point out that we dont
> > use any of the methods in that chapter.
>
> are you using a method related to the SOR method?
>
> russ.
>
> --
> Russell Smith
> http://www.q12.org
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode
>