检查框是否被球体覆盖
cub*_*ube 7 algorithm math geometry
我有一个轴对齐3D框(长方体),每个顶点都有一个球体(每个都有不同的半径).如何检查框中的所有点是否都被任何球体覆盖？
我需要一种相当快速的算法,但不一定非常精确.假阴性 - 也就是说实际上它没有覆盖盒子 - 不是一个大问题,但我仍然想尽量减少这种错误.误报是不可接受的.
预期用途是计算由带符号距离函数指定的对象的体积.我递归地划分空间,如果给定的盒子完全位于对象的外部或内部,我知道我可以在这个级别上停止递归.假阴性会导致框的额外分裂,但不会导致结果中的错误.
(虽然我试图找到一个几何上最优的版本,但这是一个简单的想法,肯定会起作用,但它可能会返回一些假阴性.)
考虑在盒子的对角相对的两个球体.每个球体具有3个或更多个点,其与盒子的边缘相交.从对角看,这些点中的一个是球体内盒子内的最远点.这意味着如果所有这些点被相反的球体覆盖,则整个盒子被这两个球体覆盖.
示例1:对角线相对球体覆盖的所有点
如果两个球体没有覆盖整个盒子,请检查其他3对对角球体.如果其中一对覆盖盒子,那么它被8个球体覆盖.如果没有一对覆盖盒子,则它可能会或可能不会被8个球体覆盖(可能是假阴性).
例2:一些未被对角线球体覆盖的点
在立方体盒子的特定情况下,两个对角相对的球体的半径覆盖整个立方体,大小为1,由下式给出:
0≤[R 一 ≤1→R b ≥√(2 +(1 - R的一个)2)
1≤[R 一 ≤√2→[R b ≥√(1 +(1 - √(R 一2 - 1))2)
√2≤[R 一 ≤√3→[R b ≥1 - √(R 一2 - 2)
为了避免耗时的计算,在几个点之间使用线性插值(包括1和√2处的断点)将给出保守的近似.也可以使用r的简单,但不太精确的近似一个2 + R b 2 ≥3(下面的曲线图中的蓝色圆圈).
有一种类似的方法,你可以考虑盒子底角周围的4个球体,找到它们的表面在盒子里面创建的"风景",然后找到这个"风景"中的最低点.如果你对顶部球体做同样的事情,并且两个风景的最小高度总和超过了盒子的高度,则盒子被球体覆盖.
然后,您还可以检查左/右和前/后最小高度,看它们是否与箱子的宽度和深度相加.如果他们中的任何一个做,那么盒子被球体覆盖.如果没有,则不确定盒子是否被遮盖(可能是假阴性).由于这种方法同时考虑了所有的球体,我认为它会产生比对角球体方法更少的假阴性.
例3a:找到4个球体的交叉点
从上面看,任意两个球体之间的交点是圆圈的两个交叉点之间的线,球体与盒子的底侧相交.
示例3b:找到交叉点上的最低点
球体之间的交叉点连接起来形成"景观"中的"山谷".两个相邻球体之间的谷的最高点位于盒子的边缘,两个对角相对的球体之间的谷的最高点位于它们的中心之间的对角线上.所以最低点是"山谷"相遇的地方.这些点中的哪一个是最低的,取决于它们与两个最大球体的中心之间的对角线的距离.
例3c:侧面未完全覆盖
如果某些"山谷"不相遇,那么底部的一部分未被这4个球体覆盖,并且最小高度显然为零.
我一直在摆弄最小高度方法的代码,计算4个球体之间最低点所需的几何实际上非常简单:
- 对于高于零的最低点,两个对角相对的球体需要相交,即r a + r c或r b + r d不小于盒侧的对角线.
- 半径的球的高度- [R上方的点即距离d远离球体的中心是√r 2 -d 2.
- 如果较大球体的中心点上方的较大球体的高度大于较小球体的半径,则盒子内部较小球体的部分完全包含在较大的球体内.然后可以忽略较小的球体,因为它对"景观"的高度没有影响.
- 两个球体一个和b,其中心在一个距离d彼此,在距离d相交2 + R 一个2 -r b 2 /2×d从球的中心一个.
