计算机辅助几何设计：B样条曲线

b_spline

1. B样条基函数

为解决Bézier曲线的全局性、端点性等问题，我们引入了Bézier样条来实现曲线的局部编辑，但由于Bézier样条曲线本质上是分段Bézier曲线，数学表达不够优美，在构造、求交等计算上较为麻烦，为此我们又引入B样条基函数的工具，能够精确表达分段Bézier曲线。

1.1. 单位B样条基函数

B样条基函数通过不同连续阶性的简单基函数进行混合得到连续性更强的高阶基函数，例如一阶单位B样条基函数定义为：
$$
N_i^1(t)=\begin{cases}
1,&\mathrm {if}\ i\leq t< i+1\\\\
0,&\mathrm{otherwise}
\end{cases}
$$
$N_i^1(t)$为$C^{-1}$连续，函数图像如下：

通过平移与混合：

可以得到$C^0$连续的基函数$N_i^2(t)$：
$$
\begin{aligned}
N_i^2(t)&=(t-i)N_i^1(t)+(i+2-t)N_{i+1}^1(t)\\\\
&=\begin{cases}
t-i,&\mathrm{if}\ i\leq t\leq i+1\\\\
i+2-t,&\mathrm{if}\ i+1\leq t\leq i+2\\\\
0,&\mathrm{otherwise}
\end{cases}
\end{aligned}
$$
依次类推，继续混合：

这样一来，可以定义$k$阶的单位均匀B样条基函数$N_i^k(t)$定义为：
$$
\begin{aligned}
N_i^1(t)&=\begin{cases}
1,&\mathrm {if}\ i\leq t< i+1\\\\
0,&\mathrm{otherwise}
\end{cases}\\\\
N_i^k(t)&=\frac{t-i}{(i+k-1)-i}N_i^{k-1}(t)+\frac{(i+k)-t}{(i+k)-(i+1)}N_{i+1}^{k-1}(t)\\\\
&=\frac{t-i}{k-1}N_i^{k-1}(t)+\frac{i+k-t}{k-1}N_{i+1}^{k-1}(t)
\end{aligned}
$$

$k$阶单位B样条基函数的性质

$N_i^k(t)>0$，$i<t<i+k$
$N_i^k(t)=0$，$t\in(-\infty,i]\cup [i+k,+\infty)$
$N_i^k(t)$为$C^{k-2}$阶连续
$N_i^k(t)$为分段$k-1$次多项式函数组成

1.2. 一般的B样条基函数

给定结序列$t_0<t_1<\cdots<t_n<\cdots<t_{n+k}$，$(t_0,t_1,\cdots,t_{n+k})$称为结向量

归一化的$k$阶（即$k-1$度）的单位B样条基函数$N_{i,k}(t)$定义为：
$$
\begin{align}
N_{i,1}(t)&=\begin{cases}
1,&t_i\leq t<t_{i+1}\\0,&\mathrm{otherwise}
\end{cases}\\\\
N_{i,k}(t)&=\dfrac{t-t_i}{t_{i+k-1}-t_i}N_{i,k-1}(t)+\dfrac{t_{i+k}-t}{t_{i+k}-t_{i+1}}N_{i+1,k-1}(t)
\end{align}
$$

$k$阶B样条基函数的性质

$i=0,1,\cdots,n$，$k\in\mathbb Z^+$
对$t\in(t_i,t_{i+k})$，有$N_{i,k}(t)>0$
对$t\in(-\infty,t_i]\cup[t_{i+k},+\infty)$，有$N_{i,k}(t)=0$
对$t\in(t_{k-1},t_{n+1})$，有$\sum_{i=1}^nN_{i,k}(t)=1$
$N_{i,k}(t)$由分段多项式函数组成，次数为$k-1$，在$[t_i,t_{i+k}]$上$C^{k-2}$阶连续
区间$[t_i,t_{i+k}]$称为$N_{i,k}$的支撑区间

2. B样条曲线

2.1. B样条曲线的定义

给定：

$n+1$个控制点$\pmb d_0,\pmb d_1,\cdots,\pmb d_n\in\mathbb R^3$
结向量$T=(t_0,\cdots,t_n,\cdots,t_{n+k})$

这是由于$N_{n,k}$定义在区间$[n,n+k]$上

则$k$阶的B样条曲线$\pmb x(t)$定义为：
$$
\pmb x(t)=\sum\limits_{i=0}^nN_{i,k}(t)\cdot\pmb d_i
$$
其中，点$\pmb d_i$称为de Boor点

注意该定义下，B样条曲线不插值de Boor点$\pmb d_i$

示例：

重复结向量

B样条曲线允许重复结向量：$T=(t_0,\cdots,t_n,\cdots,t_{n+k})$，$t_0\leq t_1\leq \cdots\leq t_{n+k}$

当重复$k$次以上时，函数值视为0，没有贡献。

当$t_0=t_1=\cdots=t_{k-1}$且$t_{n+1}=t_{n+2}=\cdots=t_{n+k}$时，将插值$\pmb d_0$和$\pmb d_1$

示例：

2.2. B样条曲线的计算——de Boor算法

给定：

de Boor点：$\pmb d_0,\pmb d_1,\cdots,\pmb d_n$
结向量：$(t_0,\cdots,t_{k-1}=t_0,t_k,t_{k+1},\cdots,t_n,t_{n+1},\cdots,t_{n+k}=t_{n+1})$

则B样条曲线的计算流程如下：

中间系数$\pmb d_i^j(t)$可以表示为一个下三角矩阵——de Boor图：
$$
\begin{matrix}
\pmb d_{r-k+1}=\pmb d^0_{r-k+1}\\\\
\pmb d_{r-k+2}=\pmb d^0_{r-k+2}&\pmb d_{r-k+2}^1\\\\
\vdots\\\\
\pmb d_{r-1}=\pmb d_{r-1}^0&\pmb d_{r-1}^1&\cdots&\pmb d_{r-1}^{k-2}\\\\
\pmb d_r=\pmb d_r^0&\pmb d_r^1&\cdots&\pmb d_r^{k-2}&\pmb d_r^{k-1}=\pmb x(t)
\end{matrix}
$$

2.3. B样条曲线的性质

2.3.1. B样条基函数 vs. Bernstein多项式

结向量$T=(t_0,t_1,\cdots,t_{2k-1})=(\underbrace{0,\cdots,0}_k,\underbrace{1,\cdots,1}k)$下的$k$阶B样条函数$N{i,k}(i=0,\cdots,k-1)$为$k-1$次Bernstein多项式$B_i^{k-1}$

2.3.2. 基本性质

给定：

结向量：$T=(\underbrace{t_0,\cdots,t_0}_ {k\ \mathrm{times}},t_ k,\cdots,t_ n,\underbrace{t_ {n+1},\cdots,t_ {n+1}}_{k\ \mathrm{times}})$
de Boor多边形$\pmb d_0,\cdots,\pmb d_n$

相应的B样条曲线$\pmb x(t)$有如下性质：

$\pmb x(t_{n+1})=\pmb d_n$，$\pmb x(t_{n+1})=\pmb d_n$（边界点插值）
$\dot{\pmb x}(t_0)=\dfrac{k-1}{t_k-t_0}(\pmb d_1-\pmb d_0)$（$\pmb d_0$处的切线方向与$\pmb d_n$处相似）
$\pmb x(t)$由$n-k+2$个$k-1$次多项式曲线段构成
多重内部结$\Rightarrow$减小了$\pmb x(t)$的连续阶数，$l$重内部结$(1\leq l<k)$意味着$C^{k-l-1}$阶连续
de Boor点的局部影响：移动$\pmb d_i$只会改变曲线的$[t_i,t_{i+k}]$区间部分
插入新的de Boor点不会改变曲线段的多项式阶数

2.4. B样条曲线插值

给定：

控制点：$\pmb k_0,\pmb k_1,\cdots,\pmb k_n$
结序列：$s_0,s_1,\cdots,s_n$

目标：

分段三次插值B样条曲线$\pmb x(t)$，满足插值条件：
$$
\pmb x(s_i)=\pmb k_i,\ \ \ \ i=0,1,\cdots,n
$$

方法：

分段三次$\Rightarrow$$k=4$
重复首尾结$k-1=3$，结向量共计$n+2k-1=n+7$个结，对应$n+7-k=n+3$个de Boor点，结向量为：
$$
\begin{align}
T&=(t_0,t_1,t_2,t_3,t_4,\cdots,t_{n+2},t_{n+3},t_{n+4},t_{n+5},t_{n+6})\\\\
&=(s_0,s_0,s_0,s_0,s_1,\cdots,s_{n-1},s_n,s_n,s_n,s_n)
\end{align}
$$
插值条件（$n+1$个条件）
$$
\begin{align}
\pmb x(s_0)&=\pmb k_0=\pmb d_0\\\\
\pmb x(s_i)&=\pmb k_i=N_{i,4}(s_i)\pmb d_i+N_{i+1,4}(s_i)\pmb d_{i+1}+N_{i+2,4}(s_i)\pmb d_{i+2}\\\\
&\mathrm{for}\ i=1,\cdots,n-1\\\\
\pmb x(s_n)&=\pmb k_n=\pmb d_{n+2}
\end{align}
$$
终值条件（2个自然终值条件）
$$
\begin{align}
\ddot{\pmb x}(s_0)&=0\Leftrightarrow \dfrac{\pmb d_2-\pmb d_1}{s_2-s_0}=\dfrac{\pmb d_1-\pmb d_0}{s_1-s_0}\\\\
\ddot{\pmb x}(s_n)&=0\Leftrightarrow \dfrac{\pmb d_{n+2}-\pmb d_{n+1}}{s_n-s_{n-1}}=\dfrac{\pmb d_{n+1}-\pmb d_n}{s_n-s_{n-2}}
\end{align}
$$

结果可以表示为求解对角系统方程：
$$
\begin{pmatrix}
1\\\\
\alpha_0&\beta_0&\gamma_0\\\\
&\alpha_1&\beta_1&\gamma_1\\\\
&&&\ddots\\\\
&&&&\alpha_{n-1}&\beta_{n-1}&\gamma_{n-1}\\\\
&&&&&\alpha_n&\beta_n&\gamma_n\\\\
&&&&&&&1
\end{pmatrix}
\begin{pmatrix}
\pmb d_0\\\\\pmb d_1\\\\\pmb d_2\\\\\vdots\\\\\pmb d_n\\\\
\pmb d_{n+1}\\\\\pmb d_{n+2}
\end{pmatrix}=
\begin{pmatrix}
\pmb k_0\\\\\pmb 0\\\\\pmb k_1\\\\\vdots\\\\\pmb k_{n-1}\\\\
\pmb 0\\\\\pmb k_{n}
\end{pmatrix}
$$
其中，
$$
\begin{align}
\alpha_0&=s_2-s_0\\\\
\beta_0&=-(s_2-s_0)-(s_1-s_0)\\\\
\gamma_0&=s_1-s_0\\\\
\\\\
\alpha_n&=s_n-s_{n-1}\\\\
\beta_n&=-(s_n-s_{n-1})-(s_n-s_{n-2})\\\\
\gamma_n&=s_n-s_{n-2}\\\\
\\\\
\alpha_i&=N_{i,4}(s_i)\\\\
\beta_i&=N_{i+1,4}(s_i)\\\\
\gamma_i&=N_{i+2,4}(s_i)\\\\
\mathrm{for}&\ i=1,\cdots,n-1
\end{align}
$$

求解方法
- 使用Thomas算法——解决对角系统矩阵
- 仅适用于对角占优矩阵
- 复杂度$O(n)$
1. 前向消除阶段
2. 后向替换阶段

2.5. Bézier曲线转B样条曲线

给定：

控制点：$\pmb k_0,\pmb k_1,\cdots, \pmb k_n$
结序列：$t_0,t_1,\cdots,t_n$
2个终值条件
$C^2$连续、插值条件
用于$C^2$连续插值的分段三次Bézier样条曲线的Bézier点$\pmb b_0,\pmb b_1,\cdots,\pmb b_{3n}$

目标：

求取相同曲线的B样条形式

结向量：
$$
T=(t_0,t_0,t_0,t_0,t_1,\cdots,t_{n-1},t_n,t_n,t_n,t_n)
$$

共$n+7$个顶点，$n+3$个de Boor点，即$\pmb d_0,\pmb d_1,\cdots,\pmb d_{n+2}$

de Boor点满足：
$$
\begin{align}
\pmb d_0&=\pmb b_0\\\\
\pmb d_1&=\pmb b_1\\\\
\pmb d_i&=\pmb b_{3i-4}+\frac{\Delta_{i-1}}{\Delta_{i-2}}(\pmb b_{3i-4}-\pmb b_{3i-5})\ \mathrm{for}\ i=2,\cdots,n\\\\
\pmb d_{n+1}&=\pmb b_{3n-1}\\\\
\pmb d_{n+2}&=\pmb b_{3n}
\end{align}
$$
其中，对于$i=0,\cdots,n-1$，有$\Delta_i=t_{i+1}-t_i$

示例：