Check if box is covered by spheres

Question

I have an axis alligned 3D box (cuboid), and a sphere at each of its vertices (each with different radius). How can I check if all points of the box are covered by any of the spheres?

I need an algorithm that is rather fast, and not necessarily exact. False negatives -- that is saying that the box is not covered when in fact it is -- are not a big problem, but still I would like to minimise this kind of errors. False positives are unacceptable.

Intended use is calculating volume of an object specified by a signed distance function. I'm recursively dividing space and if a given box is completely outside or inside of the object, I know I can stop recursion on this level. False negative would cause extra splitting of the box, but not an error in the result.

Answer 1

(While I'm trying to find a geometrically optimal version, here's a simple idea that's sure to work, but it may return some false negatives.)

Consider two spheres at diagonally opposite corners of the box. Each of the spheres has 3 or more points where it intersects with the edges of the box. Seen from the opposite corner, one of these points is the furthest point inside the box on the sphere. That means that if all these points are covered by the opposite sphere, then the whole box is covered by these two spheres.

^{example 1: all points covered by diagonally opposite sphere}

If the two spheres don't cover the whole box, check the other 3 pairs of diagonally opposite spheres. If one of the pairs covers the box, then it is covered by the 8 spheres. If none of the pairs covers the box, then it may or may not be covered by the 8 spheres (possible false negative).

^{example 2: some points not covered by diagonally opposite sphere}

---

In the specific case of a cubic box, the radius of two diagonally opposite spheres which cover the whole cube with size 1 is given by these formulas:

0 ≤ r_a ≤ 1 → r_b ≥ √(2 + (1 - r_a)²)
1 ≤ r_a ≤ √2 → r_b ≥ √(1 + (1 - √(r_a² - 1))²)
√2 ≤ r_a ≤ √3 → r_b ≥ 1 - √(r_a² - 2)

To avoid time-consuming calculations, using linear interpolation between a few points (including the breakpoints at 1 and √2) will give a conservative approximation. Or you can use the simpler but less precise approximation of r_a² + r_b² ≥ 3 (the blue circle on the graph below).

---

There is a similar method where you consider the 4 spheres around the bottom corners of the box, find the "landscape" their surfaces create inside the box, and then find the lowest point in this "landscape". If you then do the same for the top spheres, and the minimum heights of the two landscapes sum to more than the height of the box, then the box is covered by the spheres.

You can then also check the left/right and front/rear minimum heights to see whether they add up to the width and depth of the box. If any of them do, then the box is covered by the spheres. If none does, it is unsure whether the box is covered (possible false negative). Since this method considers all the spheres at once, I think it'll give fewer false negatives than the diagonally-opposite spheres method.

^{example 3a: finding the intersections of the 4 spheres}

Seen from above, the intersection between any two spheres is the line between the two intersecting points of the circles where the spheres intersect the bottom side of the box.

^{example 3b: finding the lowest points on the intersections}

The intersections between spheres join up to form the "valleys" in the "landscape". The highest point of a valley between two neighbouring spheres is at the edge of the box, the highest point of a valley between two diagonally opposite spheres is on the diagonal between their centers. So the lowest points are where the "valleys" meet. Which of these points is the lowest, is determined by their distance to the diagonal between the centers of the two largest spheres.

^{example 3c: side not completely covered}

If some of the "valleys" don't meet, then part of the bottom side is not covered by these 4 spheres, and the minimum height is obviously zero.

---

I've been fiddling around with code for the minimum-height method, and the geometry needed to calculate the lowest point between 4 spheres is actually quite simple:

• For the lowest point to be higher than zero, two diagonally opposed spheres need to intersect, i.e. r_a+r_c or r_b+r_d is not less than the box side's diagonal.
• The height of a sphere with radius r above a point that is distance d away from the sphere's center is √r²-d².
• The part of a smaller sphere inside the box is completely contained within a larger sphere if the height of the larger sphere above the center point of the smaller sphere is greater than the smaller sphere's radius. The smaller sphere can then be ignored, because it has no impact on the height of the "landscape".
• Two spheres a and b, whose centers are at a distance d from each other, intersect at a distance d²+r_a²-r_b² / 2×d from the center of sphere a.