🔒 Locked

Stack stability issues

Started by Black-Panther May 15, 2009 at 8:30 AM 16 replies 3.9k views

Original Post

28

May 15, 2009 at 8:30 AM

Hi everyone! I've written some kind of dynamics simulation (rigid bodies). But now I've the problem, that stacks aren't stable yet. I've tried out some things already, but nothing seems to work fine. Now my suspicion is that the problem lies in the main physics step, because every single part (collision detection (broad and narrow phase), contact geometry computation, collision resolution (impulses), and contact resolution) seem to work fine. But togehter, they don't behave good enough. Simple testing situations, such as one box on a static floor, work perfectly, but bigger instances (like higher stacks) are not stable. Here two videos: Big instances without stacking work quite fine But stacking isn't stable! __________________________________________________________ Since I think the mainloop arrangement is of interesst, I'll explain you how mine works: 1) Change velocity (due to impulses) according to external forces applied and gravity 2) Save current state for each object and integrate forward for dt 3) Broadphase collision detection 4) Narrowphase collision detection. All colliding pairs of objects are stored 5) If there were any collisions restore old saved state (before current frame) of each object, otherwise jump to 13 6) For each collision pair search nearest-features. If overlapping, then search for minimal penetration axis (SAT) 7) Compute contact set for nearest/overlapping features 8) If iteration limit isn't reach jump to 9), otherwise to 11) 9) Do collision response for all contact points. (if this is the last iteration, then treat all contacts as inelastic collisions!) -- For each point calc relative velocity and determine wheter the point is a contact or a collision -- Solve all collision points (Newton, elastic collision) -- See if some of the collision points became contacts, if so, add them -- Solve all contacts (inelastic collision, with additional seperating velocity if they are overlapping (depending on penetration depth in normal direction)) 10) Jump to 2) 11) Do Shockpropagation step: BFS in contact-graph, which freezes current layer and resolves collision between this and next layer! 12) Integrate dt forward. 13) Save integrated state as current and return Is there any major error in my method? Or is there a better one? How may I solve my stack stability issues? I'm thankful for any suggestions! ________________________ Maybe you want to see the problem for yourself. [especially try test.ogam] Here's the download (Press F1 to get help for the inputs!)

844

May 16, 2009 at 9:36 AM

I looked at your demos and in my opinion both your friction and normal forces don't seem correct. Besides this I scanned you main physic loop and it appears as if you use some algorithm as described in the paper by E. Guendelman. Is this correct?

Here is a simple loop that should work fine:

1) Update velocities due to external forces
2) Prepare constraints (e.g. compute position error, Jacobians, etc)
3) Satisfy constraints (compute velocity error and correct it for each constraint, iterate)
4) Update positions using new (corrected) velocities
5) Broadphase
6) Narrowphase

Note that the broad- and narrowphase come last. Otherwise the state of the broadphase for raycasts will be wrong.

HTH,
-Dirk

Author

28

May 17, 2009 at 10:27 AM

Hi!

I mainly followed the paper of Bender.
Why do you think my impulse-computations are wrong? What exactly is going wrong?

To your mainloop. I don't understand how this could even work? How do you get any information about collisions (and collision geometry) if you don't do any collision test before contact resolvation?
Furthermore if there is no loop inside the mainloop, can't a collisionresolution cause an other collision with an other object, which isn't detected by your loop?

Thanks for help!

844

May 17, 2009 at 12:10 PM

I assume that the impulse computations are wrong because:

a) Objects bounce apart
b) Objects begin to rotate around the up-axis

Maybe it is because your barrel-barrel contact only works partially and only barrel-plane works? Can you visualize you contact points? It would also be helpful if you can single step you application. Finally I suggest that you first test two boxes or barrels on top of each other and step through the code to see what is going wrong.

Here is my loop again:

void OnStartup( void )
{
mpWorld = CreateWorld();
mpWorld->Collide()
}

void OnIdle( float dt )
{
mpWorld->Step( dt );
mpWorld->Collide();
}

The World::Collide( void ) function caches the current contact geometry. This way I can create the non-penetration and friction constraints in the solver. Contacts depend on the position. So whenever you update the position of your bodies, you must update you broadphase and contact geometry. Otherwise the user will get incorrect results. As you can see I have all contact geometry in the solver as needed!

The World::Step( float dt ) function looks like this:

void World::Step( float dt )
{
// Integrate external body forces
UpdateVelocities( dt );

// Create non-penetration and friction constraints from contact geometry
PrepareConstraints( dt );

// Solve constraints using iterative solver - Projected Gauss-Seidel (PGS)
for ( n iteration )
{
SolveConstraints();
}

// Integrate corrected velocities
UpdatePositions( dt );
}

Author

28

May 17, 2009 at 12:46 PM

So you cache the contactgeometry from the previous integration step? If so, then there would be hardly a difference between yours and my main loop...

If you download my application, you can test the behaviour by your self. You CAN render the contact-geometry, you CAN singlestep through the simulation and then you'll see, that the impulscomputations should be correct.
For instance, if I put up a scene, were 2 boxes stand on top of each other, then it works just perfect (just a little jittering, but that's normal for microcollisions). Also a stack of 4 boxes works still good, but after 5 or 6 boxes height, it becomes instable... And I just don't get why!?

Edit:
The reason why the boxes start to rotate about their up-axis, is because in some frame the interpenetrate each other, and the correction impuls, to resolve the overlap is rather strong. Much bigger, than it would be to prevent interpenetration (with no initial PD!).

Perhaps some code will help:
It's less then it looks like

844

May 17, 2009 at 1:05 PM

How many iterations?
Do you warmstart?
How do you treat the penetrations (errors in the position constraints)?
What timestep do you use?

Handling penetrations or basically positions errors is called constraint stabilization. A common approach is Baumgarte stabilization. Maybe it is Bender's approach for the stabilization. I know Jan and we discussed his approach a lot. Maybe it is an issue in his solver. Did you try smaller timesteps and more iterations?

The Catto solver can handle five boxes with 4 iterations and 30 Hz. This is extremely good. You might take this as reference.

Author

28

May 17, 2009 at 2:16 PM

How many iterations?
Costumizable: In the demos 2 normal, 1 treating every collision as inelastic and 1 shockpropagation step

Do you warmstart?
What do you mean by that?

How do you treat the penetrations (errors in the position constraints)?
If a penetration occors, I compute the PD (through SAT) and give each contact-point-pair a intersection distance (which is max. the PD). Then in the iterative solver (impulse-computations) I add a certain amount of seperating velocity in dependence of the interpenetration depth. Like Jan Bender proposed it, but with a factor, that reduces the strength of the impulse (in the demo it was 0,02). Otherwise (if it was 1) everything always exploded the first time a interpenetration occured.

What timestep do you use?
60Hz

I don't know the Baumgarte stabilization.

The Catto solver can handle five boxes with 4 iterations and 30 Hz. This is extremely good. You might take this as reference.
But if this is a good reference value, how can physic engine keep stacks of 20 object and more stable??

PS: Maybe we could meet on IRC?

844

May 18, 2009 at 7:34 AM

Two iterations is not much. Try maybe 10. I remember that Bender's approach can use many iterations up to 100 until the error falls below some threshold. Also note that Bender used small timesteps in his demos. So go down maybe to 100 Hz.

Warmstarting means that you use the impulses from the last frame to start the solver in the last loop. This is one way how physic engines get stacks higher than 20 boxes. Ageia uses adaptive forces to gain more stability. Note that stacking 20 boxes is only to test the quality of an engine. In games the deactivation system will jump in. Havok has the best the stacking stability.

Instead of targeting for a relative velocity of zero at a contact point you could try to reach a separating velocity that removes some amount of the penetration. This is Baumgarte stabilization. So basically your equation becomes:

J*W*JT * lambda = -(0.1 * C / dt + J * v)

C is the position error (penetration).

Cheers,
-Dirk

Author

28

May 18, 2009 at 9:20 AM

I meant the overall collision-check and collision resolution iterations...
The iteration limit for each contact-point pair (for collision impulses) is 5. But it doesn't change much, if I put it to 8...

So, if I understood you right, there is no GOOD way to solve this problem. There are only ways to improve stability a bit. But even if this is true, a stack shouldn't "explode" due to interpenetration as mine does. I'll read some thing about the baumgarte-stabilisation, maybe I find the error.

To your suggestion to increase to 100Hz and allowing more iterations... This is HIGHLY inperformant... Then already a stack of 15boxes starts to lag!

Edit:
1) I don't use warmstart.
2) What are adaptive forces?
3) Also if I would implement a deactivation system, I don't think it would solve my problem. Because as you already noticed... boxes bounce apart!

844

May 18, 2009 at 11:44 AM

You iterate 5 times over the same contact point like this?

for ( all contact_points cp )
..for ( 5 iterations )
....cp->Resolve();

You should do:

for ( 10 iterations )
..for ( all contact_points cp )
....cp->Resolve();

Author

28

May 18, 2009 at 3:58 PM

I do it the right way...

Like this
for ( 5 iterations )
..for ( all contact_points cp )
....cp->Resolve();

132

May 19, 2009 at 3:22 AM

Definitely remove the shock step. Apart from anything else, it can cause nasty jitter at the top of stacks since little rotational adjustments at the bottom of the stack propagate up and amplify, resulting in big jumps at the top.

If the basic solver behaves nicely, and the collision detection/solver don't produce any rotation/lateral motion with reasonable amounts of interpenetration, then using warm starting instead should allow you to handle big stacks rather stably, without the shock step.

844

May 19, 2009 at 3:47 AM

Yeah, I also would recommend to remove the shockstep and try 128 iterations. This will halt your implementation if it is not efficient. But your primary focus should now be that things work.

Author

28

May 19, 2009 at 10:41 AM

I tried it out... But:
1) it goes down to 0.2 fps (in Debug-Mode) with a stack of 11 Boxes (no deactivation mode, no shockpropagation)
2) It's still far from being stable! (30 overall iteration and in each 10 iteration over all cp).

I guess, that the problem is in resolving the interpenetration case. How do you solve it? How is it "normally" solved?

844

May 19, 2009 at 1:23 PM

You use either Baumgarte stabilization or Post-Projection. See here for a quick introduction:

http://www.gphysics.com/archives/35

Author

28

May 20, 2009 at 7:24 AM

I thought of implementing the warm-starting... but there is a problem! I don't know where I even COULD use impulses from the last frame as startvalues...

Because my impuls computations are all straight forward... (as those from Jan Bender):

for(10 iterations)
{
__foreach(contactPoint cp)
__{
____urel = pA->GetPointVel(cp) - pB->GetPointVel(cp);
____uerr = vTargetVel - urel
____...
____impulse = uerr / (N * K * N);
____pA->ApplyImpulse(impulse, cp);
____pB->ApplyImpulse(-impulse, cp);
__}
}

Where should I apply/set as startvalue the impuls of the last frame?

844

May 20, 2009 at 7:53 AM

Please read Erin Catto's GDC presentations from 2005 - 2009. You can also have a look at his Box2D Lite implementation. Everything can be found here:

http://www.gphysics.com/downloads

If I were you I would drop the Bender stuff and implement Box2D Lite in 3D. Then add more shapes and more joints. You will learn a lot from this and get a high quality engine.

Author

28

May 21, 2009 at 6:51 AM

Ok... I will!

Thanks to all of you!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.