4

I am looking for an algorithm to find all (or maximum no of) contiguous faces of a continuous mesh. The faces should be ordered in an array in such a way that each face is preceded by a face linked to it on the mesh. The ultimate goal is to have a single such array. Is it possible even in theory? If not what's the best way to maximize the count of faces in the array?

In this (rather naive) implementation the selection point traverses clockwise covering end vertex of the available edge of the last face covered. But this quickly gets into a dead-end. I also tried both the ends of the edge, or all the available vertices of the face, but sooner or later each one reaches a face with no connections to un-selected faces.

Edit:

It's a triangulated mesh, i.e. each face has exactly three vertices. And the requirement is to have a set of minimum no of arrays (ideally one) covering all the connected faces of the mesh.

Blender Dadaist
  • 157
  • 6
  • how are you representing the mesh? also how do you define an dis-contiguity? ideally I presume the mesh is well formed and there are no "holes". Wouldn't every face be reachable from every other face? – Srini Sep 12 '18 at 20:52

1 Answers1

3

This is a hard problem (the Hamiltonian path problem in a planar graph (specifically, the dual of the input graph)), but you may have get good results with a local search method. There's a simple one due to Angluin and Valiant (https://doi.org/10.1016/0022-0000(79)90045-X) and a more complicated effort by Frieze (https://doi.org/10.1002/rsa.20542). These algorithms are proved in theory to work on random graphs only, but graphs without adversarial construction are often amenable too.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • I was thinking of the problem in this terms too, although I don't know if there is some topological approach that may simplify it. Looking at [Wikipedia](https://en.wikipedia.org/wiki/Hamiltonian_path_problem) it is said that 4-connected planar graphs always have a Hamiltonian path and it can be computed in linear time, so I suppose it can always be done for closed meshes of quads. Which I'm not sure if is too surprising. Also this is assuming that the mesh is "well-formed" (manifold), otherwise the graph wouldn't have to be planar I think? – jdehesa Sep 12 '18 at 16:42
  • @jdehesa Sure. Those algorithms work on general graphs. – David Eisenstat Sep 12 '18 at 16:53
  • This (Angluin and Valiant) looks very promising. I need some time to understand and implement it, though. Will share the result on this thread when I have made some progress with the implementation. – Blender Dadaist Sep 18 '18 at 11:44
  • I would really appreciate anyone with acess to the cited sources writtingva simple explaination of each. – Andrew Micallef Mar 12 '21 at 05:18
  • @AndrewMicallef I implemented A--V for another answer: https://stackoverflow.com/a/15904295/2144669 – David Eisenstat Mar 12 '21 at 13:22
  • 1
    @AndrewMicallef the short version is: extend the path randomly, if it cycles back on itself then delete one of the cycle edges incident to the degree-3 vertex and then continue at the other end. – David Eisenstat Mar 12 '21 at 13:24