Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 77 / 5

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.

Choose one grid-edge vector $a$ as the extrusion direction and an independent edge vector $b$. Label grid points $r_{i,j}=ia+jb$, so extruded height data have $z_{i,j}=g_j$, independent of $i$. The Loop subdivision stencils are affine-exact in the $x,y$ coordinates, so the refined horizontal grid has spacing one-half and the same row structure.

At an old vertex, two neighbors lie in its own row, two in the row above and two in the row below. Its refined height is thereforeA new vertex on an edge parallel to $a$ has both endpoints in row $j$ and its opposite vertices in rows $j-1,j+1$, giving exactly the same value $g_{2j}^{\prime }$. A new vertex on either of the other edge directions has endpoints in rows $j,j+1$; its two opposite vertices are also one in each of these rows. Its height isEvery refined vertex in a given row consequently has the same height. Induction proves this at every refinement level. The piecewise planar interpolating mesh is also constant along $a$ between rows, since adjacent rows have constant heights and form parallel straight lines. Taking its convergent limit preserves this invariance. Thuswhere the points lie in the domain. The limit subdivision surface is an extrusion of the univariate limit curve. This is a statement about functional data on the regular grid, not about an arbitrary spatial mesh with extraordinary vertices or independently imposed boundary stencils.

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.

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.

Let the three grid-edge vectors be $v_1=a$, $v_2=b$, $v_3=b-a$, and define the constant-coefficient differential operator $D={\sum }_{r=1}^3(v_r\cdot \nabla {)}^2$. For a stencil at grid spacing $h$, its displacement vectors $\delta$ about the new vertex have vanishing first and third moments by central symmetry. All four stencil types have the same second momentFor the old-vertex stencil, each pair $\pm h{v}_r$ contributes $h^2{v}_r{v}_r^T/8$. For an edge parallel to $a$, the endpoint displacements are $\pm ha/2$ with weights $3/8$, and the opposite displacements are $\pm h(b-a/2)$ with weights $1/8$. Their moment is $h^2[a{a}^T/4+b{b}^T/4-(a{b}^T+b{a}^T)/8]$, precisely the same expression; the other edge orientations follow by symmetry.

If $f$ is a multivariate polynomial of total degree at most three, its Taylor expansion is exact through the third-order term. Thus every refined vertex samples the single polynomialThe polynomial $Df$ has degree at most one, so subsequent refinement reproduces it exactly. Starting at unit spacing and successively halving $h$, the limit therefore isThe correction lowers degree by two, leaving the leading homogeneous term unchanged. Hence every sampled polynomial of degree at most three generates a polynomial of that same degree, even though quadratics and cubics need not be reproduced identically. For the extruded cases this gives $y^2\mapsto y^2+1/3$ and $y^3\mapsto y^3+y$.

Degree four is not guaranteed. Extruded data $g_j=j^4$ reduce to the Cardinal cubic B-spline $G(y)={\sum }_j{j}^4{M}_3(y-j)$, which is piecewise cubic and hence cannot be a single polynomial of degree four. It is not a lower-degree polynomial either: at integer rows, $G(k)=[(k-1{)}^4+4k^4+(k+1{)}^4]/6=k^4+2k^2+1/3$, which cannot agree with a cubic at all integers. This counterexample excludes every guaranteed degree $d\ge 4$. ConsequentlyThis distinguishes polynomial generation from exact reproduction and again refers to all polynomials through the stated degree.