Remove faces in contact with non-manifold edges

Support
5

Interesting.

For a start…

Either use Manifold Checker (see @Charles_Gueunet’s reply) and threshold with link number. You’ll have to experiment in ParaView for this. Then carry on from step 1.

Or if you’d like to use VTK through and through,

Begin with an input triangulation(likely has some awful non-manifold edges) and two outputs of different feature edge filters. One of them nmEdges with only non-manifold edges and another bndryEdges1 with only boundary edges.

  1. Append global point Ids to input. Helps in later steps.

  2. Insert all lines from bndryEdges1 into a container. Importantly, we’d like to know if an edge is a boundary. Either create a vector-of-bool isBoundary for all edges of the input mesh or keep boundary edges in a map or set. Ex: std::unordered_map<std::pair<vtkIdtype, vtkIdType>>.

    • The compiler will likely complain due to lack of custom comparator. Also, the edge a--b will not be treated the same as b--a if using an ordered map. So, use boost::hash_combine() or shamelessly copy-pasta it. Now, in this container, an edge a--b is treated equivalent to b--a. Just the way we want it to be.

  3. With help of line segments from nmEdges, locate triangles around those edges. No need to use cell locators, ::GetPointCells() should be fine. For the pointId arg, use the ids I appended to point-data in the previous step.

  4. vtkPolyData::DeleteCell()

  5. vtkPolyData::RemoveDeletedCells()

  6. I’ll call this holeyMesh cuz this has holes. Apply feature edges again, this time with boundary edges: on and non-manifold: off. I’ll call the output bndryEdges2.

    • Note: A sanity check here. Feature edges with non-manifold: on should produce an empty output cuz I just removed such cells in the previous step.
    • Tip: Use vtkFillHolesFilter here. If for some odd reason it doesn’t work, move on.

  7. Insert all line segments in bndryEdges2 into a vtkMutableUndirectedGraph.

  8. Now, remove line segments that make up the real boundary, i.e, edges from bndryEdges1. isBoundary from step 2 will help me here.

  9. Reconstruct manifold polygons. I’ll keep these polys in fillerPolys since they’re supposed to fill holes. Maybe do it by hand or use vtkBoostConnectedComponents for that purpose. If I were using python up to now, I’d use scipy.sparse.csgraph to identify connected components since vtk on PyPi does not enable boost at build time. You’ve been warned.

  10. Insert each cell from fillerPolys into holeyMesh to cover the holes.

The mesh should hopefully be free from awful non-manifolds.

I might’ve made a certain choice of features from C++ STL and VTK to describe the algorithm. But, there could be other better alternatives.

I did a similar process by hand a lot of times in Blender. If you dig deep enough, someone might’ve written a python plugin to automate this procedure using Blender’s wonderful BMesh API :slight_smile:

BMesh-devdoc, BMesh-userdoc

1 Like