Please enable Javascript to view the contents

计算机辅助几何设计(1):Bézier曲线

 ·  ☕ 6 分钟

image-20211221222844217

1. 基本原理

Bézier曲线于1962年,由法国工程师Pierre Bézier所提出,用于汽车的主体的几何造型设计。

二阶Bézier曲线如下图所示:

image-20211222091601106

其几何构造流程如下:

  1. 依次选定控制点$A$、$B$、$C$
  2. 在$AB$上选定一动点$D$,设参数$t=\frac{AD}{AB}$,则$t\in[0,1]$
  3. 在$BC$上构造一点$E$,满足$\frac{AD}{AB}=\frac{BE}{BC}=t$
  4. 连接$DE$
  5. 在$DE$上构造一点$F$,满足$\frac{DF}{DE}=\frac{AD}{AB}=\frac{BE}{BC}=t$
  6. 当$t$从0到1变化时,点$F$构成的轨迹即为二阶Bézier曲线

从解析几何角度看,设控制点$A$、$B$、$C$坐标依次为$\pmb p_1$、$\pmb p_2$和$\pmb p_3$,则点$D$可表示为$\pmb p_4 = (1-t)\pmb p_1+t\pmb p_2$,点$E$表示为$\pmb p_5=(1-t)\pmb p_2+t\pmb p_3$,点$F$表示为$\pmb p_6=(1-t)\pmb p_4+t\pmb p_5=(1-t)^2\pmb p_1+2(1-t)t\pmb p_2+t^2\pmb p_3$

同理我们还可以构造三阶Bézier曲线:

image-20211222092442814

我们可以从中看出规律,给定$N$个控制点,将生成$N-1$阶的Bézier曲线,几何构造方式都是通过在控制点连线上按比例参数选取新的控制点,然后通过新的控制点再往下生成控制点,直到最终只生成一个控制点,该点则对应参数下Bézier曲线的取值。

2. De Casteljau算法

2.1. 算法原理

De Casteljau算法是计算给定参数$t$下Bézier曲线上点的坐标的迭代求解方法。

对于给定控制点$\pmb b_0,\pmb b_1,\cdots,\pmb b_n\in\mathbb R^3$,我们希望得到曲线$\pmb x(t),t\in[0,1]$,De Casteljau算法的迭代方程如下:
$$
\begin{align}
\pmb b_i^0(t)&=\pmb b_i,\ \ \ \ i=0,\cdots,n\\
\pmb b_i^r(t)&=(1-t)\pmb b_i^{r-1}(t)+t\pmb b_{i+1}^{r-1}(t)\\
r=&1,\cdots,n\ \ \ \ i=0,\cdots,n-r
\end{align}
$$
最后,$\pmb b_0^n(t)$为所找的曲线点$\pmb x(t)$在参数值$t$的取值,C++程序如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
glm::vec3 BezierCurve::value(const std::vector<glm::vec3> &control_points, float t)
{
    size_t n = control_points.size();

    std::vector<glm::vec3> br(control_points);
    std::vector<glm::vec3> br_1(control_points);

    for (size_t r = 1; r < n; r++)
    {
        for (size_t i = 0; i < n - r; i++)
        {
            br[i] = (1 - t) * br_1[i] + t * br_1[i + 1];
        }
        br_1 = br;
    }

    return br_1[0];
}

2.2. 算法性质

  • 控制点$\pmb b_0,\pmb b_1,\cdots,\pmb b_n\in\mathbb R^3$依次构成的多边形称为Bézier多边形
  • 控制点$\pmb b_i$也称为Bézier点
  • 只使用凸组合,因此算法数值稳定
  • 算法复杂度
    • 时间复杂度$O(n^2)$
    • 空间复杂度$O(n)$

3. Bézier曲线的解析表达

3.1. Bernstein基描述

De Casteljau算法提供了一种迭代求解Bézier曲线的方法,同时我们也可以解析地写出Bézier曲线的基函数表达:
$$
\pmb x(t)=\sum_{i=0}^nC_n^it^i(1-t)^{n-i}\pmb b_i
$$
其中$C_n^i$为组合数$C_n^i=\frac{n!}{i!(n-i)!}$,Bernstein基定义为:
$$
B_i^n(t)=
\begin{cases}
C_n^it^i(1-t)^{n-i}&t\in[0,1],i\in[0,n],i\in\mathbb N\\\\
0&i<0\ or\ i>n\\\\
1&i=0\ and \ n=0
\end{cases}
$$
Bernstein基示例:

image-20211222095828211

3.2. Bernstein基的性质

光滑性

Bernstein基函数为$n$次多项式,显然光滑

归一性
$$
\sum\limits_{i=0}^nB_i^{n}(t)=(t+(1-t))^n=1
$$

递推
$$
B_i^n(t)=(1-t)B_i^{n-1}(t)+tB^{n-1}_{i-1}(t)
$$

证明:
$$
\begin{align}
(1-t)B_i^{n-1}(t)+tB^{n-1}_{i-1}(t)&=(1-t)C_{n-1}^{i}t^i(1-t)^{n-1-i}+tC_{n-1}^{i-1}t^{i-1}(1-t)^{n-i}\\\\
&=(C_{n-1}^{i}+C_{n-1}^{i-1})t^i(1-t)^{n-i}\\\\
&=C_n^it^i(1-t)^{n-i}\\\\
&=B_i^n(t)
\end{align}
$$

导数
$$
\frac{\mathrm d}{\mathrm dt}B_i^{n}(t)=n\left[B^{n-1}_{i-1}(t)-B_i^{n-1}(t)\right]
$$

证明:
$$
\begin{align}
\frac{\mathrm d}{\mathrm dt}B^n_i(t)&=\frac{\mathrm d}{\mathrm dt}\left( C_n^it^i(1-t)^{n-i}\right)\\\\
&=iC_n^it^{i-1}(1-t)^{n-i}-(n-i)C_n^it^i(1-t)^{n-i-1}\\\\
&=\frac{n!}{(n-i)!i!}it^{i-1}(1-t)^{n-i}-\frac{n!}{(n-i)!i!}(n-i)t^i(1-t)^{n-i-1}\\\\
&=n\left[\frac{(n-1)!}{(n-i)!(i-1)!}t^{i-1}(1-t)^{n-i}-\frac{(n-1)!}{(n-i-1)!i!}t^i(1-t)^{n-i-1} \right]\\\\
&=n\left[C_{n-1}^{i-1}t^{i-1}(1-t)^{n-i}-C_{n-1}^i t^i(1-t)^{n-i-1} \right]\\\\
&=n\left[B^{n-1}_{i-1}(t)-B_i^{n-1}(t)\right]
\end{align}
$$

最值

$B^n_i(t)$在$t=\frac{i}{n}$处取得最大值

证明:

由导数为0
$$
\frac{\mathrm d}{\mathrm dt}B_i^{n}(t)=n\left[B^{n-1}_{i-1}(t)-B_i^{n-1}(t)\right]=0
$$
可得当$t=\frac{i}{n}$时取得最大值

对称性
$$
B_i^n(t)=B_{n-i}^n(1-t)
$$

证明:
$$
\begin{align}
B_i^n(t)&=C_n^it^i(1-t)^{n-i}\\\\
&=\frac{n!}{(n-i)!i!}t^i(1-t)^{n-i}\\\\
&=\frac{n!}{(n-(n-i))!(n-i)!}(1-t)^{n-i}t^{n-(n-i)}\\\\
&=B_{n-i}^n(1-t)
\end{align}
$$

非负性
$$
\begin{align}
B_i^n(t)&\geq 0,t\in [0,1]\\\\
B_0^{(n)}(0)=1,&\ \ \ \ B_1^{(n)}(0)=\cdots=B_n^{(n)}(0)=0\\\\
B_0^{(n)}(1)=&\cdots=B_{n-1}^{(n)}=0,\ \ \ \ B_n^{(n)}(1)=1
\end{align}
$$

4. Bézier曲线的性质

聊完Bézier曲线的构造方法以及Bernstein基函数的相关内容,我们再来聊聊Bézier曲线本身具有的几何性质。

4.1. 仿射不变性

仿射变换定义为:
$$
\pmb x\rightarrow\pmb A\pmb x+\pmb b
$$
包含线性部分和平移部分。

线性不变性

Bézier曲线的线性不变性是显然的,Bézier曲线表示为基函数的线性组合:
$$
\pmb f(t)=\sum\limits_{i=1}^nb_i(t)\pmb p_i=\sum\limits_{i=1}^nb_i(t)\begin{pmatrix}
p_i^{(x)}\\p_i^{(y)}\\p_i^{(z)}
\end{pmatrix}
$$
因此
$$
A(\pmb f(t))=A\Big(\sum\limits_{i=1}^nb_i(t)\pmb p_i \Big)=\sum\limits_{i=1}^nb_i(t)(A\pmb p_i)
$$

平移不变性
$$
\sum\limits_{i=1}^nb_i(t)(\pmb p_i+\pmb b)=\sum\limits_{i=1}^nb_i(t)\pmb p_i+\sum\limits_{i=1}^nb_i(t)\pmb b=\pmb f(t)+\Big(\sum\limits_{i=1}^nb_i(t)\Big)\pmb b
$$

其中,由Bernstein基函数的归一性,$\sum\limits_{i=1}^nb_i(t)=1$,满足平移不变性。

4.2. 凸包性质

点集${\pmb p_1,\cdots,\pmb p_n}$的一个凸组合为如下形式:
$$
\sum\limits_{i=1}^n\lambda_i\pmb p_i\ \mathrm{with}\sum\limits_{i=1}^n\lambda_i=1\ \mathrm{and}\ \forall i=1,\cdots,n:0\leq\lambda_i\leq 1
$$
因此Bézier曲线为Bernstein基函数的凸组合,能够避免不良震荡,将构造的曲线限制在控制点的凸包中。

4.3. 导数性质

对于Bézier曲线
$$
\pmb x(t)=\sum_{i=0}^nB_i^n(t)\pmb p_i
$$
一阶导数:
$$
\begin{aligned}
\frac{\mathrm d\pmb x}{\mathrm dt}&=n\sum_{i=0}^{n}\left[B^{n-1}_{i-1}(t)-B_i^{n-1}(t)\right]\pmb p_i\\\\
&=n\sum_{i=0}^nB_{i-1}^{n-1}(t)\pmb p_i-n\sum_{i=0}^n B_i^{n-1}(t)\pmb p_i\\\\
&=n\sum_{i=-1}^{n-1}B_i^{n-1}(t)\pmb p_{i+1}-n\sum_{i=0}^nB_i^{n-1}(t)\pmb p_i\\\\
&=n\sum_{i=0}^{n-1}B_i^{n-1}(t)\pmb p_{i+1}-n\sum_{i=0}^nB_i^{n-1}(t)\pmb p_i\\\\
&=n\sum_{i=0}^{n-1}B_i^{n-1}(\pmb p_{i+1}-\pmb p_i)
\end{aligned}
$$
边界条件:
$$
\begin{cases}
\pmb x'(0)=n(\pmb p_1-\pmb p_0)\\\\
\pmb x'(1)=n(\pmb p_n-\pmb p_{n-1})
\end{cases}
$$
高阶导数:
$$
\frac{\mathrm d^r}{\mathrm dt^r}\pmb x(t)=\frac{n!}{(n-r)!}\sum_{i=0}^{n-r}B_i^{n-r}(t)\cdot\Delta^r\pmb p_i
$$
其中,

一阶差分:$\Delta \pmb p_i=\pmb p_{i+1}-\pmb p_i$

二阶差分:$\Delta^2\pmb p_i=\Delta\pmb p_{i+1}-\Delta \pmb p_i=\pmb p_{i+2}-2\pmb p_{i+1}+\pmb p_i$

高阶差分递推式:$\Delta^r\pmb p_i=\Delta^{r-1} \pmb p_{i+1}-\Delta^{r-1} \pmb p_i$

归纳法有:$\Delta^r\pmb p_i=\sum_{k=0}^r(-1)^kC_r^k\pmb p_{i+r-k}$

4.4. 杂项性质结论

一条 Bézier 曲线的弧长不大于其控制多边形的周长

证明:

设Bézier曲线方程为$\pmb f(t)$,曲线弧长为$L$,多边形周长为$C$,则Bézier曲线弧长为:
$$
\begin{aligned}
L&=\int_0^1\|\pmb f'(t)\|\mathrm dt\\\\
&=\int_0^1\left\|n\sum_{i=0}^{n-1}B_i^{(n-1)}(t)(\pmb p_{i+1}-\pmb p_i)\right\|\mathrm dt\\\\
&\leq n\sum_{i=0}^{n-1}\|\pmb p_{i+1}-\pmb p_i\|\cdot \int_0^1B_i^{(n-1)}(t)\mathrm dt
\end{aligned}
$$
由Bernstein基函数的性质,有:
$$
\frac{\mathrm d}{\mathrm dt}B_i^{(n)}(t)=n\left[B_{i-1}^{(n-1)}(t)-B_i^{(n-1)}(t)\right]
$$
从0到1积分得:
$$
B_i^{(n)}(1)-B_i^{(n)}(0)=n\left[\int_0^1B_{i-1}^{(n-1)}(t)-\int_0^1B_i^{(n-1)}(t)\right]=0
$$
依此类推有:
$$
\int_0^1 B_0^{(n-1)}(t)\mathrm dt=
\int_0^1 B_1^{(n-1)}(t)\mathrm dt=
\cdots=
\int_0^1 B_{n-1}^{(n-1)}(t)\mathrm dt=\frac{1}{n}
$$
因此,有:
$$
L\leq \sum_{i=0}^{n-1}|\pmb p_{i+1}-\pmb p_i|=C
$$
结论得证

圆弧不能用Bézier曲线精确表示

设有一圆弧圆心为$\pmb c$,半径为$r$,假设它能够用一Bézier曲线$\pmb f(t)$进行表示,则有:
$$
\left|\pmb f(t)-\pmb c\right|\equiv r
$$
其中,
$$
\begin{aligned}
\pmb f(t)&=\sum_{i=1}^{n}B_i^{n}(t)\pmb p_i\\\\
&=\sum_{i=1}^{n}\frac{n!}{i!(n-i)!}t^i(1-t)^{n-i}\pmb p_i
\end{aligned}
$$

$$
\left\|\sum_{i=1}^{n}\frac{n!}{i!(n-i)!}t^i(1-t)^{n-i}\pmb p_i-\pmb c\right\|\not\equiv\mathrm{const}
$$
因此假设不成立,圆弧不能用Bézier曲线精确表示

5. Bézier曲线的升阶(Degree Elevation)

给定$n+1$个Bézier控制点$\pmb b_0,\pmb b_1,\cdots,\pmb b_n$,生成Bézier曲线$\pmb x(t)$

Bézier曲线的升阶即希望生成$n+2$个Bézier控制点$\bar{\pmb b}_0,\bar{\pmb b}_1,\cdots,\bar{\pmb b}_n$,从而得到曲线$\bar{\pmb x}(t)$,满足$\bar{\pmb x}(t)=\pmb x(t)$

解决方法:
$$
\begin{aligned}
\bar{\pmb b}_0&=\pmb b_0\\\\
\bar{\pmb b}_{n+1}&=\pmb b_n\\\\
\bar{\pmb b}_j&=\dfrac{j}{n+1}\pmb b_{j-1}+\Big(1-\dfrac{j}{n+1}\Big)\pmb b_j\ \ \ \ \ \mathrm{for}\ j=1,\cdots,n
\end{aligned}
$$

证明:
$$
\begin{aligned}
(1-t)B_i^n(t)&=(1-t)C_n^it^i(1-t)^{n-i}\\\\
&=C_n^it^i(1-t)^{n+1-i}\\\\
&=\frac{n+1-i}{n+1}C_{n+1}^it^i(1-t)^{n+1-i}\\\\
&=\frac{n+1-i}{n+1}B_i^{n+1}(t)
\end{aligned}
$$
类似地,
$$
tB_i^n(t)=\dfrac{i+1}{n+1}B_i^{n+1}(t)
$$
从而有:
$$
\begin{align}
\pmb f(t)&=[(1-t)+t]\pmb f(t)\\\\
&=[(1-t)+t]\sum\limits_{i=0}^nB_i^n(t)\pmb P_i\\\\
&=\sum\limits_{i=0}^n\Big[(1-t)B_i^n(t)+tB_i^n(t)\Big]\pmb P_i\\\\
&=\sum\limits_{i=0}^n\Bigg[\dfrac{n+1-i}{n+1}B_i^{n+1}(t)+\dfrac{i+1}{n+1}B_{i+1}^{n+1}(t) \Bigg]\pmb P_i\\\\
&=\sum\limits_{i=0}^n\dfrac{n+1-i}{n+1}B_i^{n+1}(t)\pmb P_i+\sum\limits_{i=0}^n\dfrac{i+1}{n+1}B_{i+1}^{n+1}(t) \pmb P_i\\\\
&=\sum\limits_{i=0}^n\dfrac{n+1-i}{n+1}B_i^{n+1}(t)\pmb P_i+\sum\limits_{i=1}^n\dfrac{i}{n+1}B_{i}^{n+1}(t) \pmb P_{i-1}\\\\
&=\sum\limits_{i=0}^{n+1}\dfrac{n+1-i}{n+1}B_i^{n+1}(t)\pmb P_i+\sum\limits_{i=0}^n\dfrac{i}{n+1}B_{i}^{n+1}(t) \pmb P_{i-1}\\\\
&=\sum\limits_{i=0}^{n+1}B_i^{n+1}(t)\Bigg[\dfrac{n+1-i}{n+1}\pmb P_i+\dfrac{i}{n+1}\pmb P_{i-1} \Bigg]
\end{align}
$$

示例:

image-20211222135340285

6. Bézier曲线的划分(Subdivision)

给定$n+1$个Bézier控制点$\pmb b_0,\pmb b_1,\cdots,\pmb b_n$,生成Bézier曲线$\pmb x(t)$

Bézier曲线的划分即希望得到两条曲线:

  • $\pmb{b}_0^{[1]},\dots,\pmb{b}_n^{[1]}\to \pmb{x}^{[1]}(t)$
  • $\pmb{b}_0^{[2]},\dots,\pmb{b}_n^{[2]}\to \pmb{x}^{[2]}(t)$

且两条曲线合并可得$\pmb{x}=\pmb{x}^{[1]}\cup \pmb{x}^{[2]}$

解决方法:
$$
\begin{aligned}
\pmb b_i^{(1)}&=\pmb b_0^i\\\\
\pmb b_i^{(2)}&=\pmb b_0^{n-i}\\\\
\mathrm{for}\ i&=0,\cdots,n
\end{aligned}
$$
该方法的依据如下图所示:

image-20211222140816109

7. 视频演示

Bézier曲线已在IlumEngine中实现,使用De Casteljau算法进行构造。

分享

Wenbo Chen
作者
Wenbo Chen
CG Student

目录