# comp.graphics.algorithms

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

wrote in message
> surface in my case is composed of finite element elements which are
> triangles with three nodes coordinates known.

To walk the triangles, you will need to establish the
adjacency information. I cannot determine from your
like you just have an unordered collection of triangles.

> I want to make an algorithm to let user interactively choose
> two end points on two surface boundary edges. Then the
> algorithm can find out the geodesic line between these two
> end points over the mesh surface. The method in my question
> is similar to first point you mentioned:determine which triangle
> a point projects using 2-dimensional methods.

Now I see what you are doing. My company built such a tool
for a medical imaging package we work on. You should not be
projecting points to obtain the endpoints. Instead, you want
to use a 3D picking operation. A pick ray is generated based
on the camera model (perspective or orthogonal) and on the
screen location at which the user clicked the mouse. The
ray is created in the coordinate system of the triangle mesh.
If you have a small number of triangles, a simple iteration can
be made over the triangles, each a ray-triangle intersection
query. If you have a large number of triangles and if you plan
on quite a few queries, you should consider building something
like a bounding-box tree to help localize the search for
triangles intersected by the ray.

And just to make it clear, what I proposed above does not
require the triangle mesh to be the graph of a function (i.e. a
height field). The linear walk method applies when the triangle
mesh is the graph of a function.

> However, I would like to try another method as well. I am
> very interested in your "linear walk" algorithm. Can you
> The union of the triangles in my case is a convex polygon.

I recall Dave Watson (famous for the incremental Delaunay
algorithm in n-dimensions) used the term "linear walk". My
Delaunay2D sample application illustrates this. The linear
walk itself is in the Foundation library file Wm3Delaunay2.cpp,
function GetContainingTriangle(). The sample application
allows you to click on a point in a (Delaunay) triangle mesh.
A starting triangle is tested, and then a path of triangles
leading to the containing triangle is drawn.

--
Dave Eberly
http://www.geometrictools.com