Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 77 / 3 / i

Write a degree-$p$ B-spline as $C(t)={\sum }_i{P}_i{N}_{i,p}(t)$ and locate its spline knot span. There are several equivalent exact evaluation methods.

Evaluate the at most $p+1$ nonzero basis functions by the Cox-de Boor recurrence, then form their weighted sum of control points. Alternatively apply De Boor's algorithm directly to the $p+1$ active control points. In a span $[t_k,t_{k+1})$, initialize $d_j^{(0)}=P_{k-p+j}$ and repeatedly interpolate:for $r=1,\dots ,p$ and $j=p,p-1,\dots ,r$. The last point $d_p^{(p)}$ is $C(t)$; zero knot intervals are handled by the standard limiting convention or an appropriate neighboring nonempty span.

A third method precomputes the local polynomial coefficients on each span and evaluates them by Horner's method. For a uniform cubic B-spline, a fixed four-by-four basis matrix gives these coefficients. A fourth method uses knot insertion to express the relevant span as a Bézier curve, followed by De Casteljau's algorithm. Both interpolation algorithms also split the curve at the requested parameter. Repeated subdivision supplies arbitrarily accurate polygonal evaluation, although a finite subdivision mesh is generally an approximation rather than the exact requested point. Basis summation, de Boor interpolation, local polynomial evaluation and Bézier extraction are equivalent exact representations.