畫Bezier曲線：Casteljau算法

​

德卡斯特裡奧算法可以計算貝塞爾曲線上的點C(u)，u∈[0,1]。是以，通過給定一組u的值，便可以計算出貝塞爾曲線上的坐标序列，進而繪制出貝塞爾曲線。

德卡斯特裡奧算法的基礎就是在向量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 + B * u。

       定義貝塞爾曲線的控制點Pi編号為0i，其中，0表示是第0次疊代。當第一、二、三……次疊代時，0将會被1、2、3……替換。

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

如上圖，曲線控制點是00、01、02、03、04、05。線段00-01上取點10，10分該線段的比為u:1-u，類似地取點11、12、13、14，然後第二次疊代線上段10-11上取點20，點20分該線段的比為u:1-u，類似地取點21、22、23。然後進行下一次疊代，依次類推，直到最後線上段40-41上取點50，50是最終惟一的點，也是在曲線上的點。

上述直覺的算法描述可以表達成一個計算方法。 

首先，将所有給定的控制點排列成一列，在上圖中，即為最左邊的一列。每一對相鄰的控制點可以伸出兩個箭頭，分别指向右下方和右上方。在相鄰箭頭的交叉處，生成一個新的控制點。例如，控制點ij和i(j +1)生成新的控制點(i + 1)j。指向右下方的箭頭表示乘以(1 - u)，指向右上方的箭頭表示乘以u。

是以，通過第0列，可以求出第1列，然後求出第2列……，最終，在n次疊代後，可以到達惟一的一個點n0，這個點就是曲線上的點。

根據上述方法，我們可以根據給定的精度來确定一組u，根據u來計算貝塞爾曲線的一組坐标值。

void deCasteljau3D(pointArray& ctrlPts, int precision) {
    int n = ctrlPts.length;
    if (n < 2)return;
    float* xarray = new float[n - 1];
    float* yarray = new float[n - 1];
    float* zarray = new float[n - 1];
    float x = ctrlPts.arr[0].x;
    float y = ctrlPts.arr[0].y;
    float z = ctrlPts.arr[0].z;

    for (int k = 0; k <= precision; k++) {//根據計算出的坐标連線precision次
        float u = float(k) / float(precision);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < n - i; ++j) {
                if (i == 1) {//第一次疊代根據控制點得出
                    xarray[j] = ctrlPts.arr[j].x * (1 - u)
                        + ctrlPts.arr[j + 1].x * u;
                    yarray[j] = ctrlPts.arr[j].y * (1 - u)
                        + ctrlPts.arr[j + 1].y * u;
                    zarray[j] = ctrlPts.arr[j].z * (1 - u)
                        + ctrlPts.arr[j + 1].z * u;
                }
                else {//通過上一次疊代結果計算
                    xarray[j] = xarray[j] * (1 - u) + xarray[j + 1] * u;
                    yarray[j] = yarray[j] * (1 - u) + yarray[j + 1] * u;
                    zarray[j] = zarray[j] * (1 - u) + zarray[j + 1] * u;
                }
            }
        }
        glColor3f(0.0f, 1.0f, 1.0f);
        glBegin(GL_LINES);
        glVertex3f(x, y,z);
        glVertex3f(xarray[0], yarray[0],zarray[0]);
        glEnd();
        x = xarray[0];
        y = yarray[0];
        z = zarray[0];
    }
    delete[] xarray;
    delete[] yarray;
    delete[] zarray;
}