[ODE] Constraint theorizing

[Gary R. Van Sickle]

> Also it's possible to avoid the island construction
> process entirely (see ProcessIsland subroutine).
> Simply iterate for all constraints.

Right!  It wouldn't even make any *sense* to do the island construction.  It may
make sense though to sort the constraints in order of "worst offender"; getting
the most out-of-whack constraints solved first might result in faster
convergence.  Or it might be me who's out-of-whack here ;-).

One more thing before I fully think it through: is it even necessary in all
cases to do LCP solving at all?  For some joints don't we have a closed-form
solution to the restoration force that doesn't need a numerical solution?  Pin
joints come to mind here.

>  Again, should
> be possible to parallelize the computation of several
> constraints (that is, several iterations) if they
> involve different bodies.
>

Pshht!  Who needs parallel when we got O(C^3) -> O(CN)!  ;-)

> Sergi
>
> PD: Thanks but I din't realize this algorithm alone.
> I would like to note that the main contributor
> was Antonio Martini.
>

1.  Ok, you're BOTH Gods!
2.  Nothing is ever new.  I saw this exact thing being done with point masses
"simulating" rigid bodies
(http://www.ioi.dk/Homepages/thomasj/publications/gdc2001.htm) and it floated
around in my head for weeks without me seeing a direct connection to "real"
rigid body simulation.  And I'm sure this guy got it from somebody else too.  We
all add our parts to the sum of the whole... or words to that effect ;-).
3.  Nothing is ever easy.  But you guys got it done.  Again, GODS!  GODS I SAY!
;-)

--
Gary R. Van Sickle
Brewer.  Patriot.

> -----Original Message-----
> From: Gary R. Van Sickle [mailto:g.r.vansickle@worldnet.att.net]
> Sent: martes, 25 de febrero de 2003 7:29
> To: ode@q12.org
> Subject: RE: [ODE] Constraint theorizing
>
>
> > There were some discussion about such things in this list
> > (iterative schemes and the like) I have tested (succesfully)
> > a straighforward iterative  technique which solves *only*
> > 1 constraint at each step (thanks Antonio). That is, if you
> > have a system  of say C= 10 constraints, then you solve
> > every constraint separately without taking into account
> > the other constraints. The idea is that the time step is
> > subdivided into a sort of "microsimulations". Something
> > like that:
> >
> > parameter: N substeps, C constraints, Dt (ODE timestep)
> >
> > for i=0..N-1 do
> > 	for c = 0..C-1 do
> > 	 	Solve constraint c-th
> > 		Apply forces to constraint bodies
> > 	next
> > 	Integrate bodies by (Dt/N)
> > next
> >
> > The idea is that as N->inf the movement of the bodies is
> > very small so the effect of every constraint is very
> > localized and this approach becomes exact just in the limit.
> > In my tests a small number is iterations is enough to
> > get decent results.
> >
> > Please note that the core of this scheme is to solve a
> > very small (up to 6x6) LCP constraint system.  I think
> > this approach gives enough room to a lot of performance
> > improvements. The next step should be to find a fast
> > code able to solve the small system.  Also, note that
> > is no longer necessary to store a big matrix for the
> > constraint coefficients.
>
> This is like excellent to the third power!  And believe it or not, I
> actually
> thought of just this scheme during my run this evening, not that I'd have
> had
> the ability to pull it off.  So let me see if I can summarize.  ODE as-is is
> O(C^3).  The new scheme is O(CN), with N a small integer.  That improvement
> in
> scalability alone is fabulous.  PLUS, we lose the stack problems that have
> been
> plagueing people.
>
> You are a GOD!
>
> --
> Gary R. Van Sickle
> Brewer.  Patriot.
>
>
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode