Is the marching triangles algorithm guaranteed to terminate (sucessfully)?The algorithm does roughly speaking:iterate over all boundary edgesproject a new point, add a new triangle from the edge and the point, if it's admissible (the new point does not intersect the circumsphere of any existing triangle)if it's not admissible, try do connect the edge with the next or previous point (closing non-convex parts of the boundary), if they are admissibleif it's still not admissible, try to connect a point from the intersected triangle with the edgeelse skip the edge in this iterationNow i get the following caseThe algorithm correctly generated a mesh with triangles, by projecting the new points. Now there is a triangular crack, which is not local delaunay.projecting a point by a constant distance clearly failsusing the next, previous or intersection point doesn't generate a admissible triangleignoring the edge leads to a non-closed meshadding the edge for the next iteration leads to a non-terminating algorithm, as it cannot be processed in the next iteration either and no other processed edge will close the holeThe example is a simple implicit circle function as used in the paper, the seed triangle is an arbitrary edge on the implicit function connected with a point projected by the fixed distance and then projected back on the surface as defined in the algorithm.When i give the next / previous points preference (choose the next / previous point if it is nearer than $\epsilon$, even when a new triangle could be created), i can reduce the number of tight cracks, but it doesn't cover all problem cases either.Despite the obvious problem with my implementation, i do not see if the algorithm as described in the paper is guaranteed to always find a admissible triangle in an iteration until the edge list is empty.
Is the marching triangles algorithm guaranteed to terminate?
delaunay triangulation
According to the following paper, the algorithm creates cracks like you have (see figure 1 and surrounding discussion).Fournier, Marc. Surface Reconstruction: An Improved Marching Triangle  Algorithm for Scalar and Vector Implicit Field Representations. 2009  XXII Brazilian Symposium on Computer Graphics and Image Processing.  IEEE, 2009.http://www.graphicon.ru/html/2009/conference/se1/14/14_Paper.pdfThis paper claims that their new algorithm is able to reduce the cracks in the final resulting mesh.