How to Learn de Boor’s Algorithm: B-Spline Evaluation, Knot Spans, Local Support and Numerically Stable Curve Computation

Quick read: de Boor’s algorithm evaluates a B-spline curve at a chosen parameter value by repeatedly interpolating only the control points that can influence that location. It is the B-spline counterpart of de Casteljau’s method for Bézier curves and is valued for locality, efficiency and numerical stability.

One-sentence answer: find the knot span containing the parameter, copy the small local set of relevant control points, then apply degree-by-degree affine interpolation until one point remains.

Why de Boor’s algorithm is worth learning

B-splines are everywhere in geometric computing: computer-aided design, animation, scientific visualization, trajectory design, surface modelling and numerical approximation. But their notation can make them look harder than they are. de Boor’s algorithm gives learners a concrete computational story.

At beginner level, the central idea is repeated interpolation. At intermediate level, the learner adds knots, degree and local support. At advanced level, the algorithm becomes a structured evaluation scheme whose complexity depends on spline degree rather than the total number of control points. At professional level, knot conventions, multiplicities, floating-point behaviour, derivative evaluation and library interoperability matter as much as the recurrence itself.

1. First mental model: a curve controlled locally

A B-spline curve is built from control points and basis functions. Each basis function is active over only part of the parameter domain. This local support means changing one control point affects only a local region of the curve rather than the entire curve.

That locality is exactly what de Boor’s algorithm exploits. To evaluate the curve at parameter u, you do not combine every control point. You first find the knot interval containing u, then work only with the p + 1 control points relevant to a degree-p spline at that location.

2. What are knots?

The knot vector is a non-decreasing sequence such as:

[0, 0, 0, 0, 1, 2, 3, 3, 3, 3]

For a cubic spline, p = 3. Repeated endpoint knots are common in clamped B-splines because they make the curve begin and end at the first and last control points. Interior knot multiplicity changes continuity and changes how many basis functions are nonzero at that location.

The first task in evaluation is to find a span index k such that, under the usual half-open convention, t[k] <= u < t[k+1]. Endpoint handling needs an explicit convention because the final parameter value lies on the closed end of the domain in most practical APIs.

3. The interpolation idea before the formula

Suppose degree p = 3. de Boor starts with four local control points. In the first round it replaces neighbouring points with weighted points between them. In the next round it interpolates the new points again. After three rounds, one point remains. That point is the value of the B-spline curve at u.

The weights are not arbitrary. They depend on u and the knot values that bound the relevant basis functions. Each interpolation has the form:

d[j] = (1 - alpha) * d[j - 1] + alpha * d[j]

where alpha is a normalized position of u inside an appropriate knot interval.

4. The de Boor recurrence

Let the spline have degree p, knot vector t, control points P, and let u lie in knot span k. Copy:

d[j] = P[k - p + j] for j = 0, …, p.

Then for recurrence level r = 1, …, p, update from right to left. A common indexing form uses:

i = k - p + j

alpha = (u - t[i]) / (t[i + p - r + 1] - t[i])

and then performs the affine interpolation. After the final round, d[p] is the evaluated curve point.

5. A compact Python implementation

def de_boor(k, u, degree, knots, control_points):
    p = degree
    d = [list(control_points[k - p + j]) for j in range(p + 1)]

    for r in range(1, p + 1):
        for j in range(p, r - 1, -1):
            i = k - p + j
            left = knots[i]
            right = knots[i + p - r + 1]

            if right == left:
                alpha = 0.0
            else:
                alpha = (u - left) / (right - left)

            d[j] = [
                (1.0 - alpha) * a + alpha * b
                for a, b in zip(d[j - 1], d[j])
            ]

    return d[p]

This code isolates the recurrence, but a production implementation also needs a robust knot-span search, validation of degree and knot-vector length, endpoint rules, support for scalar or vector control coefficients, and a deliberate policy for repeated knots.

6. Why the inner loop runs backwards

The working array is updated in place. If you update from left to right, you overwrite a value that a later calculation still needs from the previous recurrence level. Updating from right to left preserves the required old neighbour until it has been consumed.

This is a transferable implementation lesson. Space optimization often changes update order. The same issue appears in one-dimensional dynamic programming, knapsack variants and rolling-array recurrences: when old and new states share memory, direction becomes part of correctness.

7. Complexity: degree matters more than curve size

Once the knot span is known, the triangular recurrence performs on the order of p² interpolation work and stores p + 1 temporary points. Thus evaluation is commonly described as O(p²) work with O(p) temporary storage, plus the cost of finding the knot span.

For CAD-style splines, p is usually small even when a model has many control points. Local support therefore makes a single evaluation independent of most of the control polygon. That is a major practical reason B-splines scale well for interactive geometric work.

8. de Boor versus de Casteljau

de Casteljau evaluates a Bézier curve by repeated affine interpolation over its control points. de Boor generalizes this style of computation to B-splines, where the weights depend on the knot vector and only a local subset of control points participates.

The comparison is educationally useful because it separates what is shared from what is new:

shared: repeated affine interpolation, geometric meaning, stable local combinations;
new in B-splines: knot spans, knot multiplicity, local basis support and variable interpolation weights.

Do not merge the two algorithms mentally. A Bézier curve is one polynomial segment controlled globally by its control polygon; a B-spline is a piecewise-polynomial construction with local support governed by knots.

9. Why numerical stability matters

Classical work by Cox and de Boor developed stable recurrence-based evaluation because direct divided-difference style evaluation can be numerically troublesome. The de Boor/Cox family of recurrences forms results through local affine combinations rather than by expanding high-degree polynomials into coefficients and evaluating those globally.

For learners, this is an important transition from mathematical equivalence to numerical computing. Two formulas can describe the same curve exactly on paper while behaving differently in floating-point arithmetic. Professional algorithm choice therefore asks not only “Is the formula correct?” but also “How does error grow when a finite-precision machine executes it?”

10. Knot multiplicity and zero denominators

Repeated knots can make a denominator in the interpolation weight equal to zero. That does not mean the spline is invalid. It means the implementation must follow the mathematical convention appropriate to that recurrence term rather than perform an undefined division.

This is one reason production code should be validated against a mature spline library. Repeated knots, clamped endpoints and exact-knot evaluation are not “rare weird cases”; they are ordinary parts of spline modelling.

11. Professional test strategy

Endpoint tests: verify clamped curves return the expected first and last control points under the library’s endpoint convention.
Degree-1 tests: results should reduce to ordinary piecewise-linear interpolation.
Partition-of-unity cross-check: compare de Boor evaluation with an independent basis-function sum for small examples.
Repeated-knot tests: include interior multiplicities and evaluation exactly at knots.
Affine-invariance test: translating or uniformly scaling every control point should translate or scale every evaluated point the same way.
Library differential test: compare many randomized valid splines against SciPy, a CAD kernel or another trusted implementation.
Precision test: compare double-precision output with higher-precision reference calculations on numerically awkward knot configurations.

12. Derivatives, surfaces and NURBS

Once basic curve evaluation is secure, the same spline machinery opens several professional directions.

Derivatives: differentiate the B-spline representation or use derivative control coefficients, then evaluate another spline.
Tensor-product surfaces: evaluate in one parameter direction and then the other.
NURBS: evaluate homogeneous weighted control points and divide by the final homogeneous coordinate.
Knot insertion: refine the representation without changing the represented curve.
Subdivision and tessellation: combine evaluation with adaptive geometric error criteria.

These are separate mathematical jobs, but they all become easier once knot spans, local support and stable evaluation are understood properly.

13. How to learn de Boor without getting lost in subscripts

Do not begin by memorising the full recurrence. Begin with a degree-2 or degree-3 spline and draw the triangular interpolation table. Mark the active knot span. Circle the p + 1 control points that can influence u. Then calculate one recurrence level at a time.

Only after the geometry is visible should you translate the subscripts into array indices. Predict one intermediate point before running the program. Change one knot and explain which weights change. Increase knot multiplicity and observe the effect. This predict–run–investigate–modify–make rhythm is consistent with evidence-based programming pedagogy such as PRIMM, while worked examples and explicit subgoals reduce the burden of learning notation and code simultaneously.

14. Practice ladder: beginner to professional

Beginner: perform ordinary linear interpolation between two points and explain the role of a parameter between 0 and 1.
Developing: evaluate a quadratic B-spline point using a provided triangular de Boor table.
Intermediate: implement knot-span search plus de Boor evaluation for 2D control points.
Advanced: handle repeated knots, clamped endpoints and N-dimensional coefficients, and prove affine invariance.
Professional: differential-test against an established spline library, benchmark batched evaluations, study cache-friendly data layouts, and document numerical and endpoint conventions for downstream geometry code.

15. The transferable algorithmic idea

de Boor’s algorithm teaches localize first, then recurse on only what matters. The global model may contain hundreds of control points, but a single query touches only a small active neighbourhood. This pattern appears far beyond splines: sparse computation, finite elements, local interpolation, tree queries and spatial indexing all benefit from identifying the support of a query before doing expensive work.

It also teaches a second professional lesson: preserve a numerically stable representation instead of expanding a problem into a mathematically equivalent but computationally fragile form.

Sources and further reading

Final idea: do not let the knot indices hide the geometry. Find the active span, keep only the local control points, and repeatedly interpolate until one point remains. Once that picture is clear, de Boor’s recurrence stops being a wall of subscripts and becomes a precise computational process.

Small Group Tutorials