基于局部性原理的可变步长Bezier曲线生成算法

摘要：随着数据信息时代的到来，人们对信息的立体化表现提出了更高的要求，以图形和数据、计算机的结合的信息输出方式成为直观的表现形式，Bezier曲线是基于图形学、逻辑数学、现代信息技术三者结合而形成的曲线生成算法，因其具有简便的操作性、稳定性得到了广泛的应用。随着信息技术的发展，Bezier曲线生成算法呈多元化发展的趋势，具有代表性的算法有以下三种，包括逐点绘制参数曲线的双步算法，基于插值的Bernstein多项式复合算法，离散分割算法，本文就这几种算法出发，构建新的Bezier曲线算法，该算法立足于局部性原理的可变步长曲线生成算法，通过参数步长的相对修整，以期在保持该曲线传统优点的同时降低在逐点生成算法上的重复计算率。

关键词：局部性原理；贝塞尔曲线算法；可变步长

中图分类号：TP391.41文献标识码：A文章编号：1007-9599 (2011) 07-0000-03

Bezier Variable Step Curve Generation Algorithm Based on Locality Principle

Sun Shihe,Wang Haihua,Yue Wenjing

（Laiwu Vocational and Technical College,Laiwu271100,China）

Abstract:With the data in the information age,people are three-dimensional information of a higher performance requirements to graphics and data,combined with the computer output as visual information on the manifestations,Bezier curves are based on graphics,logical-mathematical,combination of modern information technology to form the curve of the three generation algorithm,because of its easy maneuverability and stability has been widely used.With the development of information technology,Bezier curve generation algorithm with diversified development trend,a representative algorithm of the following three,including one by drawing the double-step algorithm for parametric curves,based on Bernstein polynomial interpolation of complex algorithms,discrete segmentation algorithm,this paper several algorithms in this proceeding to construct a new Bezier curve algorithm based on the locality principle of variable-step curve generation algorithm,the parameters of the relative finishing step in order to maintain the curve in the traditional advantages of reduce by-point generating algorithm in the double-counting rate.

Keywords:Locality principle;Bezier curve algorithm;Variable step

一、引言

随着计数机技术的广泛应用，信息与计算机图形学的结合成为发展的必然方向，1971年法国雷诺汽车公司的工程师Bezier提出了一种新的参数曲线表示法。这种方法能便捷地控制输入参数（控制点）以改变曲线的形状，被称为Bezier曲线。该曲线是构建在伯恩斯坦多项式的理论基础之上的，将函数和几何学结合起来，使信息直观化，能准确的判断条件和生成曲线的统一度，从而可以调节相应的参数来修正曲线。

目前对Bezier曲线的表示方法多样

（1）几何算法因其较为直观运用广泛，其具体的算法如下：首先将某变量逐次增加一个步长，由此引起的其他变量的改变的值，并以该值通过计算出点。然后将各个点逐次连接起来。这样的点并不一定是在同一水平面上，连接它们往往形成折线。如何将其转化成为曲线，就得运用浮点算法，但是这样的算法曲线的轮廓突出，过于粗略且工作量大。

（2）基于像素的算法克服了几何算法计算量大、轮廓粗略等的不足，却因为本身的不确定性使得规律性差，人控性差，过程繁琐也难以运用在实践之中。

本文就Bezier曲线算法进行深刻的原理内涵分析，通过统计学方法对其进行数据处理，并尝试通过调节可变参数来实现的新的曲线生成算法，来克服以上算法的不足。

二、Bezier曲线生成算法

（一）Bezier曲线的生成的理论支持

Bezier曲线的实质是一组折线集或具有特征的多边形（被称为Bezier特征的多边形）曲线和多边形的起点和重点是吻合的，多边形的首尾边分别表示曲线首末点处的切矢量的方向，

当定义n+1个控制点时：

，

根据向这些点趋近而绘成的Bezier特征多边形的曲线这可以这样表示：

（1）

其中， 表示控制点的向量， 是运用伯恩斯坦（Bernstein）多项式来定义的表示Bezier曲线的一个混合函数。即：

（2）

其中

（3）

（4）

（5）

（6）

（二）Bezier曲线的特质

1.端点性：当t=0时，）P（0）=P0，P0是曲线的起点，当t=1时，P（1）=Pn，Pn是曲线的终点。所以，Bezier曲线的起点、终点与相应的特征多边形的起点、终点是相互吻合的

2.凸包性：Bezier曲线处于其控制顶点P0，P1，P2，…Pn的凸包之内。

3.切矢性：当t=0时，P’（0）=n（P1-P2）；当t=1时，P’（1）=n（P1-P2），因此说明Bezier曲线在起点和终点处的切线的矢量方向是一致的。

4.变差缩减性：如果Bezier曲线的特征多边形P0P1...Pn在同一平面之内，则平面内任意直线与P（t）的交点个数小于或等于该直线和特征多边形的产生交点数，即变差缩减性质。反映了Bezier曲线的波动范围在其特征多边形波动范围之内，（Bezier曲线折线具有平滑性）

5.几何不变性：Bezier曲线的位置与形状仅与特征多边形顶点的位置有关，坐标系的选择不起决定作用。

6.仿射不变性：仿射变换下，P（t）的形式不发生相应的改变。

三、基于局部性原理的可变步长曲线生成算法的相关性讨论

（一）传统的Bezier曲线生成算法内涵分析

1.像素的定义：计算机上能显示出的最大点。大小随着计算机的显示卡显示模式不同而不同。

2.关于点和线的非数学理解。传统的电脑构图的特征是，通过点和线段组成，由此可见点和线段在对图形进行描述时是相当重要的，但它们在光栅图形中的定义和从数学的角度进行的定义是不相同的，其不仅仅是个没有面积定义的符号，包含着坐标位置的基本信息，而是可以用像素对其进行描述的；直线不仅仅是无数个点可以组成，具有长度可以进行描述，宽度却难以进行描述的特点的数学图像，而是一个最接近直线段的有限个像素构成的像素序列。

由此可见在曲线构成之前，必须在屏幕上建立坐标系，该坐标系的水平和垂直为整数。

3.Bezier曲线的逐点生成算法问题讨论。从逐点算法看，参数u的步长选取关系着曲线的有效性及快速程度，具体表现在，如下：

等步长的Bezier曲线生成算法中，由曲线上最大的曲率控制步长，这一步长在整个曲线中如果是统一的，即对于曲率大的曲线是合适的，但是则可能将曲率变率小的曲线过多的分段从而导致了速度的缓慢。

即使当选择相对较大的步长u时，又导致了曲线如准确性、平滑性差等问题的出现，小的步长u在克服这些问题同时导致了点的重复。图1正是这一问题的反应，

图1步长u为0.1图2步长u为0.0001

图3 步长u与贝塞尔生成曲线关系图

就上图（3）进行分析，不难看出步长u选取较大时，绘制的点无论是无效还是有效点均少，绘制难以用精细来形容。小步长同时也导致了点的重复率加大，降低速度性。

（二）局部性原理[7]使可变步长曲线生成算法得以实现

1.局部性原理的提出：Denning.P于1968年对其进行定义。程序在短时间内执行任务是局限于某部分的，访问的相应空间也是被限定的。

2.其局限的特性主要从时间上和空间上体现。首先，在时间上的局限表现在程序对相同指令的重复执行上，其次在空间上的局限性则表现在程序执行范围是在时间内是一定的。

从这一角度思考，不难发现，在曲线生成程序的执行中，不同的参数步长引起的无效重复使得生成速度减慢，如何寻找适合的步长成为改进这一算法的关键。

3.可变步长曲线生成算法的形成。就局部性原理出发，在如何绘制Bezier曲线，试验分析小步长时，可以发现其重复具有规律性，如上表所列出，当步长=0.0001时，无效重复为9463，分析规律得出，达27个/次到53个/次之间，由此得出调整步长对曲线绘制的精确度和速度提高上是可行的。

可变步长的原理：对每个点坐标从前后检测重复点，发现相同时便调整步幅成不可定状态，本文从这一思想的基础上对可变步长下的算法进行有效性和速度性的验证。

四、实验论证

（一）实验仪器

操作系统平台Windows XP professional；CPU（Intel）主频1.5GHz；内存865MB；实验调试使用软件平台Win-TC。

（二）实验步骤

1.选取每组控制点≤13并且≥4个的多个控制组，绘制曲线（3次）。

2.运用逐点生成算法对点进行绘制，并记录结果。

3.选定的同一组作对照实验组按照改进后的算法绘制，并记录结果。

4.对比分析记录数据，分析改进生成算法的有效性。

（三）实验的结果

选定组内的四个控制点，采用步长u不同的值进行绘制Bizier曲线（3次）A（40，160），B（100，280），C（160，80），D（280，200），实验数据如下表：

步长u 有效点 无效点 计算次数 重复率 准确率

0.1 10 0 10 0 0.027855

0.01 100 0 100 0 0.278552

0.001 324 676 1000 0.676 0.902507

0.0001 357 9643 10000 0.9643 0.994429

0.00001 359 99641 100000 0.99641 1

表1 基本步长u的不同实验数据汇总表

无效点：重复的点；

重复率：无效点与计算总数的比值。

准确率：有效点359的比值。

由表1可以得出结论：

1.生成曲线的有效性随着步长u取值的不同而不同。

2.当u趋向于小值时，生成的曲线有效点稳定性加强。

3.u从0.0001到0.00001，计算的总次数扩大了10倍，9万个无效重复的点，而有效点只增加了2个，重复率达99.6%。

本文用改进前后的算法做对比实验，数据对比如下：

基本步长u 采用算法 可变步长 有效点 无效点 重复率 准确率

0.0001 改前 无 357 9643 96.43% 99.4%

0.0001 改后 20倍 341 3181 31.81% 95.0%

0.00001 改前 无 359 99641 99.64% 100%

0.00001 改后 200倍 343 31521 31.52% 95.5%

表2 算法改进前后实验数据对比表

小结：

1.重复率明显改善的同时保证了准确率。

2.当u=0.00001时，准确率为100%到95.54%的高准确率保持的同时，重复率降低了68.12%。

3.u=0.0001时；改进后，准确率94.99%与之前的99.44%略有降低，但同时重复率降低了64.42%。

五、结论

就传统的Bezier曲线生成算法存在的问题，进行相关性的讨论，并在局部性原理的前提下通过步长的调节找到合适的步长，保持算法的准确性同时有效的降低无效重复。验证了基于局部可变步长Bezier曲线生成算法的有效可行。

参考文献：

[1]李东,孙长嵩.苏小红计算机图形学实用教程[M].北京:人民邮电出版社,2004

[2]徐建华,李善庆.有理Bezier曲线的快速逐点生成算法[J].计算机工程与应用,2004,25:73-74

[3]孙家广,杨长贵.计算机图形学[M].北京:清华大学出版社,1995

[4]刘勇奎,石教英.曲线的整数型生成算法[J].计算机学报,1998,21(3):270-280

[5]黄有度,朱功勤.有理参数曲线的快速逐点生成算法[J].计算机学报,2001,24(8):809-814

[6]王国瑾,汪国昭.计算机辅助几何设计[M].北京:高等教育出版社,1999

[7]汤子瀛,哲凤屏,汤小丹.计算机操作系统[M].西安:西安电子科技大学出版社,2001

[8]郭凤华,杨兴强.Bezier曲线最优参数化研究[J].计算机学报,2005,32(5):195-196

[9]章仁江,王国瑾.有理Bezier曲线离散终判准则的改进[J].软件学报,2003,14(10):1813-1818

[10]侯晓辉.Bezier曲线的缩减[J].计算机辅助设计与图形学学报,2003,8(15):967-978

[11]陈宇拓,韦冰.基于分段Bezier曲线的手绘雕刻图案矢量化[J].计算机工程,2008,34(9):208-210

[作者简介]孙式河（1972-），男，山东莱芜市人，讲师，硕士，研究方向：软件工程；王海华（1974-），女，山东莱芜市人，助教，硕士，研究方向：计算机应用技术；岳文静（1966-），女，山东莱芜市人，助教，学士，研究方向：计算机信息管理