Module subdivide 

Subdivision surfaces: Loop on triangle meshes, Catmull-Clark on polygon meshes.

Unlike crate::refine, which splits triangles and leaves the surface where it was, a subdivision scheme also moves every vertex by a fixed stencil (a mask) of its neighbours. Repeating it converges to a smooth limit surface: C2 except at extraordinary vertices, where it is C1. Each level is a new HalfedgeMesh; the input is not modified.

Masks

Loop (Loop 1987), triangles only, 1-to-4 split:

• new edge vertex: 3/8 (a + b) + 1/8 (c + d), c, d the corners opposite the edge;
• old vertex of valence n: (1 - n beta) v + beta sum(neighbours) with Loop’s beta = (5/8 - (3/8 + 1/4 cos(2 pi / n))^2) / n.

Catmull-Clark (Catmull and Clark 1978), any polygons, each k-gon split into k quads:

• face vertex: the centroid of the corners;
• new edge vertex: (a + b + f1 + f2) / 4 with the two face vertices;
• old vertex of valence n: (Q + 2 R + (n - 3) v) / n, Q the mean of the adjacent face vertices and R the mean of the incident edges’ midpoints.

Boundaries (both schemes) follow the cubic B-spline curve, so a boundary converges to a curve that depends on boundary vertices only and two meshes sharing a boundary stay joined: a boundary edge gets its midpoint and a boundary vertex 3/4 v + 1/8 (b1 + b2) from its two boundary neighbours. Isolated vertices are carried unchanged.

Numbering

Each level’s vertices are, in order: the input’s live vertices (so a compact input keeps its vertex ids), one per live edge in edge-id order, and for Catmull-Clark one per live face in face-id order. Faces follow the input faces in face-id order. The output is deterministic.

limit_positions evaluates where each vertex converges, from the eigen-analysis of the masks above (Halstead, Kass and DeRose 1993).

Structs

SubdivisionOptions

Options of subdivide.

Enums

SubdivisionError

Why subdivision refused.

SubdivisionScheme

A subdivision scheme.

Functions

limit_positions

The limit position of every vertex under repeated subdivision by scheme, indexed by vertex id (a removed vertex keeps its stored position).

subdivide

Subdivide mesh options.levels times.