ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2006年第46卷第10期2006,V o l.46,N o.1021/401719-1722基于自适应步长的直线生成算法黄斌茂,　张　利(清华大学电子工程系,北京100084)收稿日期:2005-07-13基金项目:国家自然科学基金资助项目(60172027)作者简介:黄斌茂(1981-),男(汉),江西,硕士研究生。

通讯联系人:张利,副教授,E-mail:chin azh angli@mail.tsingh 摘　要:为了改进计算机图形学中画线算法的效率,提出一种基于自适应步长的直线生成算法和一种集成了对称性、最大公约数和自适应步长的集成算法。

由于直线仅包含一种或两种与斜率有关的像素模式,算法利用这一特性,自适应地采用最佳步长,在单次判决中生成多个像素。

通过综合使用直线像素的中点对称性、最大公约数性质以及像素模式的有限性等3种相互独立的特性,集成算法在单次判决中可生成更多像素。

算法的仿真结果表明:新算法生成直线的效率更高、速度更快。

关键词:Bresenham 算法;自适应步长;对称性;最大公约数;像素模式中图分类号:T P 391.4文献标识码:A文章编号:1000-0054(2006)10-1719-04Self -adaptive step straight -line algorithmsHUA NG Binmao ,ZH ANG Li(Department of Electronic Engineering ,T s inghua University ,Beij ing 100084,China )Abstract :Line draw ing algorithm in computer grap hics sys tems is improved w ith a self-adaptive s tep straight-line algor ith m and an oth er integrated algorithm th at combines self-adaptive step algorithm w ith th e s ymmetr y an d greatest com mon divisor (GCD)-based algor ith ms.Th e self-adaptive step algorithm uses the limited pixel patter ns inherent in line s egments to adaptively determine the best step that corres ponds to the line slope an d then gen erates m ulti-pixels in each judgemen t.T he integrated algorithm utilizes the sym metry,GCD,an d limited pixel patterns and gen erates more p ixels in each parisons w ith Bresen ham 's algorithm sh ow th at the integrated algorithms are m ore effective and efficient.Key words :Bresen ham's algorithm ;self-adaptive steps;s ymmetr y;greatest common divisor (GCD);pixel patter n直线段(简称直线)是图形的基本单元,图形渲染的速度很大程度上取决于直线的生成速度。

Br esenham 算法[1]是目前使用最为广泛的直线生成算法,它采用整数加减运算,避免了浮点数操作和乘除运算,从而极大地提高了算法的效率。

在该算法的基础上,研究界提出了多种改进算法。

其改进思路可分为两类:1)将直线分割成多条短线段,采用并行算法生成直线[2];2)通过一次误差判别操作,在一次循环中生成多个像素[312]。

直线上的像素点关于直线中点对称,文[5]利用这一特性,每个循环生成两个像素点。

对端点为S (x s ,y s )及E (x e ,y e )的直线,当 x e -x s 和 y e -y s 的最大公约数r 不为1时,直线上有r 段像素模式相同的线段。

文[4]通过在每个循环内生成r 个像素,加速了直线的生成。

但当r =1时,该算法比Brensenham 算法效率要低。

文[68]采用N 步长(N ≥2)直线生成方法,将八分圆分成多个子区,每个子区有N +1种像素模式,根据直线的斜率可决定其子区归属。

该算法每个循环可生成N 个像素。

其不足是:每个子区中的N +1种像素模式的初始化开销很大;步长固定,不能采用最佳步长。

还有一些研究者结合对称性、多步长、最大公约数提出集成算法[9]。

文[10]简要地提出自适应步长的思想,但未给出推导证明与具体算法;文[11,12]在直线斜率为0< m <0.5时,一次生成多个像素以提高直线的生成效率,但没有注意到直线像素模式关于m =±0.5的对称性。

此外,文[11,12]都没有给出算法的仿真结果。

上述各种改进算法的共同点是在每个循环中生成多个像素,但每次生成的像素个数固定,不能自适应地采用最合适的步长。

本文利用直线在八分圆中像素模式的对称性,以及任一直线只有一种或者两种与斜率相关的像素模式这一特性,提出一种基于自适应步长的直线生成算法,并进一步集成基于对称性及基于GCD 的直线生成算法,给出一种更高效的集成算法。

1　自适应步长直线生成算法本文将“直线”约定如下:起点为S (x s ,y s ),终点为E (x e ,y e ),斜率为m 。

并使用D 、X 表示相邻像素(x i ,y i )和(x i +1,y i +1)处于对角位置或水平位置。

误差判别项为p ,所需的条件测试数为t ,更新p 所需的操作数为i ,更新x 、y 所需的加减法操作数为a 。

整数的加减操作、条件测试、累加操作都分别占用一个单位的运行时间,衡量算法性能的指标TEP(theor etical ev aluation perform ance)[10]可这样计算:TEP =t +a +i 。

直线斜率m 存在4种一般情况:-∞<m <-1,-1<m <0,0<m <1,1<m <∞;5种特殊斜率:m =0,±1,±∞;特殊斜率的直线可直接生成。

不失一般性,本文的讨论约定在0<m <1的八分圆中进行。

1.1　直线的一些性质对起点为S (x s ,y s )、终点为E (x e ,y e )的直线L 1,通过将L 1的起点S (x s ,y s )平移为S 1(0,0),可得到起点为S 1(0,0)、终点为E 1(P ,Q )的直线L 0(其中P =x e -x s ,Q =y e -y s )。

性质1　当0<m <0.5时,对直线L 0:1)L 0可表示为L 0=X n1DX n2D …DXnQ +1;2) i ∈N ,且1≤i ≤Q +1,n i 满足n i ∈N ,n i >0,且当2≤i ≤Q ,n i ∈{A ,A -1},其中A =1/m ;3)n 1、n Q +1满足n 1=n Q +1=1/2m ;4)m =Q Q +∑Q +1i =1ni.证明　初始化x =0、y =0、x end =P ,误差判别项p =m ;p 代表点C (理想直线与网格线的交点)与栅格点B 之间的差值。

显然,若p <0.5,像素点B 比A 的误差要小,反之则应该使用像素点A 逼近理想直线(按图1的情况,应该使用像素A )。

图1　中点判决准则由此可得生成直线像素时的判决准则和误差判别项p 的更新方式为:if(p <0.5){p =p +m ;下一个像素相对位置为X ;}else{p =p -1;下一个像素相对位置为D ;}1)假设存在两个连续的D ,不妨设它们位于X ni之后,设决定第n i 个X 的误差项为p i (-0.5≤p i <0.5);由假设,更新之后有p i +1=p i +m 且0.5≤p i +1<1,p i +2=p i -1+2m 且0.5≤p i +2<1。

由于0<m <0.5,因而p i +2=p i -1+2m <0.5,与上面的推理矛盾!故不可能存在连续的两个D 。

　2)假设存在i (2≤i ≤Q )使得n i 有其他取值,即n i <A -1或n i >A 。

设决定n i 个X 之前的D 的误差项为p (0.5≤p <1且p -m <0.5)。

由此可知:决定第n i 个X 的误差项为:p ′=p +n i m -1(-0.5≤p ′<0.5),决定第n i 个X 之后的D 的误差判别项为p ″=p +(n i +1)m -1(0.5≤p ″<0.5+m )。

由于A =1/m ,因而1-m <A m ≤1。

当n i >A 时,n i m ≥(A +1)m >1,由此可得:p ′≥0.5,矛盾!当n i <A -1时,(n i +1)m ≤(A -2+1)m ≤1-m ,因而有:p ″<0.5,矛盾!由此可知,0<m <0.5的直线L 0可表示为:L 0=X n 1DX n 2D …DX n Q +1。

3)由于直线关于中点对称,易得n 1=n Q 。

对于X n 1D ,假设决定D 的误差判别项为p ,此时p =(n 1+1)m ,且有0.5≤p <0.5+m ,由此可得n 1=n Q =1/2m .4)由L 0的表达式易得,证明过程略。

图2显示了起点为S (0,0)、终点为E (14,3)的直线L 0的像素模式。

该直线可表达为X 2DX 3DX 4DX 2。

由性质1易得:A =14/3=4,n 1=n 4=14/6=2。

由图可见:除去端点处的两小段像素X 2,该直线中存在的两种像素模式为DX 3和DX 4。

由于篇幅限制,只能示意短直线的像素模式,对于稍长的直线,像素模式的有限性和重复性将更加明显。

图2　直线像素模式示意图性质2　位于同一个八分圆中的直线关于m =1720清华大学学报(自然科学版)2006,46(10)±0.5具有像素模式的对称性。