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.

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?

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?

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?

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

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

1. Fitting triangles into a rectangle (triangle nesting) - Tough One.

2. Interchanging Upper triangle matrix to Lower triangle matix

3. Tesselated Sphere using equalteral triangles to fans of 5 triangles?

4. Fitting triangles into a rectangle (triangle nesting) - Tough One.

5. find adjacent triangle coords to a regular icosahedron triangle?

6. Coordinates for point C of an equilateral triangle given points A and B

7. Point in 2D triangle routine question

8. Distance between a Line Segment and a triangle in 3D

9. intersection between a line segment and a triangle

10. Insert right pointing triangle

11. Error message (yellow triangle with black exc. point)

12. How to exhaust points to form triangles?

14. Points on the interior of a triangle

15. Determine Y Coordinate of point within triangle

4 post • Page:**1** of **1**