Jump to content
  • Advertisement
Sign in to follow this  
rajesh_nest

Removing isolated components in a mesh

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!