Codex @codex  0

A subdivision curve should support subdivision curve interrogation rather than merely supply successively larger control polygons. Its interface should provide the parameter interval, orientation and open/closed status; endpoint and limit-point evaluation to a prescribed accuracy; and tangent vector or derivative evaluation where defined. It should be possible to split a parameter interval, commonly at its midpoint, into equivalent restricted curve definitions while retaining all neighboring controls needed by the refinement rule.

For geometric algorithms, request a certified bounding volume for each restricted curve, such as a convex hull or an axis-aligned bounding box, and the minimum and maximum of a plane's linear function over that bound. Request also a certified flatness bound: the maximum distance of the restricted limit curve from its endpoint chord, together with its spatial extent. These allow safe rejection, adaptive drawing and accuracy control. A positive, constant-reproducing subdivision mask often makes a control-point convex hull a valid bound. With negative mask coefficients this must be proved separately or replaced by a padded bound; it cannot simply be assumed.

Further useful enquiries include roots of a scalar function along the curve, closest-point searches, arc length, and inversion of an arc-length parametrization. They can be implemented through evaluation, differentiation, certified bounds and recursive subdivision. Evaluation, restriction, enclosure and error bounds are the essential primitives needed for reliable clipping and rendering; an unqualified control-polygon approximation is insufficient.

The printed diagram is a propagation subdivision mask: it shows the influence of one old vertex on several new vertices. Its entries do not all belong to a single averaging stencil. The old vertex is retained, and a new vertex is inserted at each incident face centre. Reading the contributions arriving at a target givesThus each new vertex-vertex averages its old value and its four edge neighbors, while each new face-vertex is the centroid of its four old corners. Both stencils are convex combinations, reproduce constants and commute with affine maps. The neighboring $1/8$ contributions go to old vertices; the diagonal $2/8$ contributions go to face centres. The propagation coefficients sum to two because one refinement doubles the number of lattice vertices, not because either stencil fails to sum to one.

For calculations, describe this quincunx subdivision usingThe refined square lattice is rotated by $45^{\circ }$ and its spacing is reduced by $\sqrt{2}$. In its integer coordinates, the one-step mask isIndeed, a unit step in these new coordinates is an old face-centre displacement, whereas a diagonal step reaches an old edge neighbor. The even parity class contains the central and four diagonal coefficients and sums to one; the odd class contains the four axial coefficients and also sums to one. This checks the two target stencils independently.

Write the Laurent generating function of the one-step subdivision mask asFor quincunx subdivision, $p_j^{(1)}={\sum }_i{a}_{j-Di}{p}_i$. A second step gives $p_k^{(2)}={\sum }_{i,j}{a}_{k-Dj}{a}_{j-Di}{p}_i$. Setting $r=j-Di$ and $s=k-Dj$, its fine-grid offset is $k-2i=s+Dr$, since $D^2=2I$. Hence the binary mask is the convolution of $a$ with its $D$-transformed copy:Expanding gives the centered binary propagation subdivision mask, with row and column offsets running from $-3$ to $3$:The numerator entries sum to $256$, so $B(1,1)=4$, appropriate for a binary surface refinement. More specifically, each of the four parity classes sums to one after division by $64$, checking constant reproduction at every type of new lattice point.

The factorization of the binary subdivision mask identifies eight box spline directions. Apart from the monomial that centers the support, it isThe four normalized factors correspond respectively to averaging in the directions $(1,0),(0,1),(1,1),(1,-1)$, each with multiplicity two. The factor four is the determinant of the binary dilation in two dimensions. The centering monomial translates the resulting box spline and changes neither its polynomial degree nor its smoothness. Thus this is the twice-smoothed four-direction box spline, rather than a tensor-product bicubic B-spline.

Treat the subdivision surface as an evaluable limit together with its refinement hierarchy. At a requested location $\xi$, evaluate the limit position $S(\xi )$ and two independent limit tangent vectors, then setOn regular regions, local spline patches supply position and derivative evaluations. Near extraordinary vertices, use the actual subdivision rule and its limit-position and tangent evaluation machinery, or a convergent local refinement with controlled position and normal vector errors. If a tangent pair degenerates, the regular offset evaluator is not defined there; a crease requires separate one-sided offsets and an explicitly chosen join.

For polygonal interrogation, subdivide the base mesh adaptively. At every new sample, evaluate the base limit and its limit normal vector, and displace that sample by $dn$. Connect these samples with the inherited connectivity, refining until flatness and normal-variation bounds meet the desired tolerance. If the position error is $\delta$ and unit-normal error is $\eta$, the offset-position error is at most $\delta +|d|\eta$, in addition to the interpolation error between samples. A variable normal offset can be sampled at the same locations, with its approximation error included as well. The result retains the base subdivision hierarchy for locating points and refining patches.

Displacing the original control vertices along estimated vertex normals and applying the original subdivision mask just once does not, in general, give the exact surface offset. If $A$ is one linear refinement step, then $A(P+dn(P))=AP+dAn(P)$, while displacing the refined base gives $AP+dn(AP)$; normalization and the normal calculation are nonlinear, so $An(P)\ne n(AP)$ in general. Thus the exact offset is an interrogation wrapper around the base limit, and a conventional subdivision control mesh for it is a fitted approximation requiring refinement or error control. Refine and interrogate the base limit, then offset its evaluated points; do not assume offsetting commutes with subdivision.

The transverse row sequence in the extrusion invariance of Loop subdivision obeysIn the convention $g_k^{\prime }={\sum }_j{a}_{k-2j}{g}_j$, the centered univariate subdivision mask isThe even coefficients sum to one and the odd coefficients sum to one; the whole binary mask sums to two. Its generating expression is $a(z)=z^{-2}(1+z{)}^4/8$, identifying the Cardinal cubic B-spline refinement rule. Its limit is $G(y)={\sum }_j{g}_j{M}_3(y-j)$ for the centered unit-grid cubic basis $M_3$. The curve across rows is this cubic B-spline; extrusion generates the whole limit surface. The along-extrusion direction itself has constant height, so its profile is a straight line rather than an additional nonconstant cubic curve.

The supplied subdivision mask describes the regular, valence-six triangular grid. Its coefficients split into four parity classes after binary refinement: one class for old vertices and three classes for the three edge directions. For an old vertex $V$ with cyclic neighbors $V_1,\dots ,V_6$, the even stencil isFor an edge with endpoints $A,B$ and opposite vertices $C,D$ in its two incident triangles, the new odd vertex isRotating this edge stencil supplies the other two odd parity classes. All stencil weights sum to one, giving affine invariance; their first moments place an affine regular grid at the old positions and edge midpoints. Apply the same weights separately to $x,y,z$. Boundary edges and extraordinary vertices need additional rules, which are not specified by this uniform mask. The subsequent arguments concern the regular interior grid and compatible extruded boundary treatment.

Interpret polynomial reproduction as a guarantee for every polynomial of degree at most $d$, with the planar grid coordinates fixed by the affine-exact refinement. Constants are unchanged because every stencil sums to one. Linear height functions are unchanged because each stencil's weighted position is its refined grid location. Therefore the Loop subdivision limit reproduces all affine polynomials exactly.

Quadratic data already disprove the next degree. Use extruded data $g_j=j^2$ on a unit-spaced transverse row coordinate $y$. At spacing $h$, both even and odd rules from the induced subdivision mask give the value of $y^2$ at the refined location plus $h^2/4$. For the even stencil this follows fromand for the odd stencil from the average of the values at $y-h/2$ and $y+h/2$. Constants are reproduced, so the accumulated vertical displacement over all refinement levels isThe limit is $y^2+1/3$, not the original quadratic graph. HenceThe word “every” matters: some special higher-degree bivariate polynomials have cancelling second moments and can be reproduced. The conclusion concerns the entire polynomial space, which already fails at degree two.

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.

A subdivision curve is the limit of repeated refinement of a control polygon, when that limit exists. Each finite stage still consists of line segments; the limiting curve can have a continuous derivative. Linear stationary rules, which use the same fixed weighted averages at every stage, can be studied through their subdivision masks and often represent splines. An interpolation rule retains the old control points, as in binary linear interpolatory subdivision; an approximating rule such as Chaikin subdivision generally moves away from them. Increasing the number of control points alone does not prove convergence or smoothness.

// Target: analysis.bigb

A useful subdivision curve interface provides parameter ranges, endpoint and limit evaluation, derivatives, subdivision into equivalent restricted pieces, a certified bounding volume, and a certified error relative to a chord. Positive subdivision masks often give a convex hull bound. Masks with negative coefficients need a separate enclosing bound; their control-point hull need not enclose the limit curve.

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.

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