Subdivision surface

A subdivision surface is the limit of repeated mesh refinement and vertex averaging. Exact interrogation evaluates this limit and, where defined, its tangent vectors and normal vectors; a finite refined control mesh is generally only an approximation to the limit.

// Target: analysis.bigb

Lateral artifacts of a subdivision surface are unwanted variations along an intended straight extrusion: input cross-sections identical along a lattice direction acquire ripples in that direction under refinement. For a stationary arity-$m$ lattice rule $a_{i,j}$, extrusion along the first lattice coordinate is preserved exactly when ${\sum }_{i\equiv r(\mathrm{mod}m)}{a}_{i,j}$ is independent of the residue $r$ for every transverse offset $j$. Then summing along each row gives a single associated univariate subdivision mask. This direction-specific criterion does not promise invariance under every possible oblique extrusion.

If a triangular-lattice subdivision mask has the displayed residue-sum equality, refining data $p_{i,j}=q_j$ gives $p_{I,J}^{\prime }={\sum }_k{b}_{J-3k}{q}_k$, independent of $I$. If affine coordinates reproduce their parameter positions, a geometrically straight extrusion is preserved. Rotationally symmetric masks give the corresponding property in all three lattice-edge directions. A boundary curve compatible with this extrusion uses the collapsed mask $b$, not just the central row of the two-dimensional mask.

Mid-edge subdivision replaces each mesh edge by its midpoint, joins successive midpoints around every old face, and joins successive midpoints around every old vertex. For an interior manifold mesh, each new vertex has valence four. Each geometric update is a convex combination, so every refined control point remains in the convex hull of the original control mesh. The regular limit is associated with the quadratic four-direction box spline.

The descendant of a face with cyclic vertices $p_0,\dots ,p_{n-1}$ has vertices $p_i^{\prime }=(p_i+p_{i+1})/2$. Their arithmetic mean is unchanged. On the cyclic Fourier basis, a mode of frequency $j$ is multiplied by $(1+e^{2\pi ij/n})/2$. Every nonconstant mode has modulus less than one, so the descendant face shrinks to the original vertex centroid. This puts that centroid on the subdivision limit, without requiring the original face to be planar.

Interrogation of a subdivision limit needs patch/topology navigation, refinement, limit evaluation and derivatives where they exist, with certified bounds and geometric error estimates. On regular patches one may use the corresponding spline representation. At extraordinary subdivision vertices, local subdivision matrices determine limit positions and tangents under the scheme's smoothness conditions. A normal vector may exist even when second derivatives and Gaussian curvature do not; finite refined polygons are approximations rather than exact limit queries.

A robust intersection search applies branch and bound to pairs of subdivision surface patches. Certified bounding volumes reject disjoint pairs, and refinement reduces unresolved pairs. Limit evaluation, tangent data and controlled approximation bounds produce and correct local intersection arcs, then patch adjacency joins them. Bounds must enclose the limit, not merely the current mesh. Flat polygon intersections are approximations and can miss tiny components or tangencies unless the associated geometric and transversality conditions are verified.

A plane section of a subdivision surface is a zero set of the plane functional evaluated on the limit parametric surface. Certified patch bounding volumes reject sign-definite patches. On a regular transverse section, $\nabla g\ne 0$ and the parameter tangent is $(-g_v,g_u)$; predictor-corrector continuation method traces a branch after every component has been isolated. Closed loops, tangencies, coplanar patches and extraordinary-vertex neighborhoods require more than corner-sign tests. Degenerate sections can contain isolated points or two-dimensional portions rather than only regular curves.

For disjoint compact bodies, the minimum occurs on their boundaries. Patch bounding volumes give certified lower bounds and evaluated limit-point pairs give upper bounds. A branch and bound search refines promising patch pairs until the global bounds differ by the tolerance. Boundary distance alone cannot detect containment; touching, crossing or nested solid bodies have ordinary set distance zero. Negative overlap values require an additional convention such as translational penetration depth.

An extraordinary subdivision vertex has a valence different from that of the regular refinement lattice. Regular box spline calculations do not alone establish smoothness at this vertex. The finite local subdivision matrix, its eigenvalues, and the associated characteristic map of a subdivision surface determine convergence and tangent behavior.

The characteristic map of a subdivision surface is the planar limit map obtained from the two independent tangent eigenvectors of its local subdivision matrix. In the usual stationary setting, a simple constant eigenvalue one, a semisimple double subdominant eigenvalue $0<\lambda <1$, strictly smaller other eigenvalues, and a regular injective characteristic map establish the standard $C^1$ tangent-plane behavior for nondegenerate data. The eigenvalue inequalities alone do not exclude a folded or singular characteristic map. For an alternating scheme these tests must use a full period of refinement.

A regular quincunx subdivision step replaces a square lattice by the union of its old vertices and face centres. In lattice indices one may useThus two steps give ordinary binary refinement. If $A(z,w)$ is the one-step subdivision mask symbol, the two-step symbol is $A(z,w)A(zw,z/w)$. The two lattice parity classes separately determine the old-vertex and face-vertex stencils; their coefficient sums must each be one to reproduce constants.

On a regular triangular grid, Loop subdivision retains an old vertex with weight $10/16$ and adds its six neighbors with weight $1/16$ each. A new edge vertex has weights $3/8$ on the endpoints and $1/8$ on the two opposite vertices. Extraordinary vertices require valence-dependent rules.

// Target: analysis.bigb

For the three unit-grid edge vectors $v_1,v_2,v_3$ and a multivariate polynomial $f$ of total degree at most three, sampled regular-grid Loop subdivision generates the graph of $f+\frac{1}{12}{\sum }_{r=1}^3(v_r\cdot \nabla {)}^{2}f$. Thus affine polynomials are reproduced exactly and all polynomials through degree three retain their degree. Fourth-degree data constant along one edge direction reduce to a Cardinal cubic B-spline, whose limit need not be a polynomial.

On an infinite regular triangular grid, height data constant along one edge direction remain constant along that direction under Loop subdivision. Across rows the induced rule is $g_{2j}^{\prime }=(g_{j-1}+6g_j+g_{j+1})/8$, $g_{2j+1}^{\prime }=(g_j+g_{j+1})/2$, the centered Cardinal cubic B-spline rule.

// Target: analysis.bigb

A stationary binary subdivision mask $a$ specifies a refinement operator $q_j={\sum }_i{a}_{j-2i}{p}_i$. Indices may be vectors for a surface. Coefficients restricted to a parity class give the stencil for one type of refined vertex.

// Target: analysis.bigb

For a stationary univariate refinement $S_{ij}=a_{i-mj}$, the subdivision mask width counts fine-grid positions from the first to the last active entry in a column, including any internal zeros. Consecutive columns are translates by $m$ rows, the subdivision arity. The number of old control points used by a particular new point is instead the size of its row stencil; it need not equal the mask width. A span convention counts $w-1$ fine intervals, so numerical width claims should specify the convention.

The subdivision arity is the integer factor $a>1$ by which a stationary refinement shrinks parameter-grid intervals: control index $i$ has coordinate $i/a^{\ell }$ after $\ell$ levels. It is distinct from the mask width and from the number of neighbors in a stencil.

For backward differences $\Delta P_i=P_i-P_{i-1}$, a scalar stationary arity-$a$ subdivision mask has symbol $M(z)={\sum }_i{M}_i{z}^i$. The identity $(1-z)M(z)=B(z)(1-z^a)$ gives the displayed intertwining whenever the quotient is a finite Laurent polynomial. Iterating supplies higher-difference masks. The coefficients $a^{r\ell }{\Delta }^r{P}_i^{\ell }$ are candidate $r$th-derivative controls. A convergent derivative scheme, proved by contraction of its first differences, establishes corresponding smoothness of the original limit under the standard consistent parameterization.

Finite local subdivision matrices for the scaled difference scheme track derivative variations in nested parameter intervals. A product-norm bound below one proves uniform contraction for every interval and therefore gives a lower bound on derivative continuity. A product eigenvalue of modulus at least one is an obstruction when its mode is reachable from the data and visible in the limit: generic data excite it, so the corresponding derivative differences fail to vanish. Harmless polynomial or unobservable modes must be removed before applying such an upper bound. Borderline smoothness needs direct analysis, not rounding a numerical exponent. Stability and convergence of the underlying scheme must be checked rather than inferred from mask width.

A local subdivision matrix maps the control points in a refinement-invariant neighborhood to the refined neighborhood. Row sums one express constant reproduction. Its constant eigenvector has eigenvalue one; remaining eigenvalues govern decay of shape modes. Near an extraordinary subdivision vertex, tangent modes and a characteristic map of a subdivision surface are needed to test geometric smoothness, beyond simple convergence.