Very slow hole filling

[cdcseacave]

Attempting to fill holes on a large mesh is extremely slow. At a fist look the reason seems to be the garbage collector run 10 times for each hole, garbage collector that is very slow, especially for large meshes:

• is garbage collector really needed during hole filling or can it be avoided?
• can the garbage collector be optimized?

I can provide an ex mesh, but any large mesh will do it. For ex a mesh with 8M faces and 81 small holes (<30 edges) takes 16min on a very fast CPU.
Windows 10 x64, Visual Studio 2019

[dsieger]

Hi,

There is some room for optimization in the garbage collector. Marking this as enhancement.

Thanks for your feedback,
Daniel

[thovide]

Hello,

I don't think the problem is in the garbage collector in all cases.

The hole triangulation code is in around o(n3), n being the number of half edges of the loop to fill. The weight computation costs a lot when holes are composed of lot of edges... Wouldn't it be more efficient to use one unique face, triangulate it and then use isometric remeshing algorithm and fully skip refinement step?

[cdcseacave]

I can tell you that I tried one experiment that suggests the hole filling code itself is fast (that is why I thought the garbage collection is the slow part):

• identify all mesh holes
• for each hole
  • extract the hole plus few triangles rings around it in a new mesh
  • fill the hole in the cropped mesh
  • port the hole filling into the full mesh

this works for any mesh size very fast

[thovide]

I think it highly depends on the kind of mesh and the kind of hole to fill. You're right if there are few edges.
I made some measures with a beetle model (~30000 vertices, ~59000 faces).
I fill all the holes (11). Number of edges for each hole 616 17 31 102 132 91 102 31 17 99 90
The overall process takes about 2 minutes 30s
triangulate_hole : 82s (compute_weight 78s). The o(n3) loop causes this and the biggest hole is probably the main contributor
refine : 65s (39s for collapse_short_edge)

In the overall process, garbage_collection takes 10s.

I've investigated a bit more my proposal and it doesn't solve anything! the compute_weight method is actually extracted from the MeshTriangulation algorithm. So just triangulating the face composed of all edges will make the problem happen

[cdcseacave]

if so, that means compute_weight takes a long time when there are many rings of triangles available around the hole; the number of edges the hole has does not seem to matter much in the work around I proposed

[thovide]

Well, I'm not sure. What I understand from the algorithm is that it's related to generic 3D polygon triangulation, which is kind of a tricky topic. The different papers I had a look on mention o(n3) to o(n4) for such a task (n being the number of edges of the polygon) depending on expected quality. I found an interesting one on possible optimizations (https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=2212&context=etd) using restricted weight search in order to highly improve performances

So in my opinion, what's around the polygon doesn't matter here (it matters probably for garbage collector which depends on the overall mesh size).