基于Zigzag塊掃描的光柵化算法設計與實現

聶瞾 田澤 馬城城

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

關鍵詞：光柵化；塊掃描；Zigzag掃描

中圖分類號：TP301 文獻標識碼：A

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

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

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

1 ZigZag塊掃描分析

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

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

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

2 基于Zigzag塊掃描的光柵化算法設計與實現

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

2.1 Zigzag塊掃描設計與實現

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

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

2）掃描控制：負責進行豎直和水平方向掃描的條件判斷，依靠當前塊與三角形的位置關系，如果水平方向沒有遇到完全在外的塊，則應繼續水平方向掃描，若遇到則說明當前行掃描完畢應向上移動一行。

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

2.2 塊與圖元位置關系判斷

塊與圖元位置關系判斷采用邊函數技術，通過塊的4個頂點數據生成12個邊函數值，利用區域分類確定三種塊與圖元位置關系，塊完全在圖元內、塊部分在圖元內和塊在圖元外。

邊函數是20世紀80年代出現的一種在2D平面內判斷點與直線關系的函數，它利用給定的直線將空間劃分為3個區域，直線之上，直線之下和直線內[ 4，5 ]。

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

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

若邊函數小于0，說明點在法線正區域，既就是點在直線上；若邊函數大于0，說明點在法線負區域，既就是點在直線下；若邊函數為0，說明點在線內包括在線的延長線上。

相似的，可以利用三角形3邊的邊函數值確定點與三角形的位置關系，判斷條件如下：

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

2）除去A的情況，則點要么在三角形內要么在三角形邊上，均認為點在三角形內。更進一步，由于塊與三角形的位置關系有完全在內、部分在內和完全在外。

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

1）如果塊的4個頂點均在三角形內部，則當前塊與三角形關系為完全在內；

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

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

根據以上的分析，設計實現中塊與圖元位置關系判斷的流程如圖2所示：

在判斷位置關系時，需要先對4個頂點的邊界函數值符號進行判斷，如果符號同號說明4個頂點要么均在三角形內要么全部在外，此時需要進一步判斷。

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

3 算法驗證

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

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

4 總結

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

參考文獻：

[1] 韓俊剛，蔣林，杜慧敏等.一種基于圖形加速器和著色器的體系結構[J].計算機輔助設計與圖形學報，2010.

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

[3] 譚顯強.基于FPGA的3D圖形處理器IP核的設計與實現[D].南京：南京航空航天大學.2010.

[4] 沈陳華.平面上點與多邊形包含關系Q算法[J].揚州大學學報，1992，2（4），24.

[5] 張全伙，張劍達.計算機圖形學[M].北京：機械工業出版社，2003.

[6] 王潤科，張彥麗.判斷點與多邊形位置關系的算法綜述[J].甘肅聯合大學學報：自然科學版，2006，20（6）.

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

導師簡介：田澤，博士，研究員，中國航空工業首席技術專家，研究方向：SoC設計、嵌入式系統設計等。