求两个三角形之间的最小距离的算法 [英] Algorithm To Find Minimum Distance Between Two Triangles

问题描述

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

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

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

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

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

解决方案

正如 Axel 的评论中提到的，可以在

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

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

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

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

<小时>

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

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

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

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

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

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

This might be better asked on Math.SE, but I'll try here first:

If I have two arbitrary triangles in 3D space, how can I determine the minimum distance between them? See the following: It's difficult to see in the image, but triangle BAC is entirely in the positive Z-plane, whereas triangle DFE is entirely in the negative Z-plane. The normals for both triangles are parallel to the X-Y plane. The minimum distance between them is probably the distance between the two points I've plotted (H and G).

Assuming the triangles are not co-planar, I know that one of the points representing the smallest distance between the two triangles must lie on either a vertex or along an edge for one of the triangles. For the other triangle, it can lie anywhere on the plane, including along the edges or vertices.

I don't actually need the minimum distance itself - ultimately, all I need to find is whether or not the triangles are within some epsilon of each other.

One thing I've tried is simply sampling the surfaces and applying a fast epsilon test to see if any points from one triangle are within epsilon of any points on the other, but this is too slow for my application. It seems to me that this should have a direct analytical solution, but I haven't been able to find anything about this problem at all.

解决方案

As mentioned in Axel's comment, an implementation can be found at 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 also mentioned that they couldn't find any publication for the algorithm, besides the PQP source code).

---

The gist of the algorithm is pretty simple:

First, find the minimum distance between each pair of edges (9 total combinations). Here, PQP uses the following algorithm:

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

Imagine the following scenario (shown in 2-D for simplicity):

Triangle ABC on the left, and triangle DEF on the right. Let's imagine we were looking at edges AB and EF - we would find that the vertices B and F define the closest points between the two line segments. We then draw two planes at the closest points which are perpendicular to the connecting vector (see below):

Note that I've colored the vertices of the two edges we're comparing blue, whereas the off-edge vertices are now green. We now look at the off-edge vertices and check if either are within the slab between the two planes. Because vertex D is between the two planes, we know that we have not found the true minimum distance between the two triangles.

Now, if we look at edges BC and DE, we see the following arrangement:

Because both off-edge vertices are outside of the two planes, we can guarantee that we've found the minimum distance between the two triangles.

---

In 2-D, it's guaranteed that the minimum distance is along the edges of both triangles, but this is not the case in 3-D. If the above checks didn't find the minimum distance (i.e., no pair of edges passed the plane test), one of the following cases must be true:

1. One of the closest points is a vertex of one triangle and the other closest point is on the face of the other triangle
2. The triangles intersect
3. An edge of one triangle is parallel to the face of the other triangle
4. One or both triangles are degenerate

First, you must check case 1:

Project the points from the first triangle onto the second and take the dot product of the projected points with the first triangle's normal. All of the dot products should have the same sign (if not, swap which triangles you operate on). Then, find the vertex with the shortest projection and check that its projection actually lies on the surface of the other triangle. If it does, you've found your two points (the vertex you're looking at, as well as its projection onto the other triangle).

Otherwise, it must fall into cases 2 - 4.

If the two triangles were shown to be disjoint in the previous checks, then it's either case 3 or 4. Regardless, simply use the minimum points found in the first test. Otherwise, it must be case 2, in which case the minimum distance is zero.

这篇关于求两个三角形之间的最小距离的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！