CODEWITHSUNDEEP
3dpolygonmesh
Tom
Tom

Reputation: 1057

Library for filling holes in 3D mesh

I'm looking for some library or an algorithm that will fill holes in 3D mesh. I need it only for filling flat meshes, but in 3D space. Something like that provides Blender. For example on the first image below I have a plane with hole.

enter image description here

Now I'm selecting vertices and ALT+F will do the work like on this second image:

enter image description here

I know that CGAL can do something like that, but I don't need whole library for simple task like that. Is there any small librares or some open source algorithms?

Upvotes: 2

Views: 1663

Answers (1)

Fedor
Fedor

Reputation: 21317

Typically by hole filling in 3D triangular meshes, one understands the problem of closing disc-like hole with triangles, where the hole is surrounded by a loop of edges having no triangle from one side.

But according to your picture, the task is to create triangles filling the space in between two existing pieces of mesh.

The algorithm for performing that can be as follows:

  1. Find the shortest distance between the boundaries of two mesh pieces.
  2. Create an edge in that place connecting two boundaries.
  3. After that the two boundary loops are merged in one combined loop, and a standard hole filling algorithm can be applied to it. However it may be not the best performing solution.

Another option is to write a specialized algorithm for stitching two holes, for example:

  1. Start again with a shortest edge between two boundary loops.
  2. Then consider all possible triangulations, where each triangle has 1-2 vertices on the first original loop and the other 1-2 vertices on the second original loop.
  3. Select the best triangulation according to some metric, which penalizes degenerate triangles and sharp angles in between of them. To keep the amount of computations under control, dynamic programming approaches are typically used.

As to a library where such algorithms are implemented, one can look at open-source MeshLib, where such function is named buildCylinderBetweenTwoHoles.

Here is some demonstration: enter image description here

  • Blue - original mesh with two boundary loops to be connected with triangles
  • Red on green - the result of triangulation, closing the space in between two loops
  • Red on white - subdivision of triangles to reach some desired size.

Upvotes: 0

Related Questions