Re: A new PGS solver
Posted: Fri May 30, 2008 10:06 pm
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).
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).