3D Collisions

Not a lot could happen in a 3D game if you could not detect collisions! Collision detection is required for the player avatar and AI units so they are restrained by the geometry of the world as well as for projectile collisions

Sphere collision detection

Note that the above image shows a wireframe sphere representation from the accompanying demo. In fact all you need to represent a sphere is a centre point and a radius. This makes it very easy to use for collision detection however it can be very inaccurate. As you can see above the collision is detected far too early and while the skeletons still look a long way apart. The fit is very poor. Of course if your entities were by nature round then it may be a very good fit - however this is normally not the case.

Representation

You need to store a sphere centre and a radius. These are normally calculated in model space at level load time. You can use functions like the Direct3D one D3DXComputeBoundingSphere to calculate the sphere from a mesh or create your own function (not the easiest thing to do). You can though quite easily create a (non optimal) sphere from a bounding box by taking the minimum and maximum x,y,z values of the box (opposite corners). Half the length of the vector between the two opposite corners is the radius. The centre is the minimum corner plus half the way to the opposite corner.  E.g. in Direct3D:

D3DXVECTOR3 vecBetween=maxBounds-minBounds;
float sphereRadius=D3DXVec3Length(&vecBetween);
D3DXVECTOR2 sphereCentre=minBounds+vecBetween*0.5f;

Collision Detection

To detect collisions between two spheres you need to find the distance between the centre points of each sphere and see if that distance is less than the sum of the two spheres radius. So given we have a model with sphere1 and one with sphere2 we may do this:

float distanceBetween=D3DXVec3Length(sphereCentre2-sphereCentre1);
if (distanceBetween < sphereRadius1 + sphereRadius2)
    // a collision occurred

Advanced

There are a number of methods to calculate a better fitting sphere. None are particularly easy. One accurate method involves finding four vertices that are on the surface of the sphere such that all other vertices are on or inside it. A bit less accurate alternative would be to find the distance of each point from the sphere centre (if you know it) and using the maximum for the radius. A search of the internet should bring up some results but ultimately, since spheres are not normally a very good fit however optimal they are, you may not want to implement such complex functionality. You can use the loose fitting sphere created from the bounding box as an early test but rely on other methods for more accurate collisions.

Axis-aligned bounding box collision detection

An axis aligned bounding box (AABB) is one that is aligned to the axis of the game world i.e. one edge is down x, another y and another z. These are very useful boxes that are normally easy to calculate and easy to check for collisions between. They do however still suffer from a rather poor fit but, normally, a better fit than a bounding sphere. As with bounding spheres early rejection of collisions can be achieved with axis aligned bounding boxes.

Representation

Since an AABB is aligned to the world axis system we only need to store minimum and maximum x,y and z values to represent our box. These are then two diagonally opposite corners of the box. All the other box corners can easily be derived from these. Therefore we only need two vectors e.g.

D3DXVECTOR3 minBounds,maxBounds;

To calculate an axis aligned bounding box is easy. Simply loop through all the vertices in your model keeping track of the minimum and maximum x,y,z values as you go along. Alternatively Direct3D has a function to calculate it for you called: D3DXComputeBoundingBox.

Note that as soon as you transform an AABB via a rotation matrix you can no longer represent it via min and max values e.g. if you transform from model space to world space. The model space AABB basically becomes an oriented bounding box (OBB) in world space. Collision detection between OOBs is much harder than between AABB so what you can do, with a further loss of accuracy, is to create an AABB from an OBB. OOBs are represented by all 8 corners so to create an AABB from an OBB you simply go through these 8 corners finding the minimum and maximum, x,y,z values.

Collision Detection

To detect a collision between two AABB we check to see if they are completely separate on one of the axis. If they are separate on any axis no collision has occurred otherwise a collision has occurred. For example given two AABBs A and B with representations minA, maxA and minB, maxB:

// Check for A completely to the left of B
if (maxA.x<minB.x)
    return false;
// Check for A to the right of B
if (minA.x>maxB.x)
    return false;
// Check for A in front of B
if (maxA.z<minB.z)
    return false;
// Check for A behind B
if (minA.z>maxB.z)
    return false;
// Check for A above B
if (minA.y>maxB.y) 
    return false;
// Check for A below B
if (maxA.y<minB.y)
   return false;

// Collision has occurred

Oriented bounding box collision detection

---

© 2004-2016 Keith Ditchburn