Splitting mesh into connected components in Openmesh [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 2 years ago.

Improve this question

I have an obj file mesh and I want to extract connected components from it through OpenMesh. I can find boundary vertices and edges, but is there a way to directly split mesh into connected components in Openmesh ?

Answer 1

This functionality is not provided by OpenMesh (the goal of the library is only to provide a mesh data structure). The OpenFlipper, a mesh processing library built on top of OpenMesh, is a more suitable candidate but also does not provide this functionality. You can however find in the codebase in MeshTools/MeshInfoT.cc a componentCount function that counts the number of connected components (it simply does a depth-first search on the vertex graph).

Based on this function, you should be able to write code to split a mesh into its connected components:

1. Add a connected component number property per vertex (initialized to -1 for instance, which means the vertex has not been visited yet).
2. Traverse the mesh vertices with a depth-first search (or breadth-first search..), and set this component number for each vertex:
   1. When an unvisited vertex is found, increment the current connected component number and create a new connected component. The found vertex is used as a seed vertex for this component.
   2. Set the component number of all the vertices traversed from the seed vertex of the connected component.
3. Once the traversal is done, the total number of connected components is known and for each vertex, its component number is also known. From this information the connected component meshes can be built (all the vertices belonging to a component are known, and the faces can be identified using the half-edge reference of the vertex). For each connected component:
   1. Create a new mesh for this connected component.
   2. Add all the vertices from the same connected component. Create a mapping from vertex handle in the initial mesh to the corresponding vertex handle in the new mesh for the connected component.
   3. Find all the faces of the component: to achieve this, a simple way can be to iterate over all the vertices of the component and for each vertex iterate over all the faces it belongs to. For each newly traversed face, create a face in the new component mesh referencing the new vertex handles (using the mapping from old to new vertex handles).

Answer 2

Actually, I solve this problem by using the dual graph of mesh. Since if you directly do graph search (BFS or DFS, etc) on the original graph, no matter you mark the connectivity on each vertex or each edge, you always need to handle some special cases, like two loops: Most of the vertices of the two rings coincide, except that one vertex does not, leaving one face out: Yellow and blue loops leaves one Face out

Thus, to check if the mesh is sliced, we actually focus on the face connection. Thus, I just do the dual operation (iterating on the faces in Openmesh and build the dual relation.) Dual relation

Then, do the DFS/BFS on the dual graph. Whenever you put the next vertex into the pending list check if this edge is the dual of an edge on one loop (note the edge must on one loop rather than two vertices on two loops separately). Finally, just simply check the number of vertices (if the loops do not slice the mesh, the number should be the same as the original vertices number in dual graph.)

You can also add labels while doing BFS/DFS to identify the different connectivity parts.