1. 基本思想

1.1. 仿射组合(Affine Combinations)

$n$点的仿射组合为：
$$
p_{\pmb\alpha}=\sum_{i=1}^n\alpha_i\pmb{p}i
$$
其中，$\sum{i=1}^n\alpha_i=1$

函数 $f$ 对参数 $x_i$ 是仿射的是指：
$$
f \left( x _ { 1 } , \ldots , \sum _ { k = 1 } ^ { n } \alpha _ { k } x _ { i } ^ { ( k ) } , \ldots , x _ { m } \right) = \sum _ { k = 1 } ^ { n } \alpha _ { k } f \left( x _ { 1 } , \ldots , x _ { i } ^ { ( k ) } , \ldots , x _ { m } \right)
$$
其中，$\sum_{i=1}^n\alpha_i=1$

示例：

  • 两点间的仿射插值为：
    $$
    \pmb{p}_\alpha = (1-\alpha)\pmb{p}_1+\alpha\pmb{p}_2
    $$
    image-20220103112000955

  • 三点间的仿射组合（亦为重心坐标）为：
    $$
    \pmb{p}=\alpha\pmb{p}_1+\beta\pmb{p}_2+\gamma\pmb{p}_3
    $$
    其中，$\alpha+\beta+\gamma=1$

    系数可用坐标表示：
    $$
    \alpha = \frac { \operatorname { area } \left( \Delta \left( p _ { 2 } , p _ { 3 } , p \right) \right) } { \operatorname { area } \left( \Delta \left( p _ { 1 } , p _ { 2 } , p _ { 3 } \right) \right) } ,
    \beta = \frac { \operatorname { area } \left( \Delta \left( p _ { 1 } , p _ { 3 } , p \right) \right) } { \operatorname { area } \left( \Delta \left( p _ { 1 } , p _ { 2 } , p _ { 3 } \right) \right) } ,
    \gamma = \frac { \operatorname { area } \left( \Delta \left( p _ { 1 } , p _ { 2 } , p \right) \right) } { \operatorname { area } \left( \Delta \left( p _ { 1 } , p _ { 2 } , p _ { 3 } \right) \right) }
    $$
    image-20220103112111944

1.2. 动机

我们希望：将（分段）多项式曲线表示为迭代线性（仿射）插值的形式

例如：

  • 对于一个多项式：$p(t)=at^3+bt^2+ct+d$

  • 能够写为$p(t)=a\cdot t\cdot t\cdot t+b\cdot t\cdot t+c\cdot t+d$

  • 将每个变量t解释为单独的参数：
    $$
    \pmb p(t_1,t_2,t_3)=\pmb at_1t_2t_3+\pmb bt_1t_2+\pmb ct_1+\pmb d
    $$

    • $t_1$控制$\pmb a+\pmb b+\pmb c$方向上的移动
    • $t_2$控制$\pmb a+\pmb b$方向上的移动
    • $t_3$控制$\pmb a$方向上的移动

  • 上述方法存在的问题：固定方向，多种表示形式

2. 极形式

2.1. 定义

将（分段）多项式曲线表示为迭代线性（仿射）插值的形式的升级版解决方法：极形式/开花

$n$次多项式$F:\mathbb{R}\to\mathbb{R}$ 的极形式/开花$f:\mathbb{R}^n\to\mathbb{R}$ 是一个满足以下性质的$ d $维函数：

  • 对角性Diagonality：$f(t,\dots,t)=F(t)$
  • 对称性Symmetry：对任意置换 $\pi$，$f(t_1,\dots,t_d)=f(t_{\pi(1)},\dots,t_{\pi(d)})$
  • 多仿射Multi-affine：$f(t_1,\dots,\sum_\limits{k=1}^n\alpha_kt_i^{(k)},\dots,t_d)=\sum_{k=1}^n\alpha_k f(t_1,\dots,t_i^{(k)},\dots,t_d)$

2.2. 唯一性

多项式 $F(t)$ 与极形式 $f(t_1,\dots,t_n)$ 是一一对应的，常用多项式的极形式如下：

  • 0 次：$f=c_0$
  • 1 次：$f(t_1)=c_0+c_1t_1$
  • 2 次：$f(t_1,t_2)=c_0+c_1\frac{t_1+t_2}{2} + c_2t_1t_2$
  • 3 次：$f(t_1,t_2,t_3)=c_0+c_1\frac{t_1+t_2+t_3}{3}+c_2\frac{t_1t_2+t_2t_3+t_1t_3}{3}+c_3t_1t_2t_3$

一般形式：
$$
\begin{aligned}
F(t)&=\sum_{i=0}^n c_i t^i\\\\
f(t_1,\cdots,t_n)&=\sum_{i=0}^n c_i \begin{pmatrix}n\\\\i\end{pmatrix}^{-1}\sum_{S\subseteq\{1,\cdots,n\},|S|=i}\prod_{j\in S}t_i
\end{aligned}
$$

2.3. 泛化

对于高维情况：
$$
\begin{aligned}
F&:\mathbb{R}^m\to \mathbb{R}^n\
f&:\mathbb{R}^{d\times m}\to \mathbb{R}^n
\end{aligned}
$$
满足性质

  • 对角性 diagonality：$f(\pmb{t},\dots,\pmb{t})=F(\pmb{t})$
  • 对称性 symmetry：对任意置换 $\pi$，$f(\pmb t_1,\cdots \pmb t_d)=f(\pmb t_ {\pi(1)},\cdots,\pmb t_ {\pi(d)})$
  • 多仿射 multi-affine：$f(\pmb t_1,\cdots,\sum_{k=1}^n\alpha_k\pmb t_i^{(k)},\cdots,\pmb t_d)=\sum_{k=1}^n\alpha_kf(\pmb t_1,\cdots,\pmb t_i^{(k)},\cdots,\pmb t_d)$

对于参数向量：

  • 需要区分点 point 和向量 vectors（点的差值）

  • 使用“帽子”记号 $\hat{v}=p-q$ 来表示向量

  • 1向量：$\hat{1}=1-0,\hat{\pmb{1}}=[1,\dots,1]^\top-\pmb{0}$

  • 极形式中向量的递归定义：
    $$
    \begin{aligned}
    f(\underbrace{t_1,\dots,t_{n-k}}{n-k},\underbrace{\hat{v}1,\dots,\hat{v}k}k)&:=\\\\
    f(\underbrace{t_1,\dots,t    {n-k}}    {n-k},p_1,\underbrace{\hat{v}2,\dots,\hat{v}{k-1}}    {k-1})&-f(\underbrace{t_1,\dots,t    {n-k}}{n-k},q_1,\underbrace{\hat{v}2,\dots,\hat{v}{k-1}}{k-1})
    \end{aligned}
    $$
    其中 $\hat{v}_i=p_i-q_i(i=1,\dots,k)$

2.4. 导数

$$
f(t_1,\cdots,t_n)=\sum_{i=0}^n c_i \begin{pmatrix}n\\\\i\end{pmatrix}^{-1}\sum_{S\subseteq\{1,\cdots,n\},|S|=i}\prod_{j\in S}t_i
$$

  • $c_i$与$t=0$处的导数值相关

  • 因此有：
    $$
    c_k=\frac{1}{k!}\frac{\mathrm d^k}{\mathrm dt^k}F(0)=\begin{pmatrix}n\\\\k\end{pmatrix}^{-1}f(\underbrace{0,\dots,0}_{n-k},\underbrace{\hat{1},\dots,\hat{1}}_k)
    $$

  • 一般情况：
    $$
    \frac{\mathrm d^k}{\mathrm dt^k}F(t)=\frac{n!}{(n-k)!}f(\underbrace{t,\dots,t}_{n-k},\underbrace{\hat{1},\dots,\hat{1}}_k)
    $$

示例：

$$
\begin{aligned}
F(t)&=c_0+c_1t+c_2t^2+c_3t^3\\\\
f \left( t _ { 1 } , t _ { 2 } , t _ { 3 } \right) &= c _ { 0 } + c _ { 1 } \frac { t _ { 1 } + t _ { 2 } + t _ { 3 } } { 3 } + c _ { 1 } \frac { t _ { 1 } t _ { 2 } + t _ { 1 } t _ { 3 } + t _ { 2 } t _ { 3 } } { 3 } + c _ { 3 } t _ { 1 } t _ { 2 } t _ { 3 }\\\\
F ^ { \prime } ( t )
&= 3f(t,t,\hat{1})\\\\
&= 3 \left[f(t,t,1)-f(t,t,0)\right]\\\\
&= 3 \left[ \left( c _ { 0 } + c_1\frac { 1 + t + t } { 3 } + c _ { 2 } \frac { 1 t + t t + 1 t } { 3 } + c _ { 3 } 1 t t \right) - \left( c _ { 0 } + c_1\frac { 0 + t + t } { 3 } + c _ { 2 } \frac { t t } { 3 } \right) \right]\\\\
&= 3 \left( c _ { 1 } \frac { 1 } { 3 } + c _ { 2 } \frac { 2 t } { 3 } + c _ { 3 } t t \right)\\\\
&= 3 c _ { 3 } t ^ { 2 } + 2 c _ { 2 } t + c _ { 1 }
\end{aligned}
$$

2.5. 连续性条件

下列三个条件分别等价

  • $F$ 和 $G$ 在 $t$ 点 $C^k$ 连续
  • $\forall t_1,\dots,t_k, f(t,\dots,t,t_1,\dots,t_k)=g(t,\dots,t,t_1,\dots,t_k)$
  • $f ( t , \ldots , t , \underbrace{\hat { 1 } , \ldots , \hat { 1 }}_k ) = g ( t , \ldots , t , \underbrace{\hat { 1 } , \ldots , \hat { 1 }}_k )$

2$\Leftrightarrow$3证明：
$$
\begin{aligned}
f(t,\cdots,t,t_1)&=f(t,\cdots,t,(t_1-0))\\\\
&=t_1f(t,\cdots,t,1)-f(t,\cdots,t,0)\\\\
&=t_1f(t,\cdots,t,\hat 1)
\end{aligned}
$$

举例：

  • $\forall t_1,t_2,t_3$：$f(t_1,t_2,t_3)=g(t_1,t_2,t_3)\Rightarrow$同一条曲线
  • $\forall t_1,t_2$：$f(t_1,t_2,t)=g(t_1,t_2,t)\Rightarrow$在$t$处$C^2$连续
  • $\forall t_1$：$f(t_1,t,t)=g(t_1,t,t)\Rightarrow$在$t$处$C^1$连续
  • $f(t,t,t)=g(t,t,t)\Rightarrow$在$t$处$C^0$连续

2.6. 升阶

给定$ d $次函数 $f(t_1,\dots,t_d)$，升阶得：
$$
f ^ { ( + 1 ) } \left( t _ { 1 } , \ldots , t _ { d + 1 } \right) = \frac { 1 } { d + 1 } \sum _ { i = 1 } ^ { d + 1 } f \left( t _ { 1 } , \ldots , t _ { i - 1 } , t _ { i + 1 } , \ldots , t _ { d + 1 } \right)
$$

  • 注意：$t_i$没了

证明$F^{(+1)}(t)=F(t)$：
$$
\begin{aligned} \forall t : f ^ { ( + 1 ) } ( t , \ldots , t ) & = \left. \frac { 1 } { d + 1 } \sum _ { i = 1 } ^ { d + 1 } f \left( t _ { 1 } , \ldots , t _ { i - 1 } , t _ { i + 1 } , \ldots , t _ { d + 1 } \right) \right| _ { t _ { 1 } = \cdots t _ { d + 1 } = t } \\\\ & = \frac { 1 } { d + 1 } \sum _ { i = 1 } ^ { d + 1 } f ( t , \ldots , t ) \\\\ & = f ( t , \ldots , t ) \end{aligned}
$$

3. Bézier样条的极形式应用

3.1. 回顾De Casteljau算法

之前我们已经推导过构造Bézier曲线的De Casteljau算法：
$$
\pmb b_i^{(r)}=(1-t)\pmb b_i^{(r-1)}+t\pmb b_{i+1}^{(r-1)}
$$
三次Bézier曲线的构造过程如下图所示：

image-20220103120516305

3.2. Bézier样条的极形式

根据极形式的仿射组合性质，导出Bernstein基函数的组合形式：
$$
\begin{aligned}
f(t,\cdots,t)
&=(1-t)f(t,\cdots,t,0)+tf(t,\cdots,t,1)\\\\
&=(1-t)[(1-t)f(t,\cdots,t,0,0)+tf(t,\cdots,t,0,1)]+
t[(1-t)f(t,\cdots,t,1,0)+tf(t,\cdots,t,1,1)]\\\\
&=(1-t)^2f(t,\cdots,t,0,0)+2t(1-t)f(t,\cdots,0,1)+t^2f(t,\cdots,t,1,1)\\\\
&=\cdots\\\\
&=\sum_{i=0}^n\begin{pmatrix}n\\\\i\end{pmatrix}t^i(1-t)^{n-i}f(\underbrace{0,\dots,0}{n-i},\underbrace{1,\dots,1}i)\\\\
&=\sum{i=0}^nB_n^i(t)f(\underbrace{0,\dots,0}{n-i},\underbrace{1,\dots,1}_i)
\end{aligned}
$$
因此，我们可以看到：

  • Bézier点为：$\pmb b_i^{(0)}(t)=f(\underbrace{0,\dots,0}_{n-i},\underbrace{1,\dots,1}_i)$

  • 中间的生成点为：$\pmb b_i^{(j)}(t)=f(\underbrace{0,\dots,0}_{n-i-j},\underbrace{1,\dots,1}_i,\underbrace{t,\dots,t}_j)$

  • De Casteljau算法递归计算：
    $$
    \begin{aligned}
    \pmb b_i^{(j)}(t)&=f(\underbrace{0,\dots,0}_ {n-i-j},\underbrace{1,\dots,1}i,\underbrace{t,\dots,t}j)\\\\
    &=(1-t)f(\underbrace{0,\dots,0}     {n-i-j+1},\underbrace{1,\dots,1}i,\underbrace{t,\dots,t} {j-1})+tf(\underbrace{0,\dots,0}     {n-i-j},\underbrace{1,\dots,1}_ {i+1},\underbrace{t,\dots,t}_ {j-1})\\\\
    &=(1-t)\pmb b_i^{(j-1)}+t\pmb b_ {i+1}^{(j-1)}(t)
    \end{aligned}
    $$

示例：

仿射组合：
$$
\begin{align}
b(0,t,1)&=b(0,0(1-t)+1t,1(1-t)+1t)\\\\
&=(1-t)b(0,0,1)+tb(0,1,1)
\end{align}
$$
image-20220103163030843

image-20220103122257916

3.3. 泛化情况

$f(t)$是$t\in [u,v]$的$d$阶 Bezier 曲线，$\pmb{p}$是$f$的极形式，则Bézier点用极形式表示为：
$$
\pmb b_i=p(u,\cdots,u,v,\cdots,v)
$$
示例：

三次Bézier曲线控制点为：

$\pmb{p}(u,u,u),\pmb{p}(u,u,v),\pmb{p}(u,v,v),\pmb{p}(v,v,v)$

image-20220103151232765

3.4. 换基

给定$n$次多项式$\pmb p(t)$，反求Bézier控制点${\pmb b_i}^n_{i=0}$

计算方法：

  • 求出极形式：$\pmb p(t)\Rightarrow\pmb b(t_1,\cdots,t_n)$
  • 求出控制点：$\pmb{b}_ i=\pmb{b}(\underbrace{0,\dots,0}_ {n-i},\underbrace{1,\dots,1}_ i)$，其中$i=0,\cdots,n$

示例：

$p(t)=1+2t+3t^2-t^3$

极形式表示：
$$
\pmb{b} \left( t _ { 0 } , t _ { 1 } , t _ { 2 } \right) = 1 + 2 \frac { t _ { 0 } + t _ { 1 } + t _ { 2 } } { 3 } + 3 \frac { t _ { 0 } t _ { 1 } + t _ { 1 } t _ { 2 } + t _ { 0 } t _ { 2 } } { 3 } - t _ { 0 } t _ { 1 } t _ { 2 }
$$
则有
$$
\begin{aligned}
\pmb{b}(0,0,0)&=1\
\pmb{b}(0,0,1)&=\frac{5}{3}\
\pmb{b}(0,1,1)&=\frac{10}{3}\
\pmb{b}(1,1,1)&=5\
\end{aligned}
$$

3.5. 分段曲线

image-20220103151955642

两条曲线段
$$
\{ \boldsymbol { p } ( 0,0,0 ) , \boldsymbol { p } ( 0,0,1 ) , \boldsymbol { p } ( 0,1,1 ) , \boldsymbol { p } ( 1,1,1 ) \} , \{ p ( 1,1,1 ) , \boldsymbol { p } ( 1,1,2 ) , \boldsymbol { p } ( 1,2,2 ) , \boldsymbol { p } ( 2,2,2 ) \}
$$

3.6. 导数

$$
\frac { \mathrm{d} } { \mathrm{d} t } F ( t ) = n f ( t , \ldots , t , \hat { 1 } ) = n ( f ( t , \ldots , t , 1 ) - f ( t , \ldots , t , 0 ) )
$$

3.7. 细分

image-20220103154022104

  • 每一次de Casteljau迭代都会产生两个新的控制多边形，分别描述Bézier曲线$f(t)$的左侧和右侧
  • 利用这两个新的控制多边形，可以将该Bézier曲线分割成两条，实现细分

3.8. 升阶

对Bézier曲线$\pmb b(t_1,\cdots,t_n)$进行升阶得到：
$$
\pmb{b} ^ { ( + 1 ) } \left( t _ { 1 } , \ldots , t _ { n + 1 } \right) = \frac { 1 } { n + 1 } \sum _ { i = 1 } ^ { n + 1 } \pmb{b} \left( t _ { 1 } , \ldots , t _ { i - 1 } , t _ { i + 1 } , \ldots , t _ { n + 1 } \right)
$$
升阶后曲线 $\pmb{b}^{(+1)}$ 的 $n+2$ 个控制点 $\pmb{b}^{(+1)}_ 0,\dots,\pmb{b}^{(+1)}_ {n+1}$ 为：
$$
\begin{aligned}
\pmb b_i^{(+1)}&=\pmb b^{(+1)}(\underbrace{0,\dots,0}{n+1-i},\underbrace{1,\dots,1}i)\\\\
&=\frac{i}{n+i}\pmb b(\underbrace{0,\dots,0}{d+1-i},\underbrace{1,\dots,1}{i-1})+\left(1-\frac{i}{n+1}\right)\pmb{b}(\underbrace{0,\dots,0}_{n-i},\underbrace{1,\dots,1}i)\\\\
&=\frac{i}{n+1}\pmb b{i-1}+\left(1-\frac{i}{n+1}\right)\pmb b_i
\end{aligned}
$$
特别地，
$$
\begin{aligned}
\pmb{b}_0^{(+1)}&=\pmb{b}0\\\\
\pmb{b}{n+1}^{(+1)}&=\pmb{b}_n\
\end{aligned}
$$

4. B样条的极形式应用

4.1. B样条的极形式

分段线性多项式曲线的极形式是存在且唯一的

给定$k$阶（$k-1$次）B样条曲线$\pmb x$

  • 结向量：$T=(t_0,\dots,t_{n+k})$
  • de Boor 点 $\pmb{d}_0,\dots,\pmb{d}_n$

设$\underline { \pmb{x} }(u_1,\dots,u_{k-1})$是$\pmb{x}(t)$的极形式，则de Boor点可表示为：
$$
\pmb{d}i=\underline{\pmb{x}}(t{i+1},\dots,t_{i+k-1})
$$

示例：

$k=4,n=5$

image-20220103161420023

4.2. de Boor算法的极形式

要确定$t$处B样条曲线的值，确定出$t$前后的$k-1$个结：
$$
r_{k-1}\leq\cdots\leq r_1\leq t\leq s_1\leq\cdots\leq s_{k-1}
$$
其中，$r_1\leq t<s_1$，则中间结点为：
$$
\pmb d_j^l(t)=\underline {\pmb x}(r_1,\cdots,r_{k-1-l-j},\underbrace{t,\cdots,t}l,s_1,\cdots,s_j)
$$
最终的曲线为：
$$
\pmb x(t)=\pmb d_0^{(k-1)}(t)=\underline{\pmb x}(\underbrace{t,\cdots,t}{k-1})
$$

示例：

$k=4$

image-20220103162640889

对于$t_2\leq t<t_4$，进行如下迭代：

image-20220103164358187