Real-Time Physics Simulation Forum

(This is aimed at whoever read or implemented Baraff's algorithm, described in his paper from 1994)
I'm trying to implement it, but got stuck in the friction part. In part 5.6 in Baraff's paper, he extends the 2D algorithm (with the sets CF, NC- and NC+) to three dimensions (with only two sets: CF and NCF).
I agree that (quoting from the paper) "it is easy to augment maxstep to move i into NCF when fx^2 + fy^2 = (kfn)^2" (k is the coefficient of friction). This requires solving a quadratic equation.
However, I disagree with the next part: "and also easy to detect when to move i back into CF". (quoted from the top-right corner of page 30.)
In the 2D case, a contact i moves back into CF when its velocity (or acceleration, depending on the implementation) turns 0, as a result of the tangential friction impulse (or force). In the 3D case, the friction impulse (or force) is only partially opposed to the tangential velocity (or acceleration). So it's most likely that the velocity or acceleration will never turn 0.
How, then, should I know when to move a contact i back into CF?

Thank you very much.

Ok then, I'll just direct this one at Redon, since I know he has successfully implemented Baraff's algorithm with friction:
Could you give us (I think more people have encountered this problem) a hint on how you implemented friction in your contact solver? I remember reading somewhere that you constrain accelerations instead of forces, but could you be a little more specific? I know this is probably documented in your big French paper, but unfortunately I can't read French and I have found absolutely no other source of information on this specific friction problem in Baraff's algorithm (if there really is such a problem and I'm not just confused).

In order to be completely clear, I'll describe the problem(s) again:

1. In 2D, a friction constraint moves from NCF to CF when its tangential velocity reaches 0 (due to the friction impulse). In 3D however, I see no reason for the tangential velocity to reach (0,0), because the friction impulse isn't precisely opposed to the velocity, and will therefore miss the (0,0) point. I have encountered this problem in my implementation, which might be wrong, but I think I have a point. Please correct me if I'm wrong.

2. In order to get around this, I've implemented a version of the algorithm which handles the X and Y friction velocities independently. But after struggling and solving several round-off error problems, I've reached a point where the algorithm usually works, but sometimes enters an infinite loop, where contacts mutually break each other. In other words, when working on some contact i, contact j (j<i) is "broken", which means the algorithm "gives up" on it. Then when I work on contact j, it breaks contact i. This repeats forever. I checked, and I believe this "breaking" is legitimate, as described in Baraff's paper: a contact moves from CF into NCF (in CF the velocity is 0), but as soon as it is checked again in NCF, its delta velocity is found to be negative, which means it should be moved back into CF, so its velocity won't turn negative (it's currently 0). Is this yet another round-off problem, or is this caused by a limitation of the algorithm? (which isn't guaranteed to work in all cases with friction)


One more thing: I keep asking about Baraff's algorithm (which is known to be slow and relatively hard to implement) because interpenetration is not allowed in my application. If objects were allowed to interpenetrate, I'd be able to use an iterative method with warm starting and a limit on the iteration count. But with no interpenetration, the solver has to reach a high degree of accuracy before it exits. This can lead to thousands of iterations with large mass ratios. If anybody could suggest a practical solution to this problem (except dropping the no-interpenetration limitation) I wouldn't need Baraff's algorithm.

Thanks again, and I'm sorry for repeating my questions. I hope I'm doing this politely enough.

Hey Michael,

I'm sorry, I never implemented Baraff with friction. In our ICRA02 paper we deal only with frictionless systems, and to compare the efficiency of a Gauss-based solver to a LCP-based solver I implemented Baraff without friction, which is simply Dantzig's algorithm. We then proposed something to include friction using a Gauss-based solver, but never published it (it's only in the french dissertation). The basic idea is super (too ) simple: you deal with friction by adding constraints in the system. It's not Coulomb friction at all, but it's mostly ok.

Sorry I can't help you more with this.

Stephane

Are there any specific reasons that you use Baraff's method now?
It's considered to be obsolete by timestepping method.
Instaneous method (the last paper we've seen is Baraff's) suffers from alot of problems, including non-existence solution, worst-case exponential,etc...

Time stepping, low level constraints (velocity or even position) is the way to go.

If you really want non-penetration then:
1. Use Stewart-Trinkle method
2. Correctly predict possible penetrations
3. Use full representation of geometries (i.e implicit object only)

Then, you may come up with 99.999% non-penetrating simulation.
But you'll need Nonlinear CP not LCP anymore for condition 3).
If you remove 3), you may also have good percentage of non-penetration.

ngbinh wrote:Are there any specific reasons that you use Baraff's method now?
It's considered to be obsolete by timestepping method.
Instaneous method (the last paper we've seen is Baraff's) suffers from alot of problems, including non-existence solution, worst-case exponential,etc...

Saying Baraff work obsolete, when all we do with rigid body dynamics is one way of another based his work, is the equivalent to Baraff saying that Newton second and third laws of physics are obsolete.

Baraff work is the formulation of the equation of Lagragian dynamics for rigid bodies, deducted from Newton first and second laws in a very elegant way.
He provided one method for solving the system of equations one get from such formulation. And all of the work on rigid body physics is based on his 1994 paper.
Implementing a different optimization tecnique to find one of the many posible solutions from the search space does not make his work automatically wrong or obsolete.

I see a great deal of confusion among people starting to study the field of classical mechanic, I believe is generated by many publications of papers that for the most part are fundamentally incorrect. Baraff work does not violate any laws of physics; it is the solution of the system of equations that required those compromises, but the formulation is 100% correct.

Baraff?s 1994 paper is the entire foundation of real-time rigid body physics, I would be more careful claiming that his work is wrong or obsolete, because I think that very few people can contest his work.

Baraff?s 1994 paper is the entire foundation of real-time rigid body physics, I would be more careful claiming that his work is wrong or obsolete, because I think that very few people can contest his work.

I don't want to get into a debate here, but we should give credit to Featherstone, Lotstedt, E. Haug, Kane, Nivravesh, and others. Their work all pre-dates Baraff's writings on the subject.

edit:
agree, I think you are right No argument here either.

Agree! No argument that could lead to flame war.
I don't mean his Lagrangian approach is obsolete. I stated directly that his instaneous equation of motion plus constraint in acceleration are kind of old and not being used anymore.

PS: Just a note on history. Baraff is not the first one to write about LCP and Lagrangian approach but surely he is the one who promote it.