Speculative Contacts

Continuous Collision Detection is difficult to achieve, so I was quite excited when I read a blog post by Paul Firth regarding "Speculative Contacts". You can find the post with the wonderful illustrations here: Speculative Contacts.

Paul doesn't claim to be the inventor of the mechanism but he made it quite popular. The idea of the algorithm is – as Paul stated:

(..) to try and move the majority of the work out of the collision detection system and into the contact solver (..)

With this new system you don't go through the troubles of generating, sorting and dealing with tois (time of impact) – you basically just make your contact solver deal with negative penetration (=seperation, "s") and let your Collision System report Contacts which don't already exist.

Let's have a look at the following picture. Object "B" is static and doesn't move. "A's" velocity is shown by an arrow. There is also the position of A, after the timestep. You can see that A just tunneled object B, because no contact was created because nothing actually collided.

We now create a speculative contact – we predict where the objects collide (yellow dots) using conservative advancement. The solver is told to remove so much normal velocity from Body A that it is in contact with B after the timestep. Our picture now looks like this:

Note that the tangent velocity stays unaffected and that we only affect the normal velocity. Looks nice – we didn't tunnel this time! But we miss all possible collisions in the middle of the picture. See the following picture with another static obstacle "C":

Doh! What went wrong? The conservative advancement check we did initially against "C" was negative – and then "B" changed our direction. I often saw the statement: "use conservative advancement and it will be fine" – no it wont! So how can we use the speculative contacts (the technique seems to be to genius to discard) ?

Find all objects within the swept-expanded bounding box of "A" (the huge light blue box) and instead of doing conservative advancement detect all closest points to all overlapping objects (yellow dots) – that's the secret of the algorithm!

The contact solver is hopefully finding a global solution now, in which neither "B" nor "C" is tunneled. Again: Doing a closest point search is not a good approximation it's absolutely necessary!

We also introduced a new problem, called ghost collisions, because we may detect a speculative contact which actually never happen. But it's hardly to notice at high velocities and a bit of cheating is allowed. Remember: You never can prevent tunneling in reasonable time, at some part you have to cheat. This method here has the advantage that it is easy to implement and very cheap in terms of CPU costs.

Speculative Contacts are implemented in Jitter (currently only in the SVN). You can enable speculative contacts using "Body.EnableSpeculativeContacts" or "CollisionSystem.EnableSpeculativeContacts". The closest point algorithm used is GJK (see GJKCollide.cs). If the swept bounding boxes of two bodies overlap and there is no "standard" collision, GJK is asked for closest distances.