[ODE] How to do iterative

[david@csworkbench.com]

In one of Baraff's papers, he stated that a fully tree structured (i.e.
acyclic) system could be solved in O(n) time.  I'm fairly sure this only
allows for equality constraints (joint limits and contacts are out of
the picture), but there is an algorithm that can be used on top of that
one to close the loops and solve inequality constraints, that is O(kn)
-- it's iterated k times.  The problem, IIRC, is that it's worse than
O(k^2) in space (not exactly sure how much worse), so it will run out of
memory for larger systems.  So it depends on whether you want to trade
space or accuracy for speed.

As far as applying that to an iterated algorithm, the same effect
happens.
 If you know you're simulating a perfectly tree structured system with
all
equality constraints, then yes, you can optimize for that.  But I can't
think of many uses where contact is not needed.

David

P.S. The box pyramid and cars was just the most complex system I could
come up with for speed testing without writing tons of code just for
testing purposes.  It just goes to show that the algorithm can simulate
the worst case scenario of the previous algorithm faster.  The good
thing about the current form of the algorithm that I'm working on is
that you can cut out of the iteration loop as soon as you have a
sufficiently small amount of error, which most tree structures would
have on their first iteration anyway.

> Just curious - does it make sense to have a solution specifically
> optimized for tree-like articulated systems? (most of the time that is
> the case in my simulations... not too interested in having a
> box-pyramid and then running cars into it ;)
>
> I'd assume that you only need to carry resultant forces >forward< in
> an iterative system that is solving a tree-structured system.
>
>
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode