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

摘　要：在图形图像处理过程中，由于贝塞尔曲线比较容易计算和稳定的特性，在众多的领域中得到了广泛的应用。然而常见的贝塞尔曲线生成算法存在着效率较低的缺陷，参数步长的选取对生成曲线的准确性和效率有极大影响。针对现有贝塞尔曲线生成算法存在的不足，本文提出了基于局部性原理的可变步长曲线生成算法。通过改变曲线生成算法的参数步长，明显降低了逐点生成算法中大量的重复点计算，该算法不仅保持了较高的准确性，而且显著地提高了曲线生成的效率，有较好的应用性。

关键词：局部性原理；逐点生成；贝塞尔曲线；伯恩斯坦多项式
1 引言
　　曲线的生成算法是计算机图形学的重要内容。1971年法国雷诺汽车公司的工程师Bezier 提出了一种新的参数曲线表示法。这种方法能方便地控制输入参数(控制点)以改变曲线的形状，被称为Bezier曲线，数学原理使用了伯恩斯坦多项式。Bezier曲线是一种采用样条逼近的方法描述的曲线，它的许多性质使它在外形设计中更加好用，更容易实现。所以，Bezier样条在许多图形系统和CAD系统中得以广泛应用。
　　对于Bezier曲线的绘制，现在经常采用的是基于几何的算法，对某一变量的每次增加一个步长并计算其他变量的值以便算出曲线上的点，然后将这些点用小直线段，折线相连而生成曲线，该算法需要浮点运算，以及所绘制的曲线不能细致，曲线光滑性差，计算量大，另一常用算法是基于像素的算法，用整数运算来逐点计算曲线图的像素，减少了计算量，能够保持曲线的光滑性，但由于自由曲线是不确定的，即曲线每一段的走向是没有规律的，要绘制自由曲线就要更多地依赖计算机自动判断方向，并且算法复杂。
　　本文通过对Bezier曲线算法的原理及性质进行了分析，对于实验数据，采用统计分析的方法，大胆提出了可变参数的曲线生成算法，使计算机量大大减少，提高了曲线生成速度，而且准确性依然较高。
2 Bezier曲线生成算法分析
2.1 Bezier曲线生成原理
　　Bezier曲线的形状是通过一组多边折线(控制多边形)的各顶点P0，P1，…，Pm所定义出来的。在多边折线的各顶点中，只有第一点P0和最后一点Pm在曲线上，其余的点则用以定义曲线的阶次。
　　如果给定n+1个控制点：
　　，
则逼近由这些控制点构成的特征多边形的n次Bezier曲线可表示为：
　　                    （1）
　　其中，为控制点向量，为Bezier混合函数，它是用伯恩斯坦（Bernstein）多项式来定义的，即：
　　                    （2）
　　其中
　　                  （3）
　　                  （4）
　　                  （5）
　　                  （6）
2.2 Bezier曲线的性质
　　Bezier曲线具有以下性质：
　　1)端点性
　　当t=0时，）P(0)=P0，故P0决定曲线的起点，当t=1时，P(1)=Pn，故Pn决定曲线的终点。因此，Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。
　　2)切矢性
　　当t=0时，P’(0)=n（P1-P2）；当t=1时，P’(1)=n(P1-P2)，因此说明Bezier曲线在起点和终点处的切线方向是一致的。
　　3)凸包性
　　Bezier曲线位于其控制顶点P0,P1,P2,…Pn的凸包之内。
　　4)几何不变性
　　Bezier曲线的位置与形状仅与特征多边形顶点的位置有关，它不依赖于坐标系的选择。
　　5)变差缩减性
　　若Bezier曲线的特征多边形P0P1...Pn是一个平面图形，则平面内任意直线与P(t)的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫变差缩减性质。此性质反映了Bezier曲线比其特征多边形的波动小，也就是说Bezier曲线比特征多边形的折线更光顺。
　　6)仿射不变性
　　对于任意的仿射变换A：
                      (7)
即在仿射变换下，P(t)的形式不变。
3　基于局部性原理的可变步长曲线生成算法
3.1  Bezier曲线生成算法存在的问题
　　点和直线是描绘图形的最基本和最常用的元素，许多复杂的图形都由点和直线段构成的。在数学上，点是一个抽象的坐标位置，没有大小或面积。数学上定义的直线是由无数个点构成的，它只有长度而没有宽度。在光栅图形中，点是有一定大小和面积的像素来表示的；而由扫描转换得到的直线段，则是在有限个像素构成的阵列中确定的最佳逼近该直线段的一个像素序列。
　　计算机显示器屏幕上所能显示的最大点数即像素，是由显示卡的不同显示模式所决定，因此，在进入图形显示方式时，首先要在显示器的屏幕上建立一个坐标系，且水平和垂直坐标均取为整数。当通过方程计算出来的x、y坐标值不为整数时，还应对该坐标值以四舍五入方式取整。


　　     
　　图1步长u为0.1          图2步长u为0.0001
　　Bezier曲线的逐点生成算法，曲线显示的有效性和快速性，与参数u的步长选取有直接的关系。在等步长的Bezier曲线生成算法中，步长是根据曲线上曲率最大的线段来确定的。如果整条曲线，都是以这个步长为统一步长，那么这个步长对于曲率较大的线段是合理的，对于曲率变化不大的线段(有的地方可能接近直线段)，将产生不必要的分段，从而导致分段数量的增加。
　　当步长u的选取较大时，曲线的平滑性和准确性比较差，如图1所示；当步长u选取很小的数时，曲线会比较平滑，但也会出现大量的点在显示时由于四舍五入取整而会重复，使曲线生成的效率大大降低。


　　
　　
　　图3  步长u与贝塞尔生成曲线关系图
　　从图3可以看出，当步长u选取较大时，曲线绘制的点也比较少，无效的点基本上没有，但是有效点同样较少，这种曲线往往存在着比较粗糙、不够逼真的缺陷(如图1)。当步长选取较小的值时，曲线趋于稳定，不再随着u的减小而增多有效点，因此，有效点趋于定值的同时，也出现了重复计算的无效点急剧增加的现象。
3.2 局部性原理 给可变步长曲线生成算法的启示
　　1968年，Denning.P曾指出：程序执行时将呈现出局部性规律，即在较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。
　　局部性原理主要表现在时间局限性和空间局限性两个方面。时间局限性指如果程序中的某条指令一旦执行，则不久后该指令可能再次执行；如果数据被访问过，则不久后仍可能被再次访问。而空间局限性,是指运行的程序在一段时间内所访问的地址，可能集中在一定的范围之内。
　　那么，根据局部性原理，Bezier曲线生成算法同样存在着这样的问题。在曲线生成的过程中，由于参 数步长的选取不同，会出现大量的重复点的计算，造成了曲线生成效率的低下，若能适度的变化步长，则可以改善曲线生成的速度。
3.3 可变步长曲线生成算法的思想
　　局部性原理是虚拟存储技术实现的前提，它给Bezier曲线的绘制带来了启示。Bezier曲线在绘制时，如果步长u选取的较小，往往曲线的平滑性、逼近性较好，但同时也出现了重复计算的点较多的缺点。通过对多组实验样本的分析发现，重复次数有一定的规律性，当步长选取0.0001时，会计算10000个点，但有效点只有357个，而重复点达到9643个，这些重复点，平均每次重复达到27个，高的可达53次，因此重复的密集性，给可变步长的绘制思想增添了可行性。
　　提出可变步长的思想是每计算一个点的坐标，如果取整后和前面的点相同，则步长u不再以固定的步幅增长，而是以可变的跳跃步幅增长。本文的思想通过多次实验，验证了算法改进的可行性，算法在保证较高准确性的同时，降低了无效点计算次数，提高了曲线生成的效率。
4实验分析
4.1实验的环境
　　本实验使用操作系统平台是Windows XP professional，CPU（Intel）主频1.5GHz，内存768MB，实验调试使用软件平台Win-TC。
4.2实验的步骤
　　1). 选定多组控制点，每组控制点个数不超过13个，但不少于4个，即至少是3次Bezier曲线；
　　2). 对于选定的一组控制点按照逐点生成算法绘制，并记录结果；
　　3). 于选定的一组控制点按照改进后的算法绘制，并记录结果；
　　4). 对比分析每组实验的记录数据，分析改进生成算法的有效性。
4.3实验的结果
　　选定四个控制点绘制三次Bizier曲线，A(40,160),
B(100,280),C(160,80),D(280,200)，使用改进前的算法，分别对步长u采用不同的值，取得实验数据如下：
表1  基本步长u的不同实验数据汇总表







　　在表1中，无效点指重复的点，重复率为无效点与计算总数的比值，准确率为有效点359的比值。从表1看以看出，随着步长u取值的不同，生成曲线的有效性也发生着巨大的变化，
　　当u越来越小时，曲线生成的有效点逐渐趋于稳定，u从0.0001到0.00001，总计算次数扩大了10倍，多计算了9万个点，而有效点只增加了2个，当然重复率达到了惊人的99.6%。
　　本文分别用改进前算法和改进后的算法做了实验，数据对比如下：　　
    表2算法改进前后实验数据对比表







　　通过上面的对比表可以看出，在算法改进前后，重复率有了明显改善，而准确率依然保持了较高的水平。当u取0.00001时，准确率100%，而重复率也达到了99.64%；改进后，在保持95.54%的高准确率的同时，重复率降低了68.12%。而在u取0.0001时，准确率99.44%，重复率为99.64%；算法改进后，准确率为94.99%，而重复率降低了64.42%。
4、结论
　　针对割角多边形算法和等步长算法等Bezier曲线生成算法存在的不足，本文提出的基于局部性原理的
可变步长曲线生成算法，不仅保持了较好的准确性，而且有效地降低了逐点生成算法中大量的重复点计算。通
过多组实验数据的对比，验证了本文提出的算法改进的可行性和有效性。

参考文献：
李东，孙长嵩，苏小红 计算机图形学实用教程 人民邮电出版社，2004
徐建华，李善庆 有理Bezier曲线的快速逐点生成算法 计算机工程与应用，2004，25：73～74.
孙家广，杨长贵 计算机图形学 清华大学出版社，1995
刘勇奎，石教英 曲线的整数型生成算法 计算机学报，1998：21（3）：270～280.
黄有度，朱功勤 有理参数曲线的快速逐点生成算法 计算机学报，2001，24（8）：809～814
王国瑾，汪国昭，等．计算机辅助几何设计．北京：高等教育出版社，1999．
汤子瀛，哲凤屏，汤小丹 计算机操作系统 西安电子科技大学出版社，2001
郭凤华，杨兴强 Bezier曲线最优参数化研究 计算机学报，2005：32（5）：195～196.
章仁江，王国瑾 有理Bezier曲线离散终判准则的改进 软件学报，2003：14（10）：1813～1818.
侯晓辉. Bezier曲线的缩减　 计算机辅助设计与图形学学报，2003：8（15）：967～978.
陈宇拓，韦冰 基于分段Bezier曲线的手绘雕刻图案矢量化 ［J］计算机工程，2008,34(9):208～210