一种改进的等分迭代Bresenham直线生成算法

李竹林，邓石冬

（延安大学 计算机学院，陕西 延安716000）

一种改进的等分迭代Bresenham直线生成算法

李竹林，邓石冬

（延安大学 计算机学院，陕西 延安716000）

本文利用直线的对称性，采用等分迭代的思想对Bresenham直线生成算法进行改进，使得原算法一次只能生成一个点的Bresenham直线生成算法改进为一次能生成四行扫描线上的所有像素点。该算法思想简单，效率较高。如果直线的长度较大时，可以将迭代分段，生成更多扫描行上的所有点，该并行操作成使算法速度成2的幂次方增加，因此该改进算法对直线生成算法效率的提高研究有重要的价值。

Bresenham；等分迭代；对称性；直线生成

直线是生成各种图形的基本元素，直线生成算法是其它各类图形算法的基础，也是光栅图形学最基本的一个任务，因此直线的生成算法已得到了人们的广泛研究，并已出现许多有效的算法，其中经典的算法有：数值微分法(DDA)、中点画线法、Bresenham算法[1-2]。其中DDA法是一种从二次曲线的微分方程生成曲线的方法。这种方法直观，但因为在算法中引入浮点运算和舍入运算，不利于硬件实现而致使算法效率太低。中点直线生成法是利用像素的中点设计了基本差别式F，根据F的符号确定下一个像素点的位置。算法又进一步消除了小数运算，所以适合硬件实现。Bresenham直线生成算法巧妙地利用一个误差项的符号值决定下一个像素点的位置，因此是3种算法中效率最高、使用最广泛方法。其优点在于不需要进行小数和取整运算，只需要使用整数加法和乘法来计算待生成的像素点。但是，Bresenham算法也存在不足。第一，没有充分利用像素之间的相关性，每生成一个点，都要进行一次误差项的符号；第二，直线的对称性没有充分利用。于是，有不少文献提出了改进的Bresenham直线生成算法，改进思想主要包括：第一，在每一条扫描线上一次生成多个点[3-4]，如二步法、四步法等；第二，利用直线的对称性，从起点终点同时出发生成直线[5]；第三，前二者结合起来，一次生成两行扫描线上的点[6-7]。在以上的改进算法中，实现了一次生成两个像素点或者一次生成两行扫描线上的2个或4个像素点甚至更多的像素点，大大提高了算法效率。

本文提出了一种基于等分迭代的改进Bresenham直线生成算法，将直线分成两段，可以一次生成四条扫描线上的直线点像素，可进一步提高了算法的效率。特别地，当直线很长且对精度要求不十分高时，还可以迭代分段，并行生成更多条扫描线上的直线像素点，以进一步提高直线的生成速度，甚至以2的幂次方增加。

1 Bresenham直线生成算法

Bresenham直线算法的基本原理是通过在每列像素中确定与理想直线最近的像素来进行直线的扫描转换的。若斜率| k|＜1，在x方向上每增加一个像素，y方向是否增加一个像素是根据计算误差项的符号e确定的，如图1所示：如果e＞0.5，y方向前进一步，即y++；如果e≤0.5，则y方向不走步，即y取原值。

图1 Bresenham画线法的误差项EFig.1 Error E of Bresenham line algorithm

假设k为斜率，且|k|＜1；若|k|＞1,将下面算法中的x,y对换即可。其中k=△y/△x-0.5。

Bresenham直线生成算法步骤如下：

Step1:设符号项e=-0.5，计算斜率k，令e=e+k；

Step2:如果e≤0，则x方向走一步，即x++；

否则，x方向走一步，y方向也走一步，且e=e-1。即x++,y++,e--；

当x＞x2时，转向Step4；

Step3:e=e+k，转向Step2；

Step4:结束。

为了避免浮点运算与除法运算，算法做了如下的处理。

1)将符号项e的初值由原来的e=e+k，即e=△y/△x-0.5的两边同时乘以2△x，使得e=2△y-△x；

2)相应地，当符号判断e＞0时，y方向也走一步，且e=e-1中的e=e-1修改为e=e-2△y。

2 改进的Bresenham直线生成算法

为了描述方便，做一些假设与定义：

设待生成直线段的两个端点坐标为(x1,y1)，(x2,y2)，且有x2≥x1、y2≥y1，则记Δx=x2-x1，Δy=y2-y1。

定义1：若Δx≥Δy，即斜率|k|≤则以x为主轴，y为副轴；反之，若Δx＜Δy，则以y为主轴，x为副轴。

2.1 并行直线生成算法

文献[7]提出了一种并行的Bresenham直线生成方法，其基本思想就是利用直线的对称性，一次同时生成两行上的多个点。算法步骤如下：

Step1:令xx1=x1，xx2=x2，yy1=y1，yy2=y2；且计算斜率的倒数1/k值；

Step2:若1/k为整数，则直线的两端在主轴上同时走1/k步（方向相反），即xx1=xx1+1/k,xx2=xx2-1/k，在副轴上同时走1步 （方向也相反），即yy1++，yy2--；若1/k为非整数，转Step3；

Step3:若1/k为非整数，如1/4.5，那么在长轴要么走4步，要么走5步。判断规则为：当符号e加偏差项后若小于等于1，则走4步，即xx1=xx1+4；否则，走5步，即xx1=xx1+5；

Step4:当xx1＜=xx2时，算法结束。

2.2 本文算法改进

2.2.1 改进算法的基本思想

将直线等分成两段，两段直线生成算法同时进行；并且根据直线的对称性，起点和终点按相反的方向同时生成直线。这样，就将原来的一条直线生成过程划分成从4个端点并行生成，4倍地提高了速度。

定义2：以主轴（假设x轴）进行划分。若Δx是偶数，则主轴划分为[x1，xm]，[xm，x2]；若 Δx是奇数，则将主轴划分为[x1，xmb]，[xmt，x2]两段，如图2、图3所示。

其中，

图2 当Δx为奇数时直线段的分割图Fig.2 The line segment segmentation graph when Δx is odd

图3 当Δx为偶数时直线段的分割图Fig.3 The line segment segmentation graph when Δx is even

定义3：分割点处y的取值。当Δx偶数时，记为；当Δx奇数时，记为ymb和ymt，如图2、图3所示。它们的取值分别如(3)、(4)式：

特别地，当ym、ymb、ymt不是整数时，四舍五入。

2.2.2 改进算法的步骤

有一条直线P1P2，端点坐标分别为(x1,y1)，(x2,y2)。

改进后的Bresenham直线生成算法步骤如下：

Step1:计算Δx与Δy，确定主轴(假设主轴为x轴)；

Step2:

if Δx为偶数，根据公式(1)和(3)，计算出xm,ym的值，则直线被分为两段[(x1,y1),(xm,ym)],[(xm,ym),(x2,y2)]；

否则，根据公式(2)和(4)，计算出xmb、xmt、ymb、ymt的值，则直线被分为两段[(x1,y1),(xmb,ymb)],[(xmt,ymt),(x2,y2)]；

Step3:将分成两段直线的四个端点起，用2.1节中文献[7]的改进Bresenham直线生成算法同时进行，方向如图2、图3中的虚线所示，直到x1＞=xmb，转向Step4；

Step4:结束。

3 结果分析

本文改进算法的思想是将直线分两段，并且左右方向同时行走，因此，直线生成的速度几乎是原直线生成算法的4倍。但是速度提高的代价是可能做取整运算。

用本文的算法一次能生成4条扫描线上的多个点（点的多少取决于斜率的倒数的大小，即1/k），如图4所示。

在做实验测试时，随机生成800条、1 200条直线，每条直线的长度不小于200个像素数。用原算法、文献[7]算法以及本文改进的算法，测试结果如表1所示。

图4 本文算法一次生成的点Fig.4 The points of this algorithm generated

表1 3种生成算法测试结果对比表Tab.1 The test resu lts com parison for three algorithm

从模拟实验结果也可以看出，本文的改进算法能大大提高直线生成的速度。但是如果生成的直线长度包含像素点较少时，就没有实际意义。另外，当直线足够长时，本文改进算法的并行思想，可拓宽成迭代划分线段，该并行操作成使算法运行速度成2幂次方增加，这样可形成快速的直线生成算法。

4 结束语

本文根据直线段本身的对称性，将线段为成等长的两段。对于这两段，从起始和终点同时按照相反的方向生成，即主轴方向的起始端每前进一步，终端就后退一步。因此，算法改进的实质是将直线段分成四段，并行生成，大大提高了算法的效率。事实上，对一些较长的直线段生成，还可以进一步迭代以提高算法的效率。不足的是，该改进算法效率的提高是以可能取整运算为代价的。因此，进一步研究该算法并设法消除本文算法中的取整运算与除法运算是下一步的主要研究方向。

[1]孙家广.计算机图形学[M].3版.北京：清华大学出版社，2005.

[2]陆玲，桂颖，等.计算机图形学[M].北京：电子工业出版社，2012.

[3]李高平,檀结庆.改进的直线BreSenham算法[J],合肥工业大学学报：自然科学版,2003,26(5):1000-1004. LI Gao-ping,TAN Qing-tan.A modif ied Bresenham's algorithm of line-drawing[J].Journal of Hefei University of Technology:Natural Science Edition,2003,26(5):1000-1004.

[4]唐荣锡，汪嘉业.计算机图形学教程[M]，北京：科学出版社，2008.

[5]舒若,张焕春,经亚枝.一种基于Bresenham算法的直线快速反走样技术[J],机械制造与研究,2002,40(5):15-17. SHU Ruo,ZHANG Huan-chun,JING Ya-zhi.A fast technique for drawing ant-ialiased straight line based on bresenham algorithm[J].Machine Building&Automation,2002,40(5):15-17.

[6]刘晶，李俊，孙涵，等.快速直线生成算法[J].金陵科技学院学报,2007,23(3):9-12. LIU Jing,LI Jun,SUN Han,et al.Fast algorithm for line drawing [J].Journal of Jinling Institute of Technology,2007,23(3):9-12.

[7]孙岩,唐棣.并行的Bresenham直线生成算法[J].计算机工程与应用,2001,4(21):136-138．SUN Yan,KANG Li.The parallel algorithm of Bresenham[J]. Computer Engineering and Applications,2001,4(21):136-138.

Improved algorithm of Bresenham line generation based on halving and iteration

LI Zhu-lin,DENG Shi-dong
（Institute of Computer Science,Yan’an University,Yan’an 716000,China）

Using the symmetry of line and adopting halving and iteration idea,the Bresenham line algorithm was improved in this paper.The advanced algorithm may generate many pixels of four scan lines,and the parallel operation can improve the speed to power of two.So,the improved algorithm has important significance to the research for line generating efficiency.

Bresenham;halving and iteration;symmetry;line generation

TP391

A

1674－6236（2015）07-0061-03

2014-08-10 稿件编号：201408041

陕西省教育厅项目(2013JK1124)；陕西省大学生创新训练项目（20141071931065）

李竹林(1972—)，女，陕西佳县人，博士，副教授。研究方向：图形图像处理。