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

问：

这个问题可能最好在 Math.SE 上问，但我会先在这里尝试：

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

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

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

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

算法几何语言无关

正如 Axel 的评论中提到的，可以在 PQP - 邻近查询包（特别是 TriDist.cpp 文件）中找到实现。但是，该算法没有附带的引用，我也找不到任何关于埃里克·拉森（Eric Larsen）的信息，他显然是写了它（事实上，这篇2014年的论文还提到，除了PQP源代码之外，他们找不到该算法的任何出版物）。

该算法的要点非常简单：

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

弗拉基米尔·卢梅尔斯基（Vladimir J. Lumelsky），关于线段之间距离的快速计算。《信息处理快报》，第21期，第55-61页，1985年。

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

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

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

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

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

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

其中一个最近的点是一个三角形的顶点，另一个最近的点位于另一个三角形的面上
三角形相交
一个三角形的边平行于另一个三角形的面
一个或两个三角形都退化了

首先，您必须检查案例 1：

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

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

如果在前面的检查中显示两个三角形不相交，则为情况 3 或情况 4。无论如何，只需使用第一次测试中发现的最低分数即可。否则，它必须是情况 2，在这种情况下，最小距离为零。

你好。我遇到了一些关于“外部”含义的问题，因为我发现两个偏离边缘的顶点都可以在两个平面之间的区域之外，而所讨论的边不具有最短的距离。imgur.com/a/zLfFkW4。“外部”的含义是，这两个离边顶点都必须位于平面之间区域之外的正确对立边上。只是以为我会强调这一点。

0赞 A.Comer 3/18/2023

谢谢亚当，这是一个我没有考虑过的有趣（而且可能很常见？）的案例。我已经编辑了答案，以澄清顶点需要位于该板的相对两侧

0赞 Shihab Shahriar Khan 11/13/2023 #2

上面的答案得到了惊人的解释。那些寻找代码的人可以参考 Nvidia 的 Physx 库中的这个实现。

我将指出算法某些方面的实现细节：

对于主要检查，即“离边顶点位于两个平面的相对两侧”，nvidia 会这样做：

             PxU32 id = i+2;
             if(id>=3)
                 id-=3;
             PxVec3 Z = p[id] - cp;
             float a = Z.dot(V);
             id = j+2;
             if(id>=3)
                 id-=3;
             Z = q[id] - cq;
             float b = Z.dot(V);

             if((a<=0.0f) && (b>=0.0f))
                 return V.dot(V);

这里是三角形 A 的离边顶点，是在 A 上找到的最近点，将该最近点连接到三角形 B 上最近点的向量（即）。表示离边顶点位于这两个红色平面定义的刺之外。对三角形 B 重复相同的操作，确保这些顶点位于平面的另一侧，然后函数返回。p[id]cpVV=cq - cpa=Z.dot(V)<=0.0(a<=0.0f) && (b>=0.0f)

如果在检查每对边后没有返回，我们尝试检查第一个边情况（“最近的点之一是三角形的顶点，另一个最近的点位于另一个三角形的面上”）：

计算三角形的面法线（比如ABC），并检查它没有退化（法线的大小>0）。如果不是这样，则找到面法线和向量 DA、EB 和 CF 的点积（包含 ABC 的边缘向量）。在这种顶点面的情况下，所有点积都应该有相似的符号（下面的两个条件）。这也会找到最接近的顶点（）。snlSVifindex
最后，检查面平面上最近顶点的投影是否位于三角形内。如果最接近的顶点是，则找到（下面的 s），找到每个具有三角形边的面法线的叉积（下图），并确保它们的点积都> 0。PPA, PB, PCVZ
如果点积> 0，则返回 P，它是在 ABC 面上的投影。

对两个三角形重复此操作。如果函数尚未返回，则表示上述答案中的边缘情况 2 或 4。休息应该很容易遵循。

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

Algorithm To Find Minimum Distance Between Two Triangles

评论

评论

评论