Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 59 (Computer Aided Geometric Design)

Fix an explicit stationary-grid convention. For subdivision arity $m>1$, write the univariate rule asA column of the subdivision matrix is one translated subdivision mask; the next column is translated by $m$ fine-grid rows. Thus the column displacement is the arity. If $a_k$ is active from $k=\alpha$ to $k=\beta$, the subdivision mask width is $w=\beta -\alpha +1$ fine-grid positions, after removing zero padding. Equivalently the mask span is $\beta -\alpha$ fine intervals. This is different from counting old control points in a row stencil: that count measures how many controls influence one newly created point. Stating the convention avoids confusing these two widths.

For a convergent subdivision curve scheme, its support is the influence region of one original control point, equivalently the support of a function of the basic limit $\varphi$ obtained from data $p_j={\delta }_{j0}$. Translation gives the representation $P(t)={\sum }_j{p}_j\varphi (t-j)$. Descendant indices of index zero have parameter positionsThus the limiting support enclosure is $[\alpha /(m-1),\beta /(m-1)]$, as in the support of a stationary subdivision scheme. Endpoint activity gives equality for the ordinary positive convergent masks under discussion.

The functional precision set of a subdivision scheme consists of functions exactly recovered from their uniformly sampled data using the scheme's consistent parameter placement. Polynomial precision records the exactly reproduced polynomial space. Sampling-grid spacing and origin must be specified; the usual arbitrary-grid precision requirement uses every spacing and shift, rather than merely membership in the fixed-grid reconstruction space.

Center the given mask at indices $-1,0,1$. Its binary linear interpolatory subdivision rule isEach new control point is either an old point or an edge midpoint. Hence every refined control polygon is the same curve with extra vertices. Starting from scalar impulse data, the limit is explicitlyThe mask width is three positions, its mask span is two, its largest row stencil uses two old control points, and its subdivision arity is two. Translating the mask indexing to $0,1,2$ translates the basic support to $[0,2]$; the support width remains two original grid intervals.

On $[j,j+1]$, reconstruction is $(j+1-t)p_j+(t-j)p_{j+1}$. Constant and affine samples are therefore recovered exactly. A non-affine polynomial cannot agree with a linear expression on a whole open interval. Thus its polynomial functional precision set of a subdivision scheme isFor continuous functions reproduced at every translated sampling grid, the same conclusion holds: agreement with all chord interpolants forces the affine interpolation identity, hence affinity. At one fixed grid, the larger exactly representable class is the space of linear splines with those spline knots; this is not a higher polynomial precision claim.

For arbitrary data, the one-sided derivatives at $j$ are $p_j-p_{j-1}$ and $p_{j+1}-p_j$. They need not coincide. Therefore the generic limit is $C^0$, not $C^1$. Its first derivative is piecewise constant; exceptional affine data, or individual matching neighboring slopes, can be smoother. This conclusion follows directly from the limit formula, not just from a heuristic mask-width test.

An efficient parametric curve interrogation interface should provide the parameter domain and open/closed status, point evaluation, one-sided endpoint enquiries, first and second derivatives wherever defined, and information about knots or singular parameters. It should also restrict a curve to an interval and subdivide it without changing its limit, return a certified bounding volume for that restriction, and supply derivative or chord error bounds when supported. These enquiries allow cheap geometric rejection before expensive exact evaluation. For a subdivision curve, limit evaluation is distinct from returning a vertex of a finite refined control polygon; the latter is usually an approximation.

For a query point $Q$, minimize $d(t)=\frac{1}{2}\Vert P(t)-Q{\Vert }^2$. At a differentiable interior minimizer,At a regular curve point this says that the query displacement is perpendicular to the tangent vector. If a second derivative exists, the local second-order test isa strictly positive value is sufficient for a strict local minimum. The stationarity equation alone also includes local maxima and is automatic at $P^{\prime }=0$, so it cannot be used as the only global search criterion.

A reliable efficient closest-point search on a subdivision curve uses branch and bound. Cover the compact curve by restricted pieces with certified enclosures $B_I$. For each piece set $L_I=\mathrm{dist}(Q,B_I)$, a lower bound on its true distance. Distances to actually evaluated limit points give upper bounds; keep the best point $P(t_{\ast })$ and distance $U$. For an axis-aligned bounding box ${\prod }_k[l_k,h_k]$, the squared lower bound is inexpensive:For positive partition-of-unity refinement, a convex hull of the active control points is an enclosure. A negative-weight scheme requires a separate certified enclosure; its control hull need not contain the limit.

The algorithm is:

Because ${\min }_I{L}_I\le d_{\min }\le U$, the reported point is at most $ϵ$ farther from $Q$ than a true nearest point. Include endpoints, nondifferentiable joins, and singular parameters in the candidate bookkeeping, or split them into separate pieces. With enclosures converging in diameter under subdivision on a compact continuous curve, the bounds converge to arbitrary prescribed positive distance tolerance. Interval bounds or outward-rounded arithmetic are needed if the guarantee is intended to be certified in floating-point computation. A single Newton root-finding iteration from a single seed supplies no such global guarantee.

A solid body transform is a rigid transformation: it preserves distances within the object. In three-dimensional coordinates it has the form $T(x)=Rx+b$, with translation $b\in {\mathbb{R}}^3$ and an orthogonal matrix $R$. For a proper physical rotation, the coefficient constraints areEquivalently the columns of $R$ are an orthonormal basis with positive orientation. A reflection also preserves distance but has $\det R=-1$ and is excluded when “solid-body motion” means a rotation and translation. There are three rotational and three translational degrees of freedom, not twelve independent matrix coefficients.

Computationally use the homogeneous coordinates representationThe last row is $(0,0,0,1)$; matrix multiplication composes transforms. Alternatively store a unit quaternion together with $b$, maintaining its unit norm. A transpose gives the rotational inverse: $T^{-1}(y)=R^T(y-b)$.

Write the cubic Bézier curve as $P(t)={\sum }_{i=0}^3{B}_i^3(t)p_i$, where $B_i^3(t)=\left(\genfrac{}{}{0ex}{}{3}{i}\right)(1-t{)}^{3-i}{t}^i$. The binomial theorem gives ${\sum }_i{B}_i^3(t)=1$. Transforming the controls producesThis proves pointwise equivariance, including the original parameter values; it is stronger than a statement that the two curves merely have the same shape.

Orthogonality was not used in the calculation. The identical proof applies to every affine map $T(x)=Ax+b$, including scales, shears and even singular affine maps. It applies to every representation $P(u)={\sum }_i{\varphi }_i(u)p_i$ with scalar, control-independent partition of unity basis functions: Bézier curves of every degree, B-splines, surfaces built on a tensor-product surface basis, triangular Bézier patches, and more general linear control-point representations. Positivity is not needed for affine equivariance of a geometric basis. For linear stationary subdivision matrices with row sums one, each refinement step commutes with the affine transformation; taking a convergent limit proves the corresponding assertion for subdivision curves and subdivision surfaces. Rules with geometry-dependent nonlinear weights require separate equivariance tests and are not covered automatically.

The affine class is the largest class that preserves every such Euclidean-control construction with unchanged basis weights, under the usual continuity assumption. In fact the degree-one case would forcefor all $x,y$ and $0\le t\le 1$. This segment identity, followed by continuity, forces $T$ to be affine. Nonlinear transforms such as perspective division generally fail it.

There is a further extension when the representation itself is enlarged: apply a projective transformation linearly to homogeneous controls $(w_i{p}_i,w_i)$, then dehomogenize the weighted sum. The transformed objects are rational Bézier curves or non-uniform rational B-splines, with transformed weights as well as transformed Euclidean controls. This works wherever the new denominator is nonzero. It does not assert projective invariance of ordinary polynomial Bézier curves with their old weights.

Lateral artifacts of a subdivision surface are spurious changes along an intended straight extrusion. For example, if every row of a control net is the same profile translated along a straight direction, a refinement rule should not create periodic ripples along that direction. This is distinct from changing or smoothing the transverse profile itself.

Use triangular-lattice coordinates $(i,j)$ with basis vectors $e_1=(1,0)$ and $e_2=(1/2,\sqrt{3}/2)$. The displayed mask is supported on $|i|,|j|,|i+j|\le 3$, with the central entry at $(0,0)$. Write its coefficients as $a_{i,j}$, including their division by12. For data constant along horizontal rows, $p_{i,j}=q_j$, ternary refinement givesThus the three residue sums in every mask row must agree if arbitrary row-constant data are to remain row-constant. Equal whole-stencil sums alone only reproduce constants and do not guarantee straight-extrusion preservation.

For the original row $j=1$, the numerator coefficients at $i=-3,-2,-1,0,1,2$ are $2,4,5,5,4,2$. Their three residue sums are $7,8,7$, which do not agree. For $j=2$ the sums are $5,5,4$. In particular input $q_j={\delta }_{j0}$ yields heights $7/12,8/12,7/12$ along the refined row $J=1$. The original mask has lateral artifacts, since it introduces a three-phase ripple into a straight extrusion. The residue-sum criterion is also the usual symbol-factor test: the mask polynomial must contain the ternary averaging factor in the extrusion direction. The original does not. This connects the concrete calculation with the directional artifact analysis in Deriving Box-Spline Subdivision Schemes, while the coefficients and correction here are computed directly from the exam PDF.

A symmetric correction with the same denominator and support is to replace the six nearest-center coefficients5 by6, and the six second-ring corner coefficients3 by2. Leave every other coefficient unchanged, including the central6. The added and subtracted weights balance. For a complete computational specification, the corrected numerator rows areEvery entry in this new table is divided by12. The corresponding horizontal residue sums, before division, areConsequently the corrected rule has extrusion invariance of a ternary triangular scheme. Sixfold symmetry gives the same residue-sum property in the other two lattice-edge directions. Every two-dimensional residue class still sums to12 before normalization, so each refinement stencil sums to one. The weights are nonnegative. Symmetry about the stencil's refined parameter location also reproduces affine coordinates: the class first moments vanish, so an initial straight geometric translation direction remains straight.

The associated univariate boundary subdivision mask is the common sum in each transverse row, rather than the central row of the bivariate mask. Centering it at indices $-3,\dots ,3$ givesIts ternary stencils can be written explicitly asEach stencil sums to one and has the correct affine parameter moment. Applying this rule to a boundary profile agrees with the bivariate rule on a straight extrusion. Endpoint or corner rules must still be chosen for a finite open boundary. The artifact-free conclusion established here concerns the three lattice-edge extrusion directions; it does not promise exact extrusion preservation for every arbitrary off-grid direction. The directional limitation is intrinsic to the mask test, not a reason to substitute the central mask row as a boundary rule.

A tensor-product surface basis is formed from two independent univariate basis families ${\varphi }_i(u)$ and ${\psi }_j(v)$ on separate parameter intervals. Given a rectangular control net $p_{ij}$, its parametric surface isThe parameters and indices vary independently over a product domain. The representation can be evaluated first in either parameter, giving a convenient computational advantage. Assume a finite basis, or locally finite spline bases, so differentiation and summation below are justified locally.

For positivity, if each factor basis is nonnegative, then ${\varphi }_i(u){\psi }_j(v)\ge 0$. If both factors are strictly positive at a point, their product is strictly positive there. Nonnegative weights are the usual geometric meaning of positivity; zero boundary weights are allowed. With partition of unity, this gives the local convex hull enclosure of the active control points.

For continuity, suppose the first family is $C^r$ and the second $C^s$, including matching derivatives across their respective spline knots. On every polynomial piece, and by matching at the knot lines,Every factor on the right is continuous in its own variable, so its product is jointly continuous. Thus all these mixed derivatives are continuous, in particular the surface is jointly $C^{\min (r,s)}$. The separate coordinate smoothness can be better: $r$ orders in $u$ and $s$ in $v$. For piecewise polynomials of degrees $d_u,d_v$, an interior knot of multiplicity $k$ in the first factor normally gives $C^{d_u-k}$ matching in $u$, inherited along that knot line; similarly for $v$. The statement is an inherited lower bound. Special control points can cancel derivative jumps, so a particular surface may be smoother than a generic member of its basis.

For summation to unity, independent summation factors exactly:This also explains why translations of all control points translate the surface by the same vector, as in affine equivariance of a geometric basis. These three arguments establish tensor-product inheritance of geometric basis properties directly from the factor identities.

A triangular Bézier patch is a non-tensor-product example. For barycentric parameters $u,v,w\ge 0$ with $u+v+w=1$, a quadratic patch isThe six basis functions have total degree two and sum to $(u+v+w{)}^2=1$. Their index constraint and triangular parameter domain do not arise from two independently indexed univariate factors on a rectangle. An individual triangular polynomial could be embedded in another larger representation, but this triangular basis and control net are not a tensor-product surface definition.

An efficient subdivision surface interrogation interface needs the mesh topology and patch adjacency, boundary and trimming information, patch-local parameter charts and their transition maps, and local restriction/refinement with the complete influencing control net. Numerical enquiries should supply limit positions $S$, first derivatives $S_u,S_v$, and second derivatives where defined; these determine normal vectors and curvatures at regular points. It must also return certified patch bounding volumes and convergent geometric/derivative error bounds. Near an extraordinary subdivision vertex, use the local subdivision matrix and limit/tangent evaluation appropriate to that scheme; second derivatives need not exist merely because a tangent plane does. Finite refined mesh vertices are not exact limit positions.

Represent the cutting plane as $n\cdot x=d$, with $n$ normalized. On each chart setThe desired plane section of a subdivision surface is the image of the zero set $g=0$. For a bounding volume $B$, compute a certified interval $[g_{\min },g_{\max }]$ for the plane functional over $B$. If that interval is strictly positive or strictly negative, reject the patch. With positive partition-of-unity weights, the minimum and maximum of $n\cdot p_i-d$ over all influencing control points already bound its limit patch. For masks without this convex hull property, the interface must provide a different valid enclosure.

An adaptive algorithm that isolates components before tracing is:

This is exhaustive to a chosen tolerance when certified subdivision isolates finitely many regular transverse branches and enclosures converge. If $\Vert \nabla g\Vert \ge \gamma >0$ locally and $\Vert DS\Vert \le M$, a residual tolerance $|g|\le \delta$ corresponds locally to a geometric correction bounded by $M\delta /\gamma$, using the gradient flow toward the level set. Bounds on second derivatives similarly control curve-segment chord error bound. As $\gamma$ approaches zero, a fixed residual tolerance no longer gives a fixed geometric error, so the step and stopping rules must reflect conditioning.

Seeding must not rely just on corner signs. For example $S(u,v)=(u,v,u^2+v^2-r^2)$ cut by $z=0$ has a closed circle wholly inside a patch whose corner values are all positive. Certified range tests plus subdivision retain it; a corner-only marching rule can miss it. Tangencies also change the nature of the output: $S=(u,v,u^2+v^2)$ meets $z=0$ in one isolated point, while a coplanar patch contributes an area rather than a curve. Thus a general plane section is not necessarily a union of regular curves; the algorithm should classify these cases instead of silently fabricating or deleting a branch.

For efficiency, cache subdivision stencils, patch extraction, limit-evaluation coefficients and bounds; reuse child data instead of reconstructing the entire refined mesh. Use local influencing neighborhoods, with the halo dictated by mask support, and keep adjacency/boundary topology separate from changing geometric coordinates. Plane-functional bounds can be computed by refining scalar signed-distance controls, which is cheaper than refining all three coordinates. Combine coarse inexpensive boxes with tighter local convex hull or interval arithmetic tests only where needed. Adapt steps to curvature and transversality, reuse branch seeds, and use regular spline evaluation away from extraordinary points. Stable edge ownership, outward-rounded bounds, scale-aware tolerances, and explicit degeneracy flags are correctness requirements as well as performance issues. The result is a limit-surface intersection computation; merely intersecting a finitely refined control polyhedron with the plane supplies only an uncontrolled approximation.