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

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

0 引言

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

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

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

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

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

1 算法思想與步驟

　　1.1 Bresenham算法

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

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

　　1.2 多線寬算法

　　（1）算法思想

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

　　用內存存儲每一列Y的增量，讓單線沿著Bresenham算法形成的區(qū)域兩端移動，因為線平行，計算它們連線只需要利用存儲的Y的增量，產生新的直線，形成的直線兩端垂直，且算法計算簡單，沒有種子填充算法的設定起始種子的局限。

　　（2）算法基本步驟

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

　　①根據(jù)給出的直線的首位坐標，計算出其dx和dy；

　　②根據(jù)指定的寬度，計算出其B與O點的偏移量，得出A、B的坐標；

　　③計算出AB直線中坐標增量，存入內存中；

　　④將點在AD、BC移動，根據(jù)內存中Y的變化量，計算出新的A′B′直線，直到到達另一個邊界。

　?。?）直角保持與寬度控制

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

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

　　-dx/dy=KAD（2）

　　平移AB用Bresenham算法計算出下一個端點B′點坐標時，直接使用OO′的dy代替AD的dx，OO′的dx代替AD的dy，保證AD最大限度垂直于OO′。BC直線上的做法相同，保證新產生A′B′的OO′與平行。這樣就可以保證線段兩端與線段垂直。

2 實驗結果及分析

　　2.1 顯示效果

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

　　2.2 復雜度分析

　　以斜率絕對值小于1為例。設長度為a，寬度為b，則一共有a×b個像素需要點亮。其運算量主要在于計算像素點的坐標。在第一次計算完成邊界線AB后，其Y坐標變化被存儲起來，由于以后畫出的直線與第一條直線平行，因此以后每次計算坐標只需要加上內存讀取器Y坐標的變化0或者1。其復雜度近似為O（N）。

　　下面為本算法使用Keil軟件在Cortex-M4內核下仿真的結果。其中圖4為長度20、寬度5不變，角度變化下4種算法產生線段時間；圖5為寬度5、角度30不變，長度變化下4種算法產生線段時間；圖6為長度36、角度30不變，寬度變化下4種算法產生線段時間圖。

　　注：以上長度、寬度單位為像素，而角度單位為度，運算時間單位為微秒。

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

　　2.3 內存消耗分析

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

3 結論

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

　　參考文獻

　　[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)的改進Bresenham反走樣算法[J].計算機技術與發(fā)展，2006，16（11）：100-102.

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

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

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