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

Use vectors in three-dimensional Euclidean space, with the usual dot product and cross product. The following explicit assignments compute the circumcenter of a tetrahedron:General position means $d\ne 0$. The reciprocal cross-product identities give $x\cdot u=|u{|}^2/2$, $x\cdot v=|v{|}^2/2$ and $x\cdot w=|w{|}^2/2$. Consequentlyand likewise for $C,D$. Thus $O$ is the unique point equidistant from the four vertices. It can lie outside the tetrahedron; no inside constraint should be imposed.

Compute twice the four opposite face areas and their weighted vertex average:These positive weights make $I$ an interior convex combination. To verify the incenter of a tetrahedron, put $\Delta =|(B-A)\cdot ((C-A)\times (D-A))|$. The altitude from $A$ to its opposite face is $\Delta /w_A$. Signed distance to that face is affine and vanishes at the other three vertices, so $I$ has distance $(w_A/w)(\Delta /w_A)=\Delta /w$. The same argument works for every face. HenceThe sphere of radius $r_{\mathrm{in}}$ centered at $I$ is tangent to all four faces. Equality of the four distances conversely forces these face-area weights, proving uniqueness.

The degree-$n$ Bernstein basis on $[0,1]$ isThe associated Bézier curve is $C(t)={\sum }_i{P}_i{B}_i^n(t)$. The basis is nonnegative and has partition of unity, since ${\sum }_i{B}_i^n(t)=(t+1-t{)}^n=1$. Thus the curve is a convex combination of its control points, giving the convex hull enclosure useful for geometric bounds. The same identity makes the construction invariant under application of affine functions.

It interpolates its endpoint controls, $C(0)=P_0$, $C(1)=P_n$, and its endpoint tangent vectors are $n(P_1-P_0)$ and $n(P_n-P_{n-1})$. These follow fromThe control polygon therefore gives direct geometric editing and tangent control. Repeated interpolation by the De Casteljau algorithm evaluates and subdivides the curve without converting to a monomial representation. Together, positive geometric weights, simple endpoint behavior and stable subdivision make this basis useful in computer aided geometric design.

A degree-$p$ B-spline basis keeps the positive partition of unity and convex hull properties while introducing local support. At a generic parameter value, only $p+1$ consecutive basis functions are nonzero. Moving one control point therefore changes only its support interval, unlike a generic interior Bézier curve control, which affects the whole polynomial segment.

Many low-degree pieces can represent a long curve with automatic continuity. At a knot of multiplicity $m$, the generic continuity is $C^{p-m}$; simple cubic knots give $C^2$. Knot positions and multiplicities control the placement of detail and joins. Knot insertion can refine the representation without changing the curve, and local refinement avoids raising the global polynomial degree. Thus B-splines combine geometric bounds, local editing and controlled smoothness with a fixed low degree. Clamped end knots can also give endpoint interpolation.

Scale the equal intervals to unit length. A nonzero compactly supported cubic B-spline with maximum continuity is $C^2$, so its fourth derivative is a sum of impulses at the knots. Equivalently it is a combination of truncated cubes,To vanish to the right of its support, the polynomial tail must be identically zero. Expanding that tail requires ${\sum }_j{a}_j{j}^r=0$ for $r=0,1,2,3$. Four or fewer distinct knots give a full-rank Vandermonde matrix and only the zero solution. Hence a nonzero function requires at least five knots, or four intervals. At knots $0,1,2,3,4$, the one-dimensional nullspace has coefficients proportional to $(1,-4,6,-4,1)$. The unscaled combination integrates to six on $[0,4]$, so unit-integral cardinal normalization gives:This is the Cardinal cubic B-spline, nonnegative with support $[0,4]$. To obtain its cubic B-spline Bézier extraction, use local parameter $t=x-j\in [0,1]$ on interval $[j,j+1]$. The four power-form numerators, with a common divisor six, areFor $a+bt+c{t}^2+d{t}^3$, the cubic Bernstein basis coefficients are $a$, $a+b/3$, $a+2b/3+c/3$, $a+b+c+d$. Applying this conversion givesEach scalar row describes a cubic Bézier curve graph piece with abscissa controls $j,j+1/3,j+2/3,j+1$. The truncated-cube construction proves value, first- and second-derivative agreement at all joins, including the zero exterior. Minimum support and maximum continuity determine the basis up to a scalar; the displayed normalization fixes that remaining freedom.

Let the original abscissae be $x_i=ih$ and vary only the ordinate of vertex $i$. Under Chaikin subdivision, the two child values on an edge are $\frac{3}{4}{y}_j+\frac{1}{4}{y}_{j+1}$ and $\frac{1}{4}{y}_j+\frac{3}{4}{y}_{j+1}$. All influence weights are nonnegative, so no cancellation removes an active descendant.

At level $r$ the spacing is $h_r=h/2^r$. If the leftmost influenced vertex is at $a_r$, the next leftmost is the quarter point on the preceding edge, $a_{r+1}=a_r-3h_r/4$; the rightmost advances by the same amount. Starting at $x_i$, the influenced vertex range is thereforeThe neighboring zero vertices bound any extra affected polygon segments by one refined spacing, which tends to zero. Passing to the limit givesIt spans three original grid intervals, with its endpoints at original edge centers. Positive descendant weights occur arbitrarily close to each endpoint, so this is the exact support closure. The support of a stationary subdivision scheme concerns the limit curve, not only the first pair of adjacent original edges. This describes interior vertices or an infinite uniform sequence; a finite open polygon needs an endpoint convention.

Use coordinates in which the current spacing is $h$. On the first child subgrid, the polynomial candidate ison the second it isFor arbitrary sufficiently long uniformly spaced data, all refined vertices can lie on one degree-$n$ polynomial only if these two candidate polynomials agree. They agree with $P$ when $n=0,1$. For $P(x)=a{x}^2+bx+c$, expansion givesThus quadratics preserve their degree, although not the same values.

For a polynomial of degree $n\ge 3$, subtract the two finite Taylor expansions. The first-derivative term cancels, while the leading nonzero differential term isIf the leading coefficient of $P$ is $a_n\ne 0$, this difference has nonzero coefficient $a_{n}n(n-1)(n-2)h^3/32$ at degree $n-3$; the higher derivatives have lower degree and cannot cancel it. Therefore the polynomial degree preservation under Chaikin subdivision holds exactly forThis is a general refinement property, independent of accidental interpolation through a small finite number of vertices.

Use the influence result and quadratic degree preservation to find each local limit piece, rather than assuming its smoothness. On $[x_i-h/2,x_i+h/2]$, only $y_{i-1},y_i,y_{i+1}$ matter. Extend these three values to a quadratic $P(x)=a{x}^2+bx+c$ across the uniform grid. Every refinement adds $3a{h}_r^2/16$, so the accumulated offset tends toBy locality this gives the same limit as the original data on the chosen interval. Put $t=(x-x_i)/h$ and $D_i=y_{i-1}-2y_i+y_{i+1}$. The limit piece is consequentlyAt the right edge center it hasThe next piece gives the same value and derivative at its left endpoint. The second derivatives on the two sides are instead $D_i/h^2$ and $D_{i+1}/h^2$, which generally differ. HenceThere is one continuous derivative in addition to the continuous curve itself. Special data such as a globally quadratic sequence can make higher derivatives match.

The rule is linear in the ordinates and translation invariant on the uniform grid, so write $s(x)={\sum }_i{y}_i\beta ((x-x_i)/h)$. Find its Chaikin basis function by setting $y_0=1$ and every other ordinate to zero. The central local piece just derived has $D_0=-2$ and gives $\beta (t)=3/4-t^2$ for $|t|\le 1/2$. On the next interval, the interpolating quadratic through values $1,0,0$ at abscissae $0,1,2$ is $\frac{1}{2}(t-1)(t-2)$. Adding its limiting offset $1/8$ gives $\frac{1}{2}(3/2-t{)}^2$. Reflection gives the left interval, and locality gives zero outside. ThusThis is a centered quadratic cardinal B-spline. It is nonnegative, and its integer translates form a partition of unity because refinement preserves constant data. Its support has width three, and its first derivative agrees at the half-integer knots while its second generally jumps, consistent with the earlier calculations.

A tensor-product surface basis combines two independent univariate bases:The coefficients $P_{ij}$ are three-dimensional control points. Fixing one parameter gives a curve in the other univariate basis; the coefficients of that curve are the corresponding weighted combinations of rows or columns of controls.

The control net must have a rectangular two-index topology, with row/column neighbors and quadrilateral mesh cells. “Rectangular” describes the index grid, not the geometry of the points: its faces need not be flat or rectangular in space. A surface requiring a triangular domain or arbitrary extraordinary mesh connectivity is not directly described by one such tensor-product patch.

Let $N_{ij}(u,v)=B_i(u)C_j(v)$. Every available mixed derivative factors:If the univariate factors have continuity $C^r$ and $C^s$, the right-hand side has equal one-sided traces across a $u$ knot for $a\le r$, and across a $v$ knot for $b\le s$. Their products therefore remain continuous, including where knot lines cross. The basis and its surface inherit coordinate-wise continuity orders $r,s$, and joint $C^{\min (r,s)}$ continuity. In particular, degree-$p$ and degree-$q$ B-splines at simple knots give $C^{p-1}$ and $C^{q-1}$ continuity in the respective directions. Higher continuity can occur through special coefficient cancellation, but is not generally guaranteed.

Nonnegativity passes to products. Their partition of unity follows fromThus the surface remains in the convex hull of its active control points and commutes with application of affine functions. The support is the Cartesian product of the two univariate supports, giving local rectangular influence regions and efficient local evaluation. Linear precision also passes independently in each coordinate. Clamped endpoint interpolation gives boundary curves determined by the outer rows/columns and corner interpolation; parameter-line curves inherit the corresponding univariate properties. These are the relevant inherited properties, rather than a claim of arbitrary global variation-diminishing behavior for surfaces.

A triangular Bézier patch is a non-tensor-product example. On barycentric parameters $u,v,w\ge 0$ with $u+v+w=1$, defineThe indices satisfy a total-degree constraint, and $w=1-u-v$ couples the two independent parameters. The control net is triangular with $(n+1)(n+2)/2$ points, rather than a rectangular product index set. The multinomial theorem gives nonnegative basis functions summing to one, but the entire basis is not a product of two independent univariate bases.

A parametric surface interrogation interface must specify its parameter domain, patch boundaries, trimming restrictions and any exceptional or singular points. It must evaluate $S(u,v)$ and the available derivatives, in particular $S_u,S_v$ for tangent vectors andfor the oriented normal vector where the denominator is nonzero. Second derivatives $S_{uu},S_{uv},S_{vv}$ are needed when the code requests curvature or second-order geometric error estimates; higher derivatives depend on the enquiry. The interface must report where these quantities exist, rather than assign an artificial normal at a singular parameter point.

Global searches also need subdivision into equivalent restricted patches, certified bounding volumes and a geometric approximation/error bound. These support intersection isolation, pruning and tolerance-controlled meshing. A single point-evaluation routine cannot guarantee a global search because it may miss remote branches or features between samples. Adjacent-patch topology and consistent orientation are needed to join results and interpret the represented surface.

Use the PDF's notation: $P$ is the fixed point light, $C(t)$ is the casting curve, and $S(u,v)$ is the receiver. A shadow point solvesThe separating-plane assumption puts the caster between light and receiver, so the relevant intersections are beyond the caster, not on the backward ray. The facing assumption supplies transverse regular intersections on the lit side. Carry out shadow tracing for a parametric curve as follows.

First subdivide the curve domain and receiving patches. Reject combinations whose certified bounding volumes cannot intersect the corresponding forward ray cone. For the remaining combinations, subdivide and isolate a hit, then correct its parameters using a three-variable Newton method with JacobianCheck that the corrected parameters lie in the patch domain and $\alpha >1$. Seed every connected component; one arbitrary initial hit does not establish that other components are absent. If a ray has several receiving hits, compare their $\alpha$ values and retain the visible first hit, rather than jumping between sheets.

At a transverse branch the Jacobian is nonsingular because $(C-P)\cdot (S_u\times S_v)\ne 0$. Differentiate the equation to predict the next hit:Use this predictor for a proposed parameter step, then apply Newton correction. To control the polygonal approximation, the shadow path is $X(t)=S(u(t),v(t))$. A second differentiation givesTogether with the surface derivatives this supplies a bound on $X^{\prime \prime }$. If $\Vert X^{\prime \prime }\Vert \le M$ over an interval of width $h$, the maximum error from its chord is at most $M{h}^2/8$. Subdivide until this bound, plus the numerical intersection error, is below the graphics tolerance. Corrected endpoints then give the requested point sequence on $S$. If second-derivative bounds are unavailable, refine until a certified enclosure of the entire branch segment lies within tolerance of its chord; a sufficiently small enclosure diameter is a conservative fallback.

Continue through adjacent patches, split at a trim or surface boundary, and stop a component when its admissible intersection ceases. Record closed components without duplicating their starting point. Use adaptive chord-error control and component isolation; a fixed fine sampling or an unverified sequence of local Newton solves can miss part of the shadow. If only estimated midpoint errors are available, those support a practical rendering heuristic rather than a certified tolerance.

Without the separation assumptions, explicitly test whether the caster lies between the light and receiver: roots with $0<\alpha \le 1$ are not receiver points shadowed by that caster point, and $\alpha <0$ belongs to the backward ray. The light can lie on the curve, making $C(t)-P=0$, or a ray can run along rather than cut the surface; both need exceptional treatment.

Without the facing assumption, allow back-facing regions, tangencies with singular continuation Jacobian, folds, multiple ray intersections, self-occlusion and changes of the visible first intersection. Visibility can create or delete whole shadow branches or switch them between receiver sheets. Also handle open boundaries, trimmed holes, disconnected receivers, closed casting loops, caster/receiver intersections and a light inside a closed receiver. Subdivision and intersection isolation must precede branch continuation near these events; normals, orientation and sorted ray distances decide which solutions are physically visible. The output can be several point sequences, rather than one connected polyline.

A subdivision surface interrogation interface needs the initial control net, its face/edge/vertex connectivity, the subdivision rule, patch addressing and refinement into child regions that cover the same limit surface. It must supply limit-point evaluation, available tangent/normal data and smoothness information, including the treatment of extraordinary subdivision vertices. A finite refined mesh point is generally not the exact limit point.

For geometric search it must provide certified bounding volumes for each descendant region, bounds that shrink under refinement, and a mesh-to-limit or chord/patch error estimate. With positive convex subdivision masks the active-control convex hull can provide such an enclosure; schemes with negative coefficients need another valid bound. A closed surface also needs consistent orientation, component navigation and containment queries for the enclosed body. The $C^1$ hypothesis supplies first-order tangent information at regular points, not automatically second derivatives or curvature everywhere. These enquiries distinguish an accurate limit-surface algorithm from a calculation only on an approximate control polyhedron.

Interpret the positive-distance assumption as disjoint compact enclosed bodies $A,B$, certified for example by disjoint enclosing volumes. Merely having disjoint drawn control meshes is insufficient if one encloses the other or the meshes do not enclose their limit surfaces. For genuinely disjoint bodies, the closest pair lies on their boundaries: an interior point could move toward the other body and decrease the distance. Thus minimize over all pairs of limit-surface patches.

Use branch and bound on patch pairs. For regions $A_i,B_j$, enclosing bounding volumes give a lower bound $L_{ij}$ on their true minimum distance. For axis-aligned bounding boxes, compute this directly asAny pair of evaluated limit points provides a feasible upper bound; retain the smallest, $U$. Start with a covering list of all coarse patch pairs. At each step, discard a pair when its lower bound is at least $U$, otherwise refine the region with larger bounding diameter/error and enqueue its child pairs. Prefer the pair with smallest lower bound. Update $U$ with new feasible pairs; a local stationary-distance solve can improve it but cannot replace the global search.

Let $L_{\ast }$ be the minimum remaining lower bound, capped by $U$ if the list is empty. The current certificate isStop when $U-L_{\ast }\le \epsilon$. Compactness and shrinking valid patch enclosures ensure convergence to this tolerance under the interface assumptions. An equivalent mesh method must add each mesh's certified limit error; for Hausdorff distance errors $e_A,e_B$, the separation error is at most $e_A+e_B$. Finite mesh distance without such a bound is not the exact minimum distance between subdivision bodies.

First distinguish the ordinary set distance from a signed overlap convention. Ordinary $d(A,B)$ is zero whenever the bodies intersect, and is never negative. Without the positive-separation assumption, test boundary intersections using the subdivision search, and test containment when the boundaries are disjoint. In particular, concentric spheres of unequal radii have positive boundary separation but overlapping enclosed bodies. Include every connected component in the containment tests.

For a meaningful negative result choose translational penetration depth, with orientation fixed:Define signed separation as ordinary positive distance for disjoint bodies, zero at contact, and $-\delta$ when their interiors overlap. This is explicit; the source does not specify which penetration convention its word “distance” intends. Simply negating the closest-boundary distance fails when boundaries cross, because that distance is already zero despite genuine interior overlap.

One implementable extension searches translation space. Obtain an initial separating translation by moving $A$ beyond $B$ along a coordinate direction, using the bodies' enclosing boxes; its norm is an upper bound $U_t$ on $\delta$. Cover a translation box containing the radius-$U_t$ ball, subdividing it into cells. Each cell has a lower bound on $\Vert t\Vert$, given by its box distance from the origin. At a sampled translation, perform certified boundary-intersection and containment queries. A nonoverlapping sample improves $U_t$.

To discard a whole colliding cell, certify an interior witness: if $x$ lies inside $B$ and $x-t_0$ lies inside $A$ with inward clearance $r$, then every translation with $\Vert t-t_0\Vert <r$ still overlaps. Boundary-distance and inside tests establish this certificate. Conversely, a separated sample with clearance $c$ remains separated under translations of norm less than $c$ away from it, by the triangle inequality. For a wholly free cell, use its point nearest the origin as a feasible translation, attaining its cell-norm lower bound. Refine cells whose status is uncertain and whose minimum norm is below $U_t$; discard certified-colliding cells and irrelevant farther cells. Keep the minimum cell-norm bound among cells that might contain a separating translation as $L_t$. Stop when $U_t-L_t\le \epsilon$, reportingRefinement/inside certificates can be implemented from the same surface hierarchy with conservative geometric bounds. Exact contact may require further refinement to decide topology; at finite numerical tolerance report a contact/uncertainty interval instead of inferring overlap from intersecting boxes. This handles crossing and containment and searches for the smallest separating translation, rather than an arbitrary visible intersection depth.