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:

• It is a purely geometry driven algorithm. This means that the smoothing criteria as well as the error measurements only depend on the intrinsic geometric properties of the surface or the PL.
• Between two user-specified or automatically computed points on the polygonal surface a smooth PL can be computed by using different smoothing filters.
  * We first introduce a "linear" filter which yields a local discrete geodesic. The visual effect is a global straightening of the initial PL.
  * Then several extensions are possible, we choose to implement a ``cubic" smoothing filter. Here the global shape of the initial PL is preserved while small details are smoothed out.
• In any case smooth PL are obtained by iteratively moving the vertices of the PL on the mesh edges (geometrical modification) and by passing through mesh vertices if necessary (topological modification).
• The algorithm is easy to implement. However, the topological operations need to be well understood.
• The whole procedure of building curves on a polygonal surface can be both, fully automatic or semi-automatic. It depends on the application. In the first case for example a mesh simplification algorithm can be used in order to produce a set of pairs of mesh points (corresponding to end points of the edges of the coarse mesh) which is given as input to the algorithm presented in this paper. In a semi-automatic environment a user can lay out a set of curves by specifying the end points of the desired PL. For each PL he/she can specify one or more (ordered) points which are interpolated by the initial crude PL. The smooth curve always interpolates the end points.