Major contact stability improvement
Posted: Wed May 23, 2012 5:21 pm
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.
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.