algorithm - 确定球体是否与物体相交

Question

我有一个由三角形表面表示描述的封闭对象(由三个顶点描述，形成右手法则，法线指向对象的“外部”)。我在靠近物体表面的某处的 3D 空间中放置了一些半径的球体。我想确定球体是否与物体相交。

我想到了 3 种方法来确定这一点，但每种方法都有其缺点，而且都不理想。

1) 我可以确定要放置球体的“面”，从那里我可以计算从引用平面到第一次遇到物体的距离的网格。我可以对球体的另一“侧”做同样的事情，然后简单地检查到物体的距离是否总是大于到球体表面的距离。如果到对象的距离总是更大，则球体不会在网格上的任何点与对象相交。

这样做的好处是它相当快，但由于我只计算离散点，所以它不是绝对的。如果我的网格分辨率太粗，则球体可能会在我的网格节点之间的某个点相交。

2) 我可以获取所有三角形的所有顶点，并根据我放置的球体方程检查它们。如果在球体内部检测到顶点，则球体绝对会部分位于对象内部。

这样做的好处是速度相当快，但也很容易出错。球体可能与三角形内的对象相交，并且错过了所有顶点。

3) 我可以计算球体表面上的点簇。然后我可以检查每个点是否在对象内部(使用 point inside a polygon 算法的 3D 版本)。如果任何一点在对象内部，则球体的一部分在对象内部。

这样做的好处是它可以非常准确，具体取决于我在球体表面使用了多少点(点密度越高 = 准确度越高)。然而，对象算法中的点是相当昂贵的，尤其是当三角形数量增加时。这种方法最好(甚至可以准确地告诉我球体与对象相交的位置和数量)，但它会非常慢。

有没有你们知道的算法或方法可以解决这样的问题？我的首要目标是准确性，我需要知道球体是否会接触到物体。知道球体接触的位置或至少一般区域也很好。最后，拥有速度总是一件好事。

谢谢

-伪造

Answer 1

这应该是您问题的完整答案。我还没有给出一个实现，所以可能需要考虑避免不必要的划分等。如果有任何不清楚的地方，请要求澄清。我正在以 John at CashCommons 的想法为基础进行构建。

令 c 为半径为 r 的球体的中心。我们真正需要知道的是:三角形 T 中的任何点(不仅仅是三个顶点)比 r 个单位更接近 c 吗？

需要考虑三种情况:

1. T 中距离 c 最近的点是 T 的一个顶点。这很简单!
2. T 中距离 c 最近的点在 T 内部。
3. T 中最接近 c 的点位于 T 的一条边上。

我们定义了一些变量:

• c: 球心
• r:球体的半径
• T:我们的三角形
• v1,v2,v3:T的顶点
• t:T中距离c最近的点
• P:包含v1,v2,v3的唯一平面
• p:P中距离c最近的点

第 1 步:检查所有三角形顶点，以防我们处于情况 1 中。

第 2 步:找到 p，即 P 中最接近 c 的点。这可以通过将 c 投影到 P 上来完成。

第 3 步:如果是情况 2，我们基本上就完成了。所以检查 p 是否在 T 中。(检查一个点是否在给定的三角形中相对容易，但我不知道最好的方法，所以我会忽略它。)如果是，检查是否dist(p,c) > r，这就是你的答案。

这只剩下案例 3。所以，假设我们有 p，并且 p 不在 T 中。现在，我们实际上从几何学中知道了一些关于 p 的具体信息:线 c-->p 垂直于 P。(如果不是，我们可以找到比 p 更接近 c 的点 p'。)由于这种垂直性，我们可以使用毕达哥拉斯定理:

Dist(c, z)^2 = Dist(c, z)^2 + D(p, z)^2

对于 P 中的任何 z。特别是对于 z=t 是这样。

所以现在我们只需要找到 t 并检查是否:

D(p,t)^2 <= r^2 - D(c,p)^2

这是一个非常相似的问题，现在是二维的。要做的事情是在 T 中找到最接近 p 的 t，从而最接近 c。我们已经检查过 t 不在 T 的内部，也不在 T 的顶点之一。因此，它必须在其中一条边上。所以，我们可以试着在每条边上找到它。如果 t 不在顶点，则 t-->p 线将垂直于边，因此这样做相当简单。

第 4 步:对于三角形的每条边 v1-->v2，执行以下操作:

4.1。从 v1 到 v2 的线段为

(x,y,z) = (v1x, v1y, v1z) + s * (v2x - v1x, v2y - v1y, v2z - v1z), 0 <= s <= 1

4.2 我们想要一条位于平面 P 中的直线，垂直于 v1-->v2，并且包含 p。该行将具有以下形式

(px, py, pz) + s * (qx, qy, qz)

所以我们只需要选择一个平行于平面 P 并垂直于 v1-->v2 的向量 q。服用

q = (p-->c) x (v1-->v2)

(即叉积)应该这样做，因为这将垂直于 P 的法线，因此平行于 P，并垂直于 v1-->v2。

4.3 求解方程组

(tx,ty,tz) = (v1x, v1y, v1z) + s1 * (v2x - v1x, v2y - v1y, v2z - v1z)
(tx,ty,tz) = (px, py, pz) + s2 * (qx, qy, qz)

找到位于两条线上的 t。这真的只是意味着解决

v1x + s1 * (v2x - v1x) = px + s2 * qx
v1y + s1 * (v2y - v1y) = py + s2 * qy
v1z + s1 * (v2z - v1z) = pz + s2 * qz

对于 s1 和 s2。

4.4。如果 s1 在 0 和 1 之间，那么我们发现了一个点 t 在 v1 和 v2 之间，应该检查它。

4.5。如果 s1 不在 0 和 1 之间，则 v1 或 v2 之一最接近 p，因此我们已经检查过了。