Module fill 

Filling a rim of an editable mesh with a patch of new faces.

The rim, as loops

A rim is named by its RimId, its lowest-numbered half-edge. A rim that passes through one point more than once, as where two holes touch at a corner, is parted there into loops that each pass through every point once, and each loop is filled on its own. The patches meet at the point the rim passed more than once and close the fans about it into one, so the point becomes a single vertex again.

A loop of two edges, and a rim edge that more faces than the rim’s own use, cannot be filled into a manifold, and are refused.

The triangulation

A loop of up to OPTIMAL_UP_TO edges is triangulated on its own vertices, by exact dynamic programming over every triangulation. The programme minimises first the largest bend and then the area. A bend is the angle between the normals of the two faces that meet across an edge, and the largest is taken over every edge of the patch, including the rim’s edges with the faces already on them. A face with collinear corners has no normal, so the triangulation never makes one, and the bend across a rim edge whose face has none counts as zero.

A bend β is compared as 4 sin²(β/2), read from the sum of the unit directions from the edge to the two far corners. That grows with the bend, needs no angle, and keeps its precision for small bends.

A bend depends on the faces on both sides of an edge, so the programme’s state is a triangle on an edge, not the edge alone. A first pass finds the least largest bend, θ. A second pass finds the least area among the triangulations that bend nowhere more than θ. Both are exact over all triangulations of the loop: θ to the bit, as computed, and the area to the rounding of its sum. Ties go to the lowest-numbered apex. Memory grows as n³/6 numbers for a loop of n edges, about 170 MB at the bound. Time grows as n³ while the cheapest apexes on each edge fit the faces beyond it, as on smooth holes, and as n⁴ at worst.

The triangulation draws no edge between two points the mesh already joins. Such an edge would have four faces.

A longer loop is flattened onto the plane across which it encloses the most area, normal to its vector area, and ear-clipped there by exact orientation tests. A loop whose shadow on that plane crosses or touches itself is refused.

Refinement

With Fill::refine, the patch is refined to the spacing of the mesh about it, by Liepa’s scheme. Each rim vertex takes the mean length of the mesh’s edges at it as its spacing σ, and each new vertex the mean of its triangle’s corners’. A triangle is split at its centroid c, into three, when c stands farther than σ/√2 from each corner m (for σ both c’s and m’s own). That is Liepa’s density factor: it leaves edges about as long as the rim’s. The centroid must also stand that far from every vertex of the patch, so that no two vertices crowd each other. New vertices lie within the rim’s convex hull, at least the smallest rim spacing over √2 apart, so the splitting ends.

After each round of splits, each edge inside the patch is flipped while that raises the smallest angle of its two faces. A flip is not made if it would turn a face over against the other, or draw an edge the patch or the mesh already has. Each flip raises the patch’s sorted angles lexicographically, so the flipping ends too.

Fairing

Only the vertices the refinement made move. Without refinement the patch is the triangulation itself.

The Laplacian is the cotangent one, weighted by the patch as refined and, at the rim, by the mesh’s faces about it. Weights read from the geometry, rather than one per neighbour, let the result converge as the mesh is refined, however unevenly the mesh about the hole is spaced.

• Fairing::Flat spans the rim tightly: a membrane, with the Laplacian vanishing at each new vertex and the rim held fixed. It is exact for linear functions, so a hole in a plane stays in the plane.
• Fairing::Curved carries the surface’s curvature across the hole. It minimises the sum, over the patch’s vertices and the rim’s, of the squared Laplacian times each vertex’s area (a third of its faces’). The Laplacian at a rim vertex reaches one ring into the surrounding mesh, which is held fixed. This is the discrete thin-plate energy, and its stationary condition is a bi-Laplacian vanishing over the patch.

The three coordinates are solved as one system, by conjugate gradients on the normal equations. The fill therefore does not depend on the axes: a hole in a plane is filled in that plane, to rounding. The solve takes about as many steps as there are new vertices, so its time grows as their square.

Structs

Fill

How a rim is filled.

FillReport

What a fill made.

Enums

Fairing

How the new vertices of a refined patch are placed.

Constants

OPTIMAL_UP_TO

The longest loop triangulated optimally, by exact dynamic programming; a longer one is ear-clipped on its plane.