文档介绍：计算机图形基本算法
离散直线的生成算法
DDA算法(Digital Differential Algorithm)
假设已知直线段AB的端点坐标是A(x1 ,y1)、B(x2 ,y2),且dy/dx=m=常数, 对于一般位置直线ax+by+c=0,显然可以导出下面的递推公式:
= (7-1)
又因为yi+1=yi+,所以
yi+1=yi+. (7-2)
这样,每增加一个增量,便可以按式(7-2)计算出yi+1来。由于屏幕上的像素只能是整数,因此要经过取整运算,即[(int)(xi+1),(int)( yi+1)]处的像素点才是显示像素点。然而,乘法运算和取整运算都需要较多的时间,因此产生直线的速度会受到影响。显然,如果在式(7-2)中令=1,则可避免做费时的乘法,公式可以简化为:
,。
当m<1时,在X方向增加一个步长,就在Y方向得到一个增量,构成一个比1小的步距,经过取整运算,可以相应点亮一个像素点,如图7-1所示。
当m>1时,那么在X方向增加一个步长,就有可能在Y方向上构成一个比1大的步距。遇到这种情况,为了保证图形显示精度,就应当把x、y的地位互换,把y看作是自变量,每次增加单位步长1,去计算因变量x,即
,
由于=1,所以
这样才不至于一次跳过多行。当然,也要对进行取整运算,再决定要显示的像素。这种情况如图7-2所示。
图7-1 m<1的情况图7-2 m>1的情况
可见DDA算法就是一个增量算法,在一个迭代算法中,其每一步的x、y值是用前
一步的值加上一个增量来获得的,即称为增量算法。在此算法中,y、k必须是float,且每一步都必须对y进行舍入取整,不利于硬件实现。
直线的Bresenham算法
为了避免做费时的乘法运算和取整运算,人们不断努力,寻找到许多效率更高的显示直线段的算法。其中在二十世纪60年代,由Bresenham提出的一种更好的直线生成算法,称为Bresenham算法。此算法的一个根本思想是借助于一个决策变量d
i,来确定下一个该点亮的像素点。对于0<m<1的情况, 图7-3 直线段与光栅网格
如图7-3所示。
Bresenham算法的分析过程如下:假设一条直线段的起点坐标为(0,0),终点坐标为(dx,dy)。
因为,且,所以
又因为,所以
整理得出
在所讨论的这种情况下,显然dx>0,所以可以用dx(s-t)<0作为选择Si为下一个该点亮的像素点的条件。因为,则表示。从图7-3可以看出,在时,应选择Si点。定义,并称之为决策变量,那么
从图7-3可以看出,,,是表示前面一个亮点的坐标值,因此可以写出决策变量的初始值为
将下标加1,则有
如果≥0(即,),则表示下一个亮点应该选Ti。一旦选择了Ti,则有,此时决策变量的表达形式如下:
如果<0(即,),则表示下一个亮点应该选。一旦选择了,则有,此时决策变量的表达形式如下:
这样,便得到一种迭代方法:由上一个决策变量可以算出下一个决策变量,再根据决策变量的正、负对与Ti进行选择。
上面讨论的是≥>0的情况。如果是>>0的情况,则要把x和y的变量地位互换。对于<0或<0的情况,则应将表达式和换成或。
由此可见,该算法中只有加法和乘以2的运算,这在计算机内部是用位移操作来实现的,所以Bresenham直线生成算法的速度明显高于前面介绍的其它方法。
下面给出的是按Bresenham算法编写的直线生成程序:
圆弧的生成算法
圆弧的生成算法与直线的生成算法一样,也有许多种。在一个高水平的图形系统中, 我们总是希望采用运算速度更快、显示质量更高的算法。下面介绍几种有代表性的圆弧生成算法。
圆弧的扫描算法
因为圆的方程可以简写为x2+y2=R2,写成y与x的函数表达式为
显然,在给定的区域内,每取一个x值,便可算出相应的y值,然后经取整运算,可以确定应该显示的像素点。但是,在这种算法中,开方运算和取整运算极大地影响了显示速度,而且还存在一个显示质量的问题,即x以相等步长变化,计算出来的相应的圆弧上的点却是间隔不均匀的,如图7-4所示。因此,在真正实用的图形系统中,一般不会采用这种算法。
x
y
图7-4 圆弧的扫描算法
圆弧的Bresenham算法
在上述的代数法与增量法中,一些费时的运算,如乘法、开方等,使得算法的效率受到了影响。如何避开费时的运算,仅根据一些分析与判断,便能确定圆弧上的点的显示呢?人们采用的仍是Bresenham算法。下面对Bresenham圆弧算法的分析过程作较为详细的介绍。
现以第一现象中的1/4圆弧为例,如图7-5a所