貝茲曲線

在數學的數值分析領域中，貝茲曲線是計算機圖形學中相當重要的引數曲線。更高維度的廣泛化貝茲曲線就稱作，其中是一種特殊的例項。貝茲曲線於1962年，由法國工程師皮埃爾·貝茲所廣泛發表，他運用貝茲曲線來為汽車的主體進行設計。貝茲曲線最初由於1959年運用德卡斯特里奧演演算法開發，以穩定數值的方法求出貝茲曲線。例項說明.線性貝茲曲線.給定點P0、P1，線性貝茲曲線只是一條兩點之間的直線。這條線由下式給出：formula_1且其等同於線性插值。二次方貝茲曲線.二次方貝茲曲線的路徑由給定點P0、P1、P2的函式B追蹤：formula_2TrueType字型就運用了以貝茲樣條組成的二次貝茲曲線。三次方貝茲曲線.P0、P1、P2、P3四個點在平面或在三維空間中定義了三次方貝茲曲線。曲線起始於P0走向P1，並從P2的方向來到P3。一般不會經過P1或P2；這兩個點只是在那裡提供方向資訊。P0和P1之間的間距，決定了曲線在轉而趨進P2之前，走向P1方向的「長度有多長」。曲線的引數形式為：formula_3現代的成象系統，如PostScript、Asymptote和Metafont，運用了以貝茲樣條組成的三次貝茲曲線，用來描繪曲線輪廓。一般化.formula_4階貝茲曲線可如下推斷。給定點P0、P1、…、Pn，其貝茲曲線即formula_5。例如formula_6：formula_7。如上公式可如下遞迴表達：用formula_8表示由點P0、P1、…、Pn所決定的貝茲曲線。則formula_9用平常話來說，formula_4階的貝茲曲線，即雙formula_11階貝茲曲線之間的插值。術語.一些關於引數曲線的術語，有formula_12即多項式formula_13又稱作"n"階的伯恩斯坦基底多項式，定義00 = 1。點P"i"稱作貝茲曲線的控制點。多邊形以帶有線的貝茲點連線而成，起始於P0並以P"n"終止，稱作貝茲多邊形包含有貝茲曲線。建構貝茲曲線.線性曲線.線性貝茲曲線函式中的"t"會經過由P0至P1的B描述一條由P0至P1的直線。二次曲線.為建構二次貝茲曲線，可以中介點Q0和Q1作為由0至1的"t"：高階曲線.為建構高階曲線，便需要相應更多的中介點。對於三次曲線，可由線性貝茲曲線描述的中介點Q0、Q1、Q2，和由二次曲線描述的點R0、R1所建構：對於四次曲線，可由線性貝茲曲線描述的中介點Q0、Q1、Q2、Q3，由二次貝茲曲線描述的點R0、R1、R2，和由三次貝茲曲線描述的點S0、S1所建構：還可階貝茲曲線的構成：這些運動軌跡使用de Casteljau演演算法計算出貝塞爾曲線。升階."n"次貝茲曲線可以轉換為一個形狀完全相同的"n+1"次貝茲曲線。這在軟體只支援特定階次的貝茲曲線時很有用。例如，Cairo只支援三次貝茲曲線，你就可以用升階的方法在Cairo畫出二次貝茲曲線。我們利用formula_15這個特性來做升階。我們把曲線方程式中每一項formula_16都乘上 (1 − "t") 或 "t"，讓每一項都往上升一階。以下是將二階升為三階的範例formula_17對任何的"n"值，我們都可以使用以下等式formula_18formula_19formula_20式中formula_21 和 formula_22可以任意挑選。因此，新的控制點為formula_23應用.電腦繪圖.由於需要點陣化更精細的解析度時，重新插值能夠處理的唯一曲線，用於光滑地近似其他曲線。二次和三次貝茲曲線最為常用。程式範例.下列程式碼為一簡單的實際運用範例，展示如何使用C語言標出三次方貝茲曲線。注意，此處僅簡單的計算多項式係數，並讀盡一系列由0至1的t值；實踐中一般不會這麼做，遞迴求解通常會更快速——以更多的記憶體為代價，花費較少的處理器時間。不過直接的方法較易於理解並產生相同結果。以下程式碼已使運算更為清晰。實踐中的最佳化會先計算係數一次，並在實際計算曲線點的迴圈中反複使用。此處每次都會重新計算，損失了效率，但程式碼更清楚易讀。曲線的計算可在曲線陣列上將相連點畫上直線——點越多，曲線越平滑。在部分架構中，下以程式碼也可由動態規劃進行最佳化。舉例來說，"dt"是一個常數，"cx" * "t"則等同於每次反覆就修改一次常數。經反覆應用這種最佳化後，迴圈可被重寫為沒有任何乘法。/*產生三次方貝茲曲線的程式碼typedef structfloat x;float y;Point2D;cp在此是四個元素的陣列:cp[0]為起始點，或上圖中的P0cp[1]為第一個控制點，或上圖中的P1cp[2]為第二個控制點，或上圖中的P2cp[3]為結束點，或上圖中的P3t為引數值，0 &lt;= t &lt;= 1Point2D 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結構的陣列。呼叫者必須分配足夠的記憶體以供輸出結果，其為void ComputeBezier( Point2D* cp, int numberOfPoints, Point2D* curve )float dt;int i;dt = 1.0 / ( numberOfPoints - 1 );for( i = 0; i &lt; numberOfPoints; i++)curve[i] = PointOnCubicBezier( cp, i*dt );另一種貝茲曲線的應用是在動畫中，描述物件的運動路徑等等。此處，曲線的x、y位置不用來標示曲線，但用來表示圖形位置。當用在這種形式時，連續點之間的距離會變的更為重要，且大多不是平均比例。點將會串的更緊密，控制點更接近每一個點，而更為稀疏的控制點會散的更開。如果需要線性運動速度，進一步處理時就需要循所需路徑將點平均分散。多項式表示法.有時我們可能想要把貝茲曲線表示為多項式，而非比較不直接的伯恩斯坦多項式。使用二項式定理和貝茲曲線的定義，重新整理後可以得到：formula_24此處formula_25計算曲線上的點時需要多次計算formula_26，因此事先計算好formula_27會比較實際；然而要小心高階曲線可能會缺乏數值穩定性。注意其空積為1。有理貝茲曲線.有理貝茲增加可調節的權重，以提供更近似於隨意的形狀。分子是加權的伯恩斯坦形式貝茲曲線，而分母是加權的伯恩斯坦多項式的總和。給定"n" + 1控制點P"i"，有理貝茲曲線可如下描述：formula_28或簡單的formula_29