1、1曲线生成算法的文献综述摘要：曲线绘制是计算机图形学和图像处理中一个基础内容,由于其具有的基础性和应用性,使曲线绘制的研究有较重要的意义。无论是随机扫描显示器还是线式绘图仪，曲线的绘制通常都是采用小的直线段来逼近各种曲线的线生成算法。 关键词：参数多项式曲线非均匀 Hilbert 曲线通用的象素级曲线中图分类号：U212.33+2 文献标识码：A 1 背景介绍 曲线的生成技术是计算机图形学的重要研究内容之一。曲线的绘制通常都是采用小的直线段来逼近各种曲线的线生成算法。在各种曲线的逼近算法中，按取点的方式不同，线生成算法可分为两大类。一类是均匀取点法，即参变数每次增加或减少一个固定的量来计算下一
2、点的坐标值，再将相邻节点用直线段连接，来逼近曲线的一种方法。这类方法计算简单，适用于变化非常规律的曲线，如圆、抛物线。其缺点是没有考虑曲线的局部变化规律，逼近程度较差。另一类是非均匀取点法，这类方法是根据曲线自身的变化规律，调整控制点，对曲线的局部变化给出较好的逼近。本文根据曲线的曲率，即曲线的弯曲程度，来控制取点的间隔，以更好地实现曲线的生成。 目前广泛使用的图形显示器是光栅扫描显示器，采用的是像素级的2图形绘制算法。这类算法充分利用光栅显示器的特点，一般只使用整数运算逐点计算曲线上的像素，因此生成的曲线是较细致的，且误差小。目前这类算法中已出现一些有效的针对于基本曲线的算法，如绘制直线的
3、Bresenham 算法，绘制圆的 Bresenham 算法、中点法、正负法以及绘制椭圆及抛物线的 Pitterway 算法等。但在开发绘制工程制图中最常见的各种自由曲线算法时，相对而言就更困难和复杂了，如 Bzier 曲线、B 样条曲线以及当前具有发展前途的非均匀 B 样条曲线都是多项式参数或有理曲线。 2 参数多项式曲线的快速生成 一些基本曲线，如直线、圆、椭圆等，都有整数型的快速生成算法。如:画直线的 Bresenhajn 算法，画圆的 Bresenhaln 算法、中点法、正负法等。对于更一般的曲线，一般采用折线来逼近，但这必将产生光顺性与计算量之间的矛盾，即曲线越光滑，则所需的计算量越
4、大。 在 CAD 及工程绘图中最常见的各种自由曲线如 Bezier 曲线、B 样条曲线都是参数多项式曲线。对于这类曲线，研制其有效的象素级绘制算法，对于减少计算量，提高显示效率和显示精度具有十分重要的意义。本节就参数多项式曲线的快速生成问题进行讨论，给出生成和绘制参数多项式曲线的一种有效的算法。该算法首先选取适当的整数将参数多项式的参数区间离散化，然后将离散化后的参数多项式曲线的系数整数化。这样，就可以保证以后的计算过程都在整数之间进行，可以有效地提高算法的效率。在计算曲线上点的过程中，通过参数多项式各阶差分的递推计算，使得在逐点生成曲线的过程中只用到整数的加减法，因此减少3了计算量，提高了显
5、示效率和精度。 2.1 参数多项式曲线的逐点生成 给定参数曲线的方程为 x=f(t)，y=g(t),t0，l，其中 f(t)和 g(t)均为有理系数多项式。根据有理数在实数中的稠密性，把多项式的系数限定为有理数不会影响曲线的精度，这样可以把曲线方程化为整数方程来处理，减少了计算量。 步骤 1 对于 Bezier 曲线应用引理（1）求出正整数 l。对于一般的参数多项式曲线，先应用引理（2）将其转化成 Bezier 形式，再应用引理(1)求出相应的正整数 l。 引理 1 设，则。 引理 2 设， ，则，其中 步骤 2 由 和 ，求和在 i=0 的各阶差分 ak， bk : ，k=1,2,m ，k=
6、1,2,n 步骤 3 由，和,求出对于 i=0 的点（x, y）和余项值。 步骤 4 画第一个点（x, y） 。 步骤 5 对 i=1,2，,l 循环： 如果，则 x=x-1，zx=zx-a1-1 否则，如果，则 x=x+1，zx=zx-a1+1 否则 zx=zx-a1 如果，则 y=y-1，zy=zy-b1-1 4否则，如果， 则 y=y+1， zy=zy-b1+1 否则 zy=zy-b1 画点（x, y） 。 ， k=1,2,m ，k=1,2,n 算法结束。 该算法适用于任意次数的参数多项式曲线，在逐点生成曲线时，只用到了整数的加减法，故算法的效率极高。 3 非均匀 Hilbert 曲线的
7、生成算法 Hilbert 的基本思想是对基本图形的复制，该方法采用多次分割空间的基本思路，在对空间的基本划分上结合 Hilbert 曲线的特性，从而完成曲线的绘制。将整个空间划分为 22n 个子空间，然后利用 n 阶 Hilbert曲线进行填充，假如某个子空间满足继续划分的条件，则对该子空间进行划分。直到每个子空间都不满足划分条件，最后连接所有子空间内的节点，得到完整的 Hilbert 遍历曲线。 当取 n=1 时，将整个空间均匀的划分成 4 个子空间(如图 1a 所示)，然后用一阶 Hilbert 曲线填充，之后寻找可以继续划分的子空间，并将该空间进行划分，如此重复该过程直到无法划分为止；最
8、后将所有的曲线段连接起来。 算法的步骤 将每个空间区域内的曲线分成从空间中心离开至边界，或从边界进入到中心的曲线段。从最下方的边,以逆时针旋转分别将边定义为：50，1，2，3 (如图 1b 所示)。详细步骤如下： 1)为原始空间定义曲线的进出口方向，这里定为-1，表示没有曲线进入或离开； 2)将原始空间的空间编号定义为 0； 3)根据 Hilbert 曲线的特性为原始空间绘制 1 阶 Hilbert 曲线； 4)根据绘制的曲线将分为 4 个子空间并对子空间进行编号； 5)检查子空间是否必要再次分割； 6)对需要分割的子空间重复 2)5)步骤； 7)当所有空间均不可再分时，将子空间内的曲线提出；
9、每段曲线由进出口表示法转化为对应的起始坐标/终止坐标表示法； 8)对于一个曲线段的起始端点和前一曲线段的终止端点坐标不相同时，添加一条连接曲线段； 9)根据坐标表示绘制出完整的曲线段。 图 1 非均匀 Hilbert 空间划分 数据的存储应该遵循 Hilbert 曲线规则，同时为了适应在曲线绘制过程中各种数据的动态变化，应对空间、节点、曲线段进行存储。各个数据结构可采用结构体或类的方式来存储，空间和曲线段的数据存储结构分别如表 1，2 所示。 表 1 空间的数据存储结构 6表 2 曲线段的数据存储结构 在运算过程中，需要充分考虑到空间信息和曲线段信息的变更，尤其是在进行子划分时需要进行必要的丢
10、弃，以及当不需要进行划分后需要进行相关信息的存储。由于在最后需要的是曲线，而对空间的划分在程序与运算完成后是不需要的；对于曲线段，本文最后是需要的，而在之前的运算中，可能需要丢弃。因此，在运算过程中制定了的数据结构如表 3 所示。 表 3 临时数据结构 关键点的实现 图 1a 为 1 阶 Hilbert 曲线的走向。本文将每个空间内的曲线段都看成是一段从空间的中心发射出来的射线，和一段射向中心的射线。图 1b为空间的 4 个边界编号。令空间中心的编号为-1，则图 1a 中的 Hilbert曲线可以分解为：-12，0-1，-11，3-1，-10，2-1。当将图 1a 中左侧的两个小区域被再次分割
11、后，形成的新的曲线如图 1c 所示。重新表示图 1c 中左侧的所有曲线，为-11，3-1，-12，0-1，-13，1-1 和 0-1，-12，0-1，-11，3-1，-10，2-1，-11 与原来图 1a 中左侧的曲线段-12，0-1，-11 比较，可以发现，当再次分割后,曲线的最初进入位置，和最终离开位置是和分割前7相同。因此，可以得到空间再次分割的曲线绘制伪代码如下： Dim down=0， left=1,up=2，right=3 Child (1).In=Parent. In Child (4).Out=Parent. Out 考虑到由于第一次划分的各个空间，对相应的新划分层次产生的影响
12、，故引入空间的编号后得到空间的编号图如图 1a，c。对图 1a 按路径顺序编号为 0，1，2，3，而图 1c 按路径对分割的第二层划分产生的空间编号顺序排列为 4，5，6，7 和 8，9，10，11。 一个通用的象素级曲线生成算法 二维平面上曲线的一般表达式为 f(x，y)=0 (1) 我们知道，绝大多数实用曲线都具有正负性质，即曲线将平面分为正、负两个区域，若将正区域中的一点代入该曲线的表达式中(式(1)的左边)，所得值大于零;而将负区域中的一点代入该曲线的表达式中，所得值为负.参考文献8，9中将具有正负性质的曲线称为正则曲线，并且专题讨论了正则曲线所应满足的条件.简单地说，如果曲线上的每一
13、点都存在切线，则其一定是正则曲线.根据这一条件，显然本文后面要讨论的Bezier 曲线和 B 样条曲线都是正则曲线。我们下面提出的算法便是利用了曲线的正负性质。 一个象素级绘制算法就是要逐点地选择距离实际曲线最近的那些象素点。设当前点的坐 标为(x，y)，则下一步就要从其相邻象素点中选择一个距离实际曲8线最近的象素。共有 8 个前进方向，我们设其为 ml 至 m8，如图 1 所示，为实现曲线绘制，我们也根据曲线的不同走向在算法中分为 8 个部分，分别处理。例如，如果曲线的某一小段的切线方向(曲线走向)在 ml 和 m2之间(或称其方向在 Rl 内)，即大于 0。而小于 45。 ，则由算法的 P
14、l 部分进行生成。又如果曲线接下来的一小段的走向变成了 R2，即在 m2 和 m3之间，则由算法相应的 P2 部分进行绘制，以此类推(见图 1)。 图 1 一个象素的八个相邻象素及对应的移动方向 下面我们以第一部分 Pl 为例来讨论算法的实现。对于这个走向的曲线，我们需要判断当前象素(x，y)的右邻象素(x+1，y)和右上邻象素(x+1，y+1)中哪一个距离曲线较近，即将(x+1，y+1)和(x+1，y)分别代入曲线表达式中(式(l)的左边)，并比较其绝对值，即比较f(x+1，y+1)和f(x+1，y+1)。如果前者的绝对值较小，则说明(x+1，y+1)点距离曲线较近，下一步就前进到该点，该点
15、也就成为下一步的当前点；如果后者的绝对较小，则下一步就到(x+1,y)点。 下面的问题就是当曲线的走向变化时，如何判断，以便转到算法中相应的部分.这是该算法的一个关键技术，即上面所说的算法的自动方向调整.具体方法如下：如果 f(x+1，y+1) 和 f(x+1，y)皆为正或皆为负，则说明(x+1，y+1)和(x+1，y)两点都在曲线的同一侧。 这时我们认为曲线的走向已绣不在 Rl 方向域内了，曲线的走向最大可能是 R2 或者 R8 应该是 R2 还是 R8，要通过判断 f(x+1，y+1)和9f(x+1，y)之间的绝对值大小来决定。如果前者小于后者，则应该是 R2；否则，应该是 R8，如图 2
16、 所示。如果曲线的走向并不在 R2 或 R8 方向域内，那么在转到算法的 P2 或 P8 部分之后仍可以继续判断曲线的走向(见下面的算法，其中在每一部分的开始都要判断曲线走向是否属于其它方向以转到算法的相应部分)。这样，算法在没有确定曲线的正确走向之前是不前进的，因此它可以生成任何弯曲度的曲线，包括在某些点处有很大转向的曲线。 图 2 当(x+1，y+1)与(二+1，y)两点均在曲线同一侧时， 如果前者距离曲线较近，则曲线属 R2 方向域 综上所述，我们可写出算法的 Pl 部分如下 P1：WHILE ORDO (Fl=f(x+1，y); F2=f(x+1，y+1); IF F1*F20 THE
17、N IFTHENGOTOP2 ELSEGOTOP8 ELSEIFTHEN(x=x+1; y=y+1; ) ELSEx=x+1; SETPOINT(x，y); ) 10STOP ； 其中 xi 和 yi 是曲线终点坐标.算法的其余 7 个部分 P2 一 P8 与上面的 Pl 部分类似，不难由相同的方法得出.另外，在算法开始执行时，还需要一个曲线的初始方向以决定最先转到算法的哪一部分，该初始方向可通过求曲线在起始点的导数得到。而对于 Bezier 曲线和 B 样条曲线这一初始方向是已知的。 观察上述算法可见，该算法实际上可生成任何可以表示成式(1)的正则曲线，只不过对于 f(x，y)是多项式函数的
18、曲线，该算法只需用整数运算。如果多项式中含有小数或分数系数，总可以通过乘一个数使这些小数或分数系数变为整系数，而对于(1)式，将其两边同乘某一个数之后仍表示原曲线。 该算法与正负法6都利用了曲线的正负性质，但正负法所生成的点中有一些点距离实际曲线的距离要大于半个象素单位。另外正负法生成曲线的轨迹往往是成直角前进的。这样不仅多计算了一些不必要的点(角点)而增加了计算量，而且也使得所生成的直线不够光滑和美观。而本文所提出的上述算法总是选择距离曲线最近的点(小于半个象素单位)，而且没有直角点.因而既减少了计算量又生成了光滑的曲线。 参考文献 1 LIEN S L,SHANTZ M,PRATT V.Adaptive forword differencing for rendering curves and surfacesJ.Computer Graphics, 1987,21(4):111-118. 2 CHANG S L,SHANTZ M ,ROCCHETTI R.Rendering cubic curves
