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

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

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

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

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.