Submit to StumbleUpon Share

Hello and welcome back to my blog...

Today i'm going to talk about a continuous collision detection technique called Speculative Contacts which has been employed in games such as Little Big Planet PS3 and PSP versions.

First of all we need to answer some basic questions.

What is continuous collision detection?

Continuous collision detection attempts to solve the bullet through paper problem as shown in Figure 1.

Figure 1

In Figure 1, object A is travelling so fast that within one frame it has passed straight through object B.

With traditional time-stepping techniques (i.e. an intersection check on each frame), this case is missed.

This is the first part of the problem (and actually the easiest part to solve). The second part of the problem is how you deal with many simultaneous collisions within one frame, the so called Time Of Impact ordering problem.

Figure 2

So in Figure 2, we've gone ahead and found the exact time of impact between A and B and we're happy until C comes along and messes everything up by colliding with A before A collides with B.

This turns out to be a real pain in the ass in general because it means that the collision detection problem is no longer separated from the act of moving objects around, its now very closely tied to it which means everything suddenly gets a lot more expensive to compute.

To solve this problem you need to treat all collisions in TOI (Time Of Impact) order, from the earliest TOI in the scene to the latest.

And even if you do that, you might find that as you resolve each collision, the trajectory of the objects changes so much that now objects that you didn't expect to be colliding at all, are now in fact colliding.

Figure 3

In Figure 3, A collides with B and is resolved, but A's new velocity causes it to collide with C which wasn't originally expected by the collision system. This cannoning problem means that collision detection must be re-performed as each TOI impact is processed, which can get very expensive.

To mitigate this problem, typically each object is bounded by a box which contains the object at the start and end of the time-step, and then all such boxes which overlap are considered to reside within a TOI island, wherein any objects are candidates for collision with any other object in the island.

This is all very tiresome and expensive, it would be nice if there was just some magic solution to all these problems, or at least some acceptable approximation...

Speculative Contacts

Enter speculative contacts. The basic idea is to try and move the majority of the work out of the collision detection system and into the contact solver, which is designed for finding the 'global correct solution' to problems involving many simultaneous interacting influences (either through projected-gauss-seidel ref: Erin Catto of the excellent Box2d, or other methods).

Figure 4

In Figure 4, we compute the closest distance d between the two objects; the idea is that we want to remove exactly the right amount of velocity from A such that it will be exactly in touching contact with B on the next frame. This is the essence of the speculative contacts technique.

Figure 5

Figure 5 shows where we want to see A on the next frame. Note that this is cheating slightly because we're throwing away time - compared to Figure 3, you can see that the motion of A is cut short; it no longer rolls across B as it used to. It postpones the secondary motion of A to the next frame.

Its very important that the speculative contact do no work (i.e. not have any influence on other objects) unless the relative normal velocity is greater than the distance between the objects divided by the time-step.

Figure 6

In Figure 6, v.n is less than the distance d (divided by time-step) - i.e. A will not touch B next frame, so the constraint should do nothing.

Contact con = contacts[i];
Vector2 n = con.m_normal;
 
// get all of relative normal velocity
double relNv = (con.m_b.m_Vel-con.m_a.m_Vel).Dot(n);
 
// we want to remove only the amount which leaves them touching next frame
double remove = relNv + con.m_dist/Constants.kTimeStep;
 
if (remove < 0)
{
	// compute impulse
	double imp = remove / (con.m_a.m_InvMass + con.m_b.m_InvMass);
 
	// apply impulse
	con.m_a.m_Vel += imp * n * con.m_a.m_InvMass;
	con.m_b.m_Vel -= imp * n * con.m_b.m_InvMass;
}

The above code fragment demonstrates the calculation involved to achieve the result in Figure 5, for a non rotating body. Note, this is simplified for understandability.

Stability

Stability is a measure of how stable a simulation is - i.e how much jittering is present, or how well the simulation copes with big piles of objects.

I just wanted to compare and contrast the discrete method for collision resolution at this point because i think it will prove very interesting.

In discrete collision detection, the above code fragment might look like this:

UPDATE: since i wrote this article a number of people contacted me and quite rightly pointed out that i didn't include any penetration resolution in the discrete solver; the main reason was that i didn't want to make the discrete solver look worse than it was in the simplest of demos - i often found that penetration resolution would actually cause a solver to jitter more than if it weren't there at all.

However, by not including it i made the more complex demos behave more poorly than they should have, since they would tend to sink and sag more than they should. I have since updated all the live demos and code snippits to include penetration resolution.

Contact con = contacts[i];
Vector2 n = con.m_normal;
 
// get all of relative normal velocity
double relNv = (con.m_b.m_Vel-con.m_a.m_Vel).Dot(n);
 
// remove all of it + resolve penetration over the course of some frames
double remove = relNv + 0.4 * (con.m_dist + 1) / Constants.kTimeStep;
 
// but only when objects are intersecting and moving towards each other
if (remove < 0 && con.m_dist < 0)
{
	double imp = remove / (con.m_a.m_InvMass + con.m_b.m_InvMass);
 
	// apply impulse
	con.m_a.m_Vel += imp * n * con.m_a.m_InvMass;
	con.m_b.m_Vel -= imp * n * con.m_b.m_InvMass;
}

Note that probably you would never even get to the above code when the objects are separated in a discrete collision system (since why would you run the contact solver on separated objects?), but for comparison purposes i've converted the original code to be discrete.

Now, the actual difference between these two pieces of code is tiny, but the difference the speculative method makes to the stability of the simulation is amazing.

In all the demos on this page, the time-step is fixed to 1 / 30 of a second.

You can pick the ball up by dragging it.

In this simple example, a frictionless ball is resting on the concave intersection of two rectangles; note the slight jittery motion of the ball. In this example there is no penetration resolution at all, and the solver defaults to the discrete code above running 1 iteration only.

The jittering present in this most simple of examples exemplifies the problem facing all physics engines which deal with the collision problem in a discrete manor - its a real PITA to solve.

The chief reason for it is this condition check (taken from the above code):

if (/*remove < 0 &&*/ con.m_dist < 0)
{
...
}

The check for intersection. The reason this causes the jittering is because it forces the contact to activate and deactivate constantly as the collision is resolved and then unresolved frame after frame.

A quick trace of the number of contacts solved on the first few frames confirms it:

  1. 1
  2. 1
  3. 1
  4. 2
  5. 1
  6. 2
  7. 1
  8. 2

Now, click on the drop-down labelled 'discrete' and change the mode to speculative. Notice the jittering is gone?

The same trace this time looks like this:

  1. 2
  2. 0
  3. 1
  4. 2
  5. 2
  6. 2
  7. 2
  8. 2

Much more pleasing - the resolved contact count stabilises quite quickly leading to a much more stable simulation.

double remove = relNv + con.m_dist/Constants.kTimeStep;
 
if (remove < 0)
{
...
}

The above is the speculative code; the only difference is the handling of what relative normal velocity to remove. The speculative code always removes enough of the relative normal velocity for the object to just touch the surface on the next frame. The contact is now not getting turned on/off so often, and this makes all the difference.

The above example defaults to a speculative solver, with a lot more balls. Note that there is still only one iteration! If you change the solver mode to discrete you can see the difference it makes.

I've included a sequential discrete solver in the drop down for comparison - even at 10 iterations the system isn't fully resolved.

Angular

No article discussing continuous collision detection and resolution would be complete without attempting to address angular continuous collision. That is, when an object rotates very quickly it should still not miss collisions.

Figure 8

In Figure 8, we would still like to be able to detect the collision of A with B even though A is very thin and rotating very quickly.

Luckily, speculative contacts do trap this case, simply by using the closest points between objects a pretty good approximation can be made with the time of collision. Its not perfect, but it does a reasonable job.

As you can see in the above demo, the collision is handled, although the exact point of collision can be slightly wrong in some cases.

It can also handle the following case which crops up a lot in production code.

Figure 9

In Figure 9, A is moving toward B quickly and with no rotation, the ensuing collision causes a fast rotation on A, which would cause the right side of A to penetrate B on the next frame. But by simply building the contact set as you would for any discrete collision system and adding both contacts, the case is handled just fine, even with only a few iterations of the solver.

Goodbye TOI ordering

Ok, so now we have the simple stuff out of the way, we can get into the really interesting part; using a simple modification of the speculative code we can actually move the TOI ordering problem out of the collision detection system and into the constraint solver.

But first we need to cover the basics of using a solver to approach the globally correct solution to the problem of constraint resolution.

Globally correct

This is a little bit tricky to describe but it basically describes a situation where all constraints have been resolved, but only just - i.e there was no constraint after the solver has run which is over-resolved (too much correction).

The problem is mainly due to the uni-lateral contact constraint, which is only allowed to 'push' objects apart but never 'pull' them together; otherwise objects would stick together like glue.

Because contacts are only allowed to push, they have no mechanism available to them to counter adjust themselves - imagine a situation where solving one contact causes another contact to be solved 'too much' (relative normal velocity now positive rather than 0), this over corrected contact can do nothing about this problem. The result is an unstable simulation.

The solution is to use a solver, such as Erin Catto's sequential impulse system which allows the uni-lateral constraints to push and pull during the iterations, but still ensures that the resulting final impulse only pushes. Please see his GDC slides for a much better explanation.

If it sounds confusing, don't worry, the actual code associated with it is rather simple by comparison.

TOI joy

Ok, so now we have a global solver we can finally tackle the TOI problem. What we do is make a small change to the speculative code:

Contact con = contacts[i];
Vector2 n = con.m_normal;
 
// get all of relative normal velocity
double relNv = (con.m_b.m_Vel-con.m_a.m_Vel).Dot(n);
 
// we want to remove only the amount which leaves them touching next frame
double remove = relNv + con.m_dist/Constants.kTimeStep;
 
// compute impulse
double imp = remove / (con.m_a.m_InvMass + con.m_b.m_InvMass);
 
// accumulate
double newImpulse = Math.Min(imp + con.m_impulse, 0);
 
// compute change
double change = newImpulse - con.m_impulse;
 
// store accumulated impulse
con.m_impusle = newImpulse;
 
// apply impulse
con.m_a.m_Vel += change * n * con.m_a.m_InvMass;
con.m_b.m_Vel -= change * n * con.m_b.m_InvMass;

Notice the condition checking for negative relative normal velocity has gone, to be replaced by a clamp inside the impulse calculation, and the impulse is accumulated. This allows the system to converge towards the global solution.

In the above demo, the balls are constrained on the y axis (you can move them by dragging them) and the ghost balls represent where the solid colour balls will end up next frame.

In the start scenario of this demo, red collides first with blue before later colliding with green, which should leave red hanging in the air incorrectly, as per the diagram in Figure 7

Figure 7

Because the mode is set to 'speculative sequential' this situation is handled correctly. If you change mode to simple 'speculative' you will see the difference.

Here is a step by step of what is happening over a course of 3 iterations (remember its the ghost balls we want to see colliding with each other):

Iteration 1

On the first iteration, red collides with blue first before green collides with blue at an earlier TOI leaving red in the air as per usual.

Iteration 2

On the second iteration, the motion of red which was postponed is now allowed to continue by the global solver (allowing pull as well as push during the iterations), but the collision isn't resolved yet.

Iteration 3

The third iteration sees the solution converging to the correct global solution.

By moving the TOI ordering problem inside the constraint solver like this, we completely avoid having to do all the hard work in the collision detection phase.

The number of solver iterations used will affect the quality of the result, as ever.

Other advantages

I just wanted to touch on a few other advantages that speculative contacts give:

  • No collision threshold required - because we don't have the discrete collision problem of toggling between colliding/not colliding we don't need to mitigate this by having a collision threshold around objects.
  • No inner hull required - now that distance is a fundamental part of the constraint system we don't need to try and avoid penetration by shrinking our collision hulls by some radius which can cause problems with triangular objects.
  • No need to distinguish between objects which are considered to be 'fast' and have special treatment in collision detection terms. All objects can go through the same system. This means you can have things which have previously been impossible, like a fast moving stack of blocks which all collide with the floor and each other.

Problems

Of course no technique is without its associated problems. The most notable problem suffered by speculative contacts is the problem of so called 'ghost' collisions.

Figure 10

In Figure 10, the closest points between A and B are shown, but due to the motion of A, a ghost collision will be generated where A incorrectly collides with the plane of the collision normal on B.

In practice the problem is less apparent for circles than it is for polygons. The correct way to solve this problem is to use a technique such as Conservative Advancement, ref Erwin Coumans of Bullet fame, rather than a simple closest points between objects approach as detailed in this article.

The second problem is that if an object is warped into severe penetration it will tend to ping back out again rather than smoothly correct to zero penetration. This can be solved by splitting the distance equation up for negative / positive, but i've not included that in this article for clarity's sake.

Update

I just realised i've committed a physics faux par by not including a demo of the physics engine 'hello world' - the traditional Pile 'O Boxes. So here it is, for your delectation. Running in only 3 iterations, the stability is impressive. I've updated the source code to contain this demo as well - if you already bought it and want this, just post a comment and i'll email you the updated code for free 🙂

Conclusion

I believe that speculative contacts are very well suited to physics simulation in computer games where the requirement for speed over absolute accuracy is a good fit for the technique. If you still remain unconvinced, buy a copy of Little Big Planet and have a play around with the 'create mode' - see if you can break it; its pretty robust.

Source code

If you found this article useful and would like to see more like this, please consider buying the source-code which i have made available on this page for a small cost - this will allow an indie developer like me to justify his existence for another month, and more importantly pay for things like food and rent!

After purchasing, you will be redirected to a page where you can download the source-code of every example in this article, written in c# and requires silverlight to build.

USD 19.99

Subscribers can access the source here

Have fun,

Cheers, Paul.

Submit to StumbleUpon Share