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

《基于局部性原理的可变步长bezier曲线生成算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、内容。1971年法国雷诺汽车公司的工程师Bezier提出了一种新的参数曲线表示法。这种方法能方便地控制输入参数(控制点)以改变曲线的形状，被称为Bezier曲线，数学原理使用了伯恩斯坦多项式。Bezier曲线是一种采用样条逼近的方法描述的曲线，它的许多性质使它在外形设计中更加好用，更容易实现。所以，Bezier样条在许多图形系统和CAD系统中得以广泛应用。对于Bezier曲线的绘制，现在经常采用的是基于几何的算法，对某一变量的每次增加一个步长并计算其他变量的值以便算出曲线上的点，然后将这些点用小直线段，折线相连而生成曲线，该算法需要浮点运算，以及所绘制的曲线不能细致，曲线光滑

3、性差，计算量大，另一常用算法是基于像素的算法，用整数运算来逐点计算曲线图的像素，减少了计算量，能够保持曲线的光滑性，但由于自由曲线是不确定的，即曲线每一段的走向是没有规律的，要绘制自由曲线就要更多地依赖计算机自动判断方向，并且算法复杂。本文通过对Bezier曲线算法的原理及性质进行了分析，对于实验数据，采用统计分析的方法，大胆提出了可变参数的曲线生成算法，使计算机量大大减少，提高了曲线生成速度，而且准确性依然较高。2Bezier曲线生成算法分析2.1Bezier曲线生成原理Bezier曲线的形状是通过一组多边折线(控制多边形)的各顶点P0，P1，…，Pm所定义出来的。在多边折

4、线的各顶点中，只有第一点P0和最后一点Pm在曲线上，其余的点则用以定义曲线的阶次。如果给定n+1个控制点：，则逼近由这些控制点构成的特征多边形的n次Bezier曲线可表示为：（1）其中，为控制点向量，为Bezier混合函数，它是用伯恩斯坦（Bernstein）多项式来定义的，即：（2）其中（3）（4）（5）（6）2.2Bezier曲线的性质Bezier曲线具有以下性质：1)端点性当t=0时，）P(0)=P0，故P0决定曲线的起点，当t=1时，P(1)=Pn，故Pn决定曲线的终点。因此，Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。2)切矢性当t=0时，P’(

5、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)仿射

6、不变性对于任意的仿射变换A：(7)即在仿射变换下，P(t)的形式不变。3基于局部性原理的可变步长曲线生成算法3.1Bezier曲线生成算法存在的问题点和直线是描绘图形的最基本和最常用的元素，许多复杂的图形都由点和直线段构成的。在数学上，点是一个抽象的坐标位置，没有大小或面积。数学上定义的直线是由无数个点构成的，它只有长度而没有宽度。在光栅图形中，点是有一定大小和面积的像素来表示的；而由扫描转换得到的直线段，则是在有限个像素构成的阵列中确定的最佳逼近该直线段的一个像素序列。计算机显示器屏幕上所能显示的最大点数即像素，是由显示卡的不同显示模式所决定，因此，在进入图形显示方式时，首

7、先要在显示器的屏幕上建立一个坐标系，且水平和垂直坐标均取为整数。当通过方程计算出来的x、y坐标值不为整数时，还应对该坐标值以四舍五入方式取整。图1步长u为0.1图2步长u为0.0001Bezier曲线的逐点生成算法，曲线显示的有效性和快速性，与参数u的步长选取有直接的关系。在等步长的Bezier曲线生成算法中，步长是根据曲线上曲率最大的线段来确定的。如果整条曲线，都是以这个步长为统一步长，那么这个步长对于曲率较大的线段是合理的，对于曲率变化不大的线段(有的地方可能接近直线段)，将产生不必要的分段，从而导