求两个三角形之间最小距离的算法
Algorithm To Find Minimum Distance Between Two Triangles
最好在 Math.SE 上提问，但我会先在这里尝试：
如果我在 3D 中有两个任意三角形 space，我如何确定它们之间的最小距离？请参阅以下内容：
在图像中很难看到，但三角形 BAC 完全位于正 Z 平面，而三角形 DFE 完全位于负 Z 平面。两个三角形的法线都平行于 X-Y 平面。它们之间的最小距离可能是我绘制的两点（H 和 G）之间的距离。
假设三角形不共面，我知道代表两个三角形之间最小距离的点之一必须位于顶点或三角形之一的边上。对于另一个三角形，它可以位于平面上的任何位置，包括沿边或顶点。
我实际上并不需要最小距离本身 - 最终，我需要找到的是三角形之间是否在某个 epsilon 内。
我尝试过的一件事是简单地对表面进行采样并应用快速 epsilon 测试以查看一个三角形中的任何点是否在另一个三角形中任何点的 epsilon 范围内，但这对我的应用程序来说太慢了。在我看来，这应该有一个直接的解析解决方案，但是我一直找不到关于这个问题的任何信息。
正如 Axel 的评论中提到的，可以在 PQP - Proximity Query Pack (in particular, the TriDist.cpp file). However, there are no accompanying citations for the algorithm, nor can I find anything on Eric Larsen, who apparently wrote it (in fact, this 2014 paper 找到一个实现，还提到除了 PQP 源代码之外，他们找不到该算法的任何出版物）。
算法的要点非常简单：
首先，找到每对边之间的最小距离（总共 9 种组合）。在这里，PQP 使用以下算法：
想象以下场景（为简单起见，以二维方式显示）：
左边是三角形ABC，右边是三角形DEF。假设我们正在查看边 AB 和 EF - 我们会发现顶点 B 和 F 定义了两条线段之间的最近点。然后我们在垂直于连接向量的最近点绘制两个平面（见下文）：
请注意，我已将要比较的两条边的顶点涂成蓝色，而离边顶点现在是绿色。我们现在查看离边顶点并检查它们是否在两个平面之间的平板内。因为顶点D在两个平面之间，所以我们知道我们还没有找到两个三角形之间真正的最小距离。
现在，如果我们查看边 BC 和 DE，我们会看到以下排列：
因为两个离边顶点都在两个平面之外，我们可以保证我们已经找到了两个三角形之间的最小距离。
在 2-D 中，保证最小距离是沿着两个三角形的边缘，但在 3-D 中并非如此。如果上述检查没有找到最小距离（即没有一对边通过平面测试），则以下情况之一必须为真：
- 最近的一个点是一个三角形的顶点，另一个最近的点在另一个三角形的面上
- 三角形相交
- 一个三角形的边平行于另一个三角形的面
- 一个或两个三角形退化
首先，您必须检查案例 1：
将第一个三角形的点投影到第二个三角形上，并将投影点与第一个三角形的法线相乘。所有的点积都应该有相同的符号（如果不是，交换你操作的三角形）。然后，找到投影最短的顶点并检查它的投影是否实际位于另一个三角形的表面上。如果是这样，你就找到了你的两个点（你正在查看的顶点，以及它在另一个三角形上的投影）。
否则，必然属于情况2-4。
如果在前面的检查中显示两个三角形不相交，那么就是情况 3 或情况 4。无论如何，只需使用在第一次测试中找到的最小点。否则，它必须是情况 2，在这种情况下最小距离为零。
最好在 Math.SE 上提问，但我会先在这里尝试：
如果我在 3D 中有两个任意三角形 space，我如何确定它们之间的最小距离？请参阅以下内容：
假设三角形不共面，我知道代表两个三角形之间最小距离的点之一必须位于顶点或三角形之一的边上。对于另一个三角形，它可以位于平面上的任何位置，包括沿边或顶点。
我实际上并不需要最小距离本身 - 最终，我需要找到的是三角形之间是否在某个 epsilon 内。
我尝试过的一件事是简单地对表面进行采样并应用快速 epsilon 测试以查看一个三角形中的任何点是否在另一个三角形中任何点的 epsilon 范围内，但这对我的应用程序来说太慢了。在我看来，这应该有一个直接的解析解决方案，但是我一直找不到关于这个问题的任何信息。
正如 Axel 的评论中提到的，可以在 PQP - Proximity Query Pack (in particular, the TriDist.cpp file). However, there are no accompanying citations for the algorithm, nor can I find anything on Eric Larsen, who apparently wrote it (in fact, this 2014 paper 找到一个实现，还提到除了 PQP 源代码之外，他们找不到该算法的任何出版物）。
算法的要点非常简单：
首先，找到每对边之间的最小距离（总共 9 种组合）。在这里，PQP 使用以下算法：
想象以下场景（为简单起见，以二维方式显示）：
左边是三角形ABC，右边是三角形DEF。假设我们正在查看边 AB 和 EF - 我们会发现顶点 B 和 F 定义了两条线段之间的最近点。然后我们在垂直于连接向量的最近点绘制两个平面（见下文）：
请注意，我已将要比较的两条边的顶点涂成蓝色，而离边顶点现在是绿色。我们现在查看离边顶点并检查它们是否在两个平面之间的平板内。因为顶点D在两个平面之间，所以我们知道我们还没有找到两个三角形之间真正的最小距离。
现在，如果我们查看边 BC 和 DE，我们会看到以下排列：
因为两个离边顶点都在两个平面之外，我们可以保证我们已经找到了两个三角形之间的最小距离。
在 2-D 中，保证最小距离是沿着两个三角形的边缘，但在 3-D 中并非如此。如果上述检查没有找到最小距离（即没有一对边通过平面测试），则以下情况之一必须为真：
- 最近的一个点是一个三角形的顶点，另一个最近的点在另一个三角形的面上
- 三角形相交
- 一个三角形的边平行于另一个三角形的面
- 一个或两个三角形退化
首先，您必须检查案例 1：
将第一个三角形的点投影到第二个三角形上，并将投影点与第一个三角形的法线相乘。所有的点积都应该有相同的符号（如果不是，交换你操作的三角形）。然后，找到投影最短的顶点并检查它的投影是否实际位于另一个三角形的表面上。如果是这样，你就找到了你的两个点（你正在查看的顶点，以及它在另一个三角形上的投影）。
否则，必然属于情况2-4。
如果在前面的检查中显示两个三角形不相交，那么就是情况 3 或情况 4。无论如何，只需使用在第一次测试中找到的最小点。否则，它必须是情况 2，在这种情况下最小距离为零。