Introduction to collision detection techniques in games (prelude to collision detection in XNA)

[This post is a refresh version of an older post published here.]

Determining if any two 3D objects intersect and get useful information about the intersection is not an easy task. Especially if you want to do it fast. The key to optimize these calculations is to quickly discard non colliding objects, before applying the full collision test. To do so, several methods can be applied.

The typical path for discarding is to first divide your scenes into parts (Google for Octrees or Portal techniques for further information), keeping track in which part the player is located (and discarding others), and then using BoundXXX discard tests with all the objects in that part. Among others, the most usual are:

• BoundSphere: Use a hypothetical sphere surrounding objects. If the distance between objects is bigger than the sum of both radius, then they don't intersect. This fits well for objects similar to a sphere, but not at all for something like a hockey stick, for example. This method is directly supported in DirectX (BoundSphereTest)
• Axis Aligned Bound Box: Use a hypothetical box surrounding objects. This box is not aligned with the object, but with the world axis (it's not rotated with the object). It just keeps track of the maximum and minimum values of X,Y,Z along the object’s geometry. It's also supported in DirectX (BoundBoxTest) and fits best with square geometry, of course.
  
• Oriented Bound Box: This one is the more accurate of the three, but of course it's more expensive to compute. It rotates the bounding box with the object, so it fits better its geometry in every case (even if rotated). It's not supported in DirectX and you'll have to do it yourself. The best is to calculate a first Bound Box using a convex hull algorithm and then transform it in the same way as the object does.

All this stuff allows you to quickly discard non-colliding objects, or to approximate the shape of the entire mesh, if that gives enough accuracy for your application. There are dozens of intersection algorithms optimized for a specific kind of geometry: Ray-Polygon, Ray-Cylinder, Ray-Box, Ray-Sphere, Sphere-Sphere, and so on...

One of the best resources about this intersection test is Real Time Rendering. I really suggest you to acquire a copy of that book. It's a must in every graphics programmer bookcase. Once you have it or read the website, try to understand each method well and the complexity it involves. As long as one of your meshes can be approximated well enough with one of those shapes, you should try to use them, because in every case they will be much faster than a full detail Mesh-Mesh intersection test.

Multi-Shape Approximation of Meshes

As previously said, those tests (Box, sphere, etc.) don't work only for discarding objects, but also to approximate their shapes making collision detection fast and pretty reliable.This is a very useful method, especially in games. Basically, what we do is to define a collection of shapes that approximate the real shape of the object, and then use Sphere-Sphere, Sphere-Mesh, or any one of those intersection tests, just like in the following picture:

Level of Detail for Collisions

Another usual method is to use one mesh with high detail for rendering and a simpler one for collisions, like this one:

You should always make this for complex meshes (like characters), if are going to apply any method that uses the entire mesh, like the following:

Full Detail: Ray-Mesh Test

If you are using DirectX, making a ray-mesh test is pretty straightforward as it's directly supported by the API via the Mesh.Intersect method. You should take note that a ray-mesh test is as complex as the mesh tested, and in general, is not the fastest way. The DirectX implementation would be:

DX.Direct3D.IntersectInformation intersectionInfo;
if (mesh.Intersect(rayOrigin, rayDirection, out intersectionInfo))
{

// There is collision

}

The IntersectInformation structure gives you the exact Distance between the ray origin and the intersection point, the face index of the mesh the ray hits, and the barycentric U,V coordinates of the intersection point. If you want to know the exact 3D point of intersection, you can easily calculate it like:

Vector3 intersectionPoint = rayOrigin + 
	(rayDirection * intersectInfo.Distance);

If you want the normal of the surface in the collision point, use the normal of the mesh face using the face index returned in IntersectInformation.

One thing you must be careful with: this method uses the current state of the mesh. It tests all of its polygons against the ray. If you move or rotate the mesh setting, a transform matrix in the Device.Transforms.World, that transformation will not be taken into account. If your objects are dynamic, you should keep track of a mesh version with all its transformations applied to the vertices.

Lastly, if you want to do some serious collision detection, especially if you are planning to do any Rigid Body simulation, my suggestion would be to have a look to the SAT Algorithm (Separation Axes Algorithm). It's fast, accurate and gives you very useful information, like the MTD (minimum translation distance and direction to solve inter-penetration). You will find dozens of resources over the net about the SAT.

History

• 20^th April, 2009: Initial post