Bezier curve & B-spline

1 Bezier曲线

1.1背景及意义

  参数$n$次曲线

$$p(t)=\sum _{i=0}^n{a}_i{f}_{i,n}(t)0\le t\le 1$$

其中，系数矢量$a_i(i=0,1,2,\dots ,n)$顺序首尾相接，$a_0$到$a_n$连成的折线称为控制多边形（Bezier多边形）。

  Bezier基函数

$$f_{i,n}=\{\begin{array}{ll}1& ,i=0\\ \frac{(-t{)}^i}{(i-1{)}^i}\frac{{\text{d}}^{i-1}}{{\text{d}}^{i-1}}[\frac{(1-t{)}^{n-1}-1}{t}]& \end{array}$$

可以化成伯恩斯坦函数

$$B_{i,n}=C_n^i{t}^i(1-t{)}^{n-1}=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-1}(i=0,1,2,\dots ,n)$$

1.2 定义

  针对Bezier曲线，给定空间$n+1$个点的位置矢量$P_i(i=0,1,2,\dots ,n)$，则Bezier曲线段的参数方程表示如下：

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)t\in [0,1]$$

其中，$p_i(x_i,y_i,z_i),i=0,1,2,\dots ,n$是控制多边形的$n+1$个顶点，即构成该曲线的特征多边形；$B_{i,n}(t)$是Bernstein基函数，有如下形式：

$$B_{i,n}=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=C_n^i{t}^i(1-t{)}^{n-i}(i=0,1,2,\dots ,n)$$

二项式定理（牛顿二项式定理），给出两数之和的整数次幂的恒等式，$\sum _{i=0}^n{B}_{i,n}(t)$恰好为二项式$[t+(1-t){]}^n$的展开式 （注：当$i=0,t=0$时，$t^i=1,i!=1$，即：$0^0=1,0!=1$）

  $P_i$代表空间中的很多点，把$t$代入可以得到平面或空间内的一个点，当$t$从0变化到1时，就可以得到空间内的一个图形，即Bezier曲线。

一次Bezier曲线

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)t\in [0,1]$$

当$n=1$时，有2个控制点$p_0$和$p_1$，Bezier多项式是一次多项式：

$$p(t)=\sum _{i=0}^1{P}_i{B}_{i,n}(t)=P_0{B}_{0,1}(t)+P_1{B}_{1,1}(t)$$

其中，

$$B_{0,1}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{1!}{0!(1-0)!}{t}^0(1-t{)}^{1-0}=(1-t)$$ $$B_{1,1}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{1!}{1!(1-0)!}{t}^1(1-t{)}^{1-1}=t$$

所以

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,1}(t)=P_0{B}_{0,1}(t)+P_1{B}_{1,1}(t)=(1-t)P_0+t{P}_1$$

恰好为连接起点$p_0$和终点$p_1$的直线段。

二次Bezier曲线

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)t\in [0,1]$$

当$n=2$时，有3个控制点$p_0$、$p_1$和$p_2$，Bezier多项式是二次多项式：

$$p(t)=\sum _{i=0}^2{P}_i{B}_{i,2}(t)=P_0{B}_{0,2}(t)+P_1{B}_{1,2}(t)+P_2{B}_{2,2}(t)$$

其中，

$$B_{0,2}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{2!}{0!(2-0)!}{t}^0(1-t{)}^{2-0}=(1-t{)}^2$$ $$B_{1,2}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{2!}{1!(2-1)!}{t}^1(1-t{)}^{2-1}=2t(i-t)$$ $$B_{2,2}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{2!}{1!(2-2)!}{t}^2(1-t{)}^{2-2}=t^2$$

所以

$$\begin{array}{rl}p(t)& =\sum _{i=0}^2{P}_i{B}_{i,2}(t)\\ & =(1-t{)}^2{P}_0+2t(1-t)P_1+t^2{P}_2\\ & =(P_2-2P_1+P_0)t^2+2(P_1-P_0)t+P_0\end{array}$$

为抛物线，其矩阵形式为：

$$p(t)=\left[\begin{array}{ccc}{t}^2& t& 1\end{array}\right]\cdot \left[\begin{array}{ccc}1& -2& 1\\ -2& 2& 0\\ 1& 0& 0\end{array}\right]\cdot \left[\begin{array}{c}{P}_0\\ P_1\\ P_2\end{array}\right]$$

三次Bezier曲线

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)t\in [0,1]$$

当$n=3$时，有4个控制点$p_0$、$p_1$、$p_2$和$p_3$，Bezier多项式是三次多项式：

$$p(t)=\sum _{i=0}^3{P}_i{B}_{i,3}(t)=P_0{B}_{0,3}(t)+P_1{B}_{1,3}(t)+P_2{B}_{2,3}(t)+P_3{B}_{3,3}(t)$$

其中，

$$B_{0,3}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{3!}{0!(3-0)!}{t}^0(1-t{)}^{3-0}=(1-t{)}^3$$ $$B_{1,3}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{3!}{1!(3-1)!}{t}^1(1-t{)}^{3-1}=3t(i-t{)}^2$$ $$B_{2,3}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{3!}{1!(3-2)!}{t}^2(1-t{)}^{3-2}=3t^2(i-t)$$ $$B_{3,3}(t)=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=\frac{3!}{1!(3-3)!}{t}^3(1-t{)}^{3-3}=t^3$$

所以

$$\begin{array}{rl}p(t)& =\sum _{i=0}^3{P}_i{B}_{i,3}(t)\\ & =(1-t{)}^3{P}_0+3t(1-t{)}^2{P}_1+3t^2(1-t)P_1+t^3{P}_3\\ & =(P_3-3P_2+3P_1-P+0)t^3+3(P_2-2P_1+P_0)t^2+3(P_1-P_0)t+P_0\end{array}$$

其中，$B_{0,3}(t)$、$B_{1,3}(t)$、$B_{2,3}(t)$ 、$B_{3,3}(t)$为三次Bezier曲线的基函数，均为三次曲线，任何三次Bezier曲线都是这四条曲线的线性组合。

Bezier曲线不能对曲线形状进行局部控制，如果改变任一控制点位置，整个曲线都会受到影响。

  三次Bezier曲线的矩阵形式为：

$$\begin{array}{rl}p(t)& =\left[\begin{array}{cccc}{t}^3& t^2& t& 1\end{array}\right]\left[\begin{array}{cccc}-1& 3& -3& 1\\ 3& -6& 3& 0\\ -3& 3& 0& 0\\ 1& 0& 0& 0\end{array}\right]\left[\begin{array}{c}{P}_0\\ P_1\\ P_2\\ P_3\end{array}\right]t\in [0,1]\\ & =T\cdot M_{be}\cdot G_{be}\end{array}$$

其中，$M_{be}$是三次Bezier曲线系数矩阵（常数），$G_{be}$是4个控制点位置矢量。

1.3 性质

1.3.1 Bernstein基函数的性质

$$B_{i,n}=C_n^i{t}^i(1-t{)}^{n-1}=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-1}(i=0,1,2,\dots ,n)$$

1.正性（非负性)

$$B_{i,n}(t)=\{\begin{array}{ll}=0& t=0,1\\ >0& t\in (0,1),i=1,2,\dots ,n-1\end{array}$$

2.权性
  基函数有$n+1$项，其和正好为1，即 $\sum _{i=0}^n{B}_{i,n}(t)\equiv 1t\in (0,1)$

3.端点性质

$$B_{i,n}(0)=\{\begin{array}{ll}1& (i=0)\\ 0& \text{otherwise}\end{array}$$ $$B_{i,n}(1)=\{\begin{array}{ll}1& (i=n)\\ 0& \text{otherwise}\end{array}$$

4.对称性

$$B_{i,n}(t)=B_{n-i,n}(1-t)$$

将n次Bezier曲线控制多边形顶点位置不变、次序颠倒，则曲线保持不变，但是走向相反。

5.递推性

$$B_{i,n}(t)=(1-t)B_{i,n-1}(t)+t{B}_{i-1,n-1}(t)(i=0,1,\dots ,n)$$

即n次Bernstein基函数可由两个n-1次Bernstein基函数线性组合而成。

6.导函数

$$B_{i,n}^{\prime }(t)=n[B_{i-1,n-1}(t)-B_{i,n-1}(t)](i=0,1,\dots ,n)$$

7.最大值

  在$t=\frac{i}{n}$处取到最大值。

8.积分

$${\int }_0^1{B}_{i,n}(t)=\frac{1}{n+1}$$

9.降阶公式

$$B_{i,n}(u)=(1-u)B_{i,n-1}(u)+u{B}_{i-1,n-1}(t)$$

即一个n次Bernstein基函数能表示成两个n-1次基函数的线性和。

1.3.2 Bezier曲线的性质

1.端点性质
  顶点$p_0$和$p_n$分别位于实际曲线段的起点和终点上，把$t=$0和1代入可以得到$p_0$和$p_n$。

2.一阶导数

$$p^{\prime }(t)=n\sum _{i=1}^n(p_i-p_{i-1})B_{i-1,n-1}(t)$$

当$t=0$时，$p^{\prime }(0)=n(p_1-p_0)$
当$t=1$时，$p^{\prime }(1)=n(p_n-p_{n-1})$

3.几何不变性

4.变差缩减性
  若Bezier曲线的特征多边形是一个平面图形， 则平面内任意直线与$p(t)$的交点个数不多于该直线与其特征多边形的交点个数。此性质表明Bezier曲线比特征多边形的折线更光顺。

1.4 Bezier曲线生成算法

1.4.1 根据定义

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)t\in [0,1]$$ $$B_{i,n}=\frac{n!}{i!(n-i)!}{t}^i(1-t{)}^{n-i}=C_n^i{t}^i(1-t{)}^{n-i}(i=0,1,2,\dots ,n)$$

1.给出$C_n^i$的递归计算式：

$$C_n^i=\frac{n!}{i!(n-i)!}=\frac{n-i+1}{i}{C}_n^{-1}n\ge i$$

2.将$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)$表示成分量坐标形式：

$$\{\begin{array}{l}x(t)=\sum _{i=0}^n{x}_i{B}_{i,n}(t)\\ y(t)=\sum _{i=0}^n{y}_i{B}_{i,n}(t)t\in [0,1]\\ z(t)=\sum _{i=0}^n{z}_i{B}_{i,n}(t)\end{array}$$

1.4.2 递推算法(de Casteljau)

由n+1个控制点$P_i(i=0,1,\dots ,n)$定义的n次Bezier曲线$P_0^n$可被定义为分别由前后n个控制点定义的两条n-1次Bezier曲线$P_0^n-1$和$P_1^{n-1}$的线性组合：

$$P_0^n=(1-t)P_0^n-1+t{P}_1^{n-1}t\in [0,1]$$

由此得到Bezier曲线的递推计算公式

$$P_i^k=\{\begin{array}{ll}{P}_i& k=0\\ (1-t)P_i^k-1+t{P}_{i+i}^{k-1}& k=1,2,\dots ,n,i=0,1,\dots ,n-k\end{array}$$

利用递推公式，在给定参数下，求Bezier曲线上一点$P(t)$非常有效

1.5 Bezier曲线的拼接及升降阶

1.5.1 Bezier曲线的拼接

$$p(t)=\sum _{i=0}^n{P}_i{B}_{i,n}(t)t\in [0,1]$$ $$B_{i,n}=C_n^i{t}^i(1-t{)}^{n-i}(i=0,1,2,\dots ,n)$$

  增加特征多边形的顶点数会引起Bezier曲线次数的提高，高次多项式会导致计算困难，所以需要采用分段设计，将各段曲线连接起来，并在接合处保持一定的连续条件。

  给定两条Bezier曲线$P(t)$和$Q(t)$，相应控制点为$P_i(i=0,1,\dots ,n)$和$Q_i(i=0,1,\dots ,m)$

(1)$G^0$连续，则：$P_n=Q_0$

(2)$G^0$连续，只要保证$P_{n-1}，P_n=Q_0,Q_1$三点共线即可（Bezier曲线的起点（终点）处的切线方向和特征多边形的第一条边（最后一条边）的走向一致）

1.5.2 Bezier曲线的升阶与降阶

升阶：保证曲线的形状和方向保持不变，但是增加定义它的顶点个数，即提高该Bezier曲线的次数。

  设给定原始控制顶点$p_0,p_1,p_n$，定义一条n次Bezier曲线，增加一个顶点后，仍定义同一条曲线的新控制顶点为$p_0^{\ast },p_1^{\ast },p_n^{\ast }$，则有

$$\sum _{i=0}^n{C}_n^i{P}_i{t}^i(1-t{)}^{n-i}=\sum _{i=0}^{n+1}{C}_{n+1}^i{P}_i^{\ast }{t}^i(1-t{)}^{n-i}$$ $$P_i^{\ast }{C}_{n+1}^i=P_i{C}_n^i+P_{n-1}{C}_n^{j-1}$$

化简得： $P_i^{\ast }=\frac{i}{n+1}{P}_{i-1}+(1-\frac{i}{n+1})P_i(i=0,1,\dots ,n+1)$

升阶后的多边形更加靠近曲线，如果一直升阶下去，控制多边形收敛于这条曲线。

降阶：升阶的逆过程

  假定$P_i$是由$P_i^{\ast }$升阶得到，则由升阶公式有：

$$P_i=\frac{n-i}{n}{P}_i^{\ast }+\frac{i}{n}{P}_{i-1}^{\ast }$$

由该方程可以导出两个递推公式：

$$P_i^{\ast }=\frac{n{P}_i-i{P}_{i-1}^{\ast }}{n-i}(i=0,1,\dots ,n-1)$$ $$P_{i-1}^{\ast }=\frac{n{P}_i-(n-i)P_i^{\ast }}{i}(i=0=n,n-1,\dots ,1)$$

可利用以上两个式子进行降阶，但不精确。

2 B样条曲线

2.1背景

  Bezier曲线存在不足：
（1）一旦确定了特征多边形的顶点数，也就确定了曲线的阶次；
（2）Bezier曲线或曲面的拼接比较复杂
（3）Bezier曲线或曲面不能作局部修改

  样条(spline)：分段连续多项式

如何分段？
  现有n+1个点，每两点之间构造一条多项式，n+1个点有n个小区间，
每个小区间构造一条三次多项式，变成了n段的三次多项式拼接在一起，段与段之间满足两次连续，这就是三次样条。

2.2 B样条的递推定义和性质

  B样条曲线的数学表达式为：

$$P(u)=\sum _{i=0}^n{P}_i{B}_{i,k}(u)u\in [u_{k-1},u_{n+1}]$$

其中，$P_i(i=0,1,\dots ,n)$是控制多边形的顶点，$B_{i,k}(u)$称为k阶（k-1次）B样条基函数，k可以是2到控制点个数n+1之间的任意整数。

  对于Bezier曲线来说，阶次和次数是一样的；但对于B样条，阶数是次数加1。

  B样条基函数是一个称为节点矢量的非递减的参数u的序列所决定的k阶分段多项式，这个序列称为节点向量。

de Boor-Cox递推定义

约定：$0/0=0$

$$B_{i,1}(u)=\{\begin{array}{ll}1& u_i<u_{i+1}\\ 0& Otherwise\end{array}$$ $$B_{i,k}(u)=\frac{u-u_i}{u_{i+k-1}-u_i}{B}_{i,k-1}(u)+\frac{u_{i+k}-u}{u_{i+k}-u_{i+1}}{B}_{i+1,k-1}(u)$$

该递推公式表明：若确定第i个k阶B样条$B_{i,k}(u)$，需要用到$u_i,u_{i+1},\dots ,u_{i+k}$共k+1个节点，称区间$[u_i,u_{i+k}]$为$B_{i,k}(u)$的支撑区间。

2.3 B样条基函数定义区间及节点向量

2.3.1 k阶B样条对应节点向量数

$$B_{i,1}(u)=\{\begin{array}{ll}1& u_i<u_{i+1}\\ 0& Otherwise\end{array}{B}_{i,k}(u)=\frac{u-u_i}{u_{i+k-1}-u_i}{B}_{i,k-1}(u)+\frac{u_{i+k}-u}{u_{i+k}-u_{i+1}}{B}_{i+1,k-1}(u)$$

对于$B_{i,k}$（k阶k-1次基函数）来说，涉及k个区间、k+1个节点。

2.3.2 B样条函数定义区间

$$P(u)=\sum _{i=0}^n{P}_i{B}_{i,k}(u)u\in [u_{k-1},u_{n+1}]$$ "阶数+顶点"=节点向量的个数

区间要合法，区间里必须要有足够的基函数与顶点匹配，B样条基函数严重依赖于节点向量的分布。

2.4 B样条曲线定义

$$P(u)=\sum _{i=0}^n{P}_i{B}_{i,k}(u)u\in [u_{k-1},u_{n+1}]$$ $$B_{i,1}(u)=\{\begin{array}{ll}1& u_i<u_{i+1}\\ 0& Otherwise\end{array}{B}_{i,k}(u)=\frac{u-u_i}{u_{i+k-1}-u_i}{B}_{i,k-1}(u)+\frac{u_{i+k}-u}{u_{i+k}-u_{i+1}}{B}_{i+1,k-1}(u)$$

其中，$U_i$是节点值，$U=(u_0,u_1,\dots ,u_{n+k})$构成了k阶（k-1）次B样条函数的节点矢量，B样条曲线对应的节点向量区间： $u\in [u_{k-1},u_{n+1}]$

2.5 B样条基函数的主要性质

1.局部支撑性

$$B_{i,k}(u)\{\begin{array}{ll}\ge 0& u_i<u_{i+k}\\ =0& otherwise\end{array}$$

对于每个区间$(u_i,u_{i+k})$，至多只有k个基函数在该区间内非零。

2.权性

$$\sum _{i=0}^n{B}_{i,k}(u)\equiv 1u\in [u_{k-1},u_{n+1}]$$

3.连续性

  $B_{i，k}(u)$在r重节点处的连续阶不低于k-1-r

4.分段参数多项式

  $B_{i,k}(u)$在每个长度非零的区间$[u_i,u_{i+1})$上都是次数不高于k-1的多项式。

2.6 B样条函数的主要性质

1.局部性

  k阶B样条曲线上的一点至多与k个控制顶点相关，与其它控制顶点均无关。移动曲线的第i个控制点$P_i$，至多影响到定义在区间上的那部分曲线的形状，对其余部分不产生影响。

2.变差缩减性

3.几何不变性

4.凸包性

  B样条曲线落在$P_i$构成的凸包之中，其凸包区域小于或等于同一组控制顶点定义的Bezier曲线凸包区域。

2.7 B样条曲线类型的划分

1.均匀B样条曲线(uniform B-spline curve)

  当节点沿参数轴均匀等距分布，即$u_{i+1}-u_i=\text{常数}>0$时，表示均匀B样条函数。
  均匀B样条的基函数呈周期性。即给定n和k，所有的基函数形状相同，每个后续基函数时前面基函数在新位置上的重复：

$$B_{i,k}(u)=B_{i+1,k}(u+\mathrm{\Delta }u)=B_{i+2,k}(u+2\mathrm{\Delta }u)$$

其中，$\mathrm{\Delta }u$是相邻节点值的间距。

2.准均匀B样条曲线(Quasi-uniform B-spline curve)

  与均匀B样条曲线的差别在于两端节点具有重复度k，这样的节点矢量定义了准均匀的B样条基，解决了均匀B样条曲线没有保留Bezier曲线端点几何性质的问题。

3.分段Bezier曲线(Piecewise Bezier Curve)

  节点矢量中两端节点具有重复度k，所有内节点重复度为k-1，这样的节点矢量定义了分段的Bernstein基。
  用分段Bezier曲线表示B样条曲线后，各曲线段就具有了相对独立性，且可以采用Bezier曲线的简单有效算法，缺点是增加了定义曲线的数据、控制定点数及节点数。

4.非均匀B样条曲线(non-uniform B-spline curve)

  当节点沿参数轴的分布不等距，即$u_{i+1}-u_i\ne \text{常数}$时，表示非均匀B样条函数。