一種快速的Bresenham直線生成改進(jìn)算法

摘 要：直線的生成算法是圖形光柵化中最基本的算法，基于經(jīng)典的Bresenham算法，提出了一種新的直線生成算法，該算法通過直線的第一和第二像素行的像素點(diǎn)數(shù)目計(jì)算其他各個(gè)像素行的像素點(diǎn)數(shù)目，利用直線的對(duì)稱性，每執(zhí)行一次生成兩個(gè)像素行。算法中不包含浮點(diǎn)運(yùn)算和取整運(yùn)算，且算法的執(zhí)行次數(shù)減少，使得直線的生成速度加快。

關(guān)鍵詞：圖形光柵化；Bresenham算法；增量；誤差項(xiàng)

中圖分類號(hào)：TP301.6

直線是圖形中的基本元素，到目前為止已有很多種直線的生成算法，如數(shù)值微分法、中點(diǎn)畫線法和Bresenham算法[1]，其中Bresenham算法研究的最多，它的原理是：以各行各列的像素為中心虛擬一組坐標(biāo)線，按直線上x坐標(biāo)從小到大的順序，計(jì)算直線與各個(gè)坐標(biāo)線的交點(diǎn)，確定與該交點(diǎn)距離最小的像素。本文在研究了經(jīng)典的Bresenham算法以及諸多改進(jìn)算法之后，提出了一種快速的Bresenham直線生成改進(jìn)算法，既保留了Bresenham算法中無需浮點(diǎn)運(yùn)算和取整運(yùn)算的優(yōu)點(diǎn)，又能使得每次計(jì)算生成一個(gè)像素行，極大地提高了算法的執(zhí)行效率。

1 Bresenham算法的基本思想

先考慮直線段位于第一象限、斜率|m|≤1時(shí)的掃描轉(zhuǎn)換過程從直線的第一個(gè)像素點(diǎn)（x0，y0）開始，以橫坐標(biāo)由大到小的順序依次尋找與直線最接近的像素點(diǎn)。如圖1所示，假設(shè)坐標(biāo)為（xk，yk）為直線的當(dāng)前像素點(diǎn)，然后在列xk+1上確定掃描線y的值。

Bresenham算法的優(yōu)點(diǎn)在于使用增量計(jì)算，確定所選的像素。相對(duì)于其他直線的生成算法而言，它避免了乘除法運(yùn)算和取整運(yùn)算，效率較高。但是每次只能判斷一個(gè)誤差項(xiàng)的符號(hào)，生成一個(gè)像素點(diǎn)。因此，許多專家對(duì)Bresenham算法作了一些改進(jìn)，基本上都是通過直線的斜率求每行的像素點(diǎn)個(gè)數(shù)[3]，來提高直線的生成速度，但由于引進(jìn)了浮點(diǎn)運(yùn)算甚至除法運(yùn)算，使得整體的改進(jìn)效率提高不大。

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

設(shè)像素點(diǎn)P（xp，yp）為當(dāng)前的像素點(diǎn)，則待選擇的像素點(diǎn)可能是點(diǎn)E或點(diǎn)G如圖2所示。設(shè)F（x，y）為需光柵化的直線函數(shù)，點(diǎn)E和點(diǎn)G的中點(diǎn)為M，如果F（M）>0，則點(diǎn)M在該直線的下方，選則點(diǎn)G，如果F（M）≤0，則點(diǎn)M在直線上方，選則點(diǎn)E。Bresenham算法定義了一個(gè)判定變量d=F（xp+1，yp+1/2），通過d值的正負(fù)來選擇下一個(gè)像素點(diǎn)的坐標(biāo)[4]。

通過以上分析可以得知，通過Bresenham算法生成的直線除卻起始和終止兩行像素點(diǎn)外，中間各像素行的像素點(diǎn)個(gè)數(shù)滿足：Q≤e≤Q+1。

確定了像素行的第k個(gè)像素點(diǎn)的判定變量的符號(hào)，可以推斷該行的像素點(diǎn)個(gè)數(shù)。因?yàn)閐k=d1+2kdy-2dx，如果dk<0，該行的像素點(diǎn)個(gè)數(shù)為Q+1；如果dk>0，下一像素行的像素點(diǎn)個(gè)數(shù)為Q個(gè)，計(jì)算一次d值可以找到一個(gè)像素行的所有像素點(diǎn)。

本改進(jìn)算法的關(guān)鍵是求Q的值，本文大膽猜測使用直線的前兩行像素點(diǎn)個(gè)數(shù)求Q的值。通過數(shù)學(xué)分析證明，若Bresenham算法生成的直線的前兩個(gè)像素行分別有n和m個(gè)像素點(diǎn)，則

可以通過兩種情況論證上述結(jié)論：

1）如果Bresenham算法生成的直線的第1個(gè)像素行的像素點(diǎn)個(gè)數(shù)為n，則2n-2≤dx/dy<2n，則該直線第n個(gè)像素點(diǎn)的d≤0，而第n+1個(gè)像素點(diǎn)的d>0，即 ，其中，d0=2dy-dx為d的初值，是直線第2個(gè)像素點(diǎn)的d值，將d0代入 ，得2n-2≤dx/dy<2n；

2）如果Bresenham算法生成的直線的第2個(gè)像素行有m個(gè)像素點(diǎn)，則m-1≤dx/dym+1，且2n-1≥m+1>dx/dy≥2n-2則Q=2n-2；若2ndx/dy≥m-1則Q=m-1；若2n=m+1，dn+1>0，而第m+n個(gè)像素點(diǎn)的判定變量dm+n≤0，且第m+n+1個(gè)像素點(diǎn)的dm+n+1>0，則Q=2n-1。

3 算法及驗(yàn)證

將上述數(shù)學(xué)思想轉(zhuǎn)化為算法[6]，程序如下。其中變量valuel，valueB是直線和背景的顏色值；函數(shù)Linel表示參照value取點(diǎn)共n個(gè)像素點(diǎn)；由Bresenham算法生成前兩行以及末行像素，新算法生成其他各像素行。

在該算法中，沒有除法、取整以及浮點(diǎn)運(yùn)算，只通過兩次減法就求得了n和m，通過一次計(jì)算又求得了Q的值，每執(zhí)行一次就能生成一個(gè)像素行，另利用直線的對(duì)稱性，使得每執(zhí)行一次就能生成兩個(gè)像素行。將該算法在計(jì)算機(jī)上實(shí)現(xiàn)，如表1所示，改進(jìn)算法與Bresenham算法相比效率明顯提高。

由算法的原理可知，當(dāng)待生成直線只有一個(gè)像素行時(shí)，改進(jìn)算法與Bresenham算法的生成速度相同，其他情況下，改進(jìn)算法的執(zhí)行速度都明顯高于經(jīng)典的Bresenham算法，且生成的像素行數(shù)越多，節(jié)省的執(zhí)行時(shí)間就越明顯。

4 結(jié)束語

本文在研究經(jīng)典Bresenham算法的基礎(chǔ)上，提出了一種快速的直線生成算法，利用直線的第一行像素點(diǎn)個(gè)數(shù)推出其他各像素行的像素點(diǎn)數(shù)目，充分利用直線的對(duì)稱性使得每執(zhí)行一次能生成兩個(gè)像素行，相對(duì)于經(jīng)典Bresenham算法每執(zhí)行一次只能生成一個(gè)像素點(diǎn)來說，極大地提高了直線的生成速度。

參考文獻(xiàn)：

[1]James D Foley.計(jì)算機(jī)圖形學(xué)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2004：48-56.

[2]Mel Slater.計(jì)算機(jī)圖形學(xué)與虛擬環(huán)境[M].北京：機(jī)械工業(yè)出版社，2004：270-272.

[3]Asiful Haque ，Mohammad Saifur Rahman ，Mehedi Bakht.Drawing lines by uniform packing[J].Computers Graphics，2006（02）：207-212.

[4]鄭宏珍.改進(jìn)的Bresenham直線生成算法[J].中國圖像圖形學(xué)報(bào)，1999（07）：606-608.

[5]SunYan.The parallel algorithm of Bresenham[J].Computer Engineering and Applications，2001（21）：136-137.

[6]孫巖.并行的Bresenham直線生成算法[J].計(jì)算機(jī)工程與應(yīng)用，2001（21）：136-137.

作者簡介：孫云（1989-），女，工學(xué)碩士，主要研究方向：圖形圖像處理。

作者單位：重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054

基金項(xiàng)目：重慶市科學(xué)技術(shù)委員會(huì)科技攻關(guān)項(xiàng)（cstc2012gg-yyjs40011）。