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.
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…
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.
Append global point Ids to input. Helps in later steps.
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.
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.
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.
Now, remove line segments that make up the real boundary, i.e, edges from bndryEdges1. isBoundary from step 2 will help me here.
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.
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
Jaswant, I need to remove non-manifold edges from my model, which was generated from appending couple of models. I am trying to understand your steps outlined above and didn’t quiet get from step 6 onwards. Can you please take a look at the following code and help with the next steps.
def DeleteNonManifoldEdgs(polyData):
boundaryEdges = vtk.vtkFeatureEdges()
boundaryEdges.BoundaryEdgesOn()
boundaryEdges.FeatureEdgesOff()
boundaryEdges.NonManifoldEdgesOff()
boundaryEdges.ManifoldEdgesOff()
boundaryEdges.SetInputData(polyData)
boundaryEdges.Update()
bePolyData = boundaryEdges.GetOutput()
nmEdges = vtk.vtkFeatureEdges()
nmEdges.BoundaryEdgesOff()
nmEdges.FeatureEdgesOff()
nmEdges.NonManifoldEdgesOn()
nmEdges.ManifoldEdgesOff()
nmEdges.SetInputData(polyData)
nmEdges.Update()
nmePolyData = nmEdges.GetOutput()
#Mark the points on the polyData that needs to be deleted
toDelete = vtk.vtkFloatArray()
toDelete.SetNumberOfComponents(1)
toDelete.SetNumberOfValues(polyData.GetNumberOfPoints())
for i in range(polyData.GetNumberOfPoints()):
toDelete.SetValue(i, 0)
for ptId in range(nmePolyData.GetNumberOfPoints()):
nmePnt = nmePolyData.GetPoint(ptId)
vertId = polyData.FindPoint(nmePnt)
toDelete.SetValue(vertId, 1)
cellIdList = vtk.vtkIdList()
#Delete the celles connected to nmEdges
for ptId in range(polyData.GetNumberOfPoints()):
if toDelete.GetValue(ptId) == 0:continue
polyData.GetPointCells (ptId, cellIdList)
for i in range(cellIdList.GetNumberOfIds()):
polyData.DeleteCell(cellIdList.GetId(i))
polyData.RemoveDeletedCells()
boundaryEdges2 = vtk.vtkFeatureEdges()
boundaryEdges2.BoundaryEdgesOn()
boundaryEdges2.FeatureEdgesOff()
boundaryEdges2.NonManifoldEdgesOff()
boundaryEdges2.ManifoldEdgesOff()
boundaryEdges2.SetInputData(polyData)
boundaryEdges2.Update()
be2PolyData = boundaryEdges2.GetOutput()
Thank you Mauro. I tried your code and found interesting things about my model. Following is the total number of facets, manifold edges, non-manifold edges and boundary edges at different steps of the code.
Thank you Jaswant. Interestingly, my model don’t have non-manifold edges. It is built from appending several models, as union using boolean filter didn’t work.
VTK’s built-in Boolean filters do not work: they may provide invalid output for valid input. If you want to combine multiple meshes you must not append them (that may introduce mesh errors that might not possible to fix automatically). Instead, you can use vtkbool package.
If you can comply with the CGAL License (GPLv3) we have the VESPA module. It bring some of the CGAL functionalities into VTK, including boolean operations. In my experience, it is much more robust.
This project is young and should be presented soon to the community.
If you don’t want to build VTK then one option is to use VTK in the virtual Python environment that 3D Slicer provides. vtkbool is built as part of the Sandbox extension, so after installing 3D Slicer, install the Sandbox extension. You can get started with vtkbool using the convenient GUI of “Combine models” module.
