# comp.graphics.algorithms

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

wrote in message

> 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