About the NNCG solver

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Gabor Puhr
Posts: 11
Joined: Tue May 07, 2013 8:19 am

About the NNCG solver

Post by Gabor Puhr »

Hi,

I have implemented the NNCG (Silcowitz,Niebe,Erleben: Nonsmooth Nonlinear Conjugate Gradient Method for Interactive Contact Force Computation) in Bullet.
It is a super awesome stuff. It made really long chains very stable even with big mass ratios.
Though I have to admit that it emphasizes the original problems of the PGS.
For example pulling a long chain can became super crazy, because the original PGS "wakes up" only one joint in a chain per step.
See one solution here to this problem:
http://www.bulletphysics.org/Bullet/php ... f=4&t=9073

What I did: after a full PGS iteration I calculate the necessary values (beta, P, Deltaf) change the m_appliedImpulse (lambda) for every constraints and refresh the solverbodies.
Unfortunately, because of that in every iteration all of the solverbodies are refreshed twice as many times than in the original PGS.

How did you (or would you) implement this? What was your experience with this solver?

Best Regards
Gabor
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: About the NNCG solver

Post by Dirk Gregorius »

How many links in the chain are you talking about? And how large are the mass ratios?
Do you let the PCG converge until the error has fallen below some lower bounds or do you exit arbitrarily after some fixed number of iterations?
Gabor Puhr
Posts: 11
Joined: Tue May 07, 2013 8:19 am

Re: About the NNCG solver

Post by Gabor Puhr »

Hi,

It is a ragdoll (not for game purposes) it has 82 bones. The longest chain is about 35 bones.
Total weight is about 80 unit.
The biggest mass difference between two arbitrary bones is 6.05 / 0.002 = 3025.
For bones next to each other: 1.9 / 0.04 = 47.5.
I currently use fix iteration count to keep it simple, but it is under development.
About 50 iteration is quite nice if I don't drag it widely, but after 500 iteration I can even pull like crazy and it stays together.

Well one exception for the good behavior is the arm. If I pull the end of one finger even with very big iteration count sometime the arm cant pull the spine.
I think the reason is what Oliver Strunk wrote in "Stop my Constraints from Blowing Up!".
Where the shoulder bone is connected to one of the spine bone those are orthogonal to each other and not even the mass ratio is big there, but also the inertia ratio.
I have to check that part a little bit more.

I was wondering: the paper wrote that it is a good termination criteria to check if the lenght of deltaf became small with a constant.
But that value is proportional with the change of the lambda (deltaImpulse). The deltaImpulse can affect the position of the body proportional of its mass.
Usually we want the positional error to be minimal so I think the epsilon for deltaf should depend from the masses in the constraint island.
For example epsilon = positionerror / bigesst_mass_among_rbs.
In this case user can set positionerror.

Best Regards
Gabor
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: About the NNCG solver

Post by Dirk Gregorius »

You should be able to do this with PGS as well. With PCG you can be very close to a good solution in one iteration and in the next you have a big error again. See the graphs in Morten's paper. This behavior makes PCG impractical for games in my opinion since you cannot exit after some fixed number of iterations. If you are unlucky (and in practice you will be unlucky often!) the error will be significant. So you need to iterate until the error is below some threshold to be sure and this can be a lot of iterations!

Here is what I would do for you problem. Tweak the masses as shown in Oliver's presentation (e.g. ramp up the inertia of the clavicle bones or even use sphere inertia). Ramp up the iteration count to 16-32 and use true position correction. This is essentially like split-impulse, but you update the Jacobians in a separate pass after the velocity solve. You can find an example implementation of post-projection in Box2D. Post projection makes a huge difference for the joint quality!

Another thing you can try is to use block solvers. E.g. instead of solving one constraint after the other, you solve e.g. all constraints that define a hinge in a 5x5 system. You can even add the limit and use direct enumeration to solve the small LCP. Again you can find an example in Box2D (e.g the revolute joint). This will be expensive though. The small matrices will be symmetric positive-definite so you might use this to your advantage.

Also make sure that your mouse joint is not too strong. Otherwise you are always able to destroy your setup.
Gabor Puhr
Posts: 11
Joined: Tue May 07, 2013 8:19 am

Re: About the NNCG solver

Post by Gabor Puhr »

These were very useful information. Thank you.

You are right about the spikes, but though this ragdoll is not for game purposes it still would be bad to let the solver run for an arbitrary time. (it is a real time application)
One trick can be done: As I could see the spikes are usually very thin. So I can store the best error so far and once I reach some first iteration limit (assuming I haven't quit so far, because the error was already small) I can say that that I continue until I reach again the best error so far, but quit if reach another iteration limit.
I assume this second iteration limit can be very close to the first limit, but I will check empirically how far this should be to decrease the possibility of ending on a spike to a marginal value.

I will check how position-correction/post-projection is implemented in Box2D.

Also could you please tell me you opinion about what I wrote in the other thread, if I am not too rude?
http://www.bulletphysics.org/Bullet/php ... f=4&t=9073
How would you solve the problem that solvers usually handle partially restricted constraints by skipping the calculation of none violated constraints, but during solving sleeping constraint can be violated too?

Thanks
Gabor
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: About the NNCG solver

Post by Erwin Coumans »

Featherstone is very suitable for higher quality ragdolls (and long chains or tree structures). Another option is using a direct (block) solver, such as Dantzig or Lemke, Both Featherstone and direct MLCP solvers are in Bullet 2.82.

I am currently working on getting a Lemke solver to work with Bullet. We should create some ragdoll demo based on Featherstone and direct MLCP solver soon. We could use Featherstone or a direct solver only for the ragdoll, and regular SI/PGS solver for anything else.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: About the NNCG solver

Post by Dirk Gregorius »

That is very interesting Erwin. We should drop some ragdolls on a pile and also compare the performance hit.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: About the NNCG solver

Post by Erwin Coumans »

Hi Dirk,
Yes, it will be interesting to compare performance and quality indeed. The current Featherstone implementation should perform reasonably, but it is not optimized yet (no SIMD etc), so I'm not sure how it compares with a ragdoll of two-body constraints.

I plan on adding some ragdoll demo using Featherstone joints and contraint limits. First, we need to implement multi-DOF joints, at least a spherical joint, for easier ragdoll setup. We are working on that right now, it should be finished soon. Another nice thing to have is some (semi?) automatic conversion from a regular btRigidBody+btTypedConstraint ragdoll to a btMultiBody+btMultiBodyConstraint setup.

By the way, I added Lemke and also NNCG (by Gabor). The NNCG is mainly useful for high-quality smaller simulations, where you can run 500 to 1000 iterations,
so NNCG competes with Dantzig and Lemke in the area of robotics and such. For gaming, you usually don't have the luxury to run at 1000 iterations of course, although perhaps you can afford it for a small amount of constraints/bodies. You could think of it as a 'block' solver of a demanding constraint setup.
Post Reply