Physics Simulation Forum

Hi,
We have been experimenting with a simple change to the bullet logic that has yielded large improvements in the quality of the simulation. I thought I would share it here. I really think the improvements make this change worth integrating in the Bullet main branch.

The motivation for the change came from trying to address 2 specific issues in Bullet:
1): At the end of the bullet simulation pass, objects visibly interpenetrate.
2): Objects frequently jitter when they should be at rest or sliding smoothly on a flat surface. This is especially true for small scale and/or bouncy objects.

Notes:
The changes discussed apply to the split impulse solver only (not using split impulse sacrifices so much contact restitution accuracy that there seems to be little point trying to remove jitter and bounce penetration in those usage cases). It might be possible to apply similar improvements to a solver not doing split impulse but we did not investigate this.
In the rest of this post I will only consider gravity as an external force but the argument remains the same with additional external forces.

1): Is caused by the order of operations in the Bullet solver steps.
This is the order of the Bullet steps in the current version:
* Apply gravity. The velocity of the object is modified based on gravity. Note that the object is not moved at this time.
* Collision detection. Contacts between objects are determined and contact constraints created.
* Solve constraints. The velocity is modified based on the contact constraints applied to the object.
* Integrate Transform. The object is moved by the new resulting velocity and pushed out of penetrations.

The last step of the simulation is moving objects by their new velocity. This means that any new collisions introduced by this displacement will only be detected in the next physics step. At the end of the physics step, objects are likely inter-penetrating from the new displacement. in most game/simulation implementations this is when rendering takes place. Objects will frequently be rendered interpenetrating each other. This was quite blatant in a soccer simulation we made where the ball would completely disappear below the ground for one frame when bouncing from high lobs.

2): Is caused by the way Bullet handles collision restitution. Contacts in Bullet keep track of how long they have existed (contact age). Restitution impulses are arbitrarily applied for the first 2 frames of a contact's existence. The amount of restitution applied is based on the object's velocity (the "new" velocity, with gravity applied). The jitter appears when a contact decides it is not valid anymore (this will happen regularly when a cube is sliding on flat ground for instance). As soon as a contact has travelled too far from its original position, the contact gets destroyed and a new contact is generated to take its place. This new contact has a brand new age of zero and therefore will be doing restitution for the next 2 frames, leading to the corner of the cube suddenly jumping up. On small objects this can cause major displacements.

Another way to look at the problem is that the amount of restitution applied is too high. In a real life situation gravity is applied continuously and the ground resists continuously as well. With a discrete timestep, as the timestep of the simulation tends towards zero the problem disappears. With the current order of operations in Bullet however, the object gets restitution for one timestep worth of gravity. In other words the object bounces as if it had been free falling for one frame, even though the contact already existed at the beginning of the frame.

We propose to make a simple change to the order of operations to address both issues. Since it is necessary to discretize the influence of gravity we also propose to discretize it to minimize restitution instead of maximizing it. In other words we use the velocity of the object at the beginning of the frame to compute restitution instead of the velocity after applying gravity. The quality gain of doing this is fairly intuitive: The velocity of the object at the start of the frame is a "real" velocity. There is a moment in time when the object was moving at this velocity. the velocity after gravity is added however is an hypothetical velocity, in the case of a resting object, the velocity after applying gravity will actually never happen (contact constraints will kill it), therefore using this fictitious velocity for restitution is introducing energy into the world out of nowhere.

Here is the proposed order of operations:
* Apply gravity. The new tentative velocity is stored separately from the object's "old" velocity.
* Move the object by the old velocity.
* Collision detection. Update contacts and create contact constraints.
* Solve constraints. The old velocity is used to compute restitution forces. the constraints however are used to constrain the new tentative velocity. A final resultant velocity is obtained and written in the object.
* Push out of penetrations. Since we use split impulse this phase does not impart any momentum to the object, it simply fixes the state of the world so there are no penetrations.

This new approach solves both issues mentioned above:
1) at the end of the frame the simulation is in a "glitch free" state. Penetrations have been resolved and objects have not moved by their next time step yet. As long as the solver was able to handle all contacts, no penetration will be visible at this time.
2) There is no need for contacts to keep track of their age anymore. Restitution is applied every frame on all contacts but using the velocity at the start of the frame. This means that a resting object will get a zero restitution force which is exactly what you would expect. This approach also leads to much more accurate sliding friction behavior with objects not erroneously sliding down inclines when friction should normally stop them.

Other benefits:
Even if the idea behind it is fairly different the code changes to switch to this new order of operations are very small. The changes only touch 5 files in Bullet and affect few lines of code.

In practice, the stability gains from this method were quite drastic. We were able to remove the erp factor altogether and get much more stable object stacking than before.

I limited the talk to gravity as a force. One thing to notice from the new method is that it becomes possible to differentiate between forces that act continuously on the objects (like gravity or magnetic fields) and instant impulses. In our implementation, we separated the two by having instant impact forces be applied directly to the (old) velocity of the object, while continuous forces get only applied to the new "tentative" velocity. This means that on an object at rest, continuous forces will only generate restitution if the contacts do not constrain them. However instant forces will generate restitution even if the constraint fights against it. A good example of this would be a rubber ball resting on a table. Gravity should not cause the ball to bounce even if the contact gets regenerated, however another ball falling on top of it will cause it to bounce upward from the impact.

I would be glad to share our modified bullet files if people are interested. They also contain other bug fixes and small optimizations that would take too long to go over in detail.

I'd be interested in trying your changes.

How high could you stack before, and how much higher can you now reach?

i'm interested and wish can help... .

I'm making a game with a lot of sliding pieces, and they are indeed jittering and penetrating the floor.
I would be so glad if you could share your modified bullet files with me so I can try them out.
Thanks in advance.

Do you, by any chance, use btBvhTriangleMeshShape for your scene? It might not be your problem, but we've recently worked around some contact point issue that made boxes jitter on a simple floor. Maybe you'll want to take a peek here; our patch is quite small.

Sounds like some awesome work - how about you share on github?

Thanks

We never compared numbers of objects stacked. That number is mostly controlled by the number of iterations you use in your solve pass. What we did compare was stability in a fixed size stack, especially relating to objects drifting on each other in what should be a static stack.

I have been trying to attach files since yesterday but the forum keeps failing on me. I'll try posting them one at a time.

I can post the entire Bullet folder if someone tells me of a way to easily post it and make it accessible to everyone.

Next file

I can't seem to be able to post the remaining files, looks like this forum has a 30kb size limit on files. The meat of the changes is in btSequentialImpulseConstraintSolver.cpp and btDiscreteDynamicsWorld.cpp and those files are too large to attach.

Can you zip them? Or, if all else fails, zip a patch file?

Zipped version

And the last one.
That's all the main changes for the change. If I find an easy way to post the entire bullet folder somewhere, I'll let you know.

I've create a patch file to try it out, only I am having trouble compiling.

You seem to have created btVector3::s_zero static member (I assume), but haven't submitted any change to btVector3.h. I am also missing getWorldPosition(), translateWorldPosition(), CF_DISABLE_STATE_CHANGE, etc. And there are errors with btRigidBody::getCenterOfMassPosition() and btRigidBody::getCenterOfMassTransform()...

What version of bullet were you basing this change from? (I was using the latest, which is 2.80-rev2531).

Sorry about that I should have been more explicit: We have many more changes in our Bullet code than the ones discussed in this thread. I would have to post our entire Bullet folder to let people compile it directly.

The files I posted are more meant to be diffed against what you have so you can integrate the changes. If you diff the files you will see that there are very few relevant code changes overall. Any function that doesn't compile is not relevant to the proposed changes and can be reverted to what is in your current implementation.

Sorry about that. I will see if I can find somewhere to post the entire folder.

What version of Bullet are you based on?