Algorithm To Find Minimum Distance Between Two Triangles

Question

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.

Answer 1

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.