Check if the field is covered with spheres

Question

I have an axial 3D block (cuboid) and a ball at each of its vertices (each with a different radius). How to check if all points of a window are covered with any sphere?

I need an algorithm that is pretty fast, and not necessarily accurate. False negatives - this suggests that the box is not covered, when in fact it is not a big problem, but still I would like to minimize such errors. False positives are not acceptable.

Intended use is the calculation of the volume of an object specified by a distance function with a sign. I recursively divide the space, and if the given box is completely outside or inside the object, I know that I can stop recursion at this level. False negative may cause additional field separation, but not an error as a result.

Answer 1

(Although I am trying to find a geometrically optimal version, here is a simple idea that certainly works, but can return some false negatives.)

Consider two spheres in the diagonally opposite corners of the box. Each of the spheres has 3 or more points where it intersects with the edges of the window. Seen in the opposite corner, one of these points is the farthest point inside the box on the sphere. This 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 a diagonally opposite sphere}

If two spheres do not cover the entire box, check the remaining 3 pairs of diagonally opposite spheres. If one of the pairs covers the box, then it is covered with 8 spheres. If none of the pairs covers the box, it can be covered or not covered with 8 balls (possible false negative).

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

---

In the specific case of a cubic box, the radius of two diagonally opposite spheres covering the entire cube of size 1 is determined by the following formulas:

0? r _a & le; 1 → r _b & ge; & radic; (2 + (1 - r _a ) ² )
1? r _a & le; & radic; 2 → r _b & ge; & radic; (1 + (1 - & radic; (r _a ² - 1)) ² )
& radic; 2? r _a & le; & radic; 3 → r _b & ge; 1 -? (r _a ² - 2)

To avoid time-consuming calculations, using linear interpolation between multiple points (including breakpoints at 1 and? 2) will give a conservative approximation. Or you can use a simpler but less accurate approximation r _a ² + r _b ² & ge; 3 (blue circle in the chart below).

---

There is a similar method in which you look at 4 spheres around the bottom corners of the box, find the “terrain” of your surfaces created inside the box, and then find the lowest point in this “landscape”. If you then do the same for the upper spheres, and the minimum heights of the two landscapes add up more than the height of the window, then the box will be covered with spheres.

Then you can also check the minimum height left / right and front / back to see if they correspond to the width and depth of the window. If one of them does, then the box is covered with spheres. If this does not happen, he is not sure if the field is covered (possibly false negative). Since this method considers all spheres at once, I think that it will give less false negatives than the method of diagonally opposite spheres.

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

As seen from above, the intersection between any two balls is the line between two intersecting points of the circles, where the spheres intersect with the bottom of the box.

^{example 3b: finding the smallest points at intersections}

The intersections between the balls combine to form “valleys” in the “landscape”. The highest point of the valley between two adjacent spheres is on the edge of the box, the highest point of the valley between two diagonally opposite spheres is located diagonally between their centers. Thus, the lowest points where the "valleys" are found. 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 is not completely closed}

If some of the “valleys” are not found, then part of the lower side is not covered by these four spheres, and the minimum height is obviously zero.

---

I was looking for code for the minimum height method, and the geometry needed to calculate the lowest point between the four spheres is actually quite simple:

• For the bottom point to be higher than zero, two intersecting diagonals of the sphere must intersect, i.e. r _a + r _c or r _b + r _{d is} not less than the diagonal of the side of the box.
• The height of a ball with a radius r above a point that is at a distance d from the center of the sphere is & ric; r ² - d ² .
• Part of the smaller sphere inside the box is completely contained in the larger sphere if the height of the larger sphere above the center point of the smaller sphere is greater than the smaller radius of the sphere. Then the smaller sphere can be ignored, since it does not affect the height of the "landscape".
• Two spheres a and b , the centers of which are located at a distance d from each other, intersect at a distance d ² + r _a ² -r _b 2/2 × d from the center of the sphere <i> a.

Answer 2

I think because of the complexity of the problem, and since you accept false negatives, it would be the right decision to just check if the radius of the sphere is larger than half of the main diagonal ( r*r > a*a + b*b + c*c ). In this case, each sphere covers at least “its” 1/8 of the cuboid and, therefore, the cuboid is covered.