Featherstone vs. Baraff's linear-time solver

[dern23]

Erwin, congratulations on the first release in Bullet of the Featherstone algorithm! Looks like it'll be pretty useful for ragdolls, stiff cables, etc. My question is what are the advantages of the Featherstone method for articulated figures over the method presented by Baraff in "Linear-Time Dynamics using Lagrange Multipliers"? It seems at first glance that the later approach would integrate into the existing framework a bit more easily, perhaps in a similar manner as that achieved by Jan Bender in "Impulse-based dynamic simulation in linear time"; and would be more familiar to developers with experience in ODE or other engines, most of which use maximal coordinates by default. Traditionally Featherstone implementations lacked motors and friction as well as non-holonomic constraints and kinematic loops, but it appears most of those problems have been solved in more recent work. On the pro side there is no drift, so error correction can be omitted. But from what I've heard the math required to derive the parametrizations necessary to implement certain constraint types can be intimidating to novice users, whereas you simply take a time derivative and construct a Jacobian in the maximal coordinate formulation. So all else being equal what drove the decision to go with Featherstone? Is there a performance difference? Was it simply more suitable for the scenarios game developers come across (you mention character being hit by a high-speed car in an old forum post)? Look forward to your response!

[Erwin Coumans]

The Featherstone articulated bodies are popular in games, movies, robotics and other industrial applications, and some of my previous colleagues worked on it: I used to work with Vangelis Kokkevis, who wrote some paper about integrating Featherstone with another constraint solver and Antonio Martini, who implemented it in a game. The main benefit is zero joint separation, while having a good performance. The constraints applied to the Featherstone btMultiBody are extremely similar to constraints applied to a regular btRigidBody, and they are solved in the same solver: contacts, limits, motors can be applied to btMultiBody vs btMultiBody, btMultiBody vs btRigidBody or btRigidBody vs btRigidBody in the same constraint row code:
See btMultiBodyConstraintSolver::resolveSingleConstraintRowGeneric in https://code.google.com/p/bullet/source ... ver.cpp#98

If you (or someone else) have implemented Baraff's linear-time solver, and consider contributing it to Bullet, we welcome contributions!
Thanks,
Erwin

[dern23]

Thanks for pointing me to Vangelis' paper, cleared up a lot of confusion. I haven't implemented Baraff's method yet, but I am seriously considering it as my goal to to simulate a cable that has some angular 'springiness' between the links. Currently I use cone joints with particular CFM and ERP values set on the swing axis to get the effect I need. From what I understand this wouldn't be possible in a Featherstone-style cable as clearly there is no drift so no ERP. So unless there is a some other way to simulate springs with the articulated body method or somehow partition the dimensions of a single constraint so that the translational portion is solved by ABM and the angular dimension using the existing solver I don't think it'll work for me

[Erwin Coumans]

You can mix Featherstone with maximimal coordinate constraints, so one option to simulate a cable with limited stretch would be to interleave revolute joints with prismatic joints, and add (maximal coordinate) constraint motors/limits on the prismatic joints, to add controlled springs.

Another approach would be to simulate the cable with an implicit solver, using conjugate gradient, as described in Baraff's 'large steps in cloth simulation'. I have a very good implementation here done by Stan Melax, but haven't added it to Bullet yet. It is rock solid, fast and you can control the stiffness.

[dern23]

Ahh, yes, I came to that realization as well after I posted my last reply and had another look through the paper; for some reason I was thinking about splitting the solving in terms of blocks instead of single rows. Sometimes it takes a couple read-throughs for ideas to sink in The CG solver sounds very interesting indeed; if you have time in the near future, and would not be too time-consuming to add, I'd love to give it a shot