Physics Simulation Forum

 

All times are UTC




Post new topic Reply to topic  [ 20 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: A new PGS solver
PostPosted: Fri May 30, 2008 10:06 pm 
Offline

Joined: Fri Jul 01, 2005 5:29 am
Posts: 324
Location: Irvine
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).


Top
 Profile  
 
 Post subject: Re: A new PGS solver
PostPosted: Fri May 30, 2008 10:13 pm 
Offline

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 871
Location: Kirkland, WA
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.


Top
 Profile  
 
 Post subject: Re: A new PGS solver
PostPosted: Sat May 31, 2008 12:05 am 
Offline

Joined: Fri Jul 01, 2005 5:29 am
Posts: 324
Location: Irvine
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?


Top
 Profile  
 
 Post subject: Re: A new PGS solver
PostPosted: Sat May 31, 2008 2:15 am 
Offline

Joined: Wed Jul 27, 2005 10:28 am
Posts: 135
Location: SCEE London
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


Top
 Profile  
 
 Post subject: Re: A new PGS solver
PostPosted: Sat May 31, 2008 4:52 am 
Offline

Joined: Fri Jul 01, 2005 5:29 am
Posts: 324
Location: Irvine
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page Previous  1, 2

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group