Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 66 / 6

A useful subdivision curve interrogation supplies the following connected capabilities. It describes the parameter interval, open or closed topology, endpoints and break points; it evaluates the limit point $C(t)$ and, where the scheme guarantees them, $C^{\prime }(t)$ and $C^{\prime \prime }(t)$; and it refines or restricts an interval while retaining the mapping to the original parameter. It also provides enclosing bounds and a certified curve-to-chord error on each restricted piece. These are enough to build clipping, intersections, closest-point searches, tangents, curvature and adaptive sampling.

The enquiries concern the subdivision limit, not just a finite refined control polygon. For a stationary local refinement matrix $A$, a limit vertex can be obtained from a normalized left eigenvector $w^{T}A=w^T$, $w^{T}1=1$, as $w^{T}P$. Derivatives use the appropriately scaled difference schemes or equivalent spline evaluation on regular intervals. The convergence and derivative hypotheses must actually hold for the scheme; no second derivative can be requested at an intrinsic crease.

If the subdivision mask is nonnegative and preserves constants, descendants and limit points lie in the relevant control-point convex hull, giving a useful enclosing volume. For subdivision masks with negative weights, that hull need not be an enclosure: the interface must supply another valid bound, for example from a proven refinement-error estimate. This distinction is important for safe spatial rejection in an algorithm.

The corresponding subdivision surface interrogation needs mesh connectivity and patch adjacency, boundary and crease flags, local coordinate charts with transition maps, and subdivision into smaller patches with their original-chart mappings. Its evaluation enquiry returns a limit point, tangent derivatives and a normal vector; second derivatives are supplied only where the limit is sufficiently smooth. Certified bounding volumes and patch approximation errors allow a hierarchy for intersection and proximity searches. Boundary-curve enquiries complete the interface for clipping.

On regular parts of a subdivision surface, these evaluations may use its equivalent tensor-product or box spline patch. Near an extraordinary subdivision vertex, the local subdivision matrix determines the limit position through its constant left eigenvector, and its tangent modes determine the normal vector under the scheme's characteristic map of a subdivision surface regularity conditions. Refinement alone does not establish those conditions. A subdivision surface may have a well-defined tangent plane there without possessing second derivatives or Gaussian curvature. An interrogation interface must distinguish these cases and can work on surrounding regular charts when a higher derivative is unavailable at the vertex itself.

Together, subdivision, bounds, topology and limit evaluation support ray–subdivision surface intersection: bounds eliminate irrelevant patches; surviving patches are refined, and regular candidate intersections are corrected using position and first derivatives. The returned intersection is a point of the limit subdivision surface with an error certificate, rather than automatically a point on the last control mesh.

Let the point light be at $L$. For a subdivision curve point $C(t)$, its projected shadow lies on the ray beyond the subdivision curve:The shadow is the first intersection of that ray with the receiving subdivision surface after the subdivision curve point. Thus solveand retain the smallest admissible $\lambda$. This is the defining equation for shadow tracing for a subdivision curve.

First organize the subdivision surface patches into a bounding volume hierarchy. For a restricted subdivision curve interval, rays through its enclosing volume define an enclosing ray cone from $L$; subdivision surface bounds that do not meet this cone can be rejected. Refine surviving subdivision curve intervals and subdivision surface patches. For a fixed $t$, isolate all possible ray intersections using those bounds, then correct each regular candidate with the Jacobian matrix for the Newton methodThe scalar triple product shows that $J$ is invertible exactly when $n\cdot (C(t)-L)\ne 0$. Enforce the patch domain and $\lambda >1$ throughout correction, and choose the smallest valid $\lambda$. Bounds or validated root isolation, rather than a fixed list of subdivision curve samples, are needed if every shadow component is to be found.

Once a regular intersection is known, follow it as $t$ changes. Differentiating $F=0$ gives a useful predictor:Take a small predictor step in $(u,v,\lambda )$ and apply a Newton method correction at the new subdivision curve parameter. Move through patch adjacency with its chart transition; shrink steps when derivatives or error estimates change rapidly. Subdivide further and test a geometric curve-to-chord bound to approximate the resulting shadow trace to a chosen tolerance.

Surface-boundary crossings terminate or clip a trace. If a ray has no admissible subdivision surface intersection, that subdivision curve parameter contributes no shadow on $S$. At grazing contact the Jacobian is singular, so use interval subdivision and root isolation to detect the event and seed any outgoing branches. If several intersections are possible, recheck which is first; facing the light locally is helpful but is not a proof of global uniqueness. Open-curve endpoints and closed-curve seams must also be accounted for. With a compact represented geometry, transversal intersections and validated subdivision bounds, this algorithm traces every visible component; a purely sampled implementation gives only a tolerance-dependent approximation and cannot certify arbitrary tiny missed components.

For a directional light, replace the ray by $C(t)+\lambda d$ for a fixed propagation vector $d$ and $\lambda >0$. The intersection equation becomes $S-C-\lambda d=0$, with Jacobian $[S_u,S_v,-d]$ and continuation right-hand side $C^{\prime }(t)$. The same enquiries and event handling apply.