# comp.graphics.algorithms

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

wrote in message
> This tricky problem is part of search of geodesic line. Suppose I have
> a surface and I want to find out the geodesic line between two points
> in the surface. This surface has curvature and is composed of many
> triangular elements.
>
> I choose two end points in the surface then I can generate a straight
> line between these points. I divide this straight line into 5 or 6
> segments. Now I want to project generated segment nodes onto the
> surface. Firstly, the x and y co-ordinates of each of the segment nodes
> are used to locate specific surface trangular element in which it lies.
> The z co-ordinate of the segment node is determined using the known
> nodal co-ordinates of the surface element by a standard shape function.
>>From these initial positions, the projected segment nodes are allowed
> to slide over the surface elements in search of the equilibrium
> configuration. Once the final state of equilibrium is attained, the
> path of a geodesic will be defined by these projected segment nodes.
>
> My questions are
> 1) how to locate specific surface trangular element using the x and y
> co-ordinates of each of the segment nodes? I know the node coordinates
> of each surface triangular element but I don't know which element I
> need locate.
> 2) how to work out the z co-ordinate of the segment node using the
> known nodal co-ordinates of the surface element by a standard shape
> function?

(the projection of points onto the surface).

My approach (used in medical image analysis software) has been
to construct the adjacency information for vertices, edges,
and triangles. Given two points on the triangle mesh,
connect each point to a vertex of the containing triangle.
Use Dijkstra's algorithm for finding a shortest-length path
consisting of triangle edges. This is the starting path for
a relaxation process which updates the polyline path.
The prototypical update starts with two consecutive edge
of a pair of triangles that share an edge--the end points
of the pair of edges are vertices opposite the shared edge.
The shared point of the two edges is moved along the shared
edge to minimize the path length. No part of this approach
requires projecting points onto the triangle mesh.

If you have a parameterized surface from which the triangles
were generated, I already have an implementation for geodesic
the "Source Code" tab, then the "Applications" tab. In the
"Miscellaneous" section, there is "Construction of geodesic
curves on B-spline height fields". This uses general code to
handle any smooth parametric surface. The documentation
section on "Curves", document title is "Computing Geodesics
on a Riemannian Manifold".

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