Module hole 

Hole filling: triangulate a boundary loop, refine the patch to the density of its surroundings, and fair it.

This is Liepa’s pipeline (Filling Holes in Meshes, SGP 2003), the one behind CGAL’s triangulate_refine_and_fair_hole:

1. Triangulate. Among all triangulations of the boundary polygon that use only its own vertices, dynamic programming picks one whose largest dihedral angle (between neighbouring patch triangles and between the patch and the faces around the hole) is the minimum over all of them, and among those, by a greedy tie-break, a small total area. Liepa’s and CGAL’s O(n^3) recurrence is only a heuristic for that minimum; here each sub-polygon’s state also names the triangle above it, which makes the angle exact at O(n^4) time and O(n^3) memory for n boundary vertices. A triangle with (numerically) collinear corners, and a diagonal joining two boundary vertices that the mesh already joins, are never used: either would break the manifold.
2. Refine. Each boundary vertex gets a scale sigma, the mean length of its edges. A patch triangle is split at its centroid while density * |centroid - corner| exceeds both the centroid’s interpolated scale and the corner’s, for every corner; after each round of splits, interior patch edges are flipped wherever the two opposite angles sum to more than pi (the Delaunay criterion).
3. Fair. The new interior vertices are placed by crate::fair() with the border fixed, so the patch continues the surrounding surface instead of spanning the hole flat.

The patch is wound like the surrounding faces, since every patch face comes from splitting the one face that closes the hole, and it shares the hole’s boundary edges, so a mesh with only this hole becomes closed.

Refusals

A boundary loop whose projection onto its own mean plane (the Newell normal’s) is not a simple polygon is refused: such a loop either crosses itself or folds over, and the minimum-weight triangulation of it would fold too. This is conservative. A strongly curved hole, for example a slot wrapping more than halfway round a cylinder, projects onto itself and is refused although it could be filled. Intersections between the finished patch and the rest of the mesh are not checked; run axiolid-heal’s self_intersections on the result when that matters.

Every refusal leaves the mesh unchanged: the work happens on a copy that replaces the mesh only on success.

Structs

HoleFillOptions

Options of fill_hole.

HoleFillReport

What fill_hole did.

Enums

HoleFillError

Why fill_hole refused. On every refusal the mesh is unchanged.

Functions

fill_hole

Fill the hole bounded by boundary, a boundary halfedge of mesh.