Please enable Javascript to view the contents

计算机辅助几何设计(4):极形式和开花算法

 ·  ☕ 8 分钟

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

仿射组合:

image-20220103163248564

对于$t_2\leq t<t_4$,进行如下迭代:

image-20220103164358187

分享

Wenbo Chen
作者
Wenbo Chen
CG Student

目录