algorithm - 检查盒子是否被球体覆盖

Question

我有一个轴对齐的 3D 框(长方体)，每个顶点都有一个球体(每个都有不同的半径)。如何检查盒子的所有点是否被任何球体覆盖？

我需要一个相当快的算法，而且不一定准确。
假阴性——也就是说盒子实际上没有被覆盖——不是一个大问题，但我仍然想尽量减少这种错误。误报是 Not Acceptable 。

预期用途是计算由带符号距离函数指定的对象的体积。我递归地划分空间，如果给定的盒子完全在对象的外部或内部，我知道我可以在这个级别停止递归。假阴性会导致额外的盒子 split ，但不会导致结果错误。

Answer 1

(虽然我试图找到一个几何最佳版本，但这里有一个简单的想法肯定会奏效，但它可能会返回一些假阴性。)

考虑长方体对角处的两个球体。每个球体都有 3 个或更多点与盒子的边缘相交。从对角看，这些点之一是球体上盒子内最远的点。这意味着如果所有这些点都被相反的球体覆盖，那么整个盒子就会被这两个球体覆盖。



示例 1:所有点都被对角线对面的球体覆盖

如果两个球体没有覆盖整个盒子，请检查其他 3 对对角相对的球体。如果其中一对覆盖盒子，则它被 8 个球体覆盖。如果没有任何对覆盖盒子，那么它可能会或可能不会被 8 个球体覆盖(可能是假阴性)。



示例 2:一些点没有被对角相对的球体覆盖

在立方体的特定情况下，覆盖整个大小为 1 的立方体的两个对角相对的球体的半径由以下公式给出:

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)

为了避免耗时的计算，在几个点(包括 1 和 √2 处的断点)之间使用线性插值将给出保守的近似值。或者您可以使用更简单但不太精确的 ra2 + rb2 ≥ 3 近似值(下图中的蓝色圆圈)。



有一个类似的方法，你考虑盒子底角周围的 4 个球体，找到它们的表面在盒子内创建的“景观”，然后找到这个“景观”中的最低点。如果然后对顶部球体执行相同操作，并且两个景观的最小高度之和大于框的高度，则框被球体覆盖。

然后，您还可以检查左/右和前/后最小高度，看看它们加起来是否等于框的宽度和深度。如果它们中的任何一个这样做，那么盒子就会被球体覆盖。如果没有，则不确定盒子是否被覆盖(可能是假阴性)。由于这种方法一次考虑所有球体，我认为它比对角对角球体方法给出的假阴性更少。



示例 3a:找到 4 个球体的交点

从上面看，任何两个球体之间的交点是球体与盒子底边相交的圆的两个交点之间的线。



示例 3b:找到交叉点上的最低点

球体之间的交叉点连接起来形成“景观”中的“山谷”。两个相邻球体之间的谷的最高点在盒子的边缘，两个对角相对的球体之间的谷的最高点在它们中心之间的对角线上。所以最低点是“山谷”相遇的地方。这些点中哪一个最低，取决于它们到两个最大球体中心之间对角线的距离。



示例 3c:未完全覆盖的一侧

如果有些“谷”不相交，那么底边的一部分就没有被这4个球体覆盖，最小高度显然为零。

我一直在摆弄最小高度方法的代码，计算 4 个球体之间最低点所需的几何图形实际上非常简单:

为了使最低点高于零，两个对角相对的球体需要相交，即 ra+rc 或 rb+rd 不小于框边的对角线。

半径为 r 的球体在距球体中心距离为 d 的点上方的高度为√r2-d2。

如果较大球体在较小球体中心点上方的高度大于较小球体的半径，则盒子内较小球体的部分完全包含在较大球体中。然后可以忽略较小的球体，因为它对“景观”的高度没有影响。

两个球体 a 和 b，其中心距彼此的距离为 d，相交于距球体 a 中心的距离为 d2+ra2-rb2/2×d。