曲线生成 | 图解B样条曲线生成原理(基本概念与节点生成算法)

0 专栏介绍

🔥附C++/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备！详细介绍全局规划(图搜索、采样法、智能算法等)；局部规划(DWA、APF等)；曲线优化(贝塞尔曲线、B样条曲线等)。

🚀详情：图解自动驾驶中的运动规划(Motion Planning)，附几十种规划算法

1 什么是B样条曲线？

为了解决贝塞尔曲线无法局部修正、控制性减弱、曲线次数过高、不易拼接的缺陷，引入B样条曲线(B-Spline)。对贝塞尔曲线不了解的同学请看曲线生成 | 图解贝塞尔曲线生成原理(附ROS C++/Python/Matlab仿真)

B样条曲线是一种用于表示和描绘曲线的数学工具，它在计算机图形学、计算机辅助设计、计算机动画和数值分析等领域得到广泛应用。其名称中的B代表了基本(basis)，而样条则是在各个领域中广泛应用的一种绘制曲线的技术，例如计算机图形学、物理学模拟、金融和经济分析等。在计算机图形学中，样条通常用于创建平滑的曲线和曲面，以便在三维场景中呈现出更真实的效果。在物理学模拟中，样条可用于描述物体的运动轨迹和变形过程。

在这里插入图片描述

B样条曲线的性质包括平滑性、局部控制性、递归计算和多项式插值。通过调整控制点的位置、权重和节点序列，可以改变B样条曲线的形状，从而实现对曲线的精确控制。B样条曲线常用于描述自然曲线和复杂曲线，如汽车外形、飞机机翼、艺术造型等。在计算机图形学中，B样条曲线可以用来生成圆滑的曲线路径，进行形状建模和渲染，以及实现动画效果等。

在运动规划中，B样条曲线也是一种很强大的曲线生成和轨迹优化工具，接下来介绍其基本原理。

2 基函数的de Boor递推式

B样条曲线的核心是具有局部性的基函数(Basic function)——当改变一个控制节点时，只会变动该点旁边有限段曲线(样条曲线则需要重新计算整条曲线，因为它由一组控制点唯一确定)，而非“牵一发动全身”。如图所示给出了B样条与贝塞尔曲线基函数的区别。

在这里插入图片描述

采用Cox-de Boor递推定义B样条曲线的基函数

$N_{i,k}\left( t \right) =\frac{t-t_i}{t_{i+k}-t_i}N_{i,k-1}\left( t \right) +\frac{t_{i+k+1}-t}{t_{i+k+1}-t_{i+1}}N_{i+1,k-1}\left( t \right)$

其中 $N_{i,k}\left( t \right)$ 称为第 $i$ 个控制节点的 $k$ 次( $k + 1$ 阶)B样条基函数， $i=0,1,\cdots ,n-1$ ， $k\geqslant 1$ 且规定 ${{0}/{0}}=0$ 。特别地，有

$N_{i,0}\left( t \right) =\begin{cases} 1,t\in \left[ t_i,t_{i+1} \right)\\ 0,\mathrm{otherwise}\\\end{cases}$

即高次B样条基函数为若干低次B样条基函数的线性组合。 $N_{i,k}\left( t \right)$ 的次数 $k$ 与控制节点的个数 $n$ 无关，因此B样条曲线自由度更大——允许定义多个控制点而不用担心曲线次数过高导致计算困难。

3 B样条曲线基本概念图解

B样条曲线定义为用基函数加权的控制节点

$\boldsymbol{P}\left( t \right) =\sum_{i=0}^{n-1}{\boldsymbol{p}_iN_{i,k}\left( t \right)}, t\in \left[ t_k,t_n \right)$

其中 $T=\left\{ t_0,t_1,\cdots ,t_{m-1} \right\}$ 是一个一维单调非递减序列，称为节点向量(knot vector)，其中的元素 $t_i$ 称为节点(knot)，区间 $\left[ t_i,t_{i+1} \right)$ 称为第 $i$ 个节点区间(knot range)，节点在样条曲线上的映射 $\boldsymbol{P}\left( t_i \right)$ 称为曲节点(knot point)。

在节点向量中，若某节点 $t_i$ 出现 $l$ 次，则称 $t_i$ 是重复度为 $l$ 的多重节点，否则为简单节点。与贝塞尔曲线不同，仅当B样条曲线首末节点重复度为 $k + 1$ 时，曲线本身才穿过首末控制点。

接下来分析B样条曲线的局部支撑性。基函数 $N_{i,k}\left( t \right)$ 在区间 $\left[ t_i,t_{i+k+1} \right]$ 上非零，因为该区间上总存在不为零的零阶基函数 $N_{i,0}$ ，该区间称为支撑区间，对应样条曲线上的区段称为支撑曲线。由于 $N_{i,k}\left( t \right)$ 直接与控制节点 $\boldsymbol{p}_i$ 相乘，所以 $\boldsymbol{p}_i$ 只影响其支撑区间 $\left[ t_i,t_{i+k+1} \right]$ 上对应支撑曲线的形状。所以B样条曲线也可视为若干段贝塞尔曲线的拼接，是贝塞尔曲线的推广，相邻贝塞尔曲线间存在若干重合节点，保留了对称性、几何不变性、变差伸缩性等优良特性。

在这里插入图片描述

为使每个控制节点都有合法的支撑区间与之匹配，节点数量应满足

$m = n + k + 1$

B样条曲线的次数指基函数多项式的最高次数，阶数则可视为控制节点 $\boldsymbol{p}_i$ 所影响的节点数。当节点区间 $\left[ t_i,t_{i+1} \right)$ 上的非零 $k$ 次基函数达到最大数量 $k + 1$ 个时，令其满足

$\sum_{j=i-k}^i{N_{j,k}}=1$

称为基函数的加权性质。显然，对于 $k$ 次基函数，节点区间 $\left[ t_0,t_k \right)$ 与 $\left[ t_n,t_{n+k} \right)$ 上的非零基函数不足 $k + 1$ 个，它们的加权和不为零，在这些区间计算B样条曲线会导致错误，因此B样条曲线定义在区间 $\left[ t_k,t_n \right)$ 上。如图所示是关于B样条曲线定义区间的实例说明。

在这里插入图片描述

4 节点生成公式

B样条曲线由控制节点与节点向量唯一确定，通过改变节点向量中节点的分布特征，可以构造不同类型的B样条曲线

均匀B样条曲线(Uniform B-Spline Curve)

节点向量中的节点沿数轴方向等距离均匀分布，所有节点区间等距，即 $t_{i+1}-t_i=\mathrm{const}>0, i=0,1,\cdots ,n+k$
准均匀B样条曲线(quasi-Uniform B-Spline Curve)

节点向量中的首末节点重复度为 $k + 1$ ，其余节点沿数轴方向等距均匀分布且重复度为1。可以证明该情况下，当 $k = n$ 时，B样条基函数 $N_{i,k}\left( t \right)$ 退化为伯恩斯坦多项式，即B样条曲线退化为贝塞尔曲线。
非均匀B样条曲线(non-Uniform B-Spline Curve)

节点向量任意分布

节点生成通常有两种方法：

均匀法
$\begin{cases} t_0=t_1=\cdots =t_k=0\\ t_{k+i}=\frac{i}{n-k+1}, i=1,2,\cdots ,n-k-1\\ t_n=t_{n+1}=\cdots =t_{n+k}=1\\\end{cases}$
该方法不依赖于参数选择。
De Boor法
$\begin{cases} t_0=t_1=\cdots =t_k=0\\ t_{k+i}=\frac{1}{k}\sum_{j=i}^{i+k-1}{u_j}, i=1,2,\cdots ,n-k-1\\ t_n=t_{n+1}=\cdots =t_{n+k}=1\\\end{cases}$
该方法对选择的参数进行窗口平滑。