Android 貝塞爾曲線原理及其繪制實作

• • • 什麼是貝塞爾曲線
    • 貝塞爾曲線示範
    • 德卡斯特裡奧算法原理
    • 貝塞爾曲線繪制原理
    • Android 貝塞爾曲線計算及繪制
    • 其他

Android動畫，特别是涉及運動軌迹的，很多時候都會使用貝塞爾曲線，下面将系統的介紹下貝塞爾曲線的相關知識。

什麼是貝塞爾曲線

貝塞爾曲線于1962年，由法國工程師皮埃爾·貝茲（Pierre Bézier）所廣泛發表，他運用貝塞爾曲線來為汽車的主體進行設計。貝塞爾曲線最初由保爾·德·卡斯特裡奧于1959年運用德卡斯特裡奧算法開發，以穩定數值的方法求出貝塞爾曲線。

下文我們将簡要介紹德卡斯特裡奧算法，并利用其實作繪制貝塞爾曲線。

貝塞爾曲線示範

一階曲線，即線性曲線：

二階曲線：

三階曲線：

四階曲線：

五階曲線：

這些運動軌迹使用德卡斯特裡奧算法計算出貝塞爾曲線。

一些值得關注的特性：

• 開始于P0并結束于Pn的曲線，即所謂的端點插值法屬性。
• 曲線是直線的充分必要條件是所有的控制點都位在曲線上。同樣的，貝塞爾曲線是直線的充分必要條件是控制點共線。
• 曲線的起始點（結束點）相切于貝塞爾多邊形（下稱折線）的第一段（最後一段）。
• 一條曲線可在任意點切割成兩條或任意多條子曲線，每一條子曲線仍是貝塞爾曲線。

德卡斯特裡奧算法原理

在向量AB上選擇一個點C，使得C分向量AB為u：1-u（即|AC|：|AB|=u）。給定點A、B的坐标以及u（u∈[0,1]）的值，點C的坐标則為C=A+(B-A)*u=（1-u）A+uB。

貝塞爾曲線繪制原理

貝塞爾曲線是用一系列點來控制曲線狀态，這些點分别是起點，終點和控制點，貝塞爾曲線可以簡單了解為小球從起點出發，在外力（控制點）的作用下做曲線運動。

為了計算n階貝塞爾曲線上的點C(u)，u∈[0,1]，首先将控制點連接配接形成一條折線10 - 11 - 12······ - 1(n-1) - 1n，利用德卡斯特裡奧算法算法，計算出折線中每條線段 0j - 0(j+1)上的一個點1j，使得點1j分該線段的比為u:1-u，然後在折線 10 - 11 - 12 - ······ -1(n-1) 上遞歸調用該算法，以此類推。最終求得一個點n0，已證明點n0一定是曲線上的點。

為了友善程式設計，我們可以将上述幾何表達轉換為算術表達，如下圖：

如上圖所示，将所有控制點排成一列，每一對相鄰的控制點之間畫出兩個箭頭，分别指向右下方和右上方，指向右下方的箭頭表示乘以(1-u)，指向右上方的箭頭表示乘以u。在兩個箭頭交彙的位置記下一個新的點。比如控制點0n和0(n-1)生成新的控制點1(n-1)。

僞代碼表述如下：

n：代表曲線點最大坐标
Q[0:n]: 曲線控制點坐标
輸出： 貝塞爾曲線點坐标

for k := 1 to n do 
	for i := 0 to n - k do 
		Q[i] := (1 - u)Q[i] + u Q[i + 1];
return Q[0];
           

上述計算也可以用遞歸表示，從德卡斯特裡奧算法可知：

Pi,j 為折線ij上控制點确定的控制點，Pi,j是(1-u)Pi-1,j和uPi-1,j+1的和。最終結果（即曲線上的點）是Pn,0。僞代碼表述如下：

P(i,j) : 代表折線ij段控制點的坐标

function deCasteljau(i,j)
begin
	if i = 0 then
		return P(0,j)
	else
		return (1-u)* deCasteljau(i-1,j) + u* deCasteljau(i-1,j+1)
end
           

雖然遞歸方式看起來簡短，但卻是非常低效，這是因為，遞歸導緻了許多重複的調用，這将導緻計算複雜度呈指數級增長。

Android 貝塞爾曲線計算及繪制

Android原生提供了繪制1到3階貝塞爾曲線的方法：

//繪制一階曲線
public void lineTo(float x, float y)  //目前點到點（x,y）的直線

//繪制二階曲線
public void quadTo(float x1, float y1, float x2, float y2)   //絕對位置畫法，（x,y）為控制點坐标
public void rQuadTo(float dx1, float dy1, float dx2, float dy2)    // 相對位置畫法，（x,y）為控制點相對起點坐标

//繪制三階曲線
public void cubicTo(float x1, float y1, float x2, float y2,   float x3, float y3)   //絕對位置畫法，（x,y）為控制點坐标
public void rCubicTo(float x1, float y1, float x2, float y2,  float x3, float y3)    // 相對位置畫法，（x,y）為控制點相對起點坐标
           

四階以上曲線繪制，根據上一節《貝塞爾曲線繪制原理》的介紹，這裡提供非遞歸和遞歸兩種方法，推薦使用非遞歸方式：

/**
 * 根據德卡斯特裡奧算法計算t時刻貝塞爾曲線的點的值 {x或y}，非遞歸實作
 *
 * @param u 時間 {0~1}
 * @param values 貝塞爾點（控制點和終點）集合 {x或y}
 * @return u時刻貝塞爾曲線所處的點坐标
 */
private float deCasteljau(float u, float... values){
    final int n = values.length;
    for (int k = 1; k < n; k++) {
        for (int j = 0; j < k; j++) {
            values[j] = values[j]+(values[j+1] - values[j])*u;
        }
    }
    //運算結果儲存第一位
    return values[0];
}

/**
 * 根據德卡斯特裡奧算法計算t時刻貝塞爾曲線的點的值 {x或y}，非遞歸實作
 *
 * @param endIndex 貝塞爾曲線結束點集合下标
 * @param startIndex  貝塞爾曲線起點集合下标
 * @param u 時間 {0~1}
 * @param values 貝塞爾點（控制點和終點）集合 {x或y}
 * @return  u時刻貝塞爾曲線點坐标 {x或y}
 */
private float deCasteljau2(int startIndex, int endIndex, float u, float... values){
    if (endIndex == 1){
        return (1-u)*values[startIndex] + u*values[startIndex+1];
    } else {
        return (1 - u) * deCasteljau2(startIndex, endIndex - 1, u,values) + u*deCasteljau2(startIndex + 1, endIndex - 1, u,values);
    }
}
           

下面是分别用原生，遞歸和非遞歸方法畫的三個曲線，效果還不錯：

順便貼下繪制的相關繪制代碼：

path.moveTo(200,600);
//三階貝塞爾曲線
path.cubicTo(400,300,600,900,800,600);
//path.rCubicTo(200,-300,400,300,600,0);

//畫筆下移
path.moveTo(200,1000);
//計算貝塞爾曲線值方法一,坐标數組包含{起點 - 控制點 - 終點}
float[] xPoints = new float[]{200,400,600,800};
float[] yPoints = new float[]{1000,700,1300,1000};

int fps = 1000;
float delta = 1.0f/fps;
for (float progress = 0; progress <= 1; progress += delta) {
    float x = deCasteljau(progress,xPoints);
    float y = deCasteljau(progress,yPoints);
    path.lineTo(x,y);
}

//畫筆下移
path.moveTo(200,1400);
//計算貝塞爾曲線值方法一,坐标數組包含{起點 - 控制點 - 終點}
xPoints = new float[]{200,400,600,800};
yPoints = new float[]{1400,1100,1700,1400};

int endIndex = xPoints.length-1;
for (float progress = 0; progress <= 1; progress += delta) {
    float x = deCasteljau2(0,endIndex,progress,xPoints);
    float y = deCasteljau2(0,endIndex,progress,yPoints);
    path.lineTo(x,y);
}
           

Demo已經上傳到GitHub,點選擷取。

其他

Android源碼中二階和三階都是直接用點計算而不适用

for

循環，效率較佳，動畫插值器

PathInterpolator

就是利用賽貝爾曲線實作的，N階賽貝爾曲線計算可以考慮放在Native層，以提升效率。

參考：

Finding a Point on a Bézier Curve: De Casteljau’s Algorithm

貝塞爾曲線 - 中文維基百科

德卡斯特裡奧算法 - 中文維基百科

貝塞爾曲線學習筆記