vtkFillHolesFilter algorithm's multiple edge neighbors case currently fails, suggestions for proper approach

Development
1

In the vtkFillHolesFilter algorithm is the following line of code for the case of multiple edge neighbors

          else if (neighbors->GetNumberOfIds() > 1)
          {
            // have to logically split this vertex
            valid = 0;
          }

which reads like an unfinished TODO item. I’ve come across this scenario with a collection of data and a model surface that I would characterize as more complex than perhaps typical, but not overly complex. When ‘valid’ is set to 0, the algorithm simply doesn’t behave well. I’ve written further details in the issue tracker: https://gitlab.kitware.com/vtk/vtk/-/issues/19209 Because of the unfinished nature of the algorithm, Mathieu and Will suggested opening a discourse on the topic.

I offered a fix for the multiple-neighbors case which makes vtkFillHolesFilter more robust for poly-data in which it arises. With the patch, the algorithm does go on to construct a triangulation, ‘valid’ becoming 0 is less likely and if the ‘valid’ variable were to become zero the algorithm terminates rather than leading to unpredictable behavior. However, what the patch doesn’t do is take into consideration the spatial relationship of neighbor edges and how that might reflect in the general quality of the triangulation. Will suggested the base construct of vtkFillHolesFilter may not be sufficiently sophisticated, as it basically extracts free edges from the links built from the polys and follows wherever they lead to.

So, I’m inviting folks to have a look at the issue and make any suggestions about a more thorough approach. Should the algorithm take a step back and construct a better topology prior to selecting the triangulation contours? Is there, perhaps, another algorithm that has effectively done something similar? (Sometimes I notice a hunk of VTK code that seems like it could have been useful in some other algorithm.)

2

We are trying to use FillHoles but it looks like nothing happens at all. Could this be due to your described issue? I observe some holes that share a vertex but also some isolated ones. I cannot upload files here yet unfortunately.
sample ply mesh

Update: I tested your modified filter with the FillHoles example but still cannot see any effect of it :frowning_face:

Output is:

nNei,nextNei,neiId = 1,0,1
nNei,nextNei,neiId = 1,0,2
nNei,nextNei,neiId = 1,0,4
nNei,nextNei,neiId = 1,0,5
nNei,nextNei,neiId = 1,0,7
nNei,nextNei,neiId = 1,0,8
nNei,nextNei,neiId = 1,0,10
nNei,nextNei,neiId = 1,0,11
nNei,nextNei,neiId = 1,0,13
nNei,nextNei,neiId = 1,0,14
nNei,nextNei,neiId = 1,0,16
nNei,nextNei,neiId = 1,0,17
nNei,nextNei,neiId = 1,0,19
nNei,nextNei,neiId = 1,0,20
nNei,nextNei,neiId = 1,0,22
nNei,nextNei,neiId = 1,0,23
nNei,nextNei,neiId = 1,0,25
....
nNei,nextNei,neiId = 1,0,17240

Our “mesh” was not actually a mesh but rather a list of triangles without any shared vertices, fixing this I was able to run both the original implementation and your patch but I fail to understand how to use the visualization in the example and could not spot a difference

3

I’ve downloaded your data set and loaded the mesh into 3D Slicer. I could post an image of what I’m seeing, but I assume you already have a means to visualize the mesh. It looks like triangulated point clouds, which often has small holes on the surface because of the general difficulty of the algorithm knowing exactly how to extend surfaces to maintain normals, or something like that (i.e., triangulation of point clouds is more difficult than one imagines, spatially smoothing the cloud can help). So, I see that you want to fill in those small holes on the surface.

However, I think what makes your particular data set challenging as far as filling holes is that there are two very distinct patches, and they are far apart from one another. If you are following what I’m saying, the vtkFillHolesFilter may be making an attempt to fill the hole that lies between those two patches… which to the human eye doesn’t look like a hole at all. Your data set may be uncovering some other bug in the algorithm. (Also, be aware there is a hole-size-limit parameter setting as part of the vtkFillHolesFilter that may be influencing things, so check that out. For example, you likely don’t want that complete outer edge to be filled in; just the smaller holes on the interior of the surface.)

To investigate that theory, I suggest chopping the PLY data set into two distinct sections using some point-cloud editing software (CloudCompare rings a bell). Then put the new polydata subsets individually through the vtkFillHolesFilter and see if the result is more like you are expecting. I’d be interested in seeing the outcome, as it might uncover something else about this algorithm.