keith" < XXXX@XXXXX.COM > wrote in message
news:h7mf8e$bre$ XXXX@XXXXX.COM ...
Let the triangles be A0 and A1. Let C0 be on A0 and C1 be on A1 such
that the two points attain the minimum distance. C0 is a vertex
(classification named V0) or an interior-edge point (on edge but not a
vertex, classification named E0) or an interior-triangle point (on triangle
but not on an edge, classificaiton named T0) of A0. Similar classifications
for C1. So you have 9 possible classifications for the pair of closest
By symmetry, you need only consider configurations V0-V1, V0-E1,
V0-T1, E0-E1, E0-T1, and T0-T1.
You can imagine configurations of A0 and A1 where the closest points
are of the configuration types V0-V1, V0-E1, V0-T1, or E0-E1. The
remaining possibilities are E0-T1 and T0-T1.
If the configuration is E0-T1, the edge containing C0 must be parallel to
the plane of A1. For if it were not parallel, you could take an
step along the edge in the direction D toward the plane of A1 and reduce
the distance. That is, C0+e*D is closer to A1 than C0 for any sufficiently
small e > 0, a contradiction to C0 being the closest point, and you still
the configuration E0-T1. Given that the edge containing C0 is parallel to
the plane of A1, there are infinitely many pairs of closest points. Walk
along the edge points as long as their projections onto the plane of A1
are in A1. You either reach an edge endpoint, in which case you have
configuration V0-T0, or you reach an interior-edge point whose projection
is on an edge of A1, in which case you have configuration E0-E1 or E0-V1.
If the configuration is T0-T1, the planes of A0 and A1 are parallel. The
argument of the last paragraph (using an infinitesimal step) applies here
as well. Walk along the A0 points as long as their projections onto
the plane of A1 are in A1. If a vertex of A0 projects to a point in A1,
you have configuration V0-T1. If no vertex of A0 projects to points in A1,
then walk to an edge and repeat the argument of the last paragraph,
obtaining configuration E0-E1 or E0-V1.
In summary, you can always reduce the problem to considering the
configurations V0-V1, V0-E1, V0-T1, or E0-E1.
Most likely you could even formulate the algorithm in terms of the
Minkowski difference A0-A1, a convex polyhedron that does not
contain the origin (you postulated that the triangles were not
intersecting). The polyhedron has a unique point that is closest
to the origin, and the distance from that point to the origin is the
triangle-triangle distance. You need to argue which configurations
of the triangles led to that closest point.
Considering that my triangle-triangle discussion is a paragraph of
5 lines, with the pseudocode to be left as an exercise, would you not
say that my discussion is also vague?
My implementation of triangle-triangle distance turns out not to be that
49-case algorithm. Instead, I make the following observation. A vertex
is an edge point, so you really have four cases. C0 is an edge point or
an interior point of A0 and C1 is an edge point or an interior point of A1.
I iterate over the three edges of A0 and do a segment-triangle distance
calculation for each. I then iterate over the three edges of A1 and do a
segment-triangle distance calculation for each. I choose the minimum
of the 6 calculations for the triangle-triangle distance. My