一種改進(jìn)的等分迭代Bresenham直線生成算法

李竹林，鄧石冬

（延安大學(xué) 計(jì)算機(jī)學(xué)院，陜西 延安716000）

一種改進(jìn)的等分迭代Bresenham直線生成算法

李竹林，鄧石冬

（延安大學(xué) 計(jì)算機(jī)學(xué)院，陜西 延安716000）

本文利用直線的對稱性，采用等分迭代的思想對Bresenham直線生成算法進(jìn)行改進(jìn)，使得原算法一次只能生成一個(gè)點(diǎn)的Bresenham直線生成算法改進(jìn)為一次能生成四行掃描線上的所有像素點(diǎn)。該算法思想簡單，效率較高。如果直線的長度較大時(shí)，可以將迭代分段，生成更多掃描行上的所有點(diǎn)，該并行操作成使算法速度成2的冪次方增加，因此該改進(jìn)算法對直線生成算法效率的提高研究有重要的價(jià)值。

Bresenham；等分迭代；對稱性；直線生成

直線是生成各種圖形的基本元素，直線生成算法是其它各類圖形算法的基礎(chǔ)，也是光柵圖形學(xué)最基本的一個(gè)任務(wù)，因此直線的生成算法已得到了人們的廣泛研究，并已出現(xiàn)許多有效的算法，其中經(jīng)典的算法有：數(shù)值微分法(DDA)、中點(diǎn)畫線法、Bresenham算法[1-2]。其中DDA法是一種從二次曲線的微分方程生成曲線的方法。這種方法直觀，但因?yàn)樵谒惴ㄖ幸敫↑c(diǎn)運(yùn)算和舍入運(yùn)算，不利于硬件實(shí)現(xiàn)而致使算法效率太低。中點(diǎn)直線生成法是利用像素的中點(diǎn)設(shè)計(jì)了基本差別式F，根據(jù)F的符號確定下一個(gè)像素點(diǎn)的位置。算法又進(jìn)一步消除了小數(shù)運(yùn)算，所以適合硬件實(shí)現(xiàn)。Bresenham直線生成算法巧妙地利用一個(gè)誤差項(xiàng)的符號值決定下一個(gè)像素點(diǎn)的位置，因此是3種算法中效率最高、使用最廣泛方法。其優(yōu)點(diǎn)在于不需要進(jìn)行小數(shù)和取整運(yùn)算，只需要使用整數(shù)加法和乘法來計(jì)算待生成的像素點(diǎn)。但是，Bresenham算法也存在不足。第一，沒有充分利用像素之間的相關(guān)性，每生成一個(gè)點(diǎn)，都要進(jìn)行一次誤差項(xiàng)的符號；第二，直線的對稱性沒有充分利用。于是，有不少文獻(xiàn)提出了改進(jìn)的Bresenham直線生成算法，改進(jìn)思想主要包括：第一，在每一條掃描線上一次生成多個(gè)點(diǎn)[3-4]，如二步法、四步法等；第二，利用直線的對稱性，從起點(diǎn)終點(diǎn)同時(shí)出發(fā)生成直線[5]；第三，前二者結(jié)合起來，一次生成兩行掃描線上的點(diǎn)[6-7]。在以上的改進(jìn)算法中，實(shí)現(xiàn)了一次生成兩個(gè)像素點(diǎn)或者一次生成兩行掃描線上的2個(gè)或4個(gè)像素點(diǎn)甚至更多的像素點(diǎn)，大大提高了算法效率。

本文提出了一種基于等分迭代的改進(jìn)Bresenham直線生成算法，將直線分成兩段，可以一次生成四條掃描線上的直線點(diǎn)像素，可進(jìn)一步提高了算法的效率。特別地，當(dāng)直線很長且對精度要求不十分高時(shí)，還可以迭代分段，并行生成更多條掃描線上的直線像素點(diǎn)，以進(jìn)一步提高直線的生成速度，甚至以2的冪次方增加。

1 Bresenham直線生成算法

Bresenham直線算法的基本原理是通過在每列像素中確定與理想直線最近的像素來進(jìn)行直線的掃描轉(zhuǎn)換的。若斜率| k|＜1，在x方向上每增加一個(gè)像素，y方向是否增加一個(gè)像素是根據(jù)計(jì)算誤差項(xiàng)的符號e確定的，如圖1所示：如果e＞0.5，y方向前進(jìn)一步，即y++；如果e≤0.5，則y方向不走步，即y取原值。

圖1 Bresenham畫線法的誤差項(xiàng)EFig.1 Error E of Bresenham line algorithm

假設(shè)k為斜率，且|k|＜1；若|k|＞1,將下面算法中的x,y對換即可。其中k=△y/△x-0.5。

Bresenham直線生成算法步驟如下：

Step1:設(shè)符號項(xiàng)e=-0.5，計(jì)算斜率k，令e=e+k；

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

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

當(dāng)x＞x2時(shí)，轉(zhuǎn)向Step4；

Step3:e=e+k，轉(zhuǎn)向Step2；

Step4:結(jié)束。

為了避免浮點(diǎn)運(yùn)算與除法運(yùn)算，算法做了如下的處理。

1)將符號項(xiàng)e的初值由原來的e=e+k，即e=△y/△x-0.5的兩邊同時(shí)乘以2△x，使得e=2△y-△x；

2)相應(yīng)地，當(dāng)符號判斷e＞0時(shí)，y方向也走一步，且e=e-1中的e=e-1修改為e=e-2△y。

2 改進(jìn)的Bresenham直線生成算法

為了描述方便，做一些假設(shè)與定義：

設(shè)待生成直線段的兩個(gè)端點(diǎn)坐標(biāo)為(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 并行直線生成算法

文獻(xiàn)[7]提出了一種并行的Bresenham直線生成方法，其基本思想就是利用直線的對稱性，一次同時(shí)生成兩行上的多個(gè)點(diǎn)。算法步驟如下：

Step1:令xx1=x1，xx2=x2，yy1=y1，yy2=y2；且計(jì)算斜率的倒數(shù)1/k值；

Step2:若1/k為整數(shù)，則直線的兩端在主軸上同時(shí)走1/k步（方向相反），即xx1=xx1+1/k,xx2=xx2-1/k，在副軸上同時(shí)走1步 （方向也相反），即yy1++，yy2--；若1/k為非整數(shù)，轉(zhuǎn)Step3；

Step3:若1/k為非整數(shù)，如1/4.5，那么在長軸要么走4步，要么走5步。判斷規(guī)則為：當(dāng)符號e加偏差項(xiàng)后若小于等于1，則走4步，即xx1=xx1+4；否則，走5步，即xx1=xx1+5；

Step4:當(dāng)xx1＜=xx2時(shí)，算法結(jié)束。

2.2 本文算法改進(jìn)

2.2.1 改進(jìn)算法的基本思想

將直線等分成兩段，兩段直線生成算法同時(shí)進(jìn)行；并且根據(jù)直線的對稱性，起點(diǎn)和終點(diǎn)按相反的方向同時(shí)生成直線。這樣，就將原來的一條直線生成過程劃分成從4個(gè)端點(diǎn)并行生成，4倍地提高了速度。

定義2：以主軸（假設(shè)x軸）進(jìn)行劃分。若Δx是偶數(shù)，則主軸劃分為[x1，xm]，[xm，x2]；若 Δx是奇數(shù)，則將主軸劃分為[x1，xmb]，[xmt，x2]兩段，如圖2、圖3所示。

其中，

圖2 當(dāng)Δx為奇數(shù)時(shí)直線段的分割圖Fig.2 The line segment segmentation graph when Δx is odd

圖3 當(dāng)Δx為偶數(shù)時(shí)直線段的分割圖Fig.3 The line segment segmentation graph when Δx is even

定義3：分割點(diǎn)處y的取值。當(dāng)Δx偶數(shù)時(shí)，記為；當(dāng)Δx奇數(shù)時(shí)，記為ymb和ymt，如圖2、圖3所示。它們的取值分別如(3)、(4)式：

特別地，當(dāng)ym、ymb、ymt不是整數(shù)時(shí)，四舍五入。

2.2.2 改進(jìn)算法的步驟

有一條直線P1P2，端點(diǎn)坐標(biāo)分別為(x1,y1)，(x2,y2)。

改進(jìn)后的Bresenham直線生成算法步驟如下：

Step1:計(jì)算Δx與Δy，確定主軸(假設(shè)主軸為x軸)；

Step2:

if Δx為偶數(shù)，根據(jù)公式(1)和(3)，計(jì)算出xm,ym的值，則直線被分為兩段[(x1,y1),(xm,ym)],[(xm,ym),(x2,y2)]；

否則，根據(jù)公式(2)和(4)，計(jì)算出xmb、xmt、ymb、ymt的值，則直線被分為兩段[(x1,y1),(xmb,ymb)],[(xmt,ymt),(x2,y2)]；

Step3:將分成兩段直線的四個(gè)端點(diǎn)起，用2.1節(jié)中文獻(xiàn)[7]的改進(jìn)Bresenham直線生成算法同時(shí)進(jìn)行，方向如圖2、圖3中的虛線所示，直到x1＞=xmb，轉(zhuǎn)向Step4；

Step4:結(jié)束。

3 結(jié)果分析

本文改進(jìn)算法的思想是將直線分兩段，并且左右方向同時(shí)行走，因此，直線生成的速度幾乎是原直線生成算法的4倍。但是速度提高的代價(jià)是可能做取整運(yùn)算。

用本文的算法一次能生成4條掃描線上的多個(gè)點(diǎn)（點(diǎn)的多少取決于斜率的倒數(shù)的大小，即1/k），如圖4所示。

在做實(shí)驗(yàn)測試時(shí)，隨機(jī)生成800條、1 200條直線，每條直線的長度不小于200個(gè)像素?cái)?shù)。用原算法、文獻(xiàn)[7]算法以及本文改進(jìn)的算法，測試結(jié)果如表1所示。

圖4 本文算法一次生成的點(diǎn)Fig.4 The points of this algorithm generated

表1 3種生成算法測試結(jié)果對比表Tab.1 The test resu lts com parison for three algorithm

從模擬實(shí)驗(yàn)結(jié)果也可以看出，本文的改進(jìn)算法能大大提高直線生成的速度。但是如果生成的直線長度包含像素點(diǎn)較少時(shí)，就沒有實(shí)際意義。另外，當(dāng)直線足夠長時(shí)，本文改進(jìn)算法的并行思想，可拓寬成迭代劃分線段，該并行操作成使算法運(yùn)行速度成2冪次方增加，這樣可形成快速的直線生成算法。

4 結(jié)束語

本文根據(jù)直線段本身的對稱性，將線段為成等長的兩段。對于這兩段，從起始和終點(diǎn)同時(shí)按照相反的方向生成，即主軸方向的起始端每前進(jìn)一步，終端就后退一步。因此，算法改進(jìn)的實(shí)質(zhì)是將直線段分成四段，并行生成，大大提高了算法的效率。事實(shí)上，對一些較長的直線段生成，還可以進(jìn)一步迭代以提高算法的效率。不足的是，該改進(jìn)算法效率的提高是以可能取整運(yùn)算為代價(jià)的。因此，進(jìn)一步研究該算法并設(shè)法消除本文算法中的取整運(yùn)算與除法運(yùn)算是下一步的主要研究方向。

[1]孫家廣.計(jì)算機(jī)圖形學(xué)[M].3版.北京：清華大學(xué)出版社，2005.

[2]陸玲，桂穎，等.計(jì)算機(jī)圖形學(xué)[M].北京：電子工業(yè)出版社，2012.

[3]李高平,檀結(jié)慶.改進(jìn)的直線BreSenham算法[J],合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版,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]唐榮錫，汪嘉業(yè).計(jì)算機(jī)圖形學(xué)教程[M]，北京：科學(xué)出版社，2008.

[5]舒若,張煥春,經(jīng)亞枝.一種基于Bresenham算法的直線快速反走樣技術(shù)[J],機(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].金陵科技學(xué)院學(xué)報(bào),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].計(jì)算機(jī)工程與應(yīng)用,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

陜西省教育廳項(xiàng)目(2013JK1124)；陜西省大學(xué)生創(chuàng)新訓(xùn)練項(xiàng)目（20141071931065）

李竹林(1972—)，女，陜西佳縣人，博士，副教授。研究方向：圖形圖像處理。