Oct 8

Written by:
Friday, October 08, 2010 

In the last post we talked about the shortcomings of discrete collision detection and why we need continuous collision detection (CCD). Now it is time to discuss ways to implement CCD to avoid tunneling of objects (missed collisions) and find the time of impact.

Supersampling

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.

Bisection Method

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.

Ray Casting

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.

Analytical Solution

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”).

Swept Bounding Spheres

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 ok 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.

Ray Casting against General Convex 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:

Conservative Advancement

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 Interactive 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.

And Else…

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

The upcoming version (v1.2) of DigitalRune Geometry supports CCD. We use the methods Ray Casting against General Convex Objects and Conservative Advancement. The DigitalRune Geometry download will contain an example that shows how to use CCD. 

If you want to implement CCD by yourself, I recommend to take a look at the open source Bullet Physics Library. It contains implementations of CCD algorithms and is an excellent source of knowledge.