**comp.graphics.algorithms**

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

news:1146467876.756331.26910@i39g2000cwa.googlegroups.com...

>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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Generate Geodesic line in 3D triangulated surface =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.