Find connected component on meshes

FDM (Fused Deposition Modeling) 3D printing can tolerate having inner cavities in the geometric model, while other manufacturing techniques might be less permissive about hollow objects. What if we want to know if our mesh object contains any inner cavities?

Inner cavity in a model.

This functionality was recently added to the poly_Mesh data structure of our open-sourced Mobius library. The analysis works on meshes taking advantage of the clear fact that a mesh is a formal graph (unless its topological relations get lost like in the STL format). Therefore, an inner cavity is necessarily a connected component in this graph (although this condition is not sufficient).

Finding vertex-adjacent triangles from the selected seeds.

Connected components are detected using the technique of region growing. That is, starting from the selected seed triangle, the algorithm takes all its vertex-adjacent elements as new seeds and repeats the process. Iterations stop when no triangles are left unvisited. The number of regions grown on a mesh is exactly the same as the number of connected components we are looking for.

Coming back to the manufacturability issues, whenever the algorithm detects more than one connected component for a model, it's probably time for a human being to interfere with the process and check what might be wrong with the part. A valid situation of having multiple connected components for traditional parts is just when an assembly is communicated as the input.

Want to discuss this? Jump in to our forum.