A Tutorial on Uniform B-Spline

Yi ZhouarXiv 2023 · DOI · arXiv

Abstract

This tutorial provides a unified mathematical framework for uniform B-splines, bridging the gap between the abstract Cox-de Boor recursion and practical matrix-based implementations. By leveraging Toeplitz matrices and "basis translation," we derive explicit, constant basis matrices that simplify trajectory generation for robotics and computer graphics. This approach unifies symbolic systems and provides a clear path to vectorized computation and optimization-friendly representations.

Introduction

B-splines are the "bread and butter" of smooth trajectory generation in fields like robotics (e.g., quadrotor planning) and computer vision. However, the standard definition—the Cox-de Boor recursion—is computationally cumbersome to implement directly. Furthermore, existing literature often uses inconsistent notation or conflicting definitions of "knots" and "control points," leading to implementation errors. This tutorial acts as a pedagogical bridge, seeking to unify these symbolic systems and provide a clear path to the matrix representation of B-splines. Matrix forms are highly desirable because they allow for efficient, vectorized computation and easier integration into optimization frameworks.

Mathematical Foundation

The mathematical foundation is built in three primary steps:

  1. The Cox-de Boor Formula: The process begins with the classic recursive definition, where a spline of degree $k$ is built from two subordinate splines of degree $k-1$.
  2. Basis Translation: To ensure numerical stability and simplify the math, a normalized variable $u \in [0, 1]$ is introduced. This "translates" the global time parameter $\tau$ into a local coordinate for each spline segment.
  3. Toeplitz Matrix Representation: The core innovation is representing the polynomial products within the recursion as operations with Toeplitz matrices (banded matrices where diagonals are constant). This allows the entire recursive process to collapse into a single basis matrix $M^k$.

Matrix Representation and Recursion

In the uniform case, where knots are evenly spaced, the basis matrices become constant. This means the matrix does not need to be recomputed for different time intervals; one can simply use the pre-derived matrix for a chosen degree $k$. The position on a spline can be calculated as a simple product: $P(u) = \mathbf{u}^T M \mathbf{P}$, where $\mathbf{u}$ is a vector of powers of $u$, $M$ is the basis matrix, and $\mathbf{P}$ is the vector of control points.

Matrix representation of a cubic B-spline and the definition of the basis matrix $M^3(3)$.

The derivation of these matrices follows a recursive structure. For example, the cubic basis matrix $M^3$ can be expressed in terms of the quadratic basis matrix $M^2$, facilitating a systematic approach to higher-order splines.

Recursive derivation of the cubic basis matrix $M^3(3)$ showing its relationship to the quadratic form $M^2(3)$.

Key Insights and Applications

  • The Matrix Shortcut: The tutorial provides ready-to-use basis matrices for common degrees, such as Linear ($k=1$), Quadratic ($k=2$), and Cubic ($k=3$). The cubic $4 \times 4$ matrix is the most common choice for smooth physical trajectories.
  • Cumulative B-splines: The paper extends this logic to cumulative B-splines, which are essential for interpolating on manifolds like $SE(3)$ (rotation and translation). By rearranging a standard B-spline into a "base point + differences" format, one can smoothly interpolate rotations by applying incremental updates to a starting orientation.
  • Efficiency: Matrix representations enable vectorized operations, which are significantly faster than recursive evaluations in high-performance applications like real-time motion planning.

Limitations

While the constant matrices derived here are powerful, they apply strictly to uniform B-splines. Non-Uniform Rational B-Splines (NURBS) require more complex matrix shortcuts that are not the focus of this tutorial. Additionally, while the math is "code-ready," practical implementation on manifolds like $SE(3)$ requires further integration with the exponential and log maps of Lie Group theory.

Summary updated

BibTeX
@misc{zhou2023tutorial,
  author = {Yi Zhou},
  title = {{A Tutorial on Uniform B-Spline}},
  year = {2023},
  eprint = {2309.15477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.15477},
}
Figure