貝茲曲線

維基百科,自由的百科全書
前往: 導覽搜尋
三次方貝茲曲線

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

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

實例說明[編輯]

線性貝茲曲線[編輯]

給定點P0P1,線性貝茲曲線只是一條兩點之間的直線。這條線由下式給出:

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

且其等同於線性插值

二次方貝茲曲線[編輯]

二次方貝茲曲線的路徑由給定點P0P1P2的函數Bt)追蹤:

\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字型就運用了以貝茲樣條組成的二次貝茲曲線。

三次方貝茲曲線[編輯]

P0P1P2P3四個點在平面或在三維空間中定義了三次方貝茲曲線。曲線起始於P0走向P1,並從P2的方向來到P3。一般不會經過P1P2;這兩個點只是在那裡提供方向資訊。P0P1之間的間距,決定了曲線在轉而趨進P3之前,走向P2方向的「長度有多長」。

曲線的參數形式為:

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

現代的成象系統,如PostScriptAsymptoteMetafont,運用了以貝茲樣條組成的三次貝茲曲線,用來描繪曲線輪廓。

一般化[編輯]

n階貝茲曲線可如下推斷。給定點P0P1、…、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}表示由點P0P1、…、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時,分成四段的貝茲曲線,可以小於千分之一的最大半徑誤差近似於圓)。
  • 位於固定偏移量的曲線(來自給定的貝茲曲線),又稱作偏移曲線(假平行於原來的曲線,如兩條鐵軌之間的偏移)無法以貝茲曲線精確的形成(某些平凡實例除外)。無論如何,現存的啟發法通常可為實際用途中給出近似值。

建構貝茲曲線[編輯]

線性曲線[編輯]

線性貝茲曲線演示動畫,t在[0,1]區間
線性貝茲曲線演示動畫,t在[0,1]區間

線性貝茲曲線函數中的t會經過由P0P1Bt)所描述的曲線。例如當t=0.25時,Bt)即一條由點P0P1路徑的四分之一處。就像由0至1的連續tBt)描述一條由P0P1的直線。

二次曲線[編輯]

為建構二次貝茲曲線,可以中介點Q0Q1作為由0至1的t

  • P0P1的連續點Q0,描述一條線性貝茲曲線。
  • P1P2的連續點Q1,描述一條線性貝茲曲線。
  • Q0Q1的連續點Bt),描述一條二次貝茲曲線。
二次貝茲曲線的結構 二次貝茲曲線演示動畫,t in [0,1]
二次貝茲曲線的結構 二次貝茲曲線演示動畫,t在[0,1]區間

高階曲線[編輯]

為建構高階曲線,便需要相應更多的中介點。對於三次曲線,可由線性貝茲曲線描述的中介點Q0Q1Q2,和由二次曲線描述的點R0R1所建構:

三次貝茲曲線的結構 三次貝茲曲線演示動畫,t in [0,1]
三次貝茲曲線的結構 三次貝茲曲線演示動畫,t在[0,1]區間

對於四次曲線,可由線性貝茲曲線描述的中介點Q0Q1Q2Q3,由二次貝茲曲線描述的點R0R1R2,和由三次貝茲曲線描述的點S0S1所建構:

四次貝茲曲線的結構 四次貝茲曲線演示動畫,t in [0,1]
四次貝茲曲線的結構 四次貝茲曲線演示動畫,t在[0,1]區間

還可參閱五階貝茲曲線的構成:

五次貝茲曲線演示動畫
五次貝茲曲線演示動畫,t在[0,1]區間

這些運動軌跡使用de Casteljau演算法計算出貝茲曲線。[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}可以任意挑選。

因此,新的控制點為[2]

\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則等同於每次反覆就修改一次常數。經反覆應用這種最佳化後,迴圈可被重寫為沒有任何乘法(雖然這個過程不是穩定數值的)。

/*
 產生三次方貝茲曲線的程式碼
*/
 
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會比較實際;然而要小心高階曲線可能會缺乏數值穩定性(需使用De Casteljau演算法來處理)。注意其empty product為1。

有理貝茲曲線[編輯]

有理貝茲曲線的示例

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

給定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
}

參閱[編輯]

參考文獻[編輯]

  1. ^ Shene, C.K. Finding a Point on a Bézier Curve: De Casteljau's Algorithm. [6 September 2012]. 
  2. ^ Farin, Gerald, Curves and surfaces for computer-aided geometric design. 4, Elsevier Science & Technology Books. 1997, ISBN 978 0 12249054 5 

外部連結[編輯]