Search code examples
geometryhittestoctree

Test if Cube is inside Sphere - Fastest Method

Is there a faster way to check if an axis aligned cube is inside a sphere than to test separately if the 8 corners are inside the Sphere?

I'm walking through an Octree checking if its cube-leafs are intersecting or enclosed within a Sphere. I found a method for intersections here: Cube sphere intersection test?

I was hoping to find a more efficient way to test for enclosement. What I need in the end is a test that returns one of three states:

  1. outside Sphere
  2. intersecting Sphere
  3. inside Sphere

The cubes are defined by two points, the sphere by its center-point and radius.

Solution

  • To find if the cube is entirely within the sphere, you can get away with testing only one vertex - the one furthest from the center of the sphere. You can determine which vertex to test by comparing the center points of the cube and sphere. For example, given a cube centered at (cx,cy,cz) and with an edge half-length of l, and a sphere at (sx,sy,sz) with radius r, the point to test will be

    tx = cx + ( cx > sx ? l : -l );
ty = cy + ( cy > sy ? l : -l );
tz = cz + ( cz > sz ? l : -l );

    However, testing the corners of the cube against the sphere will not catch all cases of intersection - consider a cube from (-5,-5,-5) to (5,5,5) and a sphere at (0,0,6) with radius 2. The two volumes do intersect but no vertex is inside the sphere.

    I'd go for a multi-pass approach:

    1. Check the axis-aligned bounding box of the sphere against the cube - really simple check with quick rejection for obviously-not-intersecting cases.
    2. Check if the sphere center lies within the cube
    3. This possibility may be precluded in your system, but you should also do a bounding box check for the case where the sphere is entirely within the cube.
    4. At this point, there's little choice but to go ahead and check for intersections between the sphere and the cube faces.

    For the purposes of walking an octree though, I would be tempted just treat the sphere as an axis-aligned bounding box and live with the small false-positive rate. I wouldn't be at all surprised to learn that this would be faster than getting the absolutely correct intersection results.