# Removing isolated components in a mesh

This topic is 2950 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

My input mesh (obtained from a laser scanner) has few isolated (noisy) components other than required mesh. (Isolated components are are those disconnected components in the mesh,which are unwanted part )

For further mesh processing, I need to identify these noisy components (isolated from the required mesh) and remove them.

How can we identify these separate components in my mesh, remove them and retain the required mesh.

##### Share on other sites
This is what you're looking for:

http://en.wikipedia....graph_theory%29

The graph is constructed by adding a vertex for each of the triangles in the input mesh and connecting them to each triangle they share an edge with. Then it's just repeated application of a search algorithm like DFS, starting from an unvisited triangle and labeling any triangle visited.

You will end up with a component index for each of the triangles. This allows you to compute the volume/area whatever of the different components, determining which set of triangles to keep. For example the component with the largest area.

##### Share on other sites
You have the right idea, but DFS is probably the worst possible choice for searching for connected components in a graph.

The canonical way to build a connected component list is to use a breadth-first search. This is orders of magnitude more efficient. Basically, you do this:

• Pick a random triangle from the mesh
• Add this triangle to the empty component you are working on
• For each triangle connected to the given triangle, add it to the component
• Remove the triangle from the search list
• Starting from one of the connected triangles, repeat steps 3-5
• Once you have traversed all connected triangles, you have one complete component
• Repeat from step 1 until all triangles are removed from the list
Once you have a complete list of connected components, use any heuristic you see fit (number of faces, total area of faces, whatever) to decide which component(s) to keep.

##### Share on other sites
Why would a BFS be so much more efficient? Wikipedia says: "It is straightforward to compute the connected components of a graph in linear time using either breadth-first search or depth-first search. " and connected_components() in boost.graph uses a DFS.

##### Share on other sites

The canonical way to build a connected component list is to use a breadth-first search. This is orders of magnitude more efficient. Basically, you do this:

• Pick a random triangle from the mesh
• Add this triangle to the empty component you are working on
• Once you have a complete list of connected components, use any heuristic you see fit (number of faces, total area of faces, whatever) to decide which component(s) to keep.

Which data structure should I use for component, to which triangles are added.

Thanks to all for nice suggestions.

##### Share on other sites
A simple list should suffice for storing the members of a component.

Why would a BFS be so much more efficient? Wikipedia says: "It is straightforward to compute the connected components of a graph in linear time using either breadth-first search or depth-first search. " and connected_components() in boost.graph uses a DFS.

I spoke too soon. A BFS is superior for directed graphs, but this is not generalizable to undirected graphs. In the directed case you save because of less recursion overhead in the bread-first approach, and this can add up very quickly across large graphs such as the ones the OP is probably dealing with. A mesh is not easily represented as a directed graph, however, at least not without a conversion step which would obliterate the savings of BFS-vs-DFS for the connected-component search.

One thing to be careful of with a DFS even in undirected graphs is how you handle the open/closed lists; it is easy to spend far too much time checking the closed list to ensure your components do not duplicate entries. However, that's an implementation detail and certainly on an algorithmic level it shouldn't make a massive difference.

As with all things, profiling the code on the actual data set is advisable if peak performance is a concern.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 30
• 9
• 16
• 22