**comp.graphics.algorithms**

## Subject: **Re: How to project a point onto a surface?**

news:1145661486.029706.80340@i39g2000cwa.googlegroups.com...

> My question is how to locate the triangular element on the

> surface in which each segment node will be projected based

> on segment node x, y coordinates and how to work out the

> z coordinate of projected segment node on this triangular

> element based on its node coordinates.

Is your triangle mesh is the graph of a function of x and y?

If so, you can determine which triangle a point projects

using 2-dimensional methods. Your triangle mesh projects

to a collection of contiguous triangles in the xy-plane.

You need to determine in which triangle the projection of

the test point P lies.

If the union of the triangles is a convex polygon, then a

"linear walk" algorithm is simple to implement. Select a first

triangle. If P is in that triangle, done. If not, P is "outside"

at least one edge. Visit the triangle adjacent to the edge

and repeat until you find a containing triangle or until you

determine P is outside the convex polygon.

If the union of the triangles is not a convex polygon, then

the linear walk has problems if the path takes you outside

the polygon--it is still possible P is inside a triangle. In this

situation, you can compute the convex hull of the triangles

and represent the "pockets" as triangles. The pockets are

those regions inside the convex hull but outside the original

triangle mesh. The linear walk may be used, but if you

determine P is in a pocket triangle, the walk terminates.

An algorithm with better asymptotic order uses a

Dobkin-Kirkpatrick hierarchy of the triangles forming the

convex polygon.

--

Dave Eberly

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

How to project a point onto a surface? =>Re: How to project a point onto a surface? =>Re: How to project a point onto a surface? =>

Replies:

Re: How to project a point onto a surface?

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.