Saturday, April 23, 2011

Nonpenetration requirement = troublesome

I skimmed through the collision detection sections of "Game Physics" to try and figure out what kind of physics engine the book has in mind.  From what I could gather, it depends on non-interpenetration.  Non-interpenetration is achieved by finding the time of collision and stopping the simulation at that point in order to handle the collision.  The most referenced method seemed to be bisection.  Bisection involves cutting the delta time in half every time a collision is found and restarting the whole simulation from the initial time.  You eventually end up with a delta time which advances the simulation up till the first collision.

One problem with making sure that there are no interpenetrations by stopping the simulation at the time of collision is that the delta time can become very, very small.  When this happens, you end up simulating many times per step in order to get through the whole step delta time.  If the computer has the power to manage this within the time allotted to the physics step then you don't have a problem, but this is rarely the case.

One example of where this could happen is when a ball is bouncing with a high velocity between two immovable blocks.  This could potentially be "solved" by putting a cap on velocities.

Another example is when a block is resting on the ground.  The block will have a normal velocity towards the ground due to gravity, and so the game detects a collision right off the bat and sets the delta time to be zero (collision occurred at the initial time).  The offending velocity is corrected and the simulation attempts to finish the step.  However, the velocity will go back each time due to the constant effect of gravity and the delta time will remain zero.  Presto!  An infinite loop.  Now, I should note that my only experience with this problem has been with a velocity-based constraint solver.  From what I understand, an acceleration-based constraint solver would negate gravity and the normal velocity would not point towards the ground.  One idea I have for solving this problem under a velocity-based solver is to detect when an object is at rest and suspend simulation of that object until something it is touching is no longer suspended (the ground is always suspended in this setup).  This would also be a rather good optimization, and I suspect it is used in several physics engines.  Deciding whether or not an object is at rest would likely involve checking if the velocity is lower than some minimum.  The minimum should be lower than the amount of velocity gained in one step due to gravity though, otherwise objects will become suspended (literally) after entering free-fall.

I'd like to mention a few things I learned about animation today, but they will have to wait till tomorrow.

No comments:

Post a Comment