As stated I have a triangle mesh I want to separate into connected components. One way I would assume would be to do a depth first search on a vertex and remove vertices, then repeat until the set is empty, but I wonder if there is a simpler (friendlier for the human) way to go about it.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Not sure if it would be friendlier, but if this is about manipulating the mesh through an interface, you can do a depth first traversal of vertices as you said during the loading and save as much information as possible for later use, such as, spanning tree, components, etc in a single pass and provide the user the required information later on $\endgroup$– Kaan E.Commented Mar 4, 2022 at 13:55
-
$\begingroup$ here is a link to a repository that does a such pass: github.com/Viva-Lambda/graphical-models/blob/master/pygmodels/… $\endgroup$– Kaan E.Commented Mar 4, 2022 at 13:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No matter how you do it, there's going to be some kind of graph traversal (e.g. BFS or DFS) involved as that's pretty inherent to the problem.
I'd first build a face neighbor array: for each face (assuming triangles), store the indices of the three neighboring faces. This can be done with a half-edge structure if you have it. If not, a simple way to do this is to create a hash table that maps edges, represented as ordered pairs of vertex indices, to face indices. Then, for each face you can look up the opposing edge and its face by swapping the two vertex indices. (This assumes the mesh is manifold.)
Then, I'd allocate an array of ints to store the component index for each face, initially all set to -1 meaning unassigned.
Start at the first face, assign it to component 0, then perform a BFS using the face neighbors array and assign everything it finds to component 0 (the component index here doubles as the "marked" flag for the BFS). Then find the first unassigned face, assign to component 1, and repeat.
Then, if need be, you can build up arrays of face indices for each component by scanning through the component index array, or build new vertex/index buffers for each component, or whatever you need.
This produces edge-connected components (two faces need to share an edge to be in the same component). An alternative is to do vertex-connected components (two faces are in the same component if they share a vertex, even if they have no shared edges), which is a little more general. For this, you would need to do similar logic but work on vertices instead of faces, which is a little trickier since each vertex can have an arbitrary number of neighbors. There's probably a clever way to build a vertex neighbor table efficiently, but it's not something I've thought about too much.
answered Mar 4, 2022 at 18:11