基于Zigzag塊掃描的光柵化算法設(shè)計與實(shí)現(xiàn)

聶瞾 田澤 馬城城

摘 要：光柵化是圖形處理器的關(guān)鍵單元，實(shí)現(xiàn)幾何圖元到片段的轉(zhuǎn)換，其功能、性能決定了圖形處理器的優(yōu)劣。傳統(tǒng)的光柵化方法大多采用線掃描方式，利用線填充算法在水平或豎直方向填充像素，計算過程復(fù)雜、資源占用量大，不適用于對硬件資源與芯片面積有極大限制的嵌入式圖形處理器設(shè)計。文中在分析Zigzag掃描原理的基礎(chǔ)上，提出一種基于Ziazag塊掃描的光柵化算法，該算法計算過程簡練、資源消耗少。通過算法仿真平臺的驗(yàn)證，功能正確、性能較傳統(tǒng)線掃描算法提升30%以上、資源占用大大降低，滿足圖形處理器設(shè)計要求。

關(guān)鍵詞：光柵化；塊掃描；Zigzag掃描

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A

在圖形應(yīng)用快速發(fā)展的背景下，復(fù)雜的3D圖形應(yīng)用需求與日俱增。圖形處理器（Graphic Processing Unit，GPU）作為顯示系統(tǒng)的核心，以硬件加速的形式實(shí)現(xiàn)了3D圖形繪制，其功能、性能直接決定了圖形繪制的質(zhì)量和速度，在計算機(jī)系統(tǒng)中的作用日益提高。

光柵化作為圖形處理器的關(guān)鍵單元，是將幾何圖元轉(zhuǎn)換為片段的重要過程，決定圖形繪制的效率和效果，是影響圖形處理器功能、性能的重要因素。傳統(tǒng)光柵化單元大多采用線掃描實(shí)現(xiàn)，如：Bresenham算法、DDA算法等，此類算法實(shí)現(xiàn)需占用大量運(yùn)算資源和較多的存儲資源[ 1 ]。然而，嵌入式圖形處理器設(shè)計對硬件資源與芯片面積都有著極大的限制要求。基于塊掃描的光柵化方法應(yīng)運(yùn)而生，塊掃描光柵化將幾何圖元分割成以塊為單元的集合，以塊為單位進(jìn)行像素處理，充分利用了圖形數(shù)據(jù)的局部性原理，大大提高了像素生成和處理效率。

Zigzag是一種應(yīng)用廣泛的塊掃描算法，本文在分析Zigzag掃描算法基礎(chǔ)上，提出一種基于Zigzag塊掃描的光柵化算法，結(jié)合Zigzag掃描原理，自下向上“Z”型掃描圖元，利用塊頂點(diǎn)的邊界函數(shù)判斷當(dāng)前塊與圖元的關(guān)系，完成豎直方向上的Zigzag塊光柵化。在實(shí)現(xiàn)中，利用邊函數(shù)的線性變換規(guī)律，通過的加、減等簡單運(yùn)算快速迭代計算塊頂點(diǎn)的邊界函數(shù)值，減低計算復(fù)雜度，大大提高了光柵化效率。

1 ZigZag塊掃描分析

Zigzag是一種全面、高效的圖元掃描算法，計算原理明晰，實(shí)現(xiàn)簡單，廣泛應(yīng)用于現(xiàn)代圖形處理器光柵化單元中[ 2 ]。Zigzag塊掃描以像素塊為單位進(jìn)行掃描，在y軸方向上從低到高以“Z”字型向上掃描。如圖1所示。

Zigzag掃描首先從底部的起始塊出發(fā)，水平掃描當(dāng)前行，直到遇到第1個完全在三角形外的像素塊，然后Y坐標(biāo)增加一個像素塊高度，反向掃描當(dāng)前像素塊行，依此方式反復(fù)掃描，直到掃描線的Y軸坐標(biāo)大于等于終止位置的Y軸坐標(biāo)，且掃描狀態(tài)由發(fā)現(xiàn)與三角形相交的像素塊過渡到發(fā)現(xiàn)完全在三角形外的像素塊為止[ 3 ]。

在掃描過程中，當(dāng)前塊與三角形關(guān)系確定了掃描的進(jìn)行方式。具體而言，在水平方向掃描時，如果當(dāng)前塊與三角形有重疊，則向正方向繼續(xù)掃描，如果當(dāng)前塊與三角形沒有重疊則需要結(jié)合當(dāng)前行掃描狀態(tài)決定是否向上移一行繼續(xù)掃描；如果遇到第一個完全在外的塊且本行已有重疊塊的情況下，說明該行已掃描完成應(yīng)該向上移一行繼續(xù)反方向掃描；如果在沒有重疊塊的情況下遇到完全在外的塊，則說明正方向上沒有重疊快，應(yīng)該向本行的負(fù)方向掃描。豎直方向僅檢測當(dāng)前掃描行與終止位置的Y軸坐標(biāo)的關(guān)系，若大于則掃描結(jié)束，若不大于則進(jìn)行該行水平方向掃描。

2 基于Zigzag塊掃描的光柵化算法設(shè)計與實(shí)現(xiàn)

基于ZigZag塊的光柵化掃描算法包含4個處理環(huán)節(jié)，分別為圖元預(yù)處理、Zigzag掃描、塊與圖元位置關(guān)系判斷和片段生成。圖元預(yù)處理主要進(jìn)行對幾何圖元頂點(diǎn)的存儲；Zigzag掃描完成控制參數(shù)計算、掃描控制、塊參數(shù)生成；塊與圖元位置關(guān)系判斷完成塊與圖元位置關(guān)系的計算，決定Zigzag掃描路徑，生成有效塊數(shù)據(jù)；片段生成負(fù)責(zé)生成片段并對其屬性進(jìn)行插值。其中，圖元預(yù)處理和片段生成屬于上下文操作，由算法仿真平臺負(fù)責(zé)管理。文本主要討論Zigzag掃描和位置關(guān)系判斷兩大部分。

2.1 Zigzag塊掃描設(shè)計與實(shí)現(xiàn)

Zigzag塊掃描實(shí)現(xiàn)對覆蓋圖元的塊的遍歷，利用沿豎直方向的“Z”型掃描完成塊的遍歷。算法包括預(yù)處理信息計算和掃描控制2個步驟：

1）預(yù)處理計算：包括豎直方向起始、終止點(diǎn)計算，掃描起始點(diǎn)確定和初始水平掃描方向計算4部分。在預(yù)處理過程中，計算三角形頂點(diǎn)中y值最大值與最小值，則豎直方向起始值為y值最小值，終止點(diǎn)為y值最大值；掃描起始點(diǎn)為y值最小的頂點(diǎn)的坐標(biāo)；初始水平掃描方向與掃描起始點(diǎn)指向三角形中間頂點(diǎn)的方向一致。

2）掃描控制：負(fù)責(zé)進(jìn)行豎直和水平方向掃描的條件判斷，依靠當(dāng)前塊與三角形的位置關(guān)系，如果水平方向沒有遇到完全在外的塊，則應(yīng)繼續(xù)水平方向掃描，若遇到則說明當(dāng)前行掃描完畢應(yīng)向上移動一行。

根據(jù)對Zigzag塊掃描的分析，采用模塊化設(shè)計思路，建立預(yù)處理計算模塊和掃描控制模塊。預(yù)處理計算模塊根據(jù)三角形頂點(diǎn)的坐標(biāo)信息，找出頂點(diǎn)中y值的最小值與最大值，計算豎直掃描起始和終止坐標(biāo)，同時確定掃描起始點(diǎn)位置和初始掃描方向。掃描控制模塊由控制信息管理、塊數(shù)據(jù)生成和塊與圖元關(guān)系判斷三部分組成。控制信息管理負(fù)責(zé)邊函數(shù)的計算和遞推值的存儲，控制邊函數(shù)信息的管理；塊數(shù)據(jù)生成完成以當(dāng)前頂點(diǎn)為左下角的塊數(shù)據(jù)生成，遞推計算塊其余3個頂點(diǎn)的邊函數(shù)便于位置關(guān)系的判斷；塊與圖元位置關(guān)系判斷根據(jù)塊4個頂點(diǎn)的12個邊函數(shù)綜合判斷確定塊與圖元的關(guān)系，如果塊與圖元由重疊則需要下發(fā)像素塊并更新當(dāng)前頂點(diǎn)，如果沒有重疊則需要上移掃描行同時更新當(dāng)前頂點(diǎn)。

2.2 塊與圖元位置關(guān)系判斷

塊與圖元位置關(guān)系判斷采用邊函數(shù)技術(shù)，通過塊的4個頂點(diǎn)數(shù)據(jù)生成12個邊函數(shù)值，利用區(qū)域分類確定三種塊與圖元位置關(guān)系，塊完全在圖元內(nèi)、塊部分在圖元內(nèi)和塊在圖元外。

邊函數(shù)是20世紀(jì)80年代出現(xiàn)的一種在2D平面內(nèi)判斷點(diǎn)與直線關(guān)系的函數(shù)，它利用給定的直線將空間劃分為3個區(qū)域，直線之上，直線之下和直線內(nèi)[ 4，5 ]。

假定直線從點(diǎn)（x0，y0）到點(diǎn)（x1，y1），法線方向?yàn)閚=（a，b），則邊函數(shù)e（x，y）為公式（1），其中a=y0-y1；b= x1-x0；c= x0y1-x1y0。

e（x，y）=ax+by+c公式（1）

若邊函數(shù)小于0，說明點(diǎn)在法線正區(qū)域，既就是點(diǎn)在直線上；若邊函數(shù)大于0，說明點(diǎn)在法線負(fù)區(qū)域，既就是點(diǎn)在直線下；若邊函數(shù)為0，說明點(diǎn)在線內(nèi)包括在線的延長線上。

相似的，可以利用三角形3邊的邊函數(shù)值確定點(diǎn)與三角形的位置關(guān)系，判斷條件如下：

1）如果3個邊界函數(shù)中至少存在一個小于0的值，則點(diǎn)在三角形外；

2）除去A的情況，則點(diǎn)要么在三角形內(nèi)要么在三角形邊上，均認(rèn)為點(diǎn)在三角形內(nèi)。更進(jìn)一步，由于塊與三角形的位置關(guān)系有完全在內(nèi)、部分在內(nèi)和完全在外。

因此，我們可以利用塊的4個頂點(diǎn)的邊函數(shù)綜合計算得到塊與三角形的位置關(guān)系，判斷條件如下：

1）如果塊的4個頂點(diǎn)均在三角形內(nèi)部，則當(dāng)前塊與三角形關(guān)系為完全在內(nèi)；

2）如果塊的4個頂點(diǎn)均在三角形外部，則塊在三角形外；

3）除去1與2的情況，剩余所有塊均為部分在內(nèi)，部分在外。

根據(jù)以上的分析，設(shè)計實(shí)現(xiàn)中塊與圖元位置關(guān)系判斷的流程如圖2所示：

在判斷位置關(guān)系時，需要先對4個頂點(diǎn)的邊界函數(shù)值符號進(jìn)行判斷，如果符號同號說明4個頂點(diǎn)要么均在三角形內(nèi)要么全部在外，此時需要進(jìn)一步判斷。

反之，可以確定塊與三角形位置為相交關(guān)系即塊部分在三角形內(nèi)部分在外。對于同號可以分為2種情況，同在內(nèi)部和同在外部，如果4個頂點(diǎn)均在三角形內(nèi)部那么塊一定在三角形內(nèi)部，反之，則需要進(jìn)一步判斷。

3 算法驗(yàn)證

為了驗(yàn)證塊掃描光柵化算法的正確性，在算法仿真平臺上繪制一個逆時針方向的紅色三角形，如圖3所示。此外，為了進(jìn)一步驗(yàn)證在各個方向和不同起始位置的條件，繪制一個通過旋轉(zhuǎn)而成的由6個三角形組成的圖案。通過與Windows平臺的比較，利用塊掃描光柵化算法的繪制結(jié)果與Windows結(jié)果基本一致，在不同起始位置和方向上，也與Windows平臺值，證明塊掃描光柵化算法的正確性，達(dá)到了預(yù)想的效果[ 6 ]。

另一方面，在算法仿真平臺上，對基于塊掃描和線掃描的三角形圖元光柵化算法的性能進(jìn)行了評估和對比，對于測試中的紅色三角形來說，線掃描算法平均需要196.37毫秒，而基于塊的掃描平均需要148.31毫秒，對該三角形來說，塊掃描技術(shù)相對線掃描少使用約48毫秒，效率提升32.4%。由于光柵化單元中三角形參數(shù)建立和屬性初始化還需要占用一定的時鐘時間，會對最終的光柵化性能產(chǎn)生影響，另外不同形狀和大小的三角形，由于邊界運(yùn)算和內(nèi)部像素填充的不同，塊掃描算法帶來的性能提升存在差異。

4 總結(jié)

本文通過對已有圖元光柵化算法的研究，著重對Zigzag掃描和邊界函數(shù)進(jìn)行深入討論，提出一種基于塊掃描的光柵化算法。該算法利用Zizag原理“Z”型掃描圖元，完成自下向上的光柵化。同時，根據(jù)塊頂點(diǎn)邊界函數(shù)方法判斷塊與圖元的位置關(guān)系，利用塊的4個頂點(diǎn)與三角形關(guān)系，推導(dǎo)得出塊與三角形的位置關(guān)系。在設(shè)計與實(shí)現(xiàn)中，利用邊函數(shù)的局部性，通過簡單的加、減操作快速迭代計算臨近點(diǎn)的邊函數(shù)值，進(jìn)一步加快判斷掃描的速度。在算法仿真平臺上的驗(yàn)證，表明塊掃描光柵化算法能夠快速準(zhǔn)確地完成圖元的光柵化，滿足圖元光柵化的正確性和實(shí)時性要求。

參考文獻(xiàn)：

[1] 韓俊剛，蔣林，杜慧敏等.一種基于圖形加速器和著色器的體系結(jié)構(gòu)[J].計算機(jī)輔助設(shè)計與圖形學(xué)報，2010.

[2] Tomas A M，Eric haines，Naty Hoffman. Real-Time Rendering[M].2 Ed.夏文宇，胡艷祥譯.北京：清華大學(xué)出版社，2000.

[3] 譚顯強(qiáng).基于FPGA的3D圖形處理器IP核的設(shè)計與實(shí)現(xiàn)[D].南京：南京航空航天大學(xué).2010.

[4] 沈陳華.平面上點(diǎn)與多邊形包含關(guān)系Q算法[J].揚(yáng)州大學(xué)學(xué)報，1992，2（4），24.

[5] 張全伙，張劍達(dá).計算機(jī)圖形學(xué)[M].北京：機(jī)械工業(yè)出版社，2003.

[6] 王潤科，張彥麗.判斷點(diǎn)與多邊形位置關(guān)系的算法綜述[J].甘肅聯(lián)合大學(xué)學(xué)報：自然科學(xué)版，2006，20（6）.

作者簡介：聶瞾（1991-），男，陜西華縣人，碩士研究生，研究方向：計算機(jī)科學(xué)與技術(shù)。

導(dǎo)師簡介：田澤，博士，研究員，中國航空工業(yè)首席技術(shù)專家，研究方向：SoC設(shè)計、嵌入式系統(tǒng)設(shè)計等。