Introduction

Finding points on a B-spline curve is a common problem in computer graphics, computer-aided design, and many other fields. De Boor’s algorithm is a numerically stable method for evaluating B-splines. This article delves into the workings of De Boor's algorithm, technical details, and an example that brings theory into practice.

What is a B-Spline?

B-splines, or Basis splines, are a generalization of Bézier curves. They offer increased flexibility and control for designers and engineers, especially when designing complex shapes. B-splines are defined by a set of control points and a knot vector, which influences the shape of the curve.

Knot Vector

Before moving to De Boor's algorithm, it’s crucial to understand the role of the knot vector in B-splines. A knot vector $T = { t_0, t_1, \ldots, t_m }$ is a non-decreasing sequence of parameter values. The values in the knot vector determine where and how the control points affect the B-spline curve.

De Boor’s Algorithm

De Boor’s algorithm is a method used to evaluate B-spline curves at a given parameter value. It is a generalization of the de Casteljau's algorithm for Bézier curves and can handle B-splines of any degree. Here is the step-by-step breakdown of De Boor's algorithm:

1. Define Parameters: • Let $n$ be the number of control points. • Let $p$ be the degree of the B-spline. • The number of knots is $m = n + p + 1$.
2. Find the Knot Span: • Given a parameter $u$, locate the interval $[t_i, t_{i+1})$ in the knot vector where $u$ lies. • This is achieved by finding $i$ such that $t_i \leq u < t_{i+1}$.
3. Initialize Control Points: • Start with the control points influencing the interval:
   • Loop over the depth from 1 to p and compute the new control points. • The desired point on the B-spline curve is given by $d_{i,p}$.

Example

• Control Points: P0(0,0), P1(1,2), P2(3,5), P3(6,5) • Knot Vector: [0, 0, 0, 0, 1, 2, 2, 2, 2] • d[3, 0] = P0(0,0) • d[4, 0] = P1(1,2) • d[5, 0] = P2(3,5) • Compute the interpolation coefficients at each layer until reaching $d_{4,3}$.

Why De Boor's Algorithm Is Useful

• Flexibility: B-splines provide greater control over the shape compared to high-degree Bézier curves. • Local Control: Moving one control point only impacts a portion of the curve. • Numerical Stability: De Boor's algorithm is robust and handles floating-point calculations effectively.