曲线生成算法的文献综述.doc

《曲线生成算法的文献综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、曲线生成算法的文献综述曲线生成算法的文献综述摘耍：曲线绘制是计算机图形学和图像处理中一个基础内容，由于其具有的基础性和应用性，使曲线绘制的研究有较重耍的意义。无论是随机扫描显示器还是线式绘图仪，曲线的绘制通常都是采用小的直线段来逼近各种曲线的线生成算法。关键词：参数多项式曲线非均匀Hilbert曲线通用的象素级曲线中图分类号：U212.33+2文献标识码：A1背景介绍曲线的生成技术是计算机图形学的重耍研究内容之一。曲线的绘制通常都是采用小的直线段来逼近各种曲线的线生成算法。在各种曲线的逼近算法中，按取点的方式不同，线生成算法可分为两大类。一类是均匀取点法，即参变数每次增加或减少一个固定的量来

2、计算下一点的坐标值，再将相邻节点用直线段连接，来逼近曲线的一种方法。这类方法计算简单，适用于变化非常规律的曲线，如圆、抛物线。其缺点是没有考虑曲线的局部变化规律，逼近程度较差。另一类是非均匀取点法，这类方法是根据曲线自身的变化规律，调整控制点，对曲线的局部变化给出较好的逼近。本文根据曲线的曲率，即曲线的弯曲程度，来控制取点的间隔，以更好地实现曲线的生成。目前广泛使用的图形显示器是光栅扫描显示器，采用的是像素级的图形绘制算法。这类算法充分利用光栅显示器的特点，一般只使用整数运算逐点计算曲线上的像素，因此生成的曲线是较细致的，且误差小。目前这类算法中已出现一些有效的针对于基本曲线的算法，如绘制直

3、线的Bresenham算法，绘制圆的Bresenham算法、中点法、正负法以及绘制椭圆及抛物线的Pitterway算法等。但在开发绘制工程制图中最常见的各种自由曲线算法时，相对而言就更困难和复杂了，如Bezier曲线、B样条曲线以及当前具有发展前途的非均匀B样条曲线都是多项式参数或有理曲线。2参数多项式曲线的快速生成一些基本曲线，如直线、圆、椭圆等，都有整数型的快速生成算法。如:画直线的Bresenhajn算法,画圆的Bresenhaln算法、中点法、正负法等。对于更一般的1#1线，一般采用折线来逼近，但这必将产生光顺性与计算量之间的矛盾，即曲线越光滑，则所需的计算量越大。在CAD及工程绘图

4、中最常见的各种自由曲线如Bezier曲线、B样条曲线都是参数多项式曲线。对于这类崩线，研制其有效的象素级绘制算法，对于减少计算量，提高显示效率和显示精度具有十分重要的意义。本节就参数多项式码线的快速生成问题进行讨论，给出生成和绘制参数多项式曲线的一种有效的算法。该算法首先选取适当的整数将参数多项式的参数区间离散化，然后将离散化后的参数多项式UH线的系数整数化。这样，就可以保证以后的计算过程都在整数之间进行，可以有效地提高算法的效率。在计算曲线上点的过程中，通过参数多项式各阶差分的递推计算，使得在逐点生成曲线的过程屮只用到整数的加减法，因此减少了计算量，提高了显示效率和精度。2.1参数多项式曲

5、线的逐点生成给定参数曲线的方程为x=f(t),y=g(t),t[O,1],其中f(t)和g(t)均为有理系数多项式。根据有理数在实数中的稠密性，把多项式的系数限定为有理数不会影响曲线的精度，这样可以把躺线方程化为整数方程来处理，减少了计算量。步骤1对于Bezier线应用引理(1)求出正整数1。对于一般的参数多项式曲线，先应用引理(2)将其转化成Bezier形式，再应用引理(1)求出相应的正整数1。引理1设，则。引理2设，，贝IJ,其中步骤2由和，求和在i二0的各阶差分de,bk:,k二1,2,•••,m,k=l,2,…，n步骤3由，和，求出对于i二0的点(x,y)和余项值。步骤4画笫一个点（

6、x,y）o步骤5对i=l,2,•••,1循环：如果，则x=x~l,zx=zx-al~l否则，如果，则x二x+1,zx二zx-al+l否则zx=zx-al如果，则y=y-Lzy=zy-bl-l否则，如果，则y二y+1,zy二zy-bl+l否则zy=zy-bl画点（x,y）o,k=l,2,•••,m,k=l,2,…，n算法结束。该算法适用于任意次数的参数多项式曲线，在逐点生成曲线时，只用到了整数的加减法，故算法的效率极高。3非均匀Hilbert曲线的生成算法Albert的基本思想是对基本图形的复制，该方法釆用多次分割空间的基本思路，在对空间的基本划分上结合Hilbert曲线的特性，从而完成曲线的

7、绘制。将整个空间划分为22n个子空间，然后利用n阶Hilbert码线进行填充，假如某个子空间满足继续划分的条件，则对该子空间进行划分。直到每个子空间都不满足划分条件，最后连接所有子空间内的节点，得到完整的H订bert遍历曲线。当取FF1吋，将整个空间均匀的划分成4个子空间（如图la所示），然后用一阶HilbertHll线填充，之后寻找可以继续划分的子空间，并将该空间进行划分，如此重复该过程直到无法划分为止；最