**comp.graphics.algorithms**

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

"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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

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

Replies:

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

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.