A new PGS solver

Please don't post Bullet support questions here, use the above forums instead.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: A new PGS solver

Post by Erin Catto »

Box2D now implements a block solver for normal contact. If the contact manifold consists of two points, then the 2-by-2 MLCP is solved directly through enumeration. For small systems enumeration is easy to implement:

1 - Assume both constraints are active and solve the 2-by-2 equality problem. If both contact forces are positive then we are done.

2 - Assume contact 1 is active and contact 2 is inactive. Solve for contact force 1. If contact force 1 is positive and contact velocity 2 is non-negative then we are done.

3 - Same as step 2 except reversed.

4 - Set contact force 1 and 2 to zero.

Dirk originally implemented this in Box2D_Lite in Jan. 07. I devised a scheme to make it work with accumlated impulses so that each block solve considers the total impulse applied over the step. Recently I ported this to Box2D 2.0.

The result is quite good and Box2D is now able to stack 24 boxes vertically without difficultly (1m cubes, 60Hz, 10 iterations, gravity = 10m/s^2). The behavior is similar to sphere stacking.

One additional contribution: you need to check the condition number of the block to avoid numerical problems. In the 2-by-2 case this is simple. If the condition number is too large then Box2D will ignore the second contact (because the constraints are somehow redundant).
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: A new PGS solver

Post by Dirk Gregorius »

Did you assert that after case four the relative velocites at the contact point are separating? I remember that I ran in situations where this was not the case which indicated that the LCP had no solution. So in this case you need to fallback on solving contact points individually. Maybe you condition number accounts for this and this doesn't happen anymore if the system is well behaved.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: A new PGS solver

Post by Erin Catto »

I took a look at this. Failure of enumeration only seems to occur infrequently. It seems to happen when the contact force and velocity are both zero at one of the two points. Round-off error creates small negative values that break the non-negativity tests.

Therefore, we should use some tolerances to guide the selection of the correct active set. I still need to determine how these tolerances should be selected. What is a tiny impulse? What is a tiny velocity?
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Re: A new PGS solver

Post by Antonio Martini »

Erin Catto wrote: 1 - Assume both constraints are active and solve the 2-by-2 equality problem. If both contact forces are positive then we are done.

2 - Assume contact 1 is active and contact 2 is inactive. Solve for contact force 1. If contact force 1 is positive and contact velocity 2 is non-negative then we are done.

3 - Same as step 2 except reversed.

4 - Set contact force 1 and 2 to zero.
given that the task is to find a set of active constraints that will solve the problem it would seem more logical and efficient to start with the simplest cases and increase the size of the system only if a solution has not been found? this should also avoid the redundant cases you mentioned i suppose.

cheers,
Antonio
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: A new PGS solver

Post by Erin Catto »

Antonio Martini wrote:given that the task is to find a set of active constraints that will solve the problem it would seem more logical and efficient to start with the simplest cases and increase the size of the system only if a solution has not been found? this should also avoid the redundant cases you mentioned i suppose.
My assumption is that if a contact point exists, then it is usually active (think of box stacking). If a contact point is not active, it will not be around much longer.

Also, the goal is to find a very accurate solution for the stacking case. So if the full manifold is not active, we could just fall back on the old sequential solution.
Post Reply