triangle-point triangle-line segment and triangle-triangle closes point question

triangle-point triangle-line segment and triangle-triangle closes point question

Post by keit » Sun, 30 Aug 2009 02:18:06


Hi! The subjects tells it all, both Eberly's 3DGED book and Ericson's
RTCD book treat these problems. Eberly's treatment seems overly
complicated to me (although correct) and Ericson's a bit vague (he makes
assertions without proofs). Are there other resources about calculating
these closest points I could use? I'd like to implement the Lin-Canny
algorithms which needs these calculations.
 
 
 

triangle-point triangle-line segment and triangle-triangle closes point question

Post by Dave Eberl » Thu, 03 Sep 2009 08:45:22


One is too complicated, the other too simple? For you to say "although
correct", that means you understand the constructions. Please suggest
alternate constructions that are not "overly complicated". From the
perspective of software engineering, the main concern is how two
different implementations compare in performance. Maybe your
alternate constructions will perform better than what Christer or I
suggested.

My approach was to formulate the problems in terms of minimizing
a quadratic function defined on a bounded convex set. This is a basic
problem handled by calculus, so it is not clear to me why you believe
it is overly complicated. For an elegant mathematical solution, you
can solve this as a Linear Complementarity Problem (LCP) .


Source code at my site that goes along with those algorithms
described in my books? Source code that is most likely available
at many other sites? Or do you simply want to implement your own
based on someone's description of the algorithms?

 
 
 

triangle-point triangle-line segment and triangle-triangle closes point question

Post by keit » Fri, 04 Sep 2009 03:58:22

Dave Eberly pravi:



RTCD book provides a simple way to calculate triangle-triangle distance,
but he is vague. For example, he asserts that the closest point between
2 nonintersecting triangles can lie either on edges of both triangles,
or on a vertex and interior point of a triangle. Intuitively that's just
fine, but where's the proof?

In your book you identify 49 possible cases to solve, I don't think your
triangle-triangle distance method is elegant, but your description of it
is not vague.


Thanks for yet another interesting technique. It seems quadratic
programming can solve many problems in geometry.


I know about your source code, you mention it in 3DGED. Other sites? I
have googled for them, but found none. I even checked the source code of
quake3, but no luck. If there are other descriptions of the distance
calculations, that'd be great (assuming you don't consider source code a
description). Are there?
 
 
 

triangle-point triangle-line segment and triangle-triangle closes point question

Post by Dave Eberl » Fri, 04 Sep 2009 05:24:43

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
points.
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
infinitesimal
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
have
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,
then
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
segment-triangle