[ODE] Speed of ODE's constraint method

Tue Jan 21 02:11:01 2003

An iterative solver not only will mean a reduction of memory usage
in complex environments. Note that even with low number of bodies 
we can still have many contacts which in turn results in large 
JMJ-1 matrix.  

The problem with the current ODE's LCP solver is that it involves
a lot of data motion (i.e matrix row & col swapping)when dealing 
with large systems (which is the situation we are facing or we 
will be facing in the near future).

There are some other schemes in the literature based on
iterative algorithms which doesn't involve such intensive
data motion. These iterative algorithms trade memory usage 
for computation.  Such an scheme will allow implementation 
of LCP solvers in parallel computing machines. For an effective
parallel algorithm of LCP problem a considerable reduction 
of data motion is required.

Moreover, an iterative scheme is a lot more easy to code than a 
direct one. One problem is that documentation on iterative 
LCP schemes is given in terms of the so-called "canonical" 
LCP problem.  This is why I asked in the past if anybody knows 
how to translate the formulation used in ODE (and I guess is 
described in section 5.3 of David Baraff's paper 
"Fast Contact Force Computation for Nonpenentrating Rigid Bodies" 
(SIGGRAPH'94)) in terms of the "standard" LCP problem.

Sergi

-----Original Message-----
From: gl [mailto:gl@ntlworld.com]
Sent: lunes, 20 de enero de 2003 19:34
To: ode@q12.org
Subject: Re: [ODE] Speed of ODE's constraint method

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
>

_______________________________________________
ODE mailing list
ODE@q12.org
http://q12.org/mailman/listinfo/ode