Sphere intersection test of AABB

Question

I have a sphere and I want to know if my axis-aligned bounding boxes (AABBs) are either fully, partially or not at all inside the sphere. I've found plenty of alghorithms but they only give either partial or outside results. Any pointers?

Answer 1

You probably have already found the most popular algorithm to determine whether an AABB intersects with a solid sphere or not by Jim Arvo, in "Graphics Gems":

        dmin = 0;
        for( i = 0; i < 3; i++ ) {
            if( C[i] < Bmin[i] ) dmin += SQR( C[i] - Bmin[i] ); else
            if( C[i] > Bmax[i] ) dmin += SQR( C[i] - Bmax[i] );     
            }
        if( dmin <= r2 ) return TRUE;

Where Bmin stores the minima of the AABB for each axis, Bmax stores the maxima of the AABB for each axis, C is the coordinate of the sphere center and r2 is the squared radius. This solution was for example also featured in this stackoverflow question: Cube sphere intersection test?

As you already have discovered, this algorithm also returns TRUE if the AABB is fully inside the sphere but you want to detect this situation as a special case. One way of doing this is by reversing what above algorithm is doing. The algorithm works by essentially finding the point of the AABB that is closest to the sphere center and summing up the squared coordinate deltas between this point and the sphere center. If that sum is less than the sphere radius squared, then (after the pythagorean theorem) the point of the AABB lies inside the sphere. As a result, the AABB is either partially or fully contained inside the sphere.

Now lets say you already ran that check and you want to find out whether the AABB is only partially or whether it's fully contained. For that, lets run a similar check but not with the point of the AABB closest to the circle center but with the point farthest away from it. If the distance of this point from the sphere center is less than the sphere radius, then the AABB is fully contained inside the sphere.

Funnily, the much quoted algorithm by Jim Arvo already contains an algorithm to do exactly that. The original code contains checks for "hollow" or "solid" spheres and AABB. Unfortunately, the original code at http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c is not available anymore but the internet archive still has it: http://web.archive.org/web/20100323053111/http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c You are basically interested in the cases with a hollow sphere. I do not know whether you want your AABB box to be hollow or not (the difference is whether your check returns true when the sphere is inside the box) so I'll be pasting both cases here:

switch( mode )
    {
    case 0: /* Hollow Box and Hollow Sphere */
        dmin = 0;
        dmax = 0;
        face = FALSE;
        for( i = 0; i < n; i++ ) {
            a = SQR( C[i] - Bmin[i] );
            b = SQR( C[i] - Bmax[i] );
            dmax += MAX( a, b );
            if( C[i] < Bmin[i] ) {
                face = TRUE;
                dmin += a;
                }
            else if( C[i] > Bmax[i] ) {
                face = TRUE;
                dmin += b;
                }
            else if( MIN( a, b ) <= r2 ) face = TRUE;
            }
        if( face && ( dmin <= r2 ) && ( r2 <= dmax ) ) return TRUE;
        break;
    case 2: /* Solid Box and Hollow Sphere */
        dmax = 0;
        dmin = 0;
        for( i = 0; i < n; i++ ) {
            a = SQR( C[i] - Bmin[i] );
            b = SQR( C[i] - Bmax[i] );
            dmax += MAX( a, b );
            if( C[i] < Bmin[i] ) dmin += a; else
            if( C[i] > Bmax[i] ) dmin += b;
            }
        if( dmin <= r2 && r2 <= dmax ) return TRUE;
        break;

To solve your initial question, you would now change the return condition. If dmin is less than r2 but dmax is greater than r2 then your AABB lies on the sphere surface (partial intersection). If dmin and dmax are less than r2 then your AABB lies fully inside your sphere.