Remove faces in contact with non-manifold edges

Hi,
I have as input a (triangular) mesh that has some holes. I’m trying to execute the vtkFillHolesFilter to close all the holes. It works well for most of the holes, but some of them are not being closed. I discovered that these roles that are not being closed by the fill holes filter are surrounded by some non-manifold edges. Then I made some test on Meshlab, I selected all the non-manifold edges, deleted all faces that share these edges and executed the fill holes, and it closed everything perfectly. But now I want to execute this process with VTK.

I need to remove from my mesh (a vtkPolyData), all the faces that are in contact with non-manifold edges.

I was able to identify all the non-manifold edges with the vtkFeatureEdges filter, but I’m not sure how to proceed to delete the faces that share these edges.

The resulting mesh should be the original mesh without any non-manifold edge.

Right now I have this:

vtkSmartPointer featureEdges = vtkSmartPointer::New();
featureEdges->SetInputData(meshPolydata);
featureEdges->BoundaryEdgesOff();
featureEdges->FeatureEdgesOff();
featureEdges->ManifoldEdgesOff();
featureEdges->NonManifoldEdgesOn();
featureEdges->Update();

But I’m not sure how to use the featureEdges->GetOutput() to delete the faces around the edges from my meshPolydata.

I would appreciate some help.

*I also accept other possible solutions to remove all non-manifold edges from the mesh.

A picture from the process in Meshlab…

2 Likes

We would like to do exactly the same (remove non-manifold edges and fill small holes). Can somebody give advice?

I remember that somebody mentioned that Kitware is working on a mesh cleanup filter. Is there any news about that?

For reasonably simple cases this shouldn’t be too hard (e.g., smaller holes, small non-manifold wings). But in general it can be quite hard (large holes, Klein bottles). Do you have sample data that you can post? We can add it to the list…

There is a Manifold checker in TTK. Used with a threshold, you should be able to do something similar, without having to develop a new filter.

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