摘  要： 直線生成算法是計(jì)算機(jī)圖形的基本算法，而現(xiàn)有算法都有其弊端，因此提出一種基于Bresenham任意寬度直線的生成算法。該算法首先根據(jù)直線的斜率、長(zhǎng)度和寬度計(jì)算出直線所形成的邊界，然后讓單線寬直線沿著邊界移動(dòng)，使整個(gè)區(qū)域填充。該算法生成的直線兩端與邊界垂直，在直線斜率變化的情況下，直線寬度不會(huì)發(fā)生變化，且具有應(yīng)用背景廣泛、運(yùn)算速度快、占用內(nèi)存小等特點(diǎn)。

　　關(guān)鍵詞： 直線生成；Bresenham畫線算法；區(qū)域填充

0 引言

　　嵌入式圖形系統(tǒng)的圖形顯示是通過光柵顯示器來實(shí)現(xiàn)的，而光柵顯示器實(shí)際上是一個(gè)像素矩陣，光柵顯示器通過點(diǎn)亮一個(gè)個(gè)像素，確定最佳逼近于圖像的像素集。直線是嵌入式圖形系統(tǒng)中最基本的元素，因此直線生成算法也是其他各類圖形算法的基礎(chǔ)，得到了廣泛的研究?，F(xiàn)有的直線生成算法主要有：DDA算法、中點(diǎn)畫線算法以及Bresenham算法等，其中應(yīng)用最廣泛的是Bresenham算法[1-3]，其優(yōu)點(diǎn)是不需要進(jìn)行小數(shù)和取整運(yùn)算，只需要進(jìn)行整數(shù)加法和乘法運(yùn)算來計(jì)算出待生成的像素點(diǎn)的坐標(biāo)。Bresenham算法是只針對(duì)于單像素寬的直線。而實(shí)際應(yīng)用中，經(jīng)常使用的線段是有線寬和線型的。對(duì)于多線寬直線的生成，目前國(guó)內(nèi)外的研究不多，現(xiàn)有方案主要有線刷子算法、正方形刷子算法和區(qū)域填充算法。

　　線刷子算法原理：假設(shè)直線斜率在[-1，1]之間，垂直的長(zhǎng)度線寬的線段中心對(duì)準(zhǔn)線段起點(diǎn)，線段順著單像素線條軌跡移動(dòng)，直到末端。對(duì)于斜率絕對(duì)值大于1的，該刷子是水平方向的。線刷子算法具有算法簡(jiǎn)單、效率高的特點(diǎn)，但是刷子法生成的直線端點(diǎn)形狀不理想，寬度小于指定寬度，而且寬度隨斜率的改變而改變。

　　正方形刷子算法則是把邊長(zhǎng)為指定線寬的正方形沿著中心線平移，獲得具有寬度的直線。與線刷子算法類似，其末端也是水平的或者垂直的，且線寬隨線段斜率的改變而改變。

　　區(qū)域填充算法[4-6]則是使用改進(jìn)的Bresenham計(jì)算出線段所形成矩形區(qū)域邊界，畫出封閉的區(qū)域，然后利用種子填充算法將矩形區(qū)域填充起來。其優(yōu)點(diǎn)是生成直線端頭標(biāo)準(zhǔn)，寬度可控，很接近理想多寬度直線。但是算法復(fù)雜，而且在背景與線段區(qū)域邊界形成多分割區(qū)域時(shí)，容易形成填充孤島，無(wú)法填充整個(gè)區(qū)域；填充過程中無(wú)法利用像素坐標(biāo)之間的內(nèi)在聯(lián)系；且該算法應(yīng)用于CAD/CAM造型系統(tǒng)，使用種子填充算法，占用內(nèi)存大。

　　綜上可以看出，以上算法都有其局限性，因此本文提出一種新的任意寬度直線的生成算法，該算法能夠生成的任意寬度直線的末端與直線方向垂直，寬度可控，算法簡(jiǎn)單，占用內(nèi)存小，適用背景廣的任意直線算法，適合嵌入式設(shè)備。

1 算法思想與步驟

　　1.1 Bresenham算法

　　Bresenham算法是應(yīng)用最廣泛的直線掃描轉(zhuǎn)換算法。其原理是：不考慮像素形狀、大小的影響，經(jīng)過各行、各列像素中心構(gòu)造一組網(wǎng)格線，若直線斜率絕對(duì)值小于1，則按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素與此交點(diǎn)的最近像素；若直線斜率絕對(duì)值大于1，則計(jì)算與水平線的交點(diǎn)最近像素。該算法的優(yōu)點(diǎn)在于采用增量計(jì)算，使得對(duì)于每一列，只要檢查當(dāng)前誤差項(xiàng)的符號(hào)，就可以確定該列的所求像素。

　　Bresenhan算法誤差項(xiàng)d遞增如圖1所示。設(shè)該直線的起始點(diǎn)為A（x1，y1），終點(diǎn)為B（xn，yb），則直線的斜率為K=dy/dx，dx=xn-x1，dy=yn-y1。從起點(diǎn)A，下一個(gè)像素的行坐標(biāo)是x1+1，列坐標(biāo)則遞增1或者不變。是否增1，取決于圖1所示誤差項(xiàng)d的值。因?yàn)锳點(diǎn)為圖像的起點(diǎn)，圖像經(jīng)過其中心，所以誤差項(xiàng)d的初始值為0。當(dāng)x增加1，d的值相應(yīng)遞增直線的斜率K，即d=d+K，若d≥1，則減去1，讓d始終在0~1之間。x1+1列像素中，到直線最近的點(diǎn)為C、D，C點(diǎn)到直線垂直距離A′C=1-d，D點(diǎn)到直線的垂直距離為A′D=d。當(dāng)d>0.5時(shí)，則A′C<A′D，則C點(diǎn)距離直線更近，取C點(diǎn)；而當(dāng)d<0.5時(shí)，D點(diǎn)更近，取D點(diǎn)；當(dāng)d=0.5時(shí)，與上述兩個(gè)像素一樣近，約定取C點(diǎn)。為了避免浮點(diǎn)運(yùn)算，將直線的斜率放大2×dx，K=dy/dx×2×dx=2×dy，誤差項(xiàng)d=d+dy×2，當(dāng)d>2×dx，則更靠近C（x1+1，y1+1）；當(dāng)d≤2×dx，則更靠近D（x1+1，y1）。對(duì)于K>1，可以將坐標(biāo)軸顛倒，根據(jù)Y變化計(jì)算X。對(duì)于K<0的情況，Y變化相反，那么X增加1，則Y的變化不變或減小1。通過遞增運(yùn)算，計(jì)算直線通過最近的每一個(gè)點(diǎn)，畫出直線。

　　1.2 多線寬算法

　?。?）算法思想

　　任意寬度直線生成算法中，直線刷子法利用生成的單寬度直線，在直線沿Y軸移動(dòng)到另一端（若直線的斜率在[-1，1]）。若直線斜率不在[-1，1]內(nèi)，則改成沿X軸移動(dòng)。而區(qū)域填充算法是使用Bresenham算法計(jì)算指定寬度直線的邊界形成封閉區(qū)域，再進(jìn)行利用種子填充算法填充，形成的直線兩端標(biāo)準(zhǔn)。結(jié)合兩種算法的優(yōu)點(diǎn)，讓單線寬線段沿著計(jì)算出的邊界移動(dòng)，即可以得到指定寬度的直線。

　　用內(nèi)存存儲(chǔ)每一列Y的增量，讓單線沿著Bresenham算法形成的區(qū)域兩端移動(dòng)，因?yàn)榫€平行，計(jì)算它們連線只需要利用存儲(chǔ)的Y的增量，產(chǎn)生新的直線，形成的直線兩端垂直，且算法計(jì)算簡(jiǎn)單，沒有種子填充算法的設(shè)定起始種子的局限。

　?。?）算法基本步驟

　　為了方便討論，假設(shè)直線斜率在[0，1]之間，其他情況可以通過坐標(biāo)軸變換得到。假設(shè)直線L的起點(diǎn)為O（x0，y0），其終點(diǎn)坐標(biāo)為O′（x1，y1），令x1>x0，y1>y0，直線的寬度為D，并記終點(diǎn)O兩側(cè)的直線終點(diǎn)分別是A、B，點(diǎn)O′兩側(cè)的直線終點(diǎn)分別是C、D，且記直線AB為L(zhǎng)1，直線CD為L(zhǎng)2。

　?、俑鶕?jù)給出的直線的首位坐標(biāo)，計(jì)算出其dx和dy；

　?、诟鶕?jù)指定的寬度，計(jì)算出其B與O點(diǎn)的偏移量，得出A、B的坐標(biāo)；

　?、塾?jì)算出AB直線中坐標(biāo)增量，存入內(nèi)存中；

　?、軐Ⅻc(diǎn)在AD、BC移動(dòng)，根據(jù)內(nèi)存中Y的變化量，計(jì)算出新的A′B′直線，直到到達(dá)另一個(gè)邊界。

　　（3）直角保持與寬度控制

　　如圖2所示，理想情況下直線OO′與直線BC、AD垂直，則可以推導(dǎo)出KBC×KOO′=-1。直線OO′斜率為KOO′=dx/dy，那么得到直線AD的斜率，則可以根據(jù)式（1）、（2）計(jì)算出邊界點(diǎn)A與起點(diǎn)O的偏移量，由于ABCD是矩形，O′是B、C中點(diǎn)，O是A、D中點(diǎn)，則B、C與O′點(diǎn)的偏移量與A、D與O′的偏移量相等，因此得到A、B、C、D坐標(biāo)。

　　dx2+dy2=（D/2）2（1）

　　-dx/dy=KAD（2）

　　平移AB用Bresenham算法計(jì)算出下一個(gè)端點(diǎn)B′點(diǎn)坐標(biāo)時(shí)，直接使用OO′的dy代替AD的dx，OO′的dx代替AD的dy，保證AD最大限度垂直于OO′。BC直線上的做法相同，保證新產(chǎn)生A′B′的OO′與平行。這樣就可以保證線段兩端與線段垂直。

2 實(shí)驗(yàn)結(jié)果及分析

　　2.1 顯示效果

　　圖3是本算法生成的直線顯示圖。從圖中可以看出，該算法產(chǎn)生的直線的兩端與邊界垂直，而且能很好地控制定制直線的寬度，使其在角度變化的情況下，直線寬度基本沒有變化。

　　2.2 復(fù)雜度分析

　　以斜率絕對(duì)值小于1為例。設(shè)長(zhǎng)度為a，寬度為b，則一共有a×b個(gè)像素需要點(diǎn)亮。其運(yùn)算量主要在于計(jì)算像素點(diǎn)的坐標(biāo)。在第一次計(jì)算完成邊界線AB后，其Y坐標(biāo)變化被存儲(chǔ)起來，由于以后畫出的直線與第一條直線平行，因此以后每次計(jì)算坐標(biāo)只需要加上內(nèi)存讀取器Y坐標(biāo)的變化0或者1。其復(fù)雜度近似為O（N）。

　　下面為本算法使用Keil軟件在Cortex-M4內(nèi)核下仿真的結(jié)果。其中圖4為長(zhǎng)度20、寬度5不變，角度變化下4種算法產(chǎn)生線段時(shí)間；圖5為寬度5、角度30不變，長(zhǎng)度變化下4種算法產(chǎn)生線段時(shí)間；圖6為長(zhǎng)度36、角度30不變，寬度變化下4種算法產(chǎn)生線段時(shí)間圖。

　　注：以上長(zhǎng)度、寬度單位為像素，而角度單位為度，運(yùn)算時(shí)間單位為微秒。

　　由于平行線采用的是線段平移，而且該線刷子法產(chǎn)生的多寬度直線的寬度小于實(shí)際直線，因此該算法的效率最高；而正方形刷子法由于像素大量冗余填寫，因此其效率很低；而區(qū)域種子填充算法采用的是種子填充算法，需要頻繁地出棧、入?；蛘哌f歸，因此效率也相對(duì)比較低。而本文提出的方法在效率上和線刷子法最接近，而且能夠控制寬度，兩端與直線完全垂直，產(chǎn)生很好的效果。

　　2.3 內(nèi)存消耗分析

　　為了加快運(yùn)算速度，本文中的線刷子算法使用內(nèi)存存儲(chǔ)單線段在X（dx>dy）變化下Y軸的變化量（1或者0），因此其使用的內(nèi)存為dx，單位bit。正方形刷子算法不需要儲(chǔ)存額外數(shù)據(jù)，不需要額外內(nèi)存。種子填充算法需要出棧入棧，因此需要很大的?？臻g。而本論文提出的算法同樣采用這種方案加快運(yùn)行速度，因此其使用與線刷子算法相同，額外占用的內(nèi)存空間很小。

3 結(jié)論

　　為了解決現(xiàn)存任意直線生成算法的弊端，提出一種基于Bresenham的算法。本算法首先計(jì)算出直線所形成的區(qū)域，然后利用斜率、長(zhǎng)度相同單直線沿著邊沿掃描整個(gè)區(qū)域，從而實(shí)現(xiàn)區(qū)域填充。該算法不僅始末端的效果好，寬度與理想直線接近，在斜率變化時(shí)基本不發(fā)生變化，而且算法復(fù)雜度小，適用于各種嵌入式設(shè)備中。圖7是本算法應(yīng)用在一嵌入式系統(tǒng)中的心電圖demo實(shí)例，其中心電圖的曲線是用幾段直線替代的。

　　參考文獻(xiàn)

　　[1] JAMES D F， ANDRIES V D ，STEVEN K F， et al. Computer graphics： principles， second edition in C[M].Pearson Education Press， 2004：21-35.

　　[2] BOYER V， BOURDIN J J. Auto-adaptive step straight-line algorithm[J]. IEEE Computer Graphics and Applications， 2000，20（5）： 67-69.

　　[3] 謝瑩，許榮斌，趙宏坤.基于嵌入式圖形系統(tǒng)的改進(jìn)Bresenham反走樣算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（11）：100-102.

　　[4] 駱朝亮，謝忠.一種快速的多線寬直線反走樣算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（21）：188-190.

　　[5] 李震霄，何援軍.任意寬度直線的繪制與反走樣[J].武漢大學(xué)學(xué)報(bào)（工學(xué)版），2006，39（4）：130-133.

　　[6] 龍艷婷.任意寬度直線生成算法的研究與實(shí)現(xiàn)[J].沈陽(yáng)工程學(xué)院學(xué)報(bào)（自然科學(xué)版），2012，8（4）：353-355，358.