图形算法：贝塞尔曲线

算法

版本：1
作者：陈小默
声明：禁止商用，禁止转载

发布于：作业部落、CSDN博客

---

一、什么是贝塞尔曲线

贝塞尔曲线是依据任意位置的点坐标绘制出的一条光滑曲线。其设计思路是按照规律u从0到1的移动过程中，在各个控制点连线的相应位置取点，并对相邻两条线上的点再次连线，重复以上过程使得没有可连接的两个点。

对于 图3.1.1-1 点J就是由A、B、C和D四个点所控制的贝塞尔曲线的在规律u时的轨迹点。u从0变化到1时示例如下：

二、贝塞尔曲线的数学推导过程

这里我们以二阶，也就是由三个坐标点控制的曲线为例，参考下图：

设A点坐标为 $(x_0,y_0)$ ，B点坐标为 $(x_1,y_1)$，C点坐标为 $(x_2,y_2)$，D点坐标为 $(x_0'(u),y_0'(u))$，E点坐标为 $(x_1'(u),y_1'(u))$，F点坐标为 $(x(u),y(u))$

$$x_0'(u)=u(x_1-x_0)+x_0 \\=ux_1+(1-u)x_0 \tag{3.1.2.1}$$

以此类推

$$x_1'(u)=ux_2+(1-u)x_1 \tag{3.1.2.2}$$

$$y_0'(u)=uy_1+(1-u)y_0 \tag{3.1.2.3}$$

$$y_1'(u)=uy_2+(1-u)y_1 \tag{3.1.2.4}$$

通过连接D、E两点得到线段DE，求点F的x轴坐标

$$x(u) =u\{x_1'(u)-x_0'(u)\}+x_0'(u) \\ =ux_1'(u) + (1-u)x_0'(u)\\ =(1-u)^2x_0+2u(1-u)x_1+u^2x_2\\ =\sum_{k=0}^2 x_kC_2^ku^k(1-u)^{2-k} \tag{3.1.2.5}$$

其中的与坐标轴无关项被称为贝塞尔多项式函数(贝塞尔方程)

$$BEZ_{k,n}(u)=C_n^ku^k(1-u)^{n-k}\tag{3.1.2.6}$$

对于式(3.1.2.5)可以使用式(3.1.2.6)扩展为任意阶数的贝塞尔公式

$$x(u) =\sum_{k=0}^n x_kBEZ_{k,n}(u) \tag{3.1.2.7}$$

$$y(u) =\sum_{k=0}^n y_kBEZ_{k,n}(u) \tag{3.1.2.8}$$

假如我们使用的是三位曲线，还可以扩展Z坐标轴

$$z(u) =\sum_{k=0}^n z_kBEZ_{k,n}(u) \tag{3.1.2.9}$$

三、使用C\C++语言实现贝塞尔曲线的计算过程

思路：由于贝塞尔曲线由控制点控制，在计算完成前我们无法确切的知道曲线路径上将要绘制的像素点个数，所以我们可以采取逼近的策略，即将计算出的相邻两点使用直线连接，已达到近似效果。以下过程使用C语言实现

//该类用来存储三维坐标
typedef struct{
    float x,y,z;
}point3D;
//整型数组
typedef struct{
    int length;
    int * arr;
}intArray;
//坐标数组
typedef struct{
    int length;
    point3D * arr;
}pointArray;
//该方法接受经过计算的贝塞尔点，并对相邻两个点进行连线处理
void drawLine(pointArray &bezPts);
//此方法用来计算二项式系数
//接受一个数组对象的引用
void binomialCoefficient(intArray &C){
    int j,n=C.length-1;
    for(int k=0;k<=n;k++){
        C.arr[k] = 1;
        for(j=n;j>k;j--)
            C.arr[k] *= j;//分子累乘
        for(j=n-k;j>1;j--)
            C.arr[k] /= j;//分母累除
    }
}
//此方法计算在第规律u处点的坐标位置
//接受的第一个参数为规律u，第二个参数为将要存放位置点的指针，第三个参数为所有控制点坐标数组，第五个参数为系数数组)
void computeBezPt(float u,point3D &bezPt,pointArray &ctrlPts,intArray &C){
    int n=ctrlPts.length-1;
    float bezFcn;//保存贝塞尔方程计算结果
    bezPt.x=bezPt.y=bezPt.z=0;//初始化
    for(int k=0;k<=n;k++){
        bezFcn = C.arr[k]*pow(u,k)*pow(1-u,n-k);
        bezPt.x+=ctrlPts.arr[k].x*bezFcn;
        bezPt.y+=ctrlPts.arr[k].y*bezFcn;
        bezPt.z+=ctrlPts.arr[k].z*bezFcn;
    }
}
//此方法为调用方法，用来产生贝塞尔曲线
//第一个参数用来接受控制点数组，第二个参数为精度，精度越高两个点之间的距离越小，但是需要的计算时间也就越长
void bezier(pointArray &ctrlPts,int precision){
    intArray C;
    C.length=ctrlPts.length;
    C.arr = new int[C.length];
    binomialCoefficient(C);//计算系数
    pointArray bezPts;//保存计算点的参数
    bezPts.length=precision+1;
    bezPts.arr = new point3D[bezPts.length];
    float u;//规律参数
    for(int k=0;k<=precision;k++){
        u = float(k)/float(precision);
        computeBezPt(u,bezPts.arr[k],ctrlPts,C);
    }
    drawLine(bezPts);
    delete[] bezPts.arr;
    delete[] C.arr;
}

以上就是贝塞尔曲线的实现过程，这里的绘制直线函数没有定义，我们可以使用其他的图形软件包去实现连线过程。下面展示使用OpenGL的GLUT软件包的实现过程。仅供参考

void drawLine(pointArray &bezPts){
    glBegin(GL_LINE_STRIP);
    for(int i=0;i<bezPts.length;i++){
        glVertex3f(bezPts.arr[i].x,bezPts.arr[i].y,bezPts.arr[i].z);
    }
    glEnd();
}
static pointArray ctrlPts_;
void displayFcn(void){
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(1,0,0);
    bezier(ctrlPts_,100);
    glFlush();
}
int main(int argc, char* argv[]){
    ctrlPts_.length = 4;
    point3D ctrlPts[4] = {{-40,-40,0},{-10,200,0},{10,-200,0},{40,40,0}};
    ctrlPts_.arr= ctrlPts;
    glutInit(&argc,argv);
    glutInitDisplayMode(GLUT_SINGLE|GLUT_RGBA);
    glutInitWindowPosition(50,50);
    glutInitWindowSize(600,600);
    glutCreateWindow("bezier curve");
    glClearColor(1,1,1,0);
    glMatrixMode(GL_PROJECTION);
    gluOrtho2D(-50,50,-50,50);
    glutDisplayFunc(displayFcn);
    glutMainLoop();
    return 0;
}