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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 Wu直線反走樣算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 改進(jìn)的邊緣反走樣算法

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

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

4.1 算法思想

4.1.1 邊緣疊加Wu反走樣直線

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

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

4.1.2 插值考慮背景值

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

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

先繪制三角形填充，再繪制直線時(shí)，在兩者重疊的坐標(biāo)處，將背景值color從DDR3 對(duì)應(yīng)地址中讀回，代入公式進(jìn)行計(jì)算，則

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

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

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

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

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

4.2.1 ModelSim 仿真

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

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

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

4.2.2 FPGA 硬件實(shí)現(xiàn)

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

5 結(jié) 論

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

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

［1］ 黃銳，付宇卓，趙峰.基于FPGA 的三角形光柵化模塊［J］.計(jì)算機(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］ 饒志恒.圖形處理器圖形管線的研究與實(shí)現(xiàn)［D］.長(zhǎng)沙：湖南大學(xué)，2011.Rao Z H.Research and implementation on graphics pipeline of graphic processing unit［D］.Changsha：Hunan University，2011.（in Chinese）

［3］ 黃銳.實(shí)時(shí)嵌入式圖形系統(tǒng)中的三角形光柵化研究與設(shè)計(jì)［D］.上海：上海交通大學(xué)，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)自校圖形設(shè)計(jì)［J］.光學(xué)精密工程，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.