Reputation: 5440
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:
The cubes are defined by two points, the sphere by its center-point and radius.
Upvotes: 2
Views: 3472
Reputation: 3009
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:
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.
Upvotes: 3
Reputation: 1512
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.
Upvotes: 0