6
$\begingroup$

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

Now i get the following case problem case in the mesh generation

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.

$\endgroup$
4
$\begingroup$

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.pdf

This paper claims that their new algorithm is able to "reduce the cracks in the final resulting mesh".

$\endgroup$
  • $\begingroup$ Their result looks familiar. It seems, that the algorithm is really not that easy as the original paper suggests. $\endgroup$ – allo Jan 5 '17 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.