求两个三角形之间最小距离的算法

Question

这可能在 Math.SE 上问得更好，但我会先在这里尝试:

如果我在 3D 空间中有两个任意三角形，我如何确定它们之间的最小距离？请参阅以下内容:在图像中很难看到，但三角形 BAC 完全位于正 Z 平面，而三角形 DFE 完全位于负 Z 平面。两个三角形的法线都平行于 X-Y 平面。它们之间的最小距离可能是我绘制的两点(H 和 G)之间的距离。

假设三角形不共面，我知道表示两个三角形之间最小距离的点之一必须位于顶点或三角形之一的边上。对于另一个三角形，它可以位于平面上的任何位置，包括沿边或顶点。

我实际上并不需要最小距离本身 - 最终，我需要找到的是三角形之间是否在某个 epsilon 内。

我尝试过的一件事是简单地对表面进行采样并应用快速 epsilon 测试来查看一个三角形中的任何点是否在另一个三角形中任何点的 epsilon 范围内，但这对我的应用程序来说太慢了。在我看来，这应该有一个直接的解析解决方案，但我根本找不到关于这个问题的任何信息。

Answer 1

如 Axel 的评论中所述，可以在 PQP - Proximity Query Pack 找到实现。 (特别是 TriDist.cpp 文件)。但是，该算法没有附带的引文，我也找不到关于 Eric Larsen 的任何内容，显然是他写的(事实上，this 2014 paper 还提到他们找不到该算法的任何出版物，除了 PQP 源代码).

---

算法的要点非常简单:

首先，找出每对边之间的最小距离(总共 9 种组合)。这里，PQP使用了如下算法:

Vladimir J. Lumelsky, On fast computation of distance between line segments. Information Processing Letters, no. 21, pages 55-61, 1985.

想象以下场景(为简单起见，以二维显示):

左边是三角形 ABC，右边是三角形 DEF。假设我们正在查看边 AB 和 EF - 我们会发现顶点 B 和 F 定义了两条线段之间的最近点。然后我们在垂直于连接向量的最近点绘制两个平面(见下文):

请注意，我已将要比较的两条边的顶点涂成蓝色，而离边顶点现在是绿色。我们现在查看离边顶点并检查它们是否在两个平面之间的平板内。因为顶点D在两个平面之间，我们知道我们还没有找到两个三角形之间真正的最小距离。

现在，如果我们查看边 BC 和 DE，我们会看到以下排列:

因为两个离边顶点都在两个平面之外，我们可以保证我们找到了两个三角形之间的最小距离。

---

在 2-D 中，保证最小距离沿着两个三角形的边，但在 3-D 中并非如此。如果上述检查没有找到最小距离(即没有一对边通过平面测试)，则以下情况之一必须为真:

1. 最近点之一是一个三角形的顶点，另一个最近点在另一个三角形的面上
2. 三角形相交
3. 一个三角形的边平行于另一个三角形的面
4. 一个或两个三角形退化

首先，您必须检查情况 1:

将第一个三角形的点投影到第二个三角形上，并将投影点与第一个三角形的法线相乘。所有的点积都应该有相同的符号(如果不是，交换你操作的三角形)。然后，找到投影最短的顶点并检查它的投影是否实际位于另一个三角形的表面上。如果是这样，你就找到了你的两个点(你正在查看的顶点，以及它在另一个三角形上的投影)。

否则，必然属于情况2-4。

如果在之前的检查中显示两个三角形不相交，则属于情况 3 或情况 4。无论如何，只需使用在第一次测试中找到的最小点。否则，它必须是情况 2，在这种情况下最小距离为零。