基于Wu反走樣的三角形光柵化邊緣反走樣算法

吳連慧，周建江，夏偉杰，陳雅雯

（南京航空航天大學 電子信息工程學院，江蘇 南京210016）

1 引 言

在機載顯示系統(tǒng)中，圖形顯示占據(jù)重要地位。傳統(tǒng)的機載圖形顯示大多通過處理器（CPU）和軟件方法實現(xiàn)。為了進一步提高圖形的實時性，考慮到FPGA 具有強大的邏輯資源和豐富的IP核，利用FPGA 來代替CPU 完成圖形處理的大量顯示運算任務，實現(xiàn)圖形硬件加速。

三角形光柵化［1－2］是圖形光柵化模塊中重要組成部分，許多復雜多邊形的光柵化都可以在CPU 端分解為多個三角形光柵化命令，通過調(diào)用三角形光柵化模塊來實現(xiàn)。由于三角形光柵化的邊緣會出現(xiàn)明顯鋸齒現(xiàn)象，因此需要對其進行反走樣處理。

本文基于水平線掃描轉(zhuǎn)換設計了一種快速的三角形光柵化硬件加速算法。同時利用Wu直線反走樣思想，研究三角形邊緣反走樣，提出了一種計算量小、顯示效果良好的邊緣反走樣算法。并在FPGA 上實現(xiàn)了該算法。

2 三角形光柵化硬件加速算法

圖形加速系統(tǒng)框圖如圖1所示，用戶接口模塊接收上層CPU 解析的圖形命令，由圖形光柵化模塊來實現(xiàn)基本圖元光柵化，并通過緩存管理模塊將其存儲到外部存儲器中。

圖1 圖形加速系統(tǒng)框圖Fig.1 Diagram of graphics acceleration

光柵化是指把物體的數(shù)學描述及其相關(guān)的顏色信息轉(zhuǎn)換為屏幕上的像素的過程。三角形光柵化算法思想是，將三角形分解為水平直線頂點信息；再調(diào)用水平直線光柵化模塊進行逐行掃描轉(zhuǎn)換，從而實現(xiàn)光柵化。難點在于如何將三角形依次分解為水平直線端點。

三角形光柵化示意圖如圖2 所示。步驟如下：

圖2 三角形光柵化示意圖Fig.2 Schematic of triangle rasterization

（1）根據(jù)三角形頂點的縱坐標將3個頂點從小到 大 重 新 排 列，記 作（xmin，ymin），（xmid，ymid），（xmax，ymax），其中ymin≤ymid≤ymax，橫坐標之間不存在大小關(guān)系。根據(jù)ymid所在水平直線將普通的三角形分解成上三角形和下三角形。同時計算出3條邊的斜率：

（2）對上三角形進行水平直線端點的分解，其中i是從1到（ymid－ymin）依次遍歷的整數(shù)，則：

（3）對下三角形進行水平直線端點的分解，其中j是從0到（ymax－ymid－1）依次遍歷的整數(shù)，則：

圖3為三角形和四邊形光柵化Matlab仿真圖，可以看出，兩者的邊緣存在明顯鋸齒狀的失真現(xiàn)象，所以需要進行反走樣處理。

圖3 光柵化仿真圖Fig.3 Simulation of rasterization

3 基于Wu算法的邊緣反走樣

常見的三角形光柵化反走樣算法有超級采樣、多級采樣和自適應采樣等［3］，共同點是通過采樣更多的子像素來反走樣，在提高圖形質(zhì)量的同時，花費了較大的資源代價和時間消耗。考慮三角形內(nèi)部像素點完全被三角形像素區(qū)域覆蓋，不需要反走樣，因此只需要對三角形邊緣區(qū)域進行反走樣，而三角形邊緣是三條直線，因此考慮可以借鑒直線反走樣算法對三角形邊緣進行反走樣處理。

3.1 Wu直線反走樣算法

Wu直線反走樣算法［4］是一種基于區(qū)域采樣原理的簡單有效且硬件易實現(xiàn)的直線反走樣算法，其算法思想是：沿著長軸方向每前進一個像素單位，在短軸方向上距離理想直線距離最近的兩個像素都點亮，兩者亮度之和等于待繪制直線的亮度值，且距離理想直線遠的亮度低，距離近的亮度高。Wu反走樣算法原理如圖4所示。

假設繪制顏色的亮度值為color，相鄰像素坐標距離為1，若坐標（x，y）在從軸方向上與理想線段之間的距離為d（0≤d≤1），坐標（x，y）上像素點的亮度值表示為G（x，y），則：

Wu反走樣算法降低了直線光柵化時候的鋸齒現(xiàn)象。借鑒這種算法思想對三角形邊緣單獨處理。

圖4 Wu直線反走樣算法示意圖Fig.4 Schematic of Wu anti－aliasing algorithm

3.2 水平直線外側(cè)直接添加插值點

由于三角形光柵化是基于水平直線掃描的，考慮每次生成水平直線時，直接利用Wu反走樣的思想對水平直線端點進行反走樣處理。

圖5 水平直線外側(cè)添加插值點示意圖Fig.5 Schematic of adding interpolation points outer the horizontal line

圖5為水平直線外側(cè)直接添加插值點示意圖。圖中以上三角形水平直線外側(cè)添加插值點為例，水平直線左側(cè)的插值點坐標為（xil，yi），對應的像素點的亮度值表示為G（xil，yi），且插值點坐標（xil，yi）到 浮 點 坐 標（xi1，yi）的 距 離 表 示 為dli。則：

其中，? 表示向下取整。水平直線右側(cè)的插值點坐標為（xir，yi），對應的像素點的亮度值表示為G（xir，yi），且 插 值 點 坐 標（xir，yi）到 浮 點 坐 標（xi2，yi）的距離表示為dri。則：

圖6為三角形和四邊形光柵化時水平直線外側(cè)添加插值點仿真圖。從圖中可以看出當斜率k較大（｜k｜＞1／2）時，圖形邊緣反走樣效果較好；但圖形邊緣斜率k較?。ǎ黭｜≤1／2）時，反走樣效果不好；且用三角形拼接成多邊形填充時，拼接處會有虛化現(xiàn)象。不同斜率顯示效果有差異的原因是，Wu算法是分長軸短軸的，按照長軸遍歷和按照短軸遍歷，效果是不一樣的。而三角形分解成的水平直線是統(tǒng)一在水平直線端點兩側(cè)添加插值點的，本身不好區(qū)分長短軸，因此會影響反走樣效果。三角形拼接處出現(xiàn)虛化現(xiàn)象是因為拼接處沒有判斷出是多邊形內(nèi)部的值，反而按照三角形邊緣進行了插值處理，既浪費了時間又影響顯示效果。

圖6 水平直線外側(cè)添加插值點仿真圖 Fig.6 Simulation of adding interpolation points outer the horizontal

水平直線外側(cè)直接添加插值點的方法比較簡單，但缺點是，沒有考慮長短軸的問題，當斜率較小時，效果不好；且拼接成多邊形時，拼接處會有虛化現(xiàn)象。

3.3 三角形三邊外側(cè)反走樣

水平直線外側(cè)添加插值點的方法是對每次分解的水平直線端點進行處理，而不是將三角形3條邊緣看作3條直線單獨處理。考慮直接將其當作3條直線用Wu算法對直線進行單側(cè)的反走樣處理。圖7為不反走樣、水平直線外側(cè)添加插值點、三邊外側(cè)反走樣對比仿真圖。從圖中可以看出，當直線與水平線夾角在±30°之內(nèi)時，該直線外側(cè)反走樣插值效果比水平直線外側(cè)直接添加插值點效果好；其他情況下兩者的效果相同。

圖7 反走樣前后仿真對比圖Fig.7 Comparison of anti－aliasing effect

最終顯示效果與圖8右側(cè)所示效果相同，三角形三邊外側(cè)反走樣優(yōu)點是顯示質(zhì)量好。缺點是，對于3條邊本身來說，已經(jīng)脫離了三角形的關(guān)系，很難判斷哪邊是外側(cè)；對于同一條邊，不同的三角形內(nèi)外側(cè)也不盡相同；對于同一條邊，端點的順序不同，內(nèi)外側(cè)是相反的。因此，對三角形三條邊單獨進行單側(cè)反走樣判斷情況過于復雜。

4 改進的邊緣反走樣算法

分析上述兩種方法的優(yōu)缺點如表1所示。綜合兩者的優(yōu)點，提出一種算法能夠有較好的顯示效果，同時實現(xiàn)簡單且沒有虛化現(xiàn)象。

表1 邊緣反走樣算法優(yōu)缺點對比Tab.1 Advantages and disadvantages of different edge anti－aliasing algorithms

4.1 算法思想

4.1.1 邊緣疊加Wu反走樣直線

由于三角形三邊外側(cè)反走樣效果好，但對于邊緣直線本身，內(nèi)外側(cè)的判斷比較復雜，所以考慮直接在三角形光柵化的基礎(chǔ)上進行3條邊的反走樣繪制。直線和三角形命令都是由上層CPU 發(fā)送的，但底層FPGA 并行處理時，先后順序是不定的。如果先繪制三角形填充再繪制直線，效果如圖8（a）所示；如果先繪制直線，再繪制三角形填充，效果如圖8（b）所示。從圖8（b）看出，此方法效果比水平直線添加插值的方法好，與三邊外側(cè)反走樣效果相同，但不需要進行內(nèi)外側(cè)的判斷?？紤]如何解決疊加順序不定帶來的影響。

圖8 邊緣疊加Wu反走樣直線仿真圖Fig.8 Simulation of overlaying Wu anti－aliasing line for the edge

4.1.2 插值考慮背景值

為了解決疊加順序不同帶來的顯示效果差異，在用單線寬直線反走樣對邊緣處理時，考慮當前坐標的背景顏色值對插值后顏色值的影響。假設坐標（x，y）在從軸方向上與理想線段之間的距離為d（0≤d≤1），坐標的背景顏色亮度為GB（x，y），當前圖形顏色值為G，若坐標（x，y）上像素點的亮度值表示為G（x，y），則：

先繪制直線，再繪制三角形填充時，在兩者重疊的坐標處，將三角形填充顏色值color直接寫入到當前坐標對應的DDR3地址中，覆蓋掉之前的插值結(jié)果。最終顯示效果與圖8（b）相同。

先繪制三角形填充，再繪制直線時，在兩者重疊的坐標處，將背景值color從DDR3 對應地址中讀回，代入公式進行計算，則

從公式可以看出，對于顏色值為color時，重疊部分讀回背景值也是color，最終結(jié)果還是color，不會出現(xiàn)虛化現(xiàn)象。最終顯示效果也與圖8（b）相同。

當前方法效果好，簡單易行，且不反走樣三角形和反走樣邊界直線的順序是任意的。多邊形光柵化時，只需要發(fā)送多邊形的邊緣直線進行反走樣，而不需要將分解的三角形各邊都進行反走樣。

此外，由于三角形光柵化是圖形加速模塊的子模塊，圖形加速模塊也包括基本的反走樣直線，可以調(diào)用現(xiàn)有的反走樣直線算法，不需要另外編寫程序。

4.2 FPGA仿真和硬件實現(xiàn)

在Xilinx的Kintex－7FPGA 上對不反走樣三角形填充和邊緣反走樣進行ModelSim 仿真［5］和FPGA 硬件實現(xiàn)，對比邊緣反走樣前后的三角形光柵化效果。

4.2.1 ModelSim 仿真

三角形填充仿真時，令輸入坐標為（280，100）；（300，250）；（170，140），對應的Matlab仿真效果如圖3（a）所示。每解析出一條水平直線端點信息，就調(diào)用水平直線光柵化程序繪制出來。從圖9可以看出，繪制時，水平直線的長度由短到長，后又由長到短。本文系統(tǒng)輸出分辨率為1 920×1 080，幀速率為60 Hz，時鐘頻率為400 MHz。用新算法繪制該三角形光柵化時，耗時約33.75μs。三條邊反走樣繪制，耗時約2.16μs。相對于三角形光柵化消耗的時間，反走樣處理占用時間少，且效果改進明顯。

圖9 三角形光柵化ModelSim 仿真圖Fig.9 Simulation of triangle rasterization by ModelSim

圖10 三角形光柵化及其反走樣屏幕顯示對比圖Fig.10 Display comparison of triangle rasterization and its anti－aliasing

4.2.2 FPGA 硬件實現(xiàn)

新算法由于計算量小，適合于硬件實現(xiàn)。三角形光柵化及其反走樣顯示效果如圖10 所示。可以看到反走樣后顯示效果比不反走樣效果好。且用新算法繪制耗時遠低于一幀圖像的最大處理時間（16.7ms），滿足系統(tǒng)設計要求，故可以用于機載圖形顯示系統(tǒng)。

5 結(jié) 論

介紹了三角形光柵化硬件加速算法，由于其邊緣存在明顯鋸齒狀的失真現(xiàn)象，所以需要進行反走樣處理。基于Wu反走樣算法的思想，考慮了水平線外側(cè)加插值點和三邊外側(cè)反走樣直線的算法。綜合兩者的優(yōu)缺點，提出了一種改進的邊緣反走樣算法。該算法在繪制光柵化的三角形的同時，疊加考慮背景像素作用的Wu反走樣直線。且用于多邊形光柵化時只需要發(fā)送多邊形的邊緣直線進行反走樣而不需要將分解的三角形各邊都進行反走樣。后續(xù)研究中可以進一步改進反走樣直線的算法［6－7］，從而改進三角形反走樣的效果。

經(jīng)過對比，本文提出的三角形光柵化的邊緣反走樣算法有效提高了三角形光柵化后邊緣的顯示效果，計算量小、效果好，且易于FPGA等硬件實現(xiàn)。

［1］ 黃銳，付宇卓，趙峰.基于FPGA 的三角形光柵化模塊［J］.計算機工程，2008，34（22）：242－244.Huang R，F(xiàn)u Y Z，Zhao F.FPGA－based triangle rasterization module［J］.Computer Engineering，2008，34（22）：242－244.（in Chinese）

［2］ 饒志恒.圖形處理器圖形管線的研究與實現(xiàn)［D］.長沙：湖南大學，2011.Rao Z H.Research and implementation on graphics pipeline of graphic processing unit［D］.Changsha：Hunan University，2011.（in Chinese）

［3］ 黃銳.實時嵌入式圖形系統(tǒng)中的三角形光柵化研究與設計［D］.上海：上海交通大學，2008.Huang R.Study and design of triangle raster in real－time embedded graphics system［D］.Shanghai：Shanghai Jiaotong University，2008.（in Chinese）

［4］ Wu X.An efficient anti aliasing technique［J］.Computer Graphics，1991，25（4）：143－152.

［5］ 王文華，何斌，任建岳.線陣CCD 成像系統(tǒng)自校圖形設計［J］.光學精密工程，2009，17（8）：2011－2016.Wang W H，He B，Ren J Y.Design of self－check figures in linear CCD imaging system［J］.Optics and Precision Engineering，2009，17（8）：2011－2016.（in Chinese）

［6］ Xian Z，Xiaobing L.Improved DDA line drawing anti－aliasing algorithm based on embedded graphics system［C］.2010 3rd International Conference on Advanced Computer Theory and Engineering （ICACTE），IEEE，2010，2：V2－497－V2－499.

［7］ Yong J，Lu－ya W，Yue－yue C.The research and implementation of line anti－aliasing algorithm based on coordinate system rotation［C］.2010 International Conference on Audio Language and Image Processing（ICALIP），IEEE，2010：180－184.