2

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.

Community
  • 1
  • 1
BoshWash
  • 5,320
  • 4
  • 30
  • 50
  • You are probably checking many cubes or many spheres, since speed matters for you. Sometimes it's possible to amortize complexity over the collection of objects, so it matters whether you have many spheres or many cubes. Please clarify which objects are numerous and whether they come in the same size or varying sizes. – Michael Aug 21 '13 at 05:44

2 Answers2

3

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.

ryanm
  • 2,979
  • 18
  • 22
0

You could measure the distance from the center of the cube to the center of the sphere. Together with the length of the diagonal of the cube and the radius of the sphere, you could determine wether the cube is inside the sphere.

Jon List
  • 1,504
  • 1
  • 14
  • 20
  • Imagine a sphere that is aligned down an axis with the center of the cube, close enough that the sphere just barely does not touch the center of the face of the cube. In this case. The distance between the center of the cube and sphere is less than the radius + the diagonal of the cube, yet they do not intersect at all. – Tyler Shellberg Apr 27 '20 at 17:21