Does it create a B-spline from measurements?

No. It evaluates a spline whose parameters have already been specified or fitted.

Why does it use only nearby control points?

B-spline basis functions have local support, so only a limited subset contributes within a knot span.

Is the parameter the distance along the curve?

Usually not. Distance-based movement requires additional arc-length calculations or an appropriate reparameterization.

AI Glossary / Mathematics and optimization / Intermediate

De Boor's algorithm

Definition

De Boor's algorithm evaluates a B-spline curve at a specified parameter value through repeated weighted combinations of nearby control points. Its inputs include the curve's degree, control points, knot vector, and evaluation parameter. The result is a point on the existing curve, not a new curve fitted to data.

What it means

A B-spline describes a curve using several overlapping polynomial pieces. Knots organize the parameter intervals, while control points influence the shape. Evaluating the curve means finding its coordinates at a chosen parameter, such as the location that a drawing tool should display next.

The algorithm exploits local influence: for a parameter inside an ordinary knot span, only the relevant degree-plus-one control points are needed. The rest of a long control-point list does not participate in that evaluation. The parameter is a mathematical coordinate along the representation; it need not equal distance traveled or elapsed time.

How it works

First locate the knot span containing the parameter. Copy its active control points into working storage. Successive rounds blend neighboring working points, reducing the active collection until one point remains.

Each blend takes the form (1−a)A+aB. Unlike the constant ratio used in a single de Casteljau evaluation, the coefficient a depends on the parameter, selected knots, and current round. Correct indexing is therefore essential even when the geometry looks simple.

Repeated knots and the final domain endpoint require appropriate conventions. A production implementation should handle these deliberately instead of dividing by a zero knot difference. Within a valid span, the local blending construction offers favorable numerical behavior, although floating-point arithmetic still introduces rounding. Knot-span lookup and curve evaluation are separate parts of the computation.

Three practical examples

1. Design software: display points on an editable B-spline outline as a designer adjusts a nearby control handle.

2. Trajectory representation: evaluate the geometric position of a spline path before a separate timing and constraint-checking stage determines how a device follows it.

3. Scientific visualization: sample a spline fitted to measured coordinates for rendering, while retaining uncertainty information from the fitting process separately.

Think of it this way

Imagine narrowing a small group of weighted location markers into one final marker. Each round replaces neighboring pairs with intermediate locations, using weights prescribed by the local knot structure.

The analogy explains the successive blends, but the weights are not subjective votes. They come from the spline definition. Changing the knots or degree changes the calculation even when the visible control markers stay in the same places.

Worked example

Take an original quadratic example with degree 2, control points P0=(0,0), P1=(1,2), P2=(3,2), and P3=(4,0). Use the knot vector [0,0,0,1,2,2,2]. Evaluate at u=0.5, inside the span [0,1).

Only P0, P1, and P2 are active. The first round produces Q1 by blending P0 and P1 with coefficient (0.5−0)/(1−0)=0.5. Thus Q1=(0.5,1).

For Q2, blend P1 and P2 with coefficient (0.5−0)/(2−0)=0.25. Thus Q2=0.75(1,2)+0.25(3,2)=(1.5,2). Notice that the two coefficients differ despite the common evaluation parameter.

The second round blends Q1 and Q2 with coefficient 0.5, giving C(0.5)=0.5(0.5,1)+0.5(1.5,2)=(1,1.5).

This point lies within the triangle formed by the three active control points, as the convex-combination construction suggests. P3 does not enter this particular evaluation. The arithmetic is a hand-derived illustration; it does not assert constant travel speed or certify a complete motion plan.

Illustrative case study

Fictional case: Cedar Packaging stores a label outline as a quadratic B-spline. A developer notices that moving a distant handle does not change points sampled in the first knot span. The team confirms that this is expected local support rather than a rendering failure.

It adds separate checks for repeated knots, endpoint evaluation, and agreement between preview and exported geometry. Designers retain control over fitting and shape changes; de Boor evaluation supplies the coordinates of the chosen curve. No measured speed improvement or manufacturing result is claimed in this scenario.

Common misconceptions and mistakes

Control points are not generally points that the curve must pass through. Certain endpoint or knot configurations create interpolation properties, but these should not be assumed for every control point.

Do not substitute the same interpolation coefficient into every blend. The knot-dependent coefficients distinguish the general B-spline calculation from a Bézier evaluation.

Evaluation does not fit noisy observations, optimize the control polygon, or check collisions. Also, evenly spaced parameter values can produce unevenly spaced geometric points. Sampling density and arc-length parameterization are separate concerns.

Business use

The algorithm is useful wherever a product stores curves compactly and needs reliable geometric coordinates repeatedly. Its local character also helps explain the scope of a designer's edits.

For implementation review, inspect degree and knot validity, endpoint behavior, units, and the intended parameter domain. Test known simple curves and repeated-knot cases. When the curve drives a downstream process, validate that process independently: a correctly evaluated point can still belong to an unsuitable shape or an unsafe trajectory.

Check your understanding

In the worked example, why are the first-round coefficients 0.5 and 0.25 rather than both 0.5?

Answer: Their denominators use different knot intervals, of lengths 1 and 2. The parameter alone does not determine a de Boor blending coefficient; the relevant knots and round also matter.

Related terms

B-splines
De Casteljau's algorithm
B-spline
knot vector
control point
Bézier curve
local support
spline interpolation
NURBS
arc length

Learn next

Draw the worked control polygon and intermediate points, then evaluate another parameter in the same span. Next move into the second span and identify the new active control points before calculating. Study repeated knots and continuity after the basic indexing is clear; these determine important shape properties that a sampled picture can conceal.

Sources

Primary source: C.-K. Shene's Michigan Technological University course notes, “De Boor's Algorithm”, https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/de-Boor.html . The knot-dependent recurrence, local support discussion, and repeated-knot treatment were read. Coordinates and scenarios here are original teaching material; no software execution or performance benchmark is claimed.

Previous: DDPM objective Next: De Casteljau's algorithm