In a 60 frames per second game the collision detection tests a moving object at 60 positions – one position per frame. Obviously, we miss less collisions if we check more positions, for example 10 intermediate positions per frame. This would increase the sample rate to 600 Hz. – A simple brute-force solution. But collision detection is one of the most expensive parts of the game engine. A part which we don’t want to make 10 times slower. Additionally, we could still miss collisions, and finding the time of impact is still not very accurate.

The bisection method (binary search) is sometimes used in physics simulation to find the time of impact: If an object has no collision in frame i and penetrates another object in frame i + 1, then the time of impact is somewhere between does frames. Let’s assume that frame i is at time 0 and frame i + 1 is at time 1. We check for collision at time 0.5. If there is no collision, we check at time 0.75. If there is a penetration, we check at time 0.625. And so on, always halving the time interval until the penetration is sufficiently small.

With this scheme we can arrive at the time of impact very quickly, but we do not touch the tunneling problem because the bisection does not start if there is no collision at frame i and i + 1.

A shooting game has typically many very fast, very small objects: bullets. Bullet collisions are better checked with ray casting. A ray is cast from the bullet’s current position to the bullet’s position of the next frame. This way no collisions are missed.

The ray casting approach can also be used for bigger objects if we cast a ray from the object center point to the future center point. We can get better results if we place more sample points in the object and shoot several rays. But this approach is not appropriate to test for collision of two moving objects because it is unlikely that rays of one object hit the rays of the other objects. The ray casting method is good for the bullet vs. slow object scenario.

So far we have looked at general solutions that work for all kind of shapes. But if the involved shapes are simple (e.g. sphere, AABB, triangle), it is possible to find an analytical solution for specific shape pairs. Especially for moving sphere vs. moving sphere it is not too difficult to develop an exact test that determines the time of impact. Several tests are discussed here: http://www.realtimerendering.com/intersections.html (see section "Dynamic Object Intersections").

If we have an analytical solution for moving sphere vs. moving sphere, we can use this to test the bounding spheres of moving objects – instead of the exact shapes. This is an approximation – but it’s okay because we use this approximation for fast moving objects where any errors are hardly noticeable on the screen.

I have seen cases where the tested spheres are not the bounding spheres but smaller spheres that represent the "core" of the moving objects.

Most of the time the involved shapes are convex (because convex shapes are a lot faster in the collision detection compared to concave shapes). Gino van den Bergen has developed an iterative algorithm that computes CCD for two convex shapes (convex hulls, spheres, capsules, boxes, …, all convex shapes!). It works by performing a GJK-based ray cast on the configuration space obstacle (CSO). It is described in the paper Ray Casting against General Convex Objects with Application to Continuous Collision Detection. – And if you think: GJK, CSO … what!? You clearly need to read this book: Collision Detection in Interactive Environments, Gino van den Bergen

The above method works only for linear movement – rotational movement is ignored. An iterative method that works for rotational movement too is Conservative Advancement. I think the paper Continuous Collision Detection for Non-Convex Polyhedra gives a very good introduction to this algorithm and how it can be extended for general polyhedra. It basically works like this: In each iteration, compute the closest points of the two objects (for example using GJK). Use this information to compute a safe distance by which the objects can move while avoiding collision (see paper). After only a few iterations the time of impact can be found.

Erwin Coumans developed a very interesting version of Conservative Advancement in the paper Continuous Collision Detection and Physics. It is very similar to Ray Casting against General Convex Objects where the ray is cast against the deforming CSO, so that the algorithm works for linear and angular movement (rotations) of convex objects.

This list is by far not comprehensive. There are many other papers and ideas about there.

Normally, game physics libraries advance the simulation in fixed time steps (e.g. 1/60 s). In each time step following steps are performed:

1. Detect collisions
2. Compute forces
3. Apply forces (this step updates the bodies' velocities)
4. Solve constraints (contacts and joints; this step corrects velocities so that constraints are all satisfied)
5. Update positions (using the corrected velocities)

The order and details of this steps can vary between simulation methods, but the steps are basically the same. The problem of discrete collision detection is: The collisions are only detected at the beginning of the time step. With large time steps the final body positions after step 5 can result in inter-penetrating bodies or even missed collisions (tunneling).

Our collision detection library (DigitalRune Geometry) can compute CCD and we have to fit this into the time step scheme above. A very simple method is motion clamping. This method is used in DigitalRune Physics. The time step is modified like this:

1. Detect collisions
2. Compute forces
3. Apply forces
4. Solve constraints
5. Update target positions
6. Use CCD to compute the first time of impact of each body
7. Move bodies to their first time of impact position

The positions computed in step 5 are not treated as final positions. They are treated as target positions for the CCD. In step 6 the time of impact is computed for the motion from the old position (of the last time step) to the new target position. This is computed for all body pairs where the motion paths overlap. For each body the earliest time of impact is stored. In step 7 the position of each body is set to its first time of impact.

In practice most body positions are already finalized in step 5 as usual, and CCD is only performed for selected, game critical bodies. In DigitalRune Physics each RigidBody has a CcdEnabled flag where CCD can be turned on or off for this body. Further, CCD is only performed for fast bodies (see MotionSettingsCcdVelocityThreshold).

This method is simple and works well in most cases, but it has a clear disadvantage: A part of the bodies' motion is simply discarded (the body loses time). Since CCD is used for fast bodies the motion clamping is mostly not visible – unless the motion is repeatedly clamped in several frames.

Here is an example: A small ball is shot at the wall. Without CCD we shoot right through the wall. With CCD the ball hits the wall.

• Video: Motion Clamping in Game Physics

In the second part of the video a large ball is shot at the wall. Without CCD the ball still hits the wall because it is too big to tunnel through. With CCD the ball’s motion appears choppy. The ball collides with many bricks and the motion is repeatedly clamped in several frames.

Using motion clamping for ragdolls is even worse if the ragdoll parts can collide with each other. The motion clamping visibly tears the limbs apart. In this case, CCD checks between ragdoll limbs should be disabled.

For big objects it is better not to use CCD – they are big anyway and it is unlikely that we miss any collisions.

For future version of DigitalRune Physics a more fine-grained control of CCD and motion clamping is planned to avoid these problems. We might even implement a real first time of impact solver.

A first time of impact solver is an advanced technique that integrates CCD with game physics. With this method the simulation does not make crude fixed time steps. Instead, the simulation steps from the smallest time of impact to the next smallest time of impact. Of course this is slower but can be optimized using an approach like: Timewarp rigid body simulation. It is also important to guarantee progress and avoid slow-downs when the time of impacts are very small and approach zero…