Is the marching triangles algorithm guaranteed to terminate (sucessfully)?
The algorithm does roughly speaking:
- iterate over all boundary edges
- project 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 admissible
- if it's still not admissible, try to connect a point from the intersected triangle with the edge
- else skip the edge in this iteration
The 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 fails
- using the next, previous or intersection point doesn't generate a admissible triangle
- ignoring the edge leads to a non-closed mesh
- adding 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 hole
The 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.