[ODE] Re: constraints

[Russ Smith]

Michael Alexander Ewert <michael.ewert@havok.com> wrote:
> 
> Hi Russell,
> 
> fantastic work you are doing.  You've mentioned a few times that you 
> think generalized coordinate constraint systems ( featherstone ) are 
> faster than the "big matrix" maximal coordinate systems.  I know, 
> O(n^2) vs. O(n). Just wondering if you have done performance tests on 
> real-world situations before?  Featherstone is O(kn) but the k is 
> pretty large.  Don't answer if you feel I am "the competition"  ;)  
> I've done a featherstone implementation and want to integrate it into 
> Havok.  In it's unoptimized state ( very unoptimized ) it was almost 
> an order of magnitude slower than our existing constraints.  Havok's 
> existing constraints are super optimized for speed. Math engine 
> doesn't use generalized coordiate constraints do they?
> 
> Thanks,
> 
> - Michael

first off, i think you mean "reduced coordinate" instead of
"generalized coordinate" - at least that's the terminology i use.

i have done various tests on featherstone methods vs cartesian methods
(i.e. "big matrix" methods). featherstone methods are almost always
faster. the fastest implementation i have seen is in scott mcmillan's
"dynamechs" library - scott did a great job of optimizing this. brian
mirtichs "multibody" library was also fastish, though 3-4 times slower
than dynamechs.

the key thing is that featherstone is O(n) for speed while 
cartesian methods are O(n^3) for speed. so anything like a 
long-chain system will go MUCH faster with featherstone. i do not
remember where the crossaver point is, but i think it's maybe 3-5 rigid
bodies before featherstone gets the advantage. this is obviously highly
dependent on the two implementations.

why does ODE use cartesian methods then? here are the reasons:

* cartesian methods are more flexible - you can make arbitrary system
  structures (as many loops as you want). the featherstone method
  requires a tree structure. actually the latest dynamechs library has
  a "loop closure" feature, but i have not looked at this yet.

* cartesian methods are more flexible (2) - you can add contact
  constraints where ever you like, and use them to model friction.
  contact constraints can't be easily added to a reduced coordinate
  tree. contact & friction modelling with a featherstone method
  either require springs & dampers (bad for speed and stability),
  or a hybrid reduced coordinate / cartesian coordinate approach
  (tricky to implement).

* cartesian methods are more flexible (3) - you can easily change
  the system structure on the fly. reduced coordinate methods encourage
  you to store bodies in trees that must be reconfigured when anything
  changes. this tends to be reflected in the APIs for these libraries.

* having a "big matrix" to factorize allows you to more easily control
  error. though it's not obvious, the O(n) computations of the
  featherstone method actually perform the steps of matrix 
  factorization. the trouble is, you get no control over elimination
  order and so lose some chances to improve numerical accuracy.

* using implicit integration to provide numerical damping of
  unstable modes Works Better with cartesian methods, IMO.

in the end a hybrid reduced coordinate / cartesian coordinate approach
may be the "best" approach.

> Math engine doesn't use generalized coordiate constraints do they?

they have done in the past, for some applications that require it, such
as catheter simulation. as far as i know it's not part of their main
toolkit.

russ.

--
Russell Smith
http://www.q12.org