时间戳

首页 > 解决方案 > 求两个三角形之间最小距离的算法

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

问题描述

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

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

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

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

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

标签： algorithmgeometrylanguage-agnostic

解决方案

正如 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 定义了两条线段之间的最近点。然后，我们在垂直于连接向量的最近点处绘制两个平面（见下文）： 在此处输入图像描述

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

现在，如果我们查看边 BC 和 DE，我们会看到以下排列： 在此处输入图像描述

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

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

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

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

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

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

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

推荐阅读