2 2 Bezier 曲线的算法描述及其程序实现 徐 　甜 ,刘凌霞 (安阳师范学院 ,河南 安阳 455002) 2006 年 　　　　　　 　　　　　　　　　　　安阳师范学院学报 94 　　[摘 　要 ]Bezier 曲线是图形学中最基本 、最重要的内容之一 ,在 CAD/ CAM 技术中得到广泛的应用 。通常的绘制方 法是用很多近似的直线段 。本文描述了 Bezier 曲线的算法 ,给出了绘制曲线的程序算法 。 [关键词 ]Bezier 曲线 ;算法 ;de Casteljau 算法 ;递推算法 [中图分类号 ]TP391 　　　[文献标识码 ]A 　　　[文章编号 ]1671 5330 (2006) 05 0049 04 1 　引言 曲线的生成算法是计算机图形学的重要内 容 。1962 年 , 法国雷诺汽车公司的工程师 Pierre Bezier 构造了一种以逼近为基础的参数曲线和曲 面的设计方法 , 并用这种方法完成了一种称为 UNISURF 的曲线和曲面设计系统 ,1972 年 , 该系 统被投入了应用 。Bezier 方法将函数逼近同几何 表示结合起来 ,使得设计师在工程设计中能比较 直观地意识到所给条件与设计出的曲线之间的关 系 ,能方便地控制输入参数来改变曲线的形状 。 Bezier 曲线具有良好的几何性质 ,能简洁 、完 美地描述和表达自由曲线曲面 , 在 CAD/ CAM 技 术中得到广泛的应用 。Bezier 曲线的最大优点之 一是 :控制点如果构成凸多边形 ,即特征多边形是 凸时 ,Bezier 曲线也是凸的 。所以要将曲线升高 、 降低 ,只要将一个控制点升高 、降低即可 ,计算非 常方便 ,因此 Bezier 曲线是曲线拟合的很好的工 具 。如何快速地绘制出各阶的 Bezier 曲线 ,仍是目 前研究的一个方向 。本文主要讨论了 Bezier 曲线 的算法 ,以及如何通过高级语言程序设计绘制出 Bezier 曲线 。 2 　Bezier 曲线的算法 2. 1 　Bezier 曲线的描述 在空间给定 n + 1 个点 P0 ,P1 ,P2 , …,Pn ,称下 列参数曲线为 n 次的 Bezier 曲线 。 P(t) = n t = 0 PiJ i ,n (t) , 　　0 ≤t ≤1 其中 J i ,n (t) 是 Bernstein 基函数 ,即 nti (1 - t) n- i J i ,n (t) = Ci Ci n = n ! i !(n - i) ! ,i = 0 , ……,n 一般称折线 P0P1P2 …Pn 为曲线 P(t) 的控制多边 形 ;称点 P0 ,P1 ,P2 , …,Pn 为 P(t) 的控制顶点 。在空 间曲线的情况下 ,曲线 P(t) = (x(t) ,y(t) ,z (t) ) 和 控制顶点 Pi = (Xi ,Yi ,Zi) 的关系用分量写出即 为 : X(t) = Y(t) = Z(t) = n i = 0 n i = 0 n i = 0 XiJ i ,n (t) YiJ i ,n (t) ZiJ i ,n (t) 当 t 在区间[0 ,1 ] 上变动时 ,就产生了Bezier 曲线 。 若只考虑 x和 y ,就是平面上的Bezier 曲线 。以三次 Bezier 曲线为例 ,它可用矩阵形式表示如下 : P0 P1 P2 P3 - 3 1 3 0 0 0 0 0 P(t) = [t3 　t2 　t 　1] - 1 3 - 3 1 3 - 6 3 0 0 ≤t ≤1 2. 2 　Bezier 曲线的性质 (1) Bezier 曲线具有以下性质 : 当 t = 0 时 ,P(0) = P0 ,故 P0 决定曲线的起 点 ,当 t = 1 时 ,P(1) = Pn ,故 Pn 决定曲线的终点 。 Bezier 曲线的起点 、终点与相应的特征多边形的 起点 、终点重合 。 Bezier 曲线 P(t) 在 P0 点与边 P0P1 相切 ,在 Pn 点与边 Pn- 1Pn 相切 。 [收稿日期 ]2006 [作者简介 ]徐甜 (1968 —) ,女 ,汉族 ,河南博爱人 ,安阳师范学院讲师 ,主要从事计算机教学及研究 。 03 24 

05 安阳师范学院学报 　 　　　　　　　　　　　　　　　　2006 年 Bezier 曲线 P(t) 位于其控制顶点 P0 ,P1 ,P2 , …,Pn 的凸包之内 。 Bezier 曲线 P(t) 具有几何不变性 。 Bezier 曲线 P(t) 具有变差缩减性 。 2. 3 　Bezier 曲线的 de Casteljau 算法 Paul de Casteljau 发现了一个 Bezier 曲线非常 有趣的特性 ,任何的 Bezier 曲线都能很容易地分 成两个同样阶次的 Bezier 曲线 。 图 1 　定比分割 如图 1 所示 ,当 P0 ,P2 固定 ,引入参数 t ,令P0P1 0 P1 0P1 P1P1 1 P1 1P2 的比值为 t : (1 - t) ,即有 : P1 0P2 0 P2 0P1 1 = = P1 0 = (1 - t) P0 + tP1 P1 1 = (1 - t) P1 + tP2 P2 0 = (1 - t) P1 0 + tP1 1 t 从 0 变到 1 ,第一 、二式是两条一次Bezier 曲线 。将 一 、二式代入第三式得 : P2 0 = (1 - t) 2P0 + 2t (1 - t) P1 + t2P2 当 t 从 0 变到 1 时 ,它表示了由 P0 、P1 、P2 三个 控制顶点形成的一条二次 Bezier 曲线 。并且表明 : 2 可以定义为分别由前两 这个二次 Bezier 曲线 P0 个顶点 (P0 ,P1) 和后两个顶点 (P1 ,P2) 决定的一次 Bezier 曲线的线性组合 。依次类推 ,由四个控制点 3 可被定义为分别由 定义的三次 Bezier 曲线 P0 (P0 ,P1 ,P2) 和 (P1 ,P2 ,P3) 确定的二条二次 Bezier 曲线的线性组合 ,由 (n + 1) 个控制点 Pi (i = 0 ,1 , n 可被定义为分别 …,n) 定义的 n 次 Bezier 曲线 P0 由前 、后 n 个控制点定义的两条 (n - 1) 次 Bezier n- 1 与 P1 曲线 P0 Pn 0 = (1 - t) Pn- 1 1 　　t ∈[0 ,1 ] n- 1 的线性组合 : + tPn- 1 0 由此得到 Bezier 曲线的递推计算公式 : Pk i = 　　Pi 　　　　　　k = 0 (1 - t)Pk- 1 + tPk- 1 i i+1 　k = 1 ,2 , …,n ,i = 0 ,1 , …,n - k (2) 这便是 de Casteljau 算法 。用这一递推公式 , 在给定参数下 ,求 Bezier 曲线上一点 P (t) 非常有 效 。上式中 :Pi P0 n 即为曲线 P(t) 上具有参数 t 的点 。 0 = Pi 是定义 Bezier 曲线的控制点 , 这一算法可通过简单的几何作图来实现 ,给 定参数 t ∈[0 ,1 ] ,把定义域分成长度为 t : (1 - t) 的两段 。依次对原始控制多边形每一边执行同样 的定比分割 ,所得分点就是第一级递推生成的中 1 (i = 0 ,1 , …,n - 1) ,对这些中间顶点构 间顶点 Pi 成的控制多边形再执行同样的定比分割 ,得第二 2 (i = 0 ,1 , …,n - 2) 。重复进行下 级中间顶点 Pi n 即为所 去 ,直到 n 级递推得到一个中间顶点 P0 求曲线上的点 P(t) 。 当 t = 1/ 2 时 ,从 (2) 式可知 ,求 Pi k 只需进行 加法和除 2 运算 ,在计算机内除 2 运算只需右移 1 位 ,计算速度快 。所以通常取 t = 1/ 2 最方便 ,即 每次求得 Bezier 曲线的中点 。 图 2 　de Casteljau 算法的几何作图 (t = 1/ 2) 如图 2 所示 ,有 0 ,1 ,2 ,3 四个控制点 ,计算每 条线的中点 01 ,12 ,23 ,再得中点 012 ,123 ,最后得 到的中点 0123 即在曲线上 。四个控制点 0 ,01 , 012 ,0123 又 定 义 了 左 边 的 曲 线 , 四 个 控 制 点 0123 ,123 ,23 ,3 又定义了右边的曲线 ,重复对左右 的两条曲线再进行定比分割 ,多次进行定比分割 后 ,就可以用直线段代替曲线段[3 ] 。 3 　通过高级语言编程绘制 Bezier 曲线实例 3. 1 　使用 Bezier 曲线方程实现 从(1) 式可知 ,计算 Bezier 曲线上的点 ,可用 Bezier 曲线方程 。已知控制点的坐标 ,只要 t 取 0 到 1 之间不同的值 ,就可以求出 Bezier 曲线上的 很多点 , 然后将这些点用小直线段 , 折线相连 , Bezier 曲线也就绘制出来了 。为了得到好的显示 效果 ,要把间距控制在视觉能接受的范围内 。 下面程序片段是使用 C 语言绘制二维 Bezier 曲线的程序片段 ,这是通过 Bezier 曲线方程完成 的 。完整程序在 TC2. 0 上通过 。运行结果如图 3 所示 。 float bezier (int p [100 ] [2 ] ,int n) 

第 5 期 　　　　　　　　　　　　　徐甜 ,刘凌霞 :Bezier 曲线的算法描述及其程序实现 15 { float b[100 ] ,a = 0 ,d = 0 ,c[100 ] [100 ] ,t ,g ; 　int i ,j ,m ; 　g = 0. 1 ; 　moveto (p [0 ] [0 ] ,p [0 ] [1 ]) ; for (t = 0 ;t < = 1. 01 ;t = t + g) { for (i = 0 ;i < = n ;i + + ) {/ chengfang (t ,i) 为用户定义的求乘方的 / chengfang (1 - t ,n jiecheng ( n - jiecheng ( n) ) / (jiecheng (i ) 函数 ,jiecheng(n) 为用户定义的求阶乘的函数 　b[i ] = (chengfang (t ,i) - i ) i) ) ; } } b[i ] ; b[i ] ; 　} 　c[i ] [0 ] = p [i ] [0 ] 　c[i ] [1 ] = p [i ] [1 ] a = 0 ;d = 0 ; for (j = 1 ;j < = i ;j + + ) { a = a + c[j - 1 ] [0 ] ; d = d + c[j - 1 ] [1 ] ; } lineto (a ,d) ; 图 3 　程序运行结果 3. 2 　使用递推算法实现 通过设计程序实现递推算法的难点是 :进行 定比分割到什么程度 ,就可以用直线段代替曲线 。 如果曲线上的点到其两端点的连线的距离小于指 定的很小正数ε时 ,则在显示和绘制时 ,就可用直 线段代替曲线段 ,否则对其控制多边形再进行定 比分割 。在适当次数的分割后 ,分得的每一段曲 线都能由其两端点的连线所代替 。 计算 Bezier 曲线 P(t) 到其两端点连线 P0P3 的 距离 d (P(t) ,P0P3) 很麻烦 ,但是由凸包性可知 : 差范围内 ,可用右端代替左端 。如图 4 中 ,只要让 d1 和 d2 中最大值小于一个指定的很小正数ε时 , 就可以用两端点的直线代替曲线段 。 图 4 　当 max(d1 ,d2) <ε,可用两端点的直线 代替曲线段 下面程序段是使用递推算法实现绘制平面 3 次 Bezier 曲线的过程描述 。 void recursive- bezier (double x0 , double y0 , 　　　　　　　　double x1 , double y1 , double x2 , double y2 , double x3 , double y3) { 　double x01 = (x0 + x1) / 2 ; double y01 = (y0 + y1) / 2 ; double x12 = (x1 + x2) / 2 ; double y12 = (y1 + y2) / 2 ; double x23 = (x2 + x3) / 2 ; double y23 = (y2 + y3) / 2 ; double x012 = ( x01 + x12) / 2 ; double y012 = (y01 + y12) / 2 ; double x123 = ( x12 + x23) / 2 ; double y123 = (y12 + y23) / 2 ; double x0123 = (x012 + x123) / 2 ; double y0123 = (y012 + y123) / 2 ; double dx = x3 - x0 ; double dy = y3 - y0 ; double d1 = fabs ( (x1 - x3) dy - (y1 - y3) dx) ; dx) ; double d2 = fabs ( (x2 x3) dy - (y2 - y3) if max(d1 ,d2) <ε { add-point ( x0123 , y0123) ; / 表示此点在 bezier 曲线上 ,从此点又分了左右两曲线 / return ; } recursive-bezier ( x0 , y0 , x01 , y01 , x012 , y012 , d ( P (t ) , P0P3) ≤max ( d ( P1 , P0P3) , d ( P2 , x0123 ,y0123) ; P0P3) ) recursive-bezier (x0123 , y0123 , x123 , y123 , x23 , 其中 d (Pi , P0P3) 表示点 Pi 到线段 P0P3 的距 离 ,计算点到直线的距离要容易 。故在一定的误 y23 ,x3 ,y3) ; } 

25 安阳师范学院学报 　 　　　　　　　　　　　　　　　　2006 年 void bezier (double x0 , double y0 , double x1 , double y1 , double x2 , double y2 , double x3 , double y3) { 　　add-point (x0 , y0) ; 　　 recursive- bezier (x0 ,y0 ,x1 ,y1 ,x2 ,y2 ,x3 , 段 ,折线相连 ,Bezier 曲线也就绘制出来了 ,对于 高阶 Bezier 曲线也可实现 。使用递推算法 ,用几 何作图简单 、清楚 ,易于理解 ,但是要用程序实现 高阶 Bezier 曲线的算法就会困难很多 ,以后还需 要继续探索使用递推算法绘制高阶 Bezier 曲线的 程序算法 。 y3) ; 　　add-point (x3 ,y3) ; } 4 　结束语 Bezier 曲线是图形学中最基本 、最重要的内 容之一 ,它广泛使用在二维和空间图形中 。但是 如何快速 、准确地绘制曲线仍是一个问题 。通常 的绘制方法是用很多近似的直线段 ,这也是一种 唯一有效的方法 。本文描述了 Bezier 曲线的算 法 ,还给出了绘制曲线的程序算法 。 第一种算法虽然需要浮点运算 ,所绘制的曲 线不太细致 ,计算量也大 ,但是知道已知控制点的 坐标 ,只要 t 取 0 到 1 之间不同的值 ,就可以求出 Bezier 曲线上的很多点 ,然后将这些点用小直线 [参考文献 ] [1 ]唐荣锡等 计算机图形学教程 (修订版) [M]. 北京 :科 学出版社 ,2005 , (6) :155 - 161. [2 ]金廷赞. 计算机图形学 [ M]. 浙江大学出版社 ,1994 : 154 - 157. [3 ] Adaptive Subdivision of Bezier Curves [ EB/ OL ] , http :/ / www. antigrain. com/ research/ adaptive- bezier/ # toc0003 , 2005. [4 ]苏步青. 计算几何 [M]. 上海 :上海科学技术出版社 , 1981 :102 - 104. [5 ]王飞. 计算机图形学基础 [M]. 北京 :北京邮电大学出 版社 ,2000 :82 - 83. [6 ]孙家广. 计算机图形学 (第三版) [M]. 北京 :清华大学 出版社 ,1998 :306 - 307. Bezier Curve Algorithm Describing and How to Dra w Bezier Curve by Program Design XU Tian ,LIU Ling xia (Anyang Normal University , Anyang 455002 , China) Abstract :Bezier curve is one of most elementary and importants contents in computer graphics , and has wide appli cations in CAD/ CAM. Bezier curve can now be drawn as a series of line segments joining the points. This paper describes Bezier curve algorithm and how to draw Bezier curve by Program design. Key words :Bezier curve ;algorithm ;the de Casteljau - algorithm ;recursive algorithm [责任编校 :弘扬 ]