贝兹曲线

<image>

在数学的数值分析领域中，贝兹曲线（Bézier curve）是计算机图形学中相当重要的参数曲线。更高维度的广泛化贝兹曲线就称作贝兹曲面，其中贝兹三角是一种特殊的实例。

贝兹曲线于1962年，由法国工程师皮埃尔·贝兹所广泛发表，他运用贝兹曲线来为汽车的主体进行设计。贝兹曲线最初由保尔·德·卡斯特里奥于1959年运用德卡斯特里奥算法开发，以稳定数值的方法求出贝兹曲线。

## 实例说明

### 线性贝兹曲线

给定点P0、P1，线性贝兹曲线只是一条两点之间的直线。这条线由下式给出：

$$\mathbf{B}(t)=\mathbf{P}_0 + (\mathbf{P}_1-\mathbf{P}_0)t=(1-t)\mathbf{P}_0 + t\mathbf{P}_1 \mbox{ , } t \in [0,1]$$

且其等同于线性插值。

### 二次方贝兹曲线

二次方贝兹曲线的路径由给定点P0、P1、P2的函数B（t）追踪：

$$\mathbf{B}(t) = (1 - t)^{2}\mathbf{P}_0 + 2t(1 - t)\mathbf{P}_1 + t^{2}\mathbf{P}_2 \mbox{ , } t \in [0,1]$$

TrueType字型就运用了以贝兹样条组成的二次贝兹曲线。

### 三次方贝兹曲线

P0、P1、P2、P3四个点在平面或在三维空间中定义了三次方贝兹曲线。曲线起始于P0走向P1，并从P2的方向来到P3。一般不会经过P1或P2；这两个点只是在那里提供方向资讯。P0和P1之间的间距，决定了曲线在转而趋进P2之前，走向P1方向的“长度有多长”。

曲线的参数形式为：

$$\mathbf{B}(t)=\mathbf{P}_0(1-t)^3+3\mathbf{P}_1t(1-t)^2+3\mathbf{P}_2t^2(1-t)+\mathbf{P}_3t^3 \mbox{ , } t \in [0,1]$$

现代的成象系统，如PostScript、Asymptote和Metafont，运用了以贝兹样条组成的三次贝兹曲线，用来描绘曲线轮廓。

## 一般化

$n$阶贝兹曲线可如下推断。给定点P0、P1、...、Pn，其贝兹曲线即

$\mathbf{B}(t)=\sum_{i=0}^n {n\choose i}\mathbf{P}_i(1-t)^{n-i}t^i ={n\choose 0}\mathbf{P}_0(1-t)^nt^{0}+{n\choose 1}\mathbf{P}_1(1-t)^{n-1}t^{1}+\cdots+{n\choose n-1}\mathbf{P}_{n-1}(1-t)^{1}t^{n-1}+{n\choose n}\mathbf{P}_n(1-t)^{0}t^n \mbox{ , } t \in [0,1]$。

例如$n=5$：

$\mathbf{B}(t)=\mathbf{P}_0(1-t)^5+5\mathbf{P}_1t(1-t)^4+10\mathbf{P}_2t^2(1-t)^3+10\mathbf{P}_3t^3(1-t)^2+5\mathbf{P}_4t^4(1-t)+\mathbf{P}_5t^5 \mbox{ , } t \in [0,1]$。

如上公式可如下递归表达：

用$\mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}$表示由点P0、P1、...、Pn所决定的贝兹曲线。则

$$\mathbf{B}(t) = \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}(t) = (1-t)\mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_{n-1}}(t) + t\mathbf{B}_{\mathbf{P}_1\mathbf{P}_2\ldots\mathbf{P}_n}(t)$$

用平常话来说，$n$阶的贝兹曲线，即双$n-1$阶贝兹曲线之间的插值。

### 术语

一些关于参数曲线的术语，有

$$\mathbf{B}(t) = \sum_{i=0}^n \mathbf{P}_i\mathbf{b}_{i,n}(t),\quad t\in[0,1]$$

即多项式

$$\mathbf{b}_{i,n}(t) = {n\choose i} t^i (1-t)^{n-i},\quad i=0,\ldots n$$

又称作n阶的伯恩斯坦基底多项式，定义00 = 1。

点Pi称作贝兹曲线的控制点。多边形以带有线的贝兹点连接而成，起始于P0并以Pn终止，称作贝兹多边形（或控制多边形）。贝兹多边形的凸包（convex hull）包含有贝兹曲线。

### 注解

- 开始于P0并结束于Pn的曲线，即所谓的端点插值法属性。
- 曲线是直线的充分必要条件是所有的控制点都在曲线上。同样的，贝兹曲线是直线的充分必要条件是控制点共线。
- 曲线的起始点（结束点）相切于贝兹多边形的第一节（最后一节）。
- 一条曲线可在任意点切割成两条或任意多条子曲线，每一条子曲线仍是贝兹曲线。
- 一些看似简单的曲线（如圆）无法以贝兹曲线精确的描述，或分段成贝兹曲线（虽然当每个内部控制点对单位圆上的外部控制点水平或垂直的的距离为$4\left(\sqrt{2} -1\right)/3$时，分成四段的贝兹曲线，可以小于千分之一的最大半径误差近似于圆）。
- 位于固定偏移量的曲线（来自给定的贝兹曲线），又称作偏移曲线（假平行于原来的曲线，如两条铁轨之间的偏移）无法以贝兹曲线精确的形成（某些平凡实例除外）。无论如何，现存的启发法通常可为实际用途中给出近似值。

## 构建贝兹曲线

### 线性曲线

<image>

线性贝兹曲线演示动画，t在0,1区间

线性贝兹曲线函数中的t会经过由P0至P1的B（t）所描述的曲线。例如当t=0.25时，B（t）即一条由点P0至P1路径的四分之一处。就像由0至1的连续t，B（t）描述一条由P0至P1的直线。

### 二次曲线

为建构二次贝兹曲线，可以中介点Q0和Q1作为由0至1的t：

- 由P0至P1的连续点Q0，描述一条线性贝兹曲线。
- 由P1至P2的连续点Q1，描述一条线性贝兹曲线。
- 由Q0至Q1的连续点B（t），描述一条二次贝兹曲线。

<image>

｜

<image>

二次贝兹曲线的结构｜二次贝兹曲线演示动画，t在0,1区间

### 高阶曲线

为建构高阶曲线，便需要相应更多的中介点。对于三次曲线，可由线性贝兹曲线描述的中介点Q0、Q1、Q2，和由二次曲线描述的点R0、R1所建构：

<image>

｜

<image>

三次贝兹曲线的结构｜三次贝兹曲线演示动画，t在0,1区间

对于四次曲线，可由线性贝兹曲线描述的中介点Q0、Q1、Q2、Q3，由二次贝兹曲线描述的点R0、R1、R2，和由三次贝兹曲线描述的点S0、S1所建构：

<image>

｜

<image>

四次贝兹曲线的结构｜四次贝兹曲线演示动画，t在0,1区间

还可参阅五阶贝兹曲线的构成：

<image>

五次贝兹曲线演示动画，t在0,1区间

这些运动轨迹使用德卡斯特里奥算法计算出贝塞尔曲线。

## 升阶

n次贝兹曲线可以转换为一个形状完全相同的n+1次贝兹曲线。

这在软件只支援特定阶次的贝兹曲线时很有用。

例如，Cairo只支援三次贝兹曲线，你就可以用升阶的方法在Cairo画出二次贝兹曲线。

我们利用$\mathbf{B}(t) = (1-t)\mathbf{B}(t) + t\mathbf{B}(t)$这个特性来做升阶。我们把曲线方程式中每一项$\mathbf{b}_{i,n}(t)\mathbf{P}_i$都乘上 (1 − t) 或 t，让每一项都往上升一阶。以下是将二阶升为三阶的范例

$$\begin{align} & {} \quad (1 - t)^{2}\mathbf{P}_0 + 2(1 - t)t\mathbf{P}_1 + t^{2}\mathbf{P}_2 \\ & = (1 - t)^{3}\mathbf{P}_0 + (1 - t)^{2}t\mathbf{P}_0 + 2(1 - t)^{2}t\mathbf{P}_1 \\ & {} \qquad + 2(1 - t)t^{2}\mathbf{P}_1 + (1 - t)t^{2}\mathbf{P}_2 + t^{3}\mathbf{P}_2 \\ & = (1 - t)^{3}\mathbf{P}_0 + 3(1 - t)^{2}t\frac{\mathbf{P}_0 + 2\mathbf{P}_1}{3} + 3(1 - t)t^{2}\frac{2\mathbf{P}_1 + \mathbf{P}_2}{3} + t^{3}\mathbf{P}_2 \end{align}$$

对任何的n值，我们都可以使用以下等式

$${n+1 \choose i}(1-t)\mathbf{b}_{i,n} = {n \choose i} \mathbf{b}_{i,n+1}, \quad (1-t)\mathbf{b}_{i,n} = \frac{n+1-i}{n+1} \mathbf{b}_{i,n+1}$$

$${n+1 \choose i+1} t\mathbf{b}_{i,n} = {n \choose i} \mathbf{b}_{i+1,n+1}, \quad t\mathbf{b}_{i,n} = \frac{i+1}{n+1} \mathbf{b}_{i+1,n+1}$$

$$\begin{align} \mathbf{B}(t) & = (1-t)\sum_{i=0}^n \mathbf{b}_{i,n}(t)\mathbf{P}_i + t\sum_{i=0}^n \mathbf{b}_{i,n}(t)\mathbf{P}_i \\ & = \sum_{i=0}^n \frac{n+1-i}{n+1}\mathbf{b}_{i,n+1}(t)\mathbf{P}_i + \sum_{i=0}^n \frac{i+1}{n+1}\mathbf{b}_{i+1,n+1}(t)\mathbf{P}_i \\ & = \sum_{i=0}^{n+1} \left(\frac{i}{n+1}\mathbf{P}_{i-1} + \frac{n+1-i}{n+1}\mathbf{P}_i\right) \mathbf{b}_{i,n+1}(t) = \sum_{i=0}^{n+1} \mathbf{b}_{i,n+1}(t)\mathbf{P'}_i \end{align}$$

式中$\mathbf{P}_{-1}$ 和 $\mathbf{P}_{n+1}$可以任意挑选。

因此，新的控制点为

$$\mathbf{P'}_i = \frac{i}{n+1}\mathbf{P}_{i-1} + \frac{n+1-i}{n+1}\mathbf{P}_i,\quad i=0,\ldots, n+1.$$

## 应用

### 电脑绘图

由于需要点阵化更精细的分辨率时，重新插值（补点）的计算量较小，贝兹曲线被广泛地在计算机图形中用来为平滑曲线建立模型。贝兹曲线是矢量图形文件和相应软件（如PostScript、PDF等）能够处理的唯一曲线，用于光滑地近似其他曲线。

二次和三次贝兹曲线最为常用。

### 程式范例

下列程式码为一简单的实际运用范例，展示如何使用C语言标出三次方贝兹曲线。注意，此处仅简单的计算多项式系数，并读尽一系列由0至1的t值；实践中一般不会这么做，递归求解通常会更快速——以更多的内存为代价，花费较少的处理器时间。不过直接的方法较易于理解并产生相同结果。以下程式码已使运算更为清晰。实践中的最佳化会先计算系数一次，并在实际计算曲线点的循环中反复使用。此处每次都会重新计算，损失了效率，但程式码更清楚易读。

曲线的计算可在曲线阵列上将相连点画上直线——点越多，曲线越平滑。

在部分架构中，下以程式码也可由动态规划进行最佳化。举例来说，dt是一个常数，cx * t则等同于每次反复就修改一次常数。经反复应用这种最佳化后，循环可被重写为没有任何乘法（虽然这个过程不是稳定数值的）。

```c
/*
 產生三次方貝茲曲線的程式碼
*/

typedef struct
{
    float x;
    float y;
}
Point2D;

/*
 cp在此是四個元素的陣列:
 cp[0]為起始點，或上圖中的P0
 cp[1]為第一個控制點，或上圖中的P1
 cp[2]為第二個控制點，或上圖中的P2
 cp[3]為結束點，或上圖中的P3
 t為參數值，0 <= t <= 1
*/

Point2D PointOnCubicBezier( Point2D* cp, float t )
{
    float   ax, bx, cx;
    float   ay, by, cy;
    float   tSquared, tCubed;
    Point2D result;

    /*計算多項式係數*/

    cx = 3.0 * (cp[1].x - cp[0].x);
    bx = 3.0 * (cp[2].x - cp[1].x) - cx;
    ax = cp[3].x - cp[0].x - cx - bx;

    cy = 3.0 * (cp[1].y - cp[0].y);
    by = 3.0 * (cp[2].y - cp[1].y) - cy;
    ay = cp[3].y - cp[0].y - cy - by;

    /*計算位於參數值t的曲線點*/

    tSquared = t * t;
    tCubed = tSquared * t;

    result.x = (ax * tCubed) + (bx * tSquared) + (cx * t) + cp[0].x;
    result.y = (ay * tCubed) + (by * tSquared) + (cy * t) + cp[0].y;

    return result;
}

/*
 ComputeBezier以控制點cp所產生的曲線點，填入Point2D結構的陣列。
 呼叫者必須分配足夠的記憶體以供輸出結果，其為<sizeof(Point2D) numberOfPoints>
*/

void ComputeBezier( Point2D* cp, int numberOfPoints, Point2D* curve )
{
    float   dt;
    int    i;

    dt = 1.0 / ( numberOfPoints - 1 );

    for( i = 0; i < numberOfPoints; i++)
        curve[i] = PointOnCubicBezier( cp, i*dt );
}
```

另一种贝兹曲线的应用是在动画中，描述物件的运动路径等等。此处，曲线的x、y位置不用来标示曲线，但用来表示图形位置。当用在这种形式时，连续点之间的距离会变的更为重要，且大多不是平均比例。点将会串的更紧密，控制点更接近每一个点，而更为稀疏的控制点会散的更开。如果需要线性运动速度，进一步处理时就需要循所需路径将点平均分散。

## 多项式表示法

有时我们可能想要把贝兹曲线表示为多项式，而非比较不直接的伯恩斯坦多项式。使用二项式定理和贝兹曲线的定义，重新整理后可以得到：

$$\mathbf{B}(t) = \sum_{j = 0}^n {t^j \mathbf{C}_j}$$

此处

$$\mathbf{C}_j = \frac{n!}{(n - j)!} \sum_{i = 0}^j \frac{(-1)^{i + j} \mathbf{P}_i}{i! (j - i)!} = \prod_{m = 0}^{j - 1} (n - m) \sum_{i = 0}^j \frac{(-1)^{i + j} \mathbf{P}_i}{i! (j - i)!} .$$

计算曲线上的点时需要多次计算$\mathbf{B}(t)$，因此事先计算好$\mathbf{C}_j$会比较实际；然而要小心高阶曲线可能会缺乏数值稳定性（需使用德卡斯特里奥算法来处理）。注意其空积为1。

## 有理贝兹曲线

<image>

有理贝兹增加可调节的权重，以提供更近似于随意的形状。分子是加权的伯恩斯坦形式贝兹曲线，而分母是加权的伯恩斯坦多项式的总和。

给定n + 1控制点Pi，有理贝兹曲线可如下描述：

$$\mathbf{B}(t) = \frac{ \sum_{i=0}^n b_{i,n}(t) \mathbf{P}_{i}w_i } { \sum_{i=0}^n b_{i,n}(t) w_i }$$

或简单的

$$\mathbf{B}(t) = \frac{ \sum_{i=0}^n {n \choose i} t^i (1-t)^{n-i}\mathbf{P}_{i}w_i } { \sum_{i=0}^n {n \choose i} t^i (1-t)^{n-i}w_i }$$

## 参阅

- 德卡斯特里奥算法
- 样条
- 贝兹样条
- 贝兹曲面
- 贝兹三角
- NURBS
- Bézier curves are also formed by many common forms of string art, where strings are looped across a frame of nails.
- 埃尔米特曲线

## 参考文献

### 来源

- Paul Bourke: Bézier curves, https://web.archive.org/web/20060708162825/http://astronomy.swin.edu.au/%7Epbourke/curves/bezier/
- Donald Knuth: Metafont: the Program, Addison-Wesley 1986, pp. 123–131. Excellent discussion of implementation details; available for free as part of the TeX distribution.
- Dr Thomas Sederberg, BYU Bézier curves, https://web.archive.org/web/20060221000535/http://www.tsplines.com/resources/class_notes/Bezier_curves.pdf
- J.D. Foley et al.: Computer Graphics: Principles and Practice in C (2nd ed., Addison Wesley, 1992)