# Physics Simulation Forum

 Page 2 of 2 [ 20 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: A new PGS solverPosted: Fri May 30, 2008 10:06 pm

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

 Post subject: Re: A new PGS solverPosted: Fri May 30, 2008 10:13 pm

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

 Post subject: Re: A new PGS solverPosted: Sat May 31, 2008 12:05 am

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

 Post subject: Re: A new PGS solverPosted: Sat May 31, 2008 2:15 am

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

 Post subject: Re: A new PGS solverPosted: Sat May 31, 2008 4:52 am

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 20 posts ] Go to page Previous  1, 2

#### Who is online

Users browsing this forum: No registered users and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities