Collision Detection

Collision detection is one of the basic components in a 3D game. It is important for a realistic appearance of the game, which needs fast and rugged collision detection algorithms. If you do not use some sort of collision detection in your game you are not able to check if there is a wall in front of your player or if your player is going to walk into another object.

No collision

Collision detected

Bounding Spheres

First we need to answer the question "What is a bounding sphere?" The bounding sphere means a ball which has nearly the same center point as the object which is enclosed by the ball. A bounding sphere is defined by its center point and its radius.

In collision detection the bounding spheres are often used for ball-shaped objects like cliffs, asteroids or space ships.

Two spheres are touching

Let's take a look at what happens when two spheres are touching. The image shows , the radius of each sphere now also defines the distance its center to the opposite sphere's skin. The interspace between the centers would be equal to radius1 + radius2. If the distance would be greater, the two spheres would not touch but if it would be less, the spheres would intersect.

A feasible way to determine if a collision has occurred between two objects with bounding spheres you can simply find the distance between their centres and see if this is less than the sum of their bounding sphere radius.

Another way to use bounding spheres is to use the balance point of the object as the center point of the bounding sphere. Thereby you use the midpoint of all vertices as the centre of the bounding sphere. This algorithm gives you a more exact midpoint than the first way.

XNA Bounding Spheres

Microsofts XNA offers a model for you to use by developing your own game called "BoundingSphere". XNA provides this for you so that there is no need to calculate it. Models in XNA are made up of 1 or more meshes. When doing collisions you will want to have one sphere that borders the whole model. That means at model load time you will want to loop through all the meshes in your model and expand a main model sphere.

foreach (ModelMesh mesh in m_model.Meshes)
{
    m_boundingSphere=BoundingSphere.CreateMerged(base.m_boundingSphere, mesh.BoundingSphere);
    ...

To see if two spheres have collided Xna provides us to use:

bool hasCollided=sphere.Intersects(otherSphere);

Bounding Rectangles or Bounding Box

Bounding box

In collision detection handling with rectangles you want to see whether two rectangular areas are in any way touching or overlapping each other. Therefor we need to use the bounding box. A bounding box is simply a box that encloses all the geometry of a 3D object. We can easily calculate one from a set of vertex by simply looping through all the vertices finding the smallest and biggest x, y and z values.

To create a bounding box around our model in model space you need to calculate the midpoint an the four corner point of the rectangle we want to enclose. Then you need to build a matrix and rotate the four point about the midpoint with the given rotation value. After that we need to go through all the vertices in the model keeping a track of the minimum and maximum x, y and z positions. This gives us two corners of the box from which all the other corners can be calculated.

XNA Bounding Box

Because each model is made from a number of mesh we need to calculate minimum and maximum values from the vertex positions for each mesh. The"ModelMesh" object in XNA is split into parts which provides access to the buffer which is keeping the data of the vertex (VertexBuffer) from which we can get a copy of the vertices using the GetData call.

public BoundingBox CalculateBoundingBox()
{

// Create variables to keep min and max xyz values for the model
Vector3 modelMax = new Vector3(float.MinValue, float.MinValue, float.MinValue);
Vector3 modelMin = new Vector3(float.MaxValue, float.MaxValue, float.MaxValue);

foreach (ModelMesh mesh in m_model.Meshes)
{
  //Create variables to hold min and max xyz values for the mesh
   Vector3 meshMax = new Vector3(float.MinValue, float.MinValue, float.MinValue);
   Vector3 meshMin = new Vector3(float.MaxValue, float.MaxValue, float.MaxValue);

  // There may be multiple parts in a mesh (different materials etc.) so loop through each
  foreach (ModelMeshPart part in mesh.MeshParts)
   {
     // The stride is how big, in bytes, one vertex is in the vertex buffer
     int stride = part.VertexBuffer.VertexDeclaration.VertexStride;

     byte[] vertexData = new byte[stride * part.NumVertices]; 
     part.VertexBuffer.GetData(part.VertexOffset * stride, vertexData, 0, part.NumVertices, 1); // fixed 13/4/11

     // Find minimum and maximum xyz values for this mesh part
     // We know the position will always be the first 3 float values of the vertex data
     Vector3 vertPosition=new Vector3();
     for (int ndx = 0; ndx < vertexData.Length; ndx += stride)
      { 
         vertPosition.X= BitConverter.ToSingle(vertexData, ndx);
         vertPosition.Y = BitConverter.ToSingle(vertexData, ndx + sizeof(float));
         vertPosition.Z= BitConverter.ToSingle(vertexData, ndx + sizeof(float)*2);

         // update our running values from this vertex
         meshMin = Vector3.Min(meshMin, vertPosition);
         meshMax = Vector3.Max(meshMax, vertPosition);
     }
   }

   // transform by mesh bone transforms
   meshMin = Vector3.Transform(meshMin, m_transforms[mesh.ParentBone.Index]);
   meshMax = Vector3.Transform(meshMax, m_transforms[mesh.ParentBone.Index]);

   // Expand model extents by the ones from this mesh
   modelMin = Vector3.Min(modelMin, meshMin);
   modelMax = Vector3.Max(modelMax, meshMax);
}

// Create and return the model bounding box
return new BoundingBox(modelMin, modelMax);
}

Terrain Collision

Un-even terrain

Collision detection with a terrain and an object is different than the collision between objects.

First of all you have to detect the coordinates of your current player (object). The height map of your terrain gives you a "gap value" which identifies the distance between two sequenced vertices. When dividing your coordinate position through those "gap values" you can detect the vertices at your position. You can get from your heightmapbuffer the 4 vertices squares where you are. Using these datas and your position in this square, you can calculate the best interspace to the terrain so that there is no collision with it.

Collision Performance

Sometimes collision detection slows down a game. It is the most time-consuming component in an application. Therefor there are data structures as quadtree and octtree.

Quadtree (2D)

A quadtree is a tree structure using a principle called ‘spatial locality’ to speed up the process of finding all possible collisions. Objects can only hit things close to them. To advance the performance you should avoid the testing again objects which are far away.

Octtree

The easiest way to check for collision is to divide the area which is going to be checked into a consistent grid and declare each object with all intersecting grid cells. The quadtree tries to overcome this weakness by recursively splitting the collision space into smaller subregions. Every region is divided exactly into 4 smaller regions of the same size, so you end up having multiple grids with different resolutions, where the number of cells in a region goes go up by a power of two every time the resolution is increased. So every object resides in the cell (called quad node or quadrant) with the highest possible resolution. A search is made by starting at the object’s node and climb up to the root node.