Hi guys,
This is my first blog post for #altdevblogaday, I hope you like it!
In this article I’m going to talk about a happy accident whereby, while writing my recent article on Speculative Contacts, I discovered the technique wasn’t just a quick fix for the continuous collision detection problem in rigid body simulation, it was actually an almost magical cure for a lot of common stability problems faced by physics engines.
Recap
Since this article is essentially a follow up to the original, it makes sense if you’ve taken a look at that already, you can read it here.
The original article was describing a new technique (well, new in collision detection terms anyway) whereby you can avoid having to compute the exact TOI (Time Of Impact) between two convex rigid bodies by simply finding the distance between the closest points on each rigid body and stuffing this info in to the constraint solver. The constraint solver then essentially does the hard work of TOI ordering for you as well as bringing the two rigid bodies to be in touching contact the next frame.
Unexpected delight
As I was coding the live demos to go with the article, I was fully expecting to have to employ Erin Catto’s accumulated impulses technique in order to get a simulation stable enough that it could demonstrate a big pile of objects all interacting with each other.
However, I was wrong.
Much to my amazement and delight I needed to employ no such magic in order to get a remarkably stable simulation.
Screen-grab from the demo
The above is a screen-grab from the demo I was writing.
What actually happened was the simulation was entirely stable, even running only one solver iteration! I was stunned. This had not been noticed during the course of me writing the physics engine for Little Big Planet PSP – what with all the other concerns about sleeping systems, internal edge bugs, incredibly tight dead-lines and so on, the scope to which this technique was fundamental to the stability of that engine was overlooked. Props must go to Dave Smith of Media Molecule from whom I first learned of this technique.
Analysis
So, what’s actually going on here?
Lets have a look at some data to clarify the situation:
Speculative velocity trace
The above is a trace of the sum of all contact constraints relative normal velocity after each constraint is resolved. Think of it as a graph of the stability of the system. As the balls all fall towards the obstacles there is a lot of interaction, but it very quickly settles down, apart from a little blip just past half way which is one of the balls hitting and rolling off a mid-air obstacle.
Now lets have a look at the same graph using a traditional discrete collision detection technique:
Discrete velocity trace
As you can see, the system never really settles down to any real equilibrium. Both examples are identical except for the solver resolution type chosen.
Contact flip/flop
The chief reason for the unexpected stability with speculative contacts, is that it solves one of the principle problems with discrete collision detection; contact flip/flop. This is when a contact is detected and then resolved repeatedly over the course of many frames. The discrete collision detection and resolution system will detect a contact (typically with distance < kThresh type comparison), resolve it and then after a few frames it will get pushed out of contact again and will fall very slightly towards the ground and get re-detected. This repeated pushing out/re-detection cycle will cause instability and jittering in the system.
The traditional way to fix this is to employ some kind of boundary distance model.
Figure 1
Figure 1 shows an artificial boundary around object A - when this boundary intersects object B the collision is resolved, but no penetration correction is done. This stops A getting pushed out of B - primarily caused by the penetration resolution.
The problem with this technique is that objects will tend to sit incorrectly as show in Figure 2
Figure 2
As you can see the boundary of A intersects B correctly so AB will be resolved, but it will not move any closer towards B, tending instead to sit awkwardly on B.
The speculative solution
Because speculative contacts deal with distance directly as a fundamental part of the contact resolution, this problem never occurs using speculative contacts. The objects are brought just into touching contact for the next frame; essentially postponing a portion of the collision response until then, thus distributing the collision load across frames allowing the constraint solver to be less stressed frame on frame.
Of course there are no threshold problems with this technique either, so objects sit exactly as they’re supposed to.
Conclusion
In this article I’ve touched upon a unexpected but very welcome side effect of this collision detection technique. I hope its of use to anyone involved in writing physics engines for games – there is certainly no way I’d considering writing a new game physics engine without it now!
Until next time, have fun,
Cheers, Paul.