Introduction

Checking  for collision between two objects can be a very complicated task, involving  tests between the many faces of each object.  To perform this task quickly, simplified volumes are often used to represent each object, allowing fast tests for collision.  These tests are of course not as precise, and often they are used as a quick test to determine if further, detailed testing is required.

In this series of articles, we will examine three such bounding volumes:

We'll take a look at the strengths and weaknesses of each, as well as the code necessary to implement them.  The focus of this series will be limited to detecting an intersection.  In future articles we will take a further look at the physics behind object interaction, how to determine reactions using each of these techniques, and how to efficiently test for collisions between a collection of objects.

Now to take a look at the first of these bounding volumes, the bounding sphere.

What is a Bounding Sphere?

Defining a Bounding Sphere

When defining a bounding sphere, one typically tries to find the tightest fit for the bounded object, that is, the smallest radius sphere that all points lie within.  Depending on the shape of the object, the techniques required for the best fit can be complex.  For simplicity sake, we'll take a look at a fairly simple algorithm that will work decently for most cases.  The function is a two step process:

1. Find the center.  In this case, we'll simply average the coordinates.
2. Loop through the coordinates and find the maximum distance from the center.  This is the radius.

To make our function versatile, I've included a stride parameter that will allow you to use this function with any structure (i.e. any conventional D3D vertex type) as long as it starts with three floats representing X, Y, and Z.  The function accepts the following parameters:

LPBOUNDINGSPHERE calcSphere(BYTE *vects,DWORD count,DWORD stride,LPBOUNDINGSPHERE sphere)

{

    // find center

    sphere->center=D3DXVECTOR3(0.0f,0.0f,0.0f);

    BYTE *ptr=vects;

    for (int i=0;i<count;i++) {

        sphere->center+=*((LPD3DXVECTOR3) ptr);

        ptr+=stride;

    }

    sphere->center/=(float)count;

    // find farthest point in set

    sphere->radius=0.0f;

    ptr=vects;

    for (int i=0;i<count;i++) {

        D3DXVECTOR3 v;

          v=*((LPD3DXVECTOR3) ptr)-sphere->center;

        float distSq=D3DXVec3LengthSq(&v);

        if (distSq>sphere->radius)

            sphere->radius=distSq;

        ptr+=stride;

    }

    sphere->radius=sqrtf(sphere->radius);

}

Note that we get the square of the length, and only take the square root when we have found the maximum distance.  This is to eliminate the use of a costly square root function for each point in the mesh.  You will see similar optimizations later, including the comparison of the square of a vectors length versus the square of the value we wish to compare the length to.  Multiplication is orders of magnitude faster than finding a square root.  

To clarify the use of the stride, let's say we had a mesh that was composed of 1024 pre-lit vertices, that is, using the D3DLVERTEX structure.  The function would be called with the size of the D3DLVERTEX structure as the stride, like this:

// given "vects" is an array of 1024 D3DVERTEX structures

BOUNDINGSPHERE sp;

calcSphere((BYTE *) vects,1024,sizeof(D3DVERTEX),&sp);

Determining if a Point is in a Sphere

Determining whether a given point is within a sphere is quite simple.  A surface of a sphere, just like a circle, is composed of all those points that are a constant distance (the radius) from the center point.  If the distance from a point to the center of the sphere is greater than the radius, while if it is less than the radius, the point falls within the sphere:

BOOL pointInSphere(LPD3DXVECTOR3 pt, LPBOUNDINGSPHERE sphere)

{

    D3DXVECTOR3 v;

    v=sphere->center-*pt;

    if (D3DXVec3LengthSq(&v)>sphere->radius*sphere->radius)

        return FALSE;

    return TRUE;

}

Determining if Two Spheres Collide

Below are two functions that perform this test.  The first returns a boolean value, returning TRUE if the spheres intersect or FALSE if they do not.  

BOOL sphereIntersect(LPBOUNDINGSPHERE s1,LPBOUNDINGSPHERE s2)

{

    D3DXVECTOR3 v;

    v=s1->center-s2->center

    float centDist=s1->radius+s2->radius;

   return (D3DXVec3LengthSq(&v)<=centDist*centDist);

}

The second function returns a floating point value, which represents the distances between the closest points between the two spheres.  If the value is negative, the spheres intersect, and the value represents the greatest distance of overlap.

float sphereIntersectDist(LPBOUNDINGSPHERE s1,LPBOUNDINGSPHERE s2)

{

    D3DXVECTOR3 v;

    v=s1->center-s2->center;

    return (D3DXVec3Length(&v)-(s1->radius+s2->radius));

}

Dealing with Object Motion

So, what happens when an object moves?  Do we have to completely re-calculate the bounding sphere?  Fortunately, we do not.  Because a sphere is symmetrical, there is no change in dimensions as it is moved.  All that changes is the center point, which we must offset from model space to the current position in world space, according to the translation of the object.  Below is a class that keeps track of the origin in model space, and allows you to offset the center as needed:

class CBoundSphere
{
    D3DVECTOR origin;
    D3DVECTOR center;
    float radius;
    CBoundSphere(LPD3DXVECTOR3 vOrigin,float fRadius);
    ~CBoundSphere() {};
    void SetTranslation(LPD3DXVECTOR3 vOffset);
    BOOL PointInSphere(LPD3DXVECTOR3 pt);
    BOOL SphereIntersect(CBoundSphere *s);
    float SphereIntersectDist(CBoundSphere *s);
}

CBoundSphere::CBoundSphere(LPD3DXVECTOR3 vOrigin,float fRadius)
{
    center=origin=*vOrigin; 
    radius=fRadius;
}

void CBoundSphere::SetTranslation(LPD3DXVECTOR3 vOffset)
{
    center=origin+*vOffset;
}

BOOL CBoundSphere::PointInSphere(LPD3DXVECTOR3 pt)
{
    D3DXVECTOR3 v;
    v=center-pt;
    return (D3DXVec3LengthSq(&v)<=radius*radius);
}

BOOL CBoundSphere::SphereIntersect(CBoundSphere *s)
{
    D3DXVECTOR3 v;
    v=center-s->center;
    float centDist=radius+s->radius;
    return (D3DXVec3LengthSq(&v) <=centDist*centDist);
}

float CBoundSphere::SphereIntersectDist(CBoundSphere *s)
{
    D3DXVECTOR3 v;
    v=center-s->center;
    return (D3DXVec3Length(&v)-(radius+s->radius));
}