Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 66 / 4

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.