贝塞尔曲线

维库，知识与思想的自由文库

TA▼▲

三次方贝塞尔曲线

在數學的數值分析領域中，贝塞尔曲线（Bézier curve）是電腦圖形學中相當重要的參數曲線。更高維度的廣泛化贝塞尔曲线就稱作貝茲曲面，其中貝茲三角是一種特殊的實例。

贝塞尔曲线於1962年，由法國工程師皮埃爾·貝茲所廣泛發表，他運用贝塞尔曲线來為汽車的主體進行設計。贝塞尔曲线最初由 Paul de Casteljau 於1959年運用 de Casteljau 演算法開發，以穩定數值的方法求出贝塞尔曲线。

[编辑] 實例說明

[编辑] 線性贝塞尔曲线

給定點 P₀、P₁，線性贝塞尔曲线只是一條兩點之間的直線。這條線由下式給出︰

$\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]$

且其等同於線性插值。

[编辑] 二次方贝塞尔曲线

二次方贝塞尔曲线的路徑由給定點 P₀、P₁、P₂ 的函數 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 字型就運用了以貝茲樣條組成的二次贝塞尔曲线。

[编辑] 三次方贝塞尔曲线

P₀、P₁、P₂、P₃ 四個點在平面或在三維空間中定義了三次方贝塞尔曲线。曲線起始於 P₀ 走向 P₁，並從 P₂ 的方向來到 P₃。一般不會經過 P₁ 或 P₂；這兩個點只是在那裡提供方向資訊。 P₀ 和 P₁ 之間的間距，決定了曲線在轉而趨進 P₃ 之前，走向 P₂ 方向的「長度有多長」。

曲線的參數形式為︰

$\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$ 階贝塞尔曲线可如下推斷。給定點 P₀、P₁、…、P_n，其贝塞尔曲线即

$\mathbf{B}(t)=\sum_{i=0}^n {n\choose i}\mathbf{P}_i(1-t)^{n-i}t^i =\mathbf{P}_0(1-t)^n+{n\choose 1}\mathbf{P}_1(1-t)^{n-1}t+\cdots+\mathbf{P}_nt^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}$ 表示由點 P₀、P₁、…、P_n 所決定的贝塞尔曲线。則

$\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 階的伯恩斯坦基底多項式，定義 0⁰ = 1。

點 P_i 稱作贝塞尔曲线的控制點。多邊形以帶有線的貝茲點連接而成，起始於 P₀ 並以 P_n 終止，稱作貝茲多邊形（或控制多邊形）。貝茲多邊形的凸包（convex hull）包含有贝塞尔曲线。

[编辑] 註解

開始於 P₀ 並結束於 P_n 的曲線，即所謂的端點插值法屬性。
曲線是直線的充分必要條件是所有的控制點都位在曲線上。同樣的，贝塞尔曲线是直線的充分必要條件是控制點共線。
曲線的起始點（結束點）相切於貝茲多邊形的第一節（最後一節）。
一條曲線可在任意點切割成兩條或任意多條子曲線，每一條子曲線仍是贝塞尔曲线。
一些看似簡單的曲線（如圓）無法以贝塞尔曲线精確的描述，或分段成贝塞尔曲线（雖然當每個內部控制點對單位圓上的外部控制點水平或垂直的的距離為 $4\left(\sqrt{2} -1\right)/3$ 時，分成四段的贝塞尔曲线，可以小於千分之一的最大半徑誤差近似於圓）。
位於固定偏移量的曲線（來自給定的贝塞尔曲线），又稱作偏移曲線（假平行於原來的曲線，如兩條鐵軌之間的偏移）無法以贝塞尔曲线精確的形成（某些瑣屑實例除外）。無論如何，現存的啟發法通常可為實際用途中給出近似值。

[编辑] 建構贝塞尔曲线

[编辑] 線性曲線

線性贝塞尔曲线演示動畫，t in [0,1]

線性贝塞尔曲线函數中的 t 會經過由 P₀ 至 P₁ 的 B(t) 所描述的曲線。例如當 t=0.25 時，B(t) 即一條由點 P₀ 至 P₁ 路徑的四分之一處。就像由 0 至 1 的連續 t，B(t) 描述一條由 P₀ 至 P₁ 的直線。

[编辑] 二次曲線

為建構二次贝塞尔曲线，可以中介點 Q₀ 和 Q₁ 作為由 0 至 1 的 t︰

由 P₀ 至 P₁ 的連續點 Q₀，描述一條線性贝塞尔曲线。
由 P₁ 至 P₂ 的連續點 Q₁，描述一條線性贝塞尔曲线。
由 Q₀ 至 Q₁ 的連續點 B(t)，描述一條二次贝塞尔曲线。


二次贝塞尔曲线的結構		二次贝塞尔曲线演示動畫，t in [0,1]

[编辑] 高階曲線

為建構高階曲線，便需要相應更多的中介點。對於三次曲次，可由線性贝塞尔曲线描述的中介點 Q₀、Q₁、Q₂，和由二次曲線描述的點 R₀、R₁ 所建構︰


三次贝塞尔曲线的結構		三次贝塞尔曲线演示動畫，t in [0,1]

對於四次曲線，可由線性贝塞尔曲线描述的中介點 Q₀、Q₁、Q₂、Q₃，由二次贝塞尔曲线描述的點 R₀、R₁、R₂，和由三次贝塞尔曲线描述的點 S₀、S₁ 所建構︰


四次贝塞尔曲线的結構		四次贝塞尔曲线演示動畫，t in [0,1]

（還可參閱五階贝塞尔曲线的構成。）

[编辑] 應用

[编辑] 電腦繪圖

Bézier path in Adobe Illustrator CS2

Example of two cubic Bézier curves patched together (solid) compared to a 6th degree Bézier curve

Bézier curves are widely used in computer graphics to model smooth curves. As the curve is completely contained in the convex hull of its control points, the points can be graphically displayed and used to manipulate the curve intuitively. Affine transformations such as translation, scaling and rotation can be applied on the curve by applying the respective transform on the control points of the curve.

Quadratic and cubic Bézier curves are most common; higher degree curves are more expensive to evaluate. When more complex shapes are needed, low order Bézier curves are patched together. This is commonly referred to as a "path" in programs like Adobe Illustrator or Inkscape. These poly-Bézier curves can also be seen in the SVG file format. To guarantee smoothness, the control point at which two curves meet and one control point on either side must be collinear.

The simplest method for scan converting (rasterizing) a Bézier curve is to evaluate it at many closely spaced points and scan convert the approximating sequence of line segments. However, this does not guarantee that the rasterized output looks sufficiently smooth, because the points may be spaced too far apart. Conversely it may generate too many points in areas where the curve is close to linear. A common adaptive method is recursive subdivision, in which a curve's control points are checked to see if the curve approximates a line segment to within a small tolerance. If not, the curve is subdivided parametrically into two segments, $0 \le t \le 0.5$ and $0.5 \le t \le 1$ and the same procedure applied to recursively to each half. There are also forward differencing methods, but great care must be taken to analyse error propagation. Analytical methods where a spline is intersected with each scan line involve finding roots of cubic polynomials (for cubic splines) and dealing with multiple roots, so they are not often used in practice.

[编辑] 程式範例

下列程式碼為一簡單的實際運用範例，展示如何使用 C 標出三次方贝塞尔曲线。注意，此處僅簡單的計算多項式係數，並讀盡一系列由 0 至 1 的 t 值；實踐中一般不會這麼做，遞歸求解通常會更快速－－以更多的記憶體為代價，花費較少的處理器時間。不過直接的方法較易於理解並產生相同結果。以下程式碼已使運算更為清晰。實踐中的最佳化會先計算係數一次，並在實際計算曲線點的迴圈中反複使用。此處每次都會重新計算，損失了效率，但程式碼更清楚易讀。

曲線的計算可在曲線陣列上將相連點畫上直線－－點越多，曲線越平滑。

在部分架構中，下以程式碼也可由動態程式設計進行最佳化。舉例來說，dt 是一個常數，cx * t 則等同於每次反覆就修改一次常數。經反覆應用這種最佳化後，迴圈可被重寫為沒有任何乘法（雖然這個過程不是穩定數值的）。

/*
 產生三次方贝塞尔曲线的程式碼
*/

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 位置不用來標示曲線，但用來表示圖形位置。當用在這種形式時，連續點之間的距離會變的更為重要，且大多不是平均比例。點將會串的更緊密，控制點更接近每一個點，而更為稀疏的控制點會散的更開。如果需要線性運動速度，進一步處理時就需要循所需路徑將點平均分散。

[编辑] 有理贝塞尔曲线

有理貝茲增加可調節的權重，以提供更近似於隨意的形狀。分子是加權的伯恩斯坦形式贝塞尔曲线，而分母是加權的伯恩斯坦多項式的總和。

給定 n + 1 控制點 P_i，有理贝塞尔曲线可如下描述︰

$\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 }$

[编辑] 參閱

de Casteljau算法
樣條
貝茲樣條
貝茲曲面
貝茲三角
NURBS
string art，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, http://astronomy.swin.edu.au/~pbourke/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, 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)

[编辑] 外部連結

贝塞尔曲线互動 applet
三階贝塞尔曲线 applet
即時數學貝茲 applet
各種樣條類型的即時數學貝茲 applet，樣條的 JAVA 程式設計在互動式介紹樣條
Don Lancaster 的三次方樣條庫，敘述如何用贝塞尔曲线畫出近似圓（或圓弧、雙曲線）；使用三次方樣條進行影像插值，並說明曲線背後的數學原理。
埃立克·魏爾斯史甸在MathWorld中所描述之贝塞尔曲线。

Module for Bezier Curves by John H. Mathews
二次方贝塞尔曲线的建構，互動式 applet 顯示如何建構二次方贝塞尔曲线。（需要 Java）
三次方贝塞尔曲线的建構，互動式 applet 顯示如何建構三次方贝塞尔曲线。（需要 Java）
貝茲 / 拋物線，互動式 applet 顯示二次方贝塞尔曲线和拋物線之間的關係。（需要 Java）
PolyBezier，微軟Win32 图形设备接口 API函式，可在Windows圖形應用程式中繪製贝塞尔曲线，如MS Paint。
找出雙贝塞尔曲线所有的交叉點，找出雙贝塞尔曲线之間的交叉點是一件困難的一般性問題，because of the variety of degenerate cases. By Richard J. Kinch。
SketchPad，使用 C 和 Win32 撰寫的小程式，實作出建立和編輯贝塞尔曲线的功能。也示範使用 de Casteljau 演算法切割贝塞尔曲线。
Hermite與Bezier曲線繪製方法
北斗星君簡介贝塞尔曲线
CAD/CAM基礎於逆向工程技術之研究，36 頁︰3-1 Bezier 曲線/曲面之數學式。

来自“http://www.wikilib.com/wiki/%E8%B2%9D%E8%8C%B2%E6%9B%B2%E7%B7%9A”

个人工具