王利祥，肖鐵軍

（江蘇大學 計算機科學與通信工程學院，江蘇 鎮(zhèn)江212013）

0 引 言

傳統(tǒng)的嵌入式圖形顯示的處理方式主要依賴于微處理器，然而當面對高質量和高效率顯示需求時，單純使用軟件來實現多邊形填充［1，2］這一復雜的過程，顯然成為了圖形顯示質量的一個瓶頸，因此使用硬件來滿足高要求顯示不失為一種可行的方案。

傳統(tǒng)的邊標志算法［3］在遇到極值點［4］及狹長條時會出現異常填充的現象，因此許多文獻對其進行了改進，如王秀華等［5］提出了一種改進的邊標志算法，該算法成功解決了極值點問題，但是引入了掃描線填充算法［6］中使用的邊表結構，使得算法的數據結構變得復雜；葉國棟等［7］提出了解決狹長條多邊形填充的方法，但是在算法實現過程中使用了求交點運算，使得算法的效率有所降低。本文在深刻理解目前邊標志算法的基礎上，提出了一種新的改進算法。該算法充分利用了光柵化多邊形邊界時的特點，使用計數型的邊標記變量flag，采用對訪問的邊界像素點的標記進行加1的操作，方便簡捷地將極值點和狹長條上的點與普通邊界點區(qū)別開來，從而解決了極值點和狹長條填充時產生異?，F象的問題。該算法既保持了傳統(tǒng)邊標志算法不需要邊表結構以及求交點運算的優(yōu)點，又解決了特殊點填充時產生異?，F象的問題，最終使用現場可編程門陣列（FPGA）［8］進行實現并加以驗證。

1 傳統(tǒng)邊標志算法分析及缺陷

1.1 傳統(tǒng)邊標志算法的概述

傳統(tǒng)的邊標志算法的思想及實現比較簡單，大致可以分為兩步：

（1）邊標記，即在將多邊形的邊進行掃描轉換時對邊界上的像素點打上邊的標志。

（2）填充，對于每條與多邊形相交的掃描線，按照從左到右的順序逐個像素點進行掃描，判斷該像素點是否在多邊形的內部，如果在多邊形的內部則進行填充。填充的具體實現規(guī)則為：設置一個布爾變量insider，用于表示當前點的狀態(tài)。對于每條掃描線，insider的初始值為假。當訪問到邊界像素點時insider的值便取反。當insider的值為真時，便把該像素點填充為填充色；否則便填充為背景色。

1.2 缺 陷

傳統(tǒng)的邊標志算法在遇到以下情景時便會出現異常填充現象。

1.2.1 極值點

極值點的一般判斷方法是設某兩條邊的交點為A，如果兩條邊的另一個頂點都位于點A的同側，則點A即為極值點。否則不是極值點。例如，對于含有極值點的多邊形（10，10）、（50，120）、（90，10）、（50，70），當掃描線為10和120時，就會出現在點 （50，120）處出現帶 “尾巴”的現象以及2個最高點處不應該連接。填充結果如圖1所示。

圖1 未處理極值點時的實際填充效果

1.2.2 狹長條

狹長條問題是指當多邊形的兩條邊的斜率非常接近時，其多邊形區(qū)域太過細窄以致在這個區(qū)域中容納不下掃描線上任何可見的最短跨段。例如對于狹長條多邊形 （50，25）、（50，225）、（90，225）、（90，125）、（55，125），對于點 （50，25）附近即會出現帶 “尾巴”的填充效果，如圖2所示。

2 改進的邊標志算法及流程圖

圖2 未處理狹長條問題的實際填充效果

基于上述描述分析可以發(fā)現，之所以產生填充錯誤的原因在于傳統(tǒng)的邊標志算法沒有將普通的邊界點與極值點和狹長條上的像素點區(qū)別開來，因此針對上述原因，本文提出了一種新的改進方法，其主要思想為：在進行光柵化多邊形的邊時，使用flag（初始值為0）標記是否為多邊形的邊界，當在對其余邊進行光柵化時取出當前像素點的flag值，對flag值加1之后，再存儲到當前像素點的flag中。依次光柵化多邊形的每一條邊。在進行填充的過程中，首先取出當前像素點的flag值，如果當前像素點的flag值為1，則分別取出其前一個和后一個像素點的flag值，若前后2個像素點的flag值都為1，則布爾變量insider保持不變，否則取反。填充顏色時如果flag的值大于0或者insider為真時，則對當前像素點進行填充，否則填充為背景色。如對于圖1中的A點和B點，在對兩點所在邊界光柵化之后他們的flag值等于2，是大于1的，因此在進行多邊形填充時首先將A和B點的顏色填充為填充色。又因為其前后2個像素點的flag值不都為1，因此insider的值仍未假，從而兩點右邊的像素點不進行填充。算法的流程如圖3所示。

3 硬件實現

3.1 多邊形邊界的光柵化

在光柵化多邊形的邊界時，鑒于Bresenham直線算法［9－11］沒有除法及小數運算等適合硬件實現的優(yōu)點，本文選用了Bresenham直線算法。大致思想為：將二維平面劃分為8個區(qū)域，如圖4所示，首先將任意斜率的直線統(tǒng)一映射到直線斜率為 ［0，1］的IA區(qū)域中，因此在對任意直線的光柵化就簡化為只對區(qū)域IA中的直線進行光柵化，然后再使用傳統(tǒng)的Bresenham直線畫法繪制直線。在光柵化的過程中再映射到原始的任意直線。這樣不僅使硬件結構得到簡化，硬件資源占有量也會得到相應的減少。

在邊標志算法硬件實現中，直線光柵化的大致繪制過程：在圖5中，ST0狀態(tài)用于接收多邊形邊的頂點信息，如果邊是水平邊或豎直邊則相應的轉移到ST2、ST3、ST4或者ST5。若為傾斜的直線則轉移到ST6狀態(tài)，在狀態(tài)PRE＿DRAW對直線進行映射處理，將其它區(qū)域的直線映射到統(tǒng)一的區(qū)域IA中，在狀態(tài)POST＿DRAW時將統(tǒng)一區(qū)域的直線映射回到原始的區(qū)域中，在狀態(tài)ADDRESS中得到相應的地址，進入狀態(tài)READ＿RAM對邊標記存儲器進行讀操作，GET＿FLAG時得到當前地址的flag，并在狀態(tài)JUDGE＿FLAG時flag加1，然后將處理之后的flag值在狀態(tài)WRITE＿MEMORY寫入到邊標記存儲器中，依次對下一個像素點進行處理，直至邊的終點。

3.2 多邊形掃描轉換

在圖6中，對第一條邊進行掃描時，在INIT＿MAX＿MIN狀態(tài)對橫縱坐標的最大最小值用得到的邊的頂點信息初始化，然后GET＿POINT狀態(tài)得到以后各個邊的頂點信息。在ORIGIN＿MAX＿MIN及TERMINAL＿MAX＿MIN求得多邊形掃描的最小區(qū)域，即多邊形頂點的橫縱坐標的最大值和最小值。之后進入多邊形邊的光柵化狀態(tài)即上述的Bresenham直線算法。當bresenham＿done信號有效后即多邊形的一個邊光柵化之后，轉入JUDGE＿LINE狀態(tài)，判斷是否對所有的邊進行了光柵化，若有，則轉向GET＿POINT狀態(tài)，進行下一個邊的光柵化；否則，轉向SCAN＿Y狀態(tài)，開始多邊形的掃描轉換過程。

所有的邊光柵化之后，根據求得的多邊形的最小掃描區(qū)域，掃描線scan＿y從最小值Y＿MIN開始依次對該水平線上的每個在X＿MIN和X＿MAX之間的像素點進行掃描，直至Y＿MAX，并在ADDRESS狀態(tài)時得到當前像素點及其前后兩個像素點在存儲器中的地址。依次對多邊形的最小掃描區(qū)域中的每個像素點進行處理。當scan＿y大于Y＿MAX時轉移到IDLE＿POLY狀態(tài)，表示多邊形中的每個像素點處理完畢。

4 驗證系統(tǒng)及實驗結果分析

為了驗證改進后的邊標志算法的實際填充效果，本文首先在Intel酷睿i3雙核主頻為2.0GHz的處理器，內存為1G的PC計算機上分別以極值點多邊形 （10，10）、 （50，120）、 （90，10）、 （50，70）和狹長條多邊形 （50，25）、（50，225）、（90，225）、（90，125）、（55，125）作為實例使用VC＋＋6.0在上述PC機上進行了驗證，驗證結果表明沒有出現異常填充的現象，之后采用DE2－70FPGA開發(fā)板和分辨率為800＊480的LCD顯示屏搭建了如圖7所示的基于FPGA的顯示方案。

從圖8可以看出，當掃描線scan＿y和scan＿x都等于10時，遇到極值點 （10，10），此時從邊標志存儲器中讀取該極值點的標記值iflag＿poly等于2，根據本文提出的算法思想，將該極值點填充為填充色，即ocolor＿data＿poly等于0。此時insider的值沒有被取反，即仍為0，因此該極值點之后的像素點沒有被填充。由此可見本文提出的算法正確處理了極值點問題，同樣可以驗證狹長條問題。從實際填充效果圖9和圖10中可以看出，使用改進之后的邊標志算法填充后的多邊形完全解決了極值點和狹長條問題，填充效果良好。

從系統(tǒng)資源占用情況的角度分析，該系統(tǒng)使用的邏輯單元總數為1938個。由此可以看出改進之后的算法在硬件資源的占用量上還是比較少的，適合在嵌入式系統(tǒng)中使用。

圖9 有極值點時的填充效果

圖10 狹長條多邊形的填充效果

從實時性角度分析，系統(tǒng)中使用的時鐘頻率為33 MHz。由上述狀態(tài)機可以得到一個邊界像素點的處理大約需要8個時鐘周期，掃描轉換過程中一個像素點需要10個時鐘周期。對于上述的極值點多邊形來說，邊界像素點為174個，多邊形的最小掃描范圍中像素點的個數為9061個，從而可以估算出處理該多邊形大約需要的時間為2.95ms。從上面的分析可以看出，改進之后的算法完全可以滿足嵌入式系統(tǒng)中高質量顯示的要求。

5 結束語

本文提出的改進方法不僅保持了傳統(tǒng)的邊標志算法數據結構簡單、思想簡單以及容易實現的優(yōu)點，而且僅采用對邊標記變量進行加1的方法，統(tǒng)一進行邊界點標志，便可一次性的完成了極值點和狹長條上的點與普通邊界點的區(qū)別，從而成功解決了極值點多邊形和狹長條多邊形填充時產生的異?，F象。在改進后的算法的實現過程中不僅完全避免了為解決極值點和狹長條問題而引進復雜的邊表結構或者引入求交點運算的問題，而且在使用硬件實現之后在很大程度上提高了填充效率，能夠減輕嵌入式系統(tǒng)中微處理器的負擔，提高系統(tǒng)的處理能力。

［1］LI Zhaoheng，ZHANG Anding，WANG Zhoulong.An improved rasterizing algorithm based on boundary－labeling ［J］.Science of Surveying and Mapping，2009，34 （5）：121－122（in Chinese）.［李兆恒，張安定，王周龍.改進的邊標志柵格化算法 ［J］.測繪科學，2009，34 （5）：121－122.］

［2］LIU Yang，LI Qingcheng，BAI Zhenxuan.Research and implementation of polygon filling algorithm based on hardware［J］.Journal of Tianjin Normal University （Natural Science Edition），2010，30 （1）：19－22 （in Chinese）.［劉洋，李慶誠，白振軒.多邊形填充硬件算法的研究與實現 ［J］.天津師范大學學報 （自然科學版），2010，30 （1）：19－22.］

［3］HAO Xiaosong.The common problems and solutions of boundary labeling method in the course of realization ［J］.Journal of Xi’an University of Engineering Science and Technology，2006，20 （5）：643－645 （in Chinese）.［郝筱松.邊標志算法實現過程中的常見問題及解決方法 ［J］.西安工程科技學院學報，2006，20 （5）：643－645.］

［4］WU Zhangwen，YANG Dailun，GOU Chengjun，et al.Singular point distinguishing algorithm for area filling ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2003，15 （8）：979－983 （in Chinese）.［吳章文，楊代倫，勾成俊，等.區(qū)域填充極點判別算法 ［J］.計算機輔助設計與圖形學學報，2003，15 （8）：979－983.］

［5］WANG Xiuhua，YAN Bing.An improved edge marking algorithm ［J］.Journal of Computer Applications，2004，24（s1）：181－182 （in Chinese）.［王秀華，嚴兵.一種邊標志填充的改進算法 ［J］.計算機應用，2004，24 （s1）：181－182.］

［6］LI Ping，HAN Jungang，LI Zidi.The hardware design and implementation of area filling scan－line algorithm ［J］.Microcomputer Information，2011，27 （6）：124－125 （in Chinese）.［李平，韓俊剛，李自迪.區(qū)域填充掃描線算法的硬件設計與實現 ［J］.微計算機信息，2011，27 （6）：124－125.］

［7］Ye Guodong，Lin Gui，Zhu Changqing.A designed edge marking fill algorithm for elongated polygon ［C］／／Database Technology and Applications，2009：22－24.

［8］HUA Chun，XIAO Tiejun.Moving object detection algorithm with Gauss modeling based on FPGA ［J］.Computer Engineering and Design，2011，32 （9）：3000－3003 （in Chinese）.［華純，肖鐵軍.基于FPGA的高斯建模運動目標檢測算法［J］.計算機工程與設計，2011，32 （9）：3000－3003.］

［9］JIA Yunning，ZHAO Feng.Implementation of graphics accelerator of line raster based on Bresenham algorithm ［J］.Information Technology，2008，32 （9）：229－232 （in Chinese）.［賈運寧，趙峰.Bresenham直線光柵化算法的硬件實現方法研究 ［J］.信息技術，2008，32 （9）：229－232.］

［10］LIU Jing，LI Jun，SUN Han.A modified Bresenham algorithm for line generation ［J］.Computer Applications and Software，2008，25 （10）：247－249 （in Chinese）.［劉晶，李俊，孫涵.改進的Bresenham直線生成算法 ［J］.計算機應用與軟件，2008，25 （10）：247－249.］

［11］Niu Lianqiang，Feng Haiwen.A line segments approximation algorithm of grating lines ［C］／／IEEE Computer Society，2009：34－37.