Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 66 (Computer-aided Geometric Design)

Use closest points on two line segments as a small constrained convex optimization problem. Write the two line segments asand put $w=P_1-P_2$. Minimize the squared Euclidean distance $D(s,t)=\Vert w+sd-te{\Vert }^2$; minimizing its square also minimizes the distance. Compute the dot productsFor nonzero, nonparallel directions, an interior minimum must satisfy the two derivative equationsTheir determinant is $\Delta =\alpha \gamma -{\beta }^2>0$, so the stationary candidate isRetain this candidate only when both parameters lie in the unit interval.

The other possibilities are on the boundary. Define $\mathrm{clip}(x)=\max (0,\min (1,x))$. Minimizing the same quadratic on each of the four edges gives these candidates by orthogonal projection onto a line segment:Evaluate $D$ at every retained candidate and choose the smallest. The resulting $R_1(s),R_2(t)$ are the required closest points. The quadratic is convex because it is the squared norm of an affine map. A minimum in the interior is stationary, and a minimum on the boundary minimizes one of these edge restrictions, so the list is exhaustive. Ties correspond to multiple equally valid answers.

Handle degenerate line segments before dividing: if $\alpha =0$ and $\gamma >0$, set $s=0$ and $t=\mathrm{clip}(\epsilon /\gamma )$; if $\gamma =0$ and $\alpha >0$, set $t=0$ and $s=\mathrm{clip}(-\delta /\alpha )$; if both vanish, use the two endpoints. For exactly parallel directions, $\Delta =0$. The distance depends on a single linear combination of $s,t$; any interior minimizing level line reaches the boundary, so the four edge candidates still include a minimum.

For nearly parallel directions, compare $\Delta$ with the scale $\alpha \gamma$, and solve the interior least-squares problem using QR decomposition or singular value decomposition if necessary. A small determinant should trigger a stable solve, not arbitrary rejection of a possibly valid interior solution. In particular, do not merely clip both coordinates of the infinite-line solution: the dot product $\beta$ couples the two parameters, and changing one changes the optimum for the other.

Work first in the parameter rectangle of the parametric surface. Set $g(u,v)=f(F(u,v))$. With $F_u,F_v$ linearly independent, the chain rule givesThe intersection is transversal precisely when the implicit normal vector $\nabla f(F)$ and the parametric normal vector $F_u\times F_v$ are not parallel. Consequently $(g_u,g_v)\ne (0,0)$, and the implicit function theorem makes $g=0$ a locally regular parameter curve. This is the setting for transversal surface intersection tracing by a predictor-corrector continuation method.

Find one seed on the required component. Subdivide parameter patches, enclosing their images by bounding volumes and testing whether a certified range of $f$ excludes zero. For a positive-weight NURBS, the active control-point convex hull supplies a convenient enclosure; interval arithmetic can tighten the range of the composed function. Search the surviving patches for a bracketed root or a local corrected seed. Merely checking signs at four corners is inadequate: a small closed intersection can lie wholly inside a patch with the same corner signs. An adaptive or certified patch search, or a supplied seed, avoids this failure. For a sphere centered at $C$, use $f(P)=\Vert P-C{\Vert }^2-r^2$ and $\nabla f=2(P-C)$; for a torus, use its implicit polynomial and its differentiated polynomial in the same algorithm.

At a corrected seed ${\eta }_k=(u_k,v_k)$, an unnormalized parameter tangent vector and a unit spatial tangent vector areChoose the sign consistently with the previous tangent vector. Normalize $q=q_0/\Vert DF{q}_0\Vert$ and predict ${\eta }_p={\eta }_k+hq$, so $h$ is approximately a physical arc length step. Correct the predictor by Newton method applied toThe Jacobian has rows $(g_u,g_v)$ and $(T_k\cdot F_u,T_k\cdot F_v)$. At the starting point its first row vanishes along $q$, whereas its second row applied to $q$ is one. The two rows are therefore independent. The transverse-plane condition prevents the corrector from sliding arbitrarily along the intersection. Restrict correction to a neighborhood of the predictor, use damping, and reduce $h$ when correction fails or its displacement becomes excessive; this prevents jumps to another nearby branch.

To obtain a sufficiently dense sequence, impose a physical point-spacing bound, a bound on tangent turning, and a chord-error estimate. For local curvature $\kappa$, the small-step sagitta is approximately $\kappa h^2/8$; estimate curvature from successive tangent vectors and reduce $h$ until this and the desired spacing are acceptable. The correction residual should be small relative to the drawing tolerance. Uniform steps in $u$ or $v$ alone do not ensure spatial density because the surface metric can vary considerably.

For an open component, trace in both tangent directions from the seed. On reaching a parameter boundary, locate the endpoint by solving $g=0$ together with that boundary's parameter equation, rather than accepting an overshoot. For a closed component, stop only after nontrivial travel and return to the initial parameter location with compatible tangent orientation; near-coincidence in three-dimensional space alone can mistake a self-intersection or neighboring branch for closure. Cross periodic seams using the appropriate chart identification. Adaptive physical stepping, local correction, and component-aware termination give the required point sequence. A vanishing parameter gradient signals a tangency or singularity outside the transversal hypothesis and must be reported rather than passed through by this regular algorithm.

Use the prescribed-speed time parametrization of a curve. On a regular part traversed in increasing $u$, let $q(u)=\Vert F^{\prime }(u)\Vert >0$ and assume the prescribed speed $v(F(u))$ is positive. The chain rule for velocity givesIntegrate this scalar ordinary differential equation with an adaptive Runge-Kutta method, arranging output at the exact times $t_k=t_0+k\Delta t$. Evaluate $P_k=F(u(t_k))$. Internal integration steps may be shorter than $\Delta t$; output interpolation must meet the same error tolerance, so variable numerical steps do not create variable frame times.

An equivalent implementation precomputesby adaptive numerical integration. This function is strictly increasing. Bracket each $t_k$ in the table and invert using safeguarded Newton method or interval bisection; monotonicity makes each solution unique. Stop at $u=1$, with a shorter final time interval if the total travel time is not a multiple of $\Delta t$. This accounts for changes in both the curve's parameter speed and the physical speed, unlike equal increments in $u$.

If the specified speed vanishes, examine the reciprocal-speed integral at that event. It may diverge, giving asymptotic approach, or be integrable, giving arrival in finite time. A scalar speed does not determine whether motion reverses or how it resumes after stopping; such behavior needs the physical dynamics or a chosen continuation. The positive-speed formula applies between these events, with the direction changed if the traversal reverses.

Use the equal-time points to estimate velocity and acceleration with centered finite differences:At the endpoints use one-sided formulas of the desired order. A differentiated path and its time parametrization can instead supply these quantities. Let $g_k$ denote the gravitational acceleration, directed downwards. In the accelerating camera, the effective downward vector is $g_k-a_k$, so the locally felt upward vector is $U_k=a_k-g_k$. For a stationary camera this gives $-g_k$, fixing the sign.

The apparent-gravity camera frame is obtained by orthogonal projection and a cross product:When $W_k\ne 0$, $X_k,Z_k$ are perpendicular unit vectors, and $Y_k$ completes a right-handed orthonormal basis: $X_k\times Y_k=Z_k$. Also $U_k=(U_k\cdot X_k)X_k+\Vert W_k\Vert Z_k$, so the felt-up vector lies in the $XZ$ plane, with its transverse component pointing towards positive $Z$.

The stated exclusion of $a_k=g_k$ ensures $U_k\ne 0$, but it does not ensure $W_k\ne 0$. If felt-up is parallel to travel, the roll angle is undetermined rather than the construction being impossible. Every transverse orthonormal basis then has the required plane property. For continuity, project the previous $Z$ into $X_k^{\perp }$ and normalize it, using $Y_k=Z_k\times X_k$. If this projection is also too small, choose a coordinate unit vector least aligned with $X_k$ and project that vector instead. Switch to this transported choice near the parallel case to avoid numerical amplification. A stopped vehicle likewise needs a chosen limiting travel tangent vector, since its zero velocity itself has no direction. None of this requires a Frenet frame, which can fail where curvature vanishes.

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.

Orient the plane relative to the eye. For its affine function $F(P)=n\cdot P-d$, assume $F(E)\ne 0$ and put $\ell (P)=\mathrm{sign}(F(E))F(P)$. The desired closed half-space is $\ell \ge 0$. If the eye is on the plane, the notion of its side is undefined and a side convention must be supplied.

Apply recursive half-space clipping of a subdivision curve to each initial curve piece. Obtain a certified bounding volume $K$, and calculate $l={\min }_K\ell$, $h={\max }_K\ell$. For a control-point convex hull, these extrema occur at its vertices, so this test is inexpensive. If $h<0$, discard the piece. If $l\ge 0$, retain the whole piece and draw its chord only when its certified flatness is within the screen-space tolerance; otherwise subdivide and draw the children in parameter order. If $l<0\le h$, subdivide and repeat the classification.

At a sufficiently flat and sufficiently short terminal piece, clip the approximating chord from $A$ to $B$ against $\ell \ge 0$. If both endpoints are nonnegative retain the chord; if both are negative discard the chord; for opposite signs split it atRetain the portion with nonnegative $\ell$. Handle an endpoint exactly on the plane without dividing by zero, and retain a coplanar chord under the closed-half-space convention. The recursion yields an ordered polyline rather than connecting endpoints of disconnected retained pieces.

Crucially, do not reject an unresolved whole curve merely because its endpoints have negative signs: it can cross the plane twice and have a visible interior excursion. The preceding terminal chord rule is a rendering approximation at an explicitly chosen spatial tolerance. A flatness bound and a diameter bound make any missed leaf-sized excursion spatially small; they do not prove exact crossing topology, especially for a near-tangent contact or an unfavorable projection. Use the actual viewing projection to enforce a screen-space tolerance, with special handling near a perspective singularity.

If exact clipping intervals are required for a spline representation, isolate all roots of $\ell (C(t))$, split at them and classify each intervening interval. Bernstein basis coefficient bounds, derivative bounds and recursive subdivision can isolate roots on polynomial spans, including even-multiplicity tangencies. Treat identically coplanar spans separately. For a general subdivision curve, keep unresolved straddling pieces flagged or refine to the chosen tolerance instead of claiming that a finite endpoint-sign test is exact. Certified half-space rejection combined with adaptive subdivision is the recursive drawing algorithm; exact boundary topology needs additional root isolation.

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.

In a regular region, moving one control point adds its displacement multiplied by a translate of the twice-smoothed four-direction box spline. Measure parameter distances in original grid-edge units, with the affected control point at the origin. The convex hull of the binary mask offsets isAfter successive binary refinements the physical displacements are scaled by $2^{-1},2^{-2},\dots$. Their possible accumulated offsets therefore form ${\sum }_{j\ge 1}{2}^{-j}Z=Z$. The box spline description confirms that this zonotope is the actual support, not merely a loose enclosure. Equivalently,It is an octagon with vertices $(3,1),(1,3),(-1,3),(-3,1),(-3,-1),(-1,-3),(1,-3),(3,-1)$. Its enclosing square is six original grid intervals wide in each direction. Cutting four right triangles of area two from this $6\times 6$ square gives area $36-8=28$ parameter-square units. Outside this octagon the control-point displacement has no effect; its closure is the support, although the basis function can vanish on its boundary.

The regular influence footprint is this width-six, area-28 parameter octagon. For a nonplanar control mesh, the affected part of the spatial surface is the image of the octagon, not necessarily a planar octagon of the same metric size. Near an extraordinary subdivision vertex, use the actual refinement neighborhood instead of assuming a globally regular lattice footprint.

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.

A two-dimensional box spline built from $m$ spanning directions is piecewise polynomial of total degree at most $m-2$. Here there are eight directions, counting multiplicities, so the regular pieces have total degree six. This is total degree, not separate degree six in each parameter.

For the box spline smoothness criterion, let $r$ be the smallest number of directions whose removal leaves a set that does not span the plane. In this direction multiset, a line can contain at most two of the eight vectors, since each of the four distinct directions appears twice. At least six vectors must therefore be removed, and removing the six outside one chosen direction does achieve loss of rank. Hence $r=6$, givingIn particular all fourth partial derivatives are continuous across the piece boundaries; generic fifth derivatives need not be. The box spline criterion and this degree-six four-direction example are documented in the primary paper 4–8 Subdivision. The factor count also explains the large support: the extra smoothing comes from repeating all four directional averaging factors. This regular-grid calculation does not establish $C^4$ at an extraordinary subdivision vertex.

Choose coefficients using the local subdivision matrix, not just by copying a pleasant-looking regular stencil. Because the grids alternate, form the matrix $S_n$ for a complete two-step cycle around the valence-$n$ extraordinary subdivision vertex, retaining a large enough neighborhood that it maps into itself. The three local coefficients enter this matrix through the specified vertex and face rules.

First require constant reproduction and commutation with affine maps: every target stencil must sum to one, and the valence-four rules must reduce to the regular ones already found. A propagation mask need not itself sum to one. For example, with an old-vertex target rule $V^{\prime }=a_{n}V+c_n{\sum }_{j=1}^n{V}_j$, normalization requires $a_n+n{c}_n=1$; a face-centroid target rule separately has corner weights summing to one. If face weights depend on incident valences, impose their sum on each actual face, rather than incorrectly using a propagation-column normalization. Rotational and reflection symmetry around the vertex should preserve an isotropic treatment of its sectors. Nonnegative coefficients are desirable for convex hull bounds and stability, although they are not by themselves a smoothness proof.

For convergence, seek a simple eigenvalue one corresponding to the constant eigenvector, with all remaining eigenvalues of modulus below one. For a well-defined tangent plane, seek two independent, semisimple tangent modes with a common positive subdominant eigenvalue:The angular modes should be the first sine and cosine modes around the ring. On the regular lattice the full two-step tangent scale is $1/2$, which provides a useful consistency check. These requirements suppress persistent unwanted modes and ensure that generic first-order geometry is dominated by a two-dimensional tangent space.

Then check that the characteristic map of a subdivision surface built from those tangent eigenvectors is regular and injective on the punctured neighborhood. A dominant tangent pair together with a regular, nonfolding characteristic map is the crucial $C^1$ target; eigenvalues alone are insufficient. This check rules out folds or vanishing tangent area that a spectrum cannot detect. For reasonable curvature behavior, also try to keep second-order modes at or below ${\lambda }^2$ in modulus, with equality and appropriate mode structure when nonzero finite curvature is desired. Avoid negative or complex modes that produce visible alternating ripples, excessive shrinkage and strongly anisotropic shape response.

These are selection criteria, not a uniquely determined triple of coefficients. The disappearance of extraordinary faces after one step simplifies the subsequent local matrix, but the extraordinary vertex remains and its smoothness still needs these tests. In particular, the regular $C^4$ result cannot simply be assigned to arbitrary valence.

Choose the knot origin so the span most influenced by $P_i$ is $[i,i+1]$, and use its local parameter $t\in [0,1]$. The three active uniform quadratic B-spline basis functions giveThe central coefficient reaches its maximum at $t=1/2$, so this is indeed the span centered on the strongest influence of $P_i$. Express it in the quadratic Bernstein basis:Matching constant, linear and quadratic coefficients gives the quadratic Bézier curve controlsFor example, $C_i^{\prime }(0)=2(B_1-B_0)=P_i-P_{i-1}$ and $C_i^{\prime }(1)=2(B_2-B_1)=P_{i+1}-P_i$, checking the endpoint derivatives and the $C^1$ joins of neighboring spans.

Use degree elevation of Bernstein coefficients. If $b_j$ are degree-$p$ Bézier curve controls, the identical curve has degree-$(p+1)$ controlsThis follows by multiplying each degree-$p$ Bernstein basis polynomial by $(1-t)+t$ and collecting the degree-$(p+1)$ terms, so the operation changes the representation, not the curve.

For the quadratic controls in part (a), the cubic controls areRaise these cubic Bézier curve controls once more. ThenThus the requested quartic Bézier curve controls, expressed in the original polygon, areEach expression is an affine combination whose coefficients sum to one. Endpoint positions and derivatives are preserved at each degree-raising step, as is every point of the span.

Use the quartic treble-knot representation of a quadratic B-spline. Specify the indexing as well as the controls: for the interior of the long curve, take the quartic spline knot sequenceWith the standard B-spline convention that control $Q_j$ multiplies $N_{j,4}$ supported on $[{\tau }_j,{\tau }_{j+5}]$, the answer isIn other words, keep the three interior quartic Bézier curve controls $E_{1,i},E_{2,i},E_{3,i}$ for each span in that order. The offset $3i-1$ matters for the stated knot indexing; shifting all indices together gives an equivalent convention.

To prove the representation, insert each integer interior knot once, changing multiplicity three to four. A degree-four knot of multiplicity four separates Bézier curve spans while leaving their shared endpoint common. The three interior controls $E_{1,i},E_{2,i},E_{3,i}$ remain, and knot insertion constructs the shared endpoint from its neighboring controls with weights $1/2,1/2$, since adjacent knot intervals have equal length. In fact,The right endpoint is obtained in the same way. Hence every extracted quartic span has exactly the five controls proved in part (b). Knot insertion leaves the curve unchanged, so the assembled quartic B-spline is identical to the original quadratic one on every span.

There is also a derivative check at each join:This is why treble knots are appropriate: degree four with interior knot multiplicity three permits $C^{4-3}=C^1$ continuity, exactly the generic continuity of the uniform quadratic B-spline. For a finite clamped curve, include its endpoint controls and endpoint knot multiplicities using the same degree elevation of Bernstein coefficients and knot insertion; the displayed formulas describe the long interior requested here, without imposing an unstated end condition.