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.

Answer 2

And intersection test resulting in true for at least partial intersection and false for no intersection is detailed here.

You now want to check whether the AABB is fully inside the sphere. You can easily do this by checking whether all of your points are inside the sphere. This test can be simplified to checking whether two opposing vertices of the AABB are inside the sphere. Comparing the squared distance to the squared radius of the sphere makes this test very fast.

You can chain both tests together easily:

• Check whether the AABB is fully contained. If not, check whether it's partially contained or not at all.
• Or vice versa: check whether the AABB is at least partially contained. If it is, check whether it's fully contained.

Depending on how often each case occurs, one or the other may be better - profile your code if you feel the need for speed.

Answer 3

Try this algorithm: the sphere collides with AABB if the sphere lies (or partially lies) on inside side of all planes of the AABB. Inside side of plane means the half-space directed to AABB center.

So, you should check for sphere vs. axis-aligned plane intersections for each of 6 AABB planes (xmin/xmax, ymin/ymax, zmin/zmax). This comparison is pretty simple if you extrude plane by sphere radius and check sphere center point vs. extruded plane.

P. S. I didn't try it on practice. This algorithm is based on similar method to determine point inside triangle (https://stackoverflow.com/a/2049593/326017)