**comp.graphics.algorithms**

## Subject: **Re: Distance between a Line Segment and a triangle in 3D**

Dave Eberly wrote:

> "Maik Wagner"

> news:e5f28e$8ke$1@anderson.hrz.tu-chemnitz.de...

>

>

>>I need to calculate the distance between a line segment and a triangle.

>

>

> My approach is to minimize the quadratic function

> F(u,v,w) = |T(u,v) - L(w)|^2, where T(u,v) is a

> point on the triangle and L(w) is a point on the

> line segment. The triangle point is

> T(u,v) = P0 + u*(P1 - P0) + v*(P2 - P0)

> where P0, P1, and P2 are the triangle vertices and

> where u >= 0, v >= 0, u+v <= 1. The line segment

> point is

> L(w) = Q0 + w*(Q1 - Q0)

> where Q0 and Q1 are the line segment endpoints and

> where 0 <= w <= 1.

>

> The domain is a prism in (u,v,w) space. When the line

> segment is not parallel to the triangle, the minimum

> of F(u,v,w) occurs at

> (1) an interior point of the prism, or

> (2) an interior point of the face of the prism, or

> (3) an interior point of an edge of the prism, or

> (4) a vertex of the prism.

> It is easy enough to associate the geometric configuration

> for each of these cases.

>

> If the line segment and triangle are parallel, F(u,v,w) has

> a minimum value occurring on a line segment in the (u,v,w)

> domain.

>

> A source code implementation is at my website, select the

> Source tab and then the Distance tab. Files are

> Wm3DistSegment3Triangle3.* (although I actually use a

> center-radius formulation for the line segment to help with

> numerical robustness).

>

> --

> Dave Eberly

> http://www.geometrictools.com

>

>

Thanks for this detailed and useful answer.

I just had a quick look at your implementation, and it looks like you're

doing it nearly as i was up to. (Hard to say if these are good or bad

news :))

But i think the order you're doing it will be more effective, as there

are only 3 calculations of the distance line-segment instead of 3 times

segment-segment like i would've done it.

By the way: I had a look on your site even before using google, but it

seems it wasn't close enough :)

Maik

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Distance between a Line Segment and a triangle in 3D =>Re: Distance between a Line Segment and a triangle in 3D =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.