Box2D now implements a block solver for normal contact. If the contact manifold consists of two points, then the 2by2 MLCP is solved directly through enumeration. For small systems enumeration is easy to implement:
1  Assume both constraints are active and solve the 2by2 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 nonnegative 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 2by2 case this is simple. If the condition number is too large then Box2D will ignore the second contact (because the constraints are somehow redundant).
A new PGS solver

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: A new PGS solver
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.

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: A new PGS solver
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. Roundoff error creates small negative values that break the nonnegativity 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?
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?

 Posts: 135
 Joined: Wed Jul 27, 2005 10:28 am
 Location: SCEE London
Re: A new PGS solver
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.Erin Catto wrote: 1  Assume both constraints are active and solve the 2by2 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 nonnegative then we are done.
3  Same as step 2 except reversed.
4  Set contact force 1 and 2 to zero.
cheers,
Antonio

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: A new PGS solver
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.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.
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.