Split Impulses and Joints

[raigan2]

Erin: that looks a lot more stable than my rigid joints; looking through the code, it would appear that I was calculating the 3rd column of the M matrix incorrectly.

It's good to know that it's not a problem with my code or approach; I did intend on making case-specific adjustments, I just wanted to make sure my simulator was correct before hacking it up I had assumed that since iterative impulse-based methods such as your own and Jan's could handle chains and trees/stacks, they could handle the same sort of constraint graph, with a different sort of constraint.

The problem with Featherstone is that I haven't yet managed to wrap my head around the reduced coordinates! I understand what they represent abstractly, but I'm not yet able to develop intuitions about how the velocity of a joint should change when you apply a force at a given point.

Anyway, I think I can work with what I've got, now that I know that the behaviour I'm seeing isn't indicative of a bug.


Dirk: here's a paper by the person who presented the GDC 2004 talk on articulated-body-method simulation, that deals with motors:
http://citeseer.ist.psu.edu/kokkevis96u ... olled.html

[Erin Catto]

A common misconception is that you cannot have constraints on top of Featherstone. But you can!

You can have:
- loops
- contact
- motors and limits

You can solve these extra constraints with any LCP solver (PGS, SI, etc).

[Dirk Gregorius]

The other approach would be to use a direct solver (like the Dantzig solver in the ODE) as a subsolver. From my intuition I would say that the Featherstone approach will give you very rigid constraints, but will the results for be good enough for physical based animation when you need "strong" "motors to drive the animation? On the other hand I am curious how "rigid" the constraints with a direct LCP solver will be.

Any experiences with this? Ideas, suggestions, ...?


Cheers,
-Dirk

PS: What is a nice direct method for small LCP system (max_size <=4)

[Etherton]

A common misconception is that you cannot have constraints on top of Featherstone. But you can!

You can have:
- loops
- contact
- motors and limits

You can solve these extra constraints with any LCP solver (PGS, SI, etc).

sound like the silver bullet (no pun intended)
Then why not using Featherstone for stacking and everything else?

[Dirk Gregorius]

I think because

a) Featherstone can only handle bilateral constraints
b) It should be quite tricky to compute the reduced coordinate set at runtime

[Erin Catto]

People have used joint coordinates in games before.

I used Featherstone in engineering software quite awhile ago and we successfully modeled loops with auxiliary constraints. For accurate and robust simulation, it is far superior to body coordinates.

Here are some reasons why joint coordinates haven't been used:
- difficult to understand
- the common misconceptions I mentioned already
- it is tricky to have breakable joints
- it cannot handle compliant joints
- it is difficult to optimize

It is much easier to optimize body coordinates than joint coordinates.

It is also unclear how well PGS/SI + Featherstone will behave. For example, joint limits will have to be handled by PGS/SI or some other LCP solver.

It is hopeless to model contacts with joint coordinates. So stacking would receive no benefit from joint coordinates and Featherstone.

Dirk: think of it this way:

In joint coordinates you have:

M(q) qdd = f(q,qd,t)

There is no reason you can't augment some constraints:

C(q,t) = 0
M(q) qdd = f(q,qd,t) + dC/dq * lambda

[Dirk Gregorius]

Thanks Erin.

Here is an (relatively old) Featherstone implementation. I never looked into it, but simply bookmarked it since R. Smith said on the ODE mailing list that this is the fastest Featherstone implementation to his knowledge. Note that this post is also quite a while back, since R. Smith seems not to be active on the list anymore. Did anybody look a this:

http://dynamechs.sourceforge.net/

Any other Featherstone implementations worth to look at?

Cheers,
-Dirk

[Erin Catto]

Brian Mirtich's dissertation has an excellent presentation of the Featherstone algorithm. Note that Featherstone's algorithm is not a modeling technique, it is just a way of inverting the dense joint coordinate mass matrix in order N time. It is possible to use joint coordinates without using Featherstone's algorithm, in which case the mass matrix invertion is typically order N^3.

[mewert]

Featherstone has similar problems as Lagrange multiplier solutions do. They are both linear approximations to a non-linear system. So where, with Lagrange Mult ( e.g. a GS solver with baumgart ) you will get stretching in your joints; with featherstone you'll get a very high frequency jitter around the the solution angle.

Motors work really nicely with Featherstone, it appears to be a superior solver to use for biomech control code.

Integration with an squential impulse GS solver is a pain if you want to keep your memory usage and performance somewhat O(n), but there are some optimizations you can do which make it work well in the end.

Personally I would not recommend featherstone due to disporportionate amount of time needed to code and debug it compared to a GS solver. But it all depends on what you sort of systems you want to solve.

As far as reduced coordinate approaches to non-holonomic constraints ( contacts ) go, this is an interesting step in that direction:

http://www.research.rutgers.edu/~kaufman/ffdfrb.html

[/img]

[Erwin Coumans]

We used Featherstone in some games in the past indeed, and I've seen other games using Featherstone. Especially if you do Naturalmotion style motor-powered ragdolls the quality is nice, and PGS might require too many iterations to converge with very strong motors. But also the impact of high-speed cars crashing into characters really leaves a gap when you hit the torso, while the head/arms is still meters away (in one frame). When you do continuous physics (like Havok does, and Bullet will enable too this year), you can increase the quality of some constraints so that they take the time-of-impact into account. In other words, you subdivide the timestep taking the discontinuities into account for both collisions and all constraints that are involved in that 'simulation island'.

Motors work really nicely with Featherstone, it appears to be a superior solver to use for biomech control code.

Integration with an squential impulse GS solver is a pain if you want to keep your memory usage and performance somewhat O(n), but there are some optimizations you can do which make it work well in the end.

My collegue Vangelis Kokkevis has written a paper that mentions combining Featherstone with unilateral constraints like contacts and limits.

See:
http://research.scea.com/research/pdfs/ ... DC2004.pdf
http://www.continuousphysics.com/Bullet ... .php?p=395

Personally I would not recommend featherstone due to disporportionate amount of time needed to code and debug it compared to a GS solver.

To make it easier, I plan to provide a Featherstone implementation in Bullet this year, next to other constraints improvements and optimizations. It was already on the wishlist:
http://www.continuousphysics.com/mediaw ... BulletTodo

Erwin

[Jan Bender]

To make it easier, I plan to provide a Featherstone implementation in Bullet this year, next to other constraints improvements and optimizations. It was already on the wishlist:

Cool, I'm very interested in such an implementation. I just made a comparison of my iterative method and my new linear-time method using impulses with the linear-time method of David Baraff. A student of mine tried to implement the algorithm of Featherstone but he had no success. It could be interesting to see which method is faster, more robust and more accurate.

Jan

[Erin Catto]

I'm working on an implementation of Featherstone in a version of Box2D called Box2Dj (joints). I've got it working with contacts and motors using SI. I only have revolute (hinge) joints right now. I'm also using motors to provide joint friction.

Check it out:
http://www.gphysics.com/files/Box2Dj_preview.zip

Sorry, no code yet.

[Antonio Martini]

the best way to learn about the Featherstone's method/s is his book 'Robot Dynamics Algorithms' where the 'general joint model' , O(n) forward/inverse/hybrid dynamics and optimisations are discussed. Even more important is Spatial Algebra itself which is very helpful for developing new algorithms or implementing existing ones.

If you want stiff joints, presumably you also want stiff motors especially when dealing with control problems(balancing etc..). I doubt that suddendly PGS or SI will behave like a stiff solver for motors when integrated with the Featherstone method. I needed over 200 iterations with exact preconditioning for my tests a few years ago. In a realistic representation of the human body there can be big mass differences.
However i don't exclude that there could have been a few bugs in my implementation.

A pivoting method for motors maybe be optimised by considering the fact that the LCP solver at each iteration is solving a linear system for an active set of motors. That could be done in O(n) time by a version of the Feasterstone's algorithms previously mentioned. The linear system should stay almost constant at every iteration(one motor added or removed from the active set) and by exploiting this fact we may even end up with a almost constant time inner loop. This is just an idea i didn't have time to investigate, so here is the question:

Has anybody explored the possibility of exploiting Featherstone style computations in the context of stiff motors and direct LCP solvers?

cheers,
Antonio

[Erin Catto]

You can make joint motors infinitely stiff in a joint coordinate model if you make the torque limits infinite. In that case you just treat the joint angle and speed as input.

If the number of motors is small, the problem might be reasonably solved with a direct LCP solver. I would expect the LCP matrix to be dense.

Another approach would be to solve the inverse dynamics problem (prescribed joint torques) and use the computed joint torques as an initial guess for an iterative method. If you are not hitting torque limits, then you could skip the iterations. This takes order N time.

Back in '99 I didn't know about iterative methods, so I wrote an engine that combined Featherstone with Lemke. You can read more about it here: http://www.gphysics.com/archives/26

[Antonio Martini]

You can make joint motors infinitely stiff in a joint coordinate model if you make the torque limits infinite. In that case you just treat the joint angle and speed as input.

unfortunately realistic torque limits are essential for realistic behaviours.

Another approach would be to solve the inverse dynamics problem (prescribed joint torques) and use the computed joint torques as an initial guess for an iterative method. If you are not hitting torque limits, then you could skip the iterations. This takes order N time.

when you hit the limits the system may suddendly soften because of the iterative solver.

Back in '99 I didn't know about iterative methods, so I wrote an engine that combined Featherstone with Lemke. You can read more about it here: http://www.gphysics.com/archives/26

yes i remember that,thanks, it was possible to download them from the gphysics site years ago.

If the number of motors is small, the problem might be reasonably solved with a direct LCP solver. I would expect the LCP matrix to be dense.

what i meant was that it should be possible to use Featherstone style computations inside a direct LCP solver in order to bring down the complexity.
If a pivoting method at each step is solving a linear system for a subset of the links, thats what the inverse/direct/hybrid dynamics versions of featherstone are doing in O(n). If the linear system is not changing too much from one iteration to another(thats the case for pivoting methods) we may even be able to optimise even more by reusing the previous computations.

as another example and outside the solver if we are trying to solve for the motors forces(so no contacts) we are trying to match the accelerations within given force limits

a = M*f (plus extra conditions)

where M is the system matrix, which could be computed for example by a unit force method, or more specifically by applying unit torques and reading the results out of the forward dynamics algorithm. see also Kokkevis "practical character physics" for the details..

now if we want to do some preconditioning we can premultiply both sides by the inverse of M and we get:

b = I*f (I = identity)

M_i*a = b

M_i*a can be computed by the inverse dynamics algorithm or more in general by the O(N) hybrid dynamics. So no explicit M and M_i is required.
If i didn't get anything wrong we end up with unit system matrix and a direct solver shouldn't struggle too much with it in order to enforce the LCP conditions.

the general idea is that the various versions of the Featherstone algorithm allow us to compute multiplications of a vector by the system matrix, its inverse or the hybrid dynamics case in O(n) for the entire hierarchy, so it should be possible to do the same for a subset of the hierarchy. Where all these case arise we can simplify the problem. This would work just for the motors, contacts may still be solved by a SI,GS,impulsive solver.

as i stated earlier on, these are just ideas i didn't have time to verify in depth. I was mainly focused on the control problem rather than the solver when i came across them.

generally speaking we know that the maximum subsystem dimension is somehow fixed(a human, a robot etc..), so O(n) or not the important thing is the total running time. Even if we want to stack controlled ragdolls we can do that by an iterative solver on the top level.

cheers,
Antonio