# comp.graphics.algorithms

## Subject: Re: Generate Geodesic line in 3D triangulated surface

wrote in message
>I want to generate a geodesic line in 3D membrane surface which is
> meshed into a number of triangular elements. This surface is not
> analytically defined but descibed by discrete mesh nodes. Suppose I
> choose two end points on two boundary edges of this surface. I want to
> generate a geodesic line between these two end points over the mesh
> surface. Is anyone know how to deal with this problem? Any suggestions
> would be appreciated. Thanks in advances.

If B0 and B1 are your boundary points, let V0 and V1 be the
closest vertices of your mesh to those points. Use Dijkstra's
algorithm to compute the shortest path between V0 and V1,
say {V0,P0,P1,...,Pn,V1}. You now have a polyline that
connects B0 and B1, say {B0,V0,P0,...,Pn,V1,B1}, and that
lies on the mesh.

The next step is to iteratively apply a relaxation method.
For a consecutive triple of polyline vertices, {U0,U1,U2},
you want to replace U1 by U1' so that {U0,U1',U2} has
smaller length than {U0,U1,U2}. This is a relatively easy
construction to apply when U1 is on an edge shared by
two triangles, one triangle containing U0 and the other
triangle containing U2. It is a bit more challenging when
U1 is a mesh vertex and U0 and U2 are on triangles that
share only U1 (i.e. sharing a vertex but not sharing an
edge).

Another possibility that is simpler to implement, but requires
much more memory (and possibly time) is to rasterize your
mesh into a high-resolution 3D grid of voxels. B0 and B1
are closest to two voxels in this grid. Now apply Dijkstra's
to the graph implied voxel data set.

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