Baraff's LCP

Game Mechanics
#1

So you guys … this LCP stuffs makes my head spinning :’(
So I told myself - let’s see maybe I’m able to recode it (even if I won’t succeed, it will probably very much help me understand it) … I looked in that paper (sig94) explaining the algorithm (there’s a link in the physics resources thread)… it looked quite possible…at least the frictionless case.
So I coded it and now it fairly works, there’s still a problem with my Gauss-Algorithm part (in cases where there is not exactly one result - it gives me NaN’s then)

Even if I’m able to finish it, also with friction, I don’t know if it’ll always works, because it somewhere said, that it is designed for non interpenetrating bodies, but they’ll ofcourse do, so I don’t know if this also have to get handled by the LCP, or if it’s done at a different part.

Ohh yeah - one very good thing about my implementation - I followed very close that paper, so even the names of the functions is the same. So if one day I decide to put it on the cvs, I believe it’ll be pretty easy to understand with the paper lying next to it :wink:

#2

Congratulations, that’s really cool.

At the moment I am doing the same - trying to understand the LCP. I have found some papers as well and tried to match the solutions with the LCP implementations in JOODE. And surprise, surprise, my understanding of the code is getting better and better. But at the moment I do not have any results.

One problem I have figured out is the “step” method in the StepperFunction implementations. It is doing too much different stuff (apply gravitation, build jacobian matrix, buidl secondary matrices, apply forces to the bodies). I have found out that a large amount of the code is shared between the different stepper implementations. I think we could benefit from an abstract StepperFunction implementation, that already provides most of these functions.

Next thing that could be improved is the building of the Jacobian matrix. The RealPointer stuff always makes me stumble if everything is right about the implementation (is the index set at the right position etc.). In fact the getInfo2() method in Joint is a addMyConstraintsToJacobianMatrix() function. Wouldn’t it be nice to change the Joint.Info2 class to a class JacobianMatrixBuilder with explicit methods for adding the constraints (e.g. addBodyLinearVelocity(Body body, Vector3 velocity, int contraint) and let the JacobianMatrixBuilder fill in the values at the correct position?

#3

[quote]One problem I have figured out is the “step” method in the StepperFunction implementations. It is doing too much different stuff (apply gravitation, build jacobian matrix, buidl secondary matrices, apply forces to the bodies). I have found out that a large amount of the code is shared between the different stepper implementations. I think we could benefit from an abstract StepperFunction implementation, that already provides most of these functions.
[/quote]
yes - an abstract StepperFunction Implementation would be good - I think at least now we should value design much higher than performance. + It’ll probably remove error prone parts.

[quote]Next thing that could be improved is the building of the Jacobian matrix. The RealPointer stuff always makes me stumble if everything is right about the implementation (is the index set at the right position etc.). In fact the getInfo2() method in Joint is a addMyConstraintsToJacobianMatrix() function. Wouldn’t it be nice to change the Joint.Info2 class to a class JacobianMatrixBuilder with explicit methods for adding the constraints (e.g. addBodyLinearVelocity(Body body, Vector3 velocity, int contraint) and let the JacobianMatrixBuilder fill in the values at the correct position?
[/quote]
If this is possible - it’ll be much nicer than now :slight_smile: - Those RealPointers stink!!

[quote]At the moment I am doing the same - trying to understand the LCP. I have found some papers as well and tried to match the solutions with the LCP implementations in JOODE. And surprise, surprise, my understanding of the code is getting better and better. But at the moment I do not have any results.
[/quote]
hehe - me too

#4

yes - an abstract StepperFunction Implementation would be good - I think at least now we should value design much higher than performance. + It’ll probably remove error prone parts.
[/quote]
+1. Always privilegiate Design over Speed, until it works.

#5

Oh yeah all that code sucks. The only problem with following Baraffs paper is that ODE has put a load of extra stuff on top of it.

[quote]The RealPointer stuff
[/quote]
The real pointer stuff is really horrible from a Java point of view. But it makes porting the c stuff easy with that class. You can literally translate the c code much easier. I thought its easier to do a literal port then refactor rather than trying to do both at the same time. Refactoring the classes makes alot of sense now that we have the basic framework working. The problem was that when I started I needed so much code to be ported without any way of knowing whether any of it works. Now we can tinker and see whether it breaks our existing system.

#6

yeah for the beginning the RealPointers were ok

#7

Ok one basic difference between the algorithm described in the paper and the algorithm used in JOODE:
the algorithm implemented in JOODE is more generalized.
in JOODE we’ve a flexible lower and upper bound, while in the paper the lower bound is always 0 and there is no upper bound.

So both algorithms try to solve the following Equation (A,b are given, a, f have to be found):

a=Af+b (this is an equivalent problem to Ax = b+w as it’s described in lcp.cpp [we really should move that description to our sources, too] )
Now there are different extra conditions (let lo be the lower bound and hi the upper bound):
JOODE:
( lo(i) <= f(i) <= hi(i) and a(i) = 0 )
or ( a(i)>0 and f(i) = lo(i) )
or ( a(i)<0 and f(i) = hi(i) )

in the paper:
a(i) >= 0 and f(i) >= 0 and a(i)*f(i) = 0
this is equivalent to (for comparison with above):
( 0 <= f(i) <= +infinity and a(i) = 0 )
or ( a(i)>0 and f(i) = 0 )

tomorrow (if I have time) I’ll try to make those adjustments to my code. It actually works for contacts with the current algorithm, but it sometimes fails (strange behaviors, or endless loops).
this nub variable (number of unbounded constraints?) has something to do with those bounds I think (maybe no bounds… hmm)

so I’ll still only have to find out, whats that findex stuff’s about… :slight_smile:

#8

ok implemented now with hi and lo bounds - Box-Box-Collisions work fine, but the Joint-Tests don’t seem to work correctly yet, bet theres some mistake somewhere…

#9

IT WORKS!!!
I’ve tested most of the tests - and no problems ;D
woooo!!!
now the only stuff yet missing is that findex stuff (friction).
so it’s now on the cvs (as the default stepper).
It’ll might be a bit slow, because it’s still printing loads of output…

ohh yes it should be fairly easy to understand - I’ve did loads of dokumenting (I hope my comments are clear enough). For some things (especially in maxstep) pen and paper might help you … mmh I forgot one important part of the doku (the part that already was in the C-Source as doku) - ok I’ll add that.

#10

Oh great work arne. What does findex do? Does that mean your stepper is frictionless? I thought the findex stuff stood for feedback, for forces in joints and things, but I may (probably in fact) be wrong.

#11

it somewhere explains it as the friction index - but I still don’t understand the concept of it