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

Question

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

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

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

实际上，我实际上并不需要最小距离，最终，我需要找到的只是这些三角形是否在彼此的ε之间。

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

Answer 1

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

该算法的要点非常简单：

首先，找到每对边之间的最小距离（总共 9 种组合）。这里，PQP 使用以下算法：

Vladimir J. Lumelsky，在线段之间距离的快速计算。信息处理信件，编号。21，第 55-61 页，1985 年。

想象一下以下场景（为简单起见，以二维形式显示）：

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

请注意，我已将要比较的两条边的顶点着色为蓝色，而离边顶点现在为绿色。我们现在查看边缘顶点并检查它们是否位于两个平面的相对侧（感谢评论中的 Adam 对此进行了澄清）。因为顶点 D 位于两个平面之间，所以我们知道我们还没有找到两个三角形之间真正的最小距离。

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

因为两个离边顶点都位于两个平面的相对侧，所以我们可以保证找到两个三角形之间的最小距离。

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

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

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

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

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

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