Curves on surfaces have applications in many different areas. In visualization,
their ability to reveal global surface features or local details at a very low
graphical and memory cost has been used to help visualizing large data sets.
Curves on surfaces are also important in surface segmentation. The
applications of surface segmentation span a large field of research from
visualization, to reconstruction and parameterization. Irregular polygonal
meshes can be reparameterized on a coarse mesh by first constructing a set of
smooth PL on a fine mesh that yield a segmentation of the mesh into three sided
patches. The reconstruction of parametric surfaces from dense polygonal data can
be first based on the interactive design of a mesh of smooth polygonal lines on
the polygonal data.
In this work we introduce an algorithm for building smooth polygonal lines (PL) on 2D manifold triangular meshes. An initial PL is first computed from a set of user specified mesh triangles. This is a crude (non smooth) approximation of the desired PL. Then an iterative execution of geometrical optimization steps and topological operations enables to smooth this initial PL on the surface. During this algorithm the PL always lies exactly on the mesh. A key feature of the algorithm is that it relies solely on the surface geometry and the PL geometry. It is independent of any surface parameterization or any external smooth curves.
The algorithm can be decomposed in four steps:
Step A: The user specifies a few triangles in the mesh, not necessarily adjacent. The order of the picked triangles is relevant: the initial triangle strip will interpolate these triangles in the given order. Note that these initial triangles can be interpolated by the final PL, if desired.
Step B: A Dijkstra algorithm is performed, that outputs a triangle strip, i.e. a sequence of adjacent triangles joining the triangles specified in step A. The output of step B is a triangle strip that gives a crude initial PL. Each vertex of this initial PL is chosen as the mid point of the edges between consecutive triangles in the strip.
Steps C and D are looped until an exit criterion is fulfilled.
Step C: This is the geometrical part of the algorithm. The PL is optimized within the current triangle strip. The vertices of the PL are constraint to stay on the same edge during step C. Different criteria can be used for this geometrical optimization. The result of step C is a PL that can either be strictly included in the current triangle strip, or that can touch the boundary of this strip. If it is strictly included in the triangle strip, the algorithm stops and outputs the final PL.
Step D: This is the topological part of the algorithm. The output of step C is a PL in which some of the vertices have merged with the mesh vertices. This happens when the geometrical optimization performed in step C has pushed some vertices of the PL towards one of the two end points of the edge where these PL vertices lie on. Around such vertices, a sequence of triangles of the current triangle strip is replaced by a new sequence of triangles. The resulting new sequence of triangles is still a triangle strip and it still includes the PL.
The algorithm has the following features:
Return to Stefanie Hahmann's homepage.