面向3D圖形處理器快速分層的深度預測試方法

摘要：提出了一種快速分層的深度預測試方法.通過結合Z_max和Z_min算法，從像素塊和像素點兩個單位層次，快速地預剔除了無需繪制的像素點，避免了諸如深度值、顏色值和紋理值的讀寫等針對像素點的繪制操作，降低了渲染場景所需的時間.合理的共享像素塊緩存（TileZcache）的設計，有效地提高了命中率，進一步減少了預測試的時間.同時提出的動態更新像素塊的方法，以更小的硬件代價，提高了深度預測試的效率.仿真結果表明，對于隨機測試的繪制場景，這種快速分層的深度預測試方法，使得每幀繪制時間減少了12.5%～25.6%，訪存的帶寬節省與每個像素點的存儲面積比最大增加了43.8%，適用于嵌入式3D的渲染引擎中.

關鍵詞：3D圖形處理器；深度預測試；存儲帶寬

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

A Fast and Hierarchical Early Z-Test for 3D Graphics Processors

ZHANG Jun-jie1，WEI Ji-zeng2，WANG Hang-sheng2，GUO Wei2，3

（1.School of Electronic Information Engineering，Tianjin Univ，Tianjin 300072，China；

2.School of Computer Science and Technology，Tianjin Univ，Tianjin 300072，China；

3. Tianjin Key Laboratory of Cognitive Computing and Application（Tianjin Univ），Tianjin 300072，China）

Abstract： A Fast and Hierarchical Early Z-Test （FH-EZT） was proposed to reject the pixels unnecessary to draw as soon as possible from the tile level and pixel level by combining Z_max and Z_min algorithm. Redundant pre-pixel operations including Z reads/writes， color reads/writes and texture reads were avoided efficiently to decrease the rendering times. Shared tile cache （TileZcache） with high hit rate cuts down the testing cycles and the values of tiles can update dynamically utilizing less cost. Experiments show that the proposed algorithm can reduce 12.5% up to 25.6% rendering cycles for each random tested frame and enhance 4% up to 43.8% for the ratio of bandwidth reduction and storage area per pixel， which is suitable for embedded 3D engine.

Key words： 3D graphics processors；early Z-test；memory bandwidth

隨著嵌入式終端的迅猛發展，游戲、3D導航、人機接口等多媒體應用得到廣泛關注.因此，如何在高分辨率的屏幕上，以最小的功耗代價實時地對復雜3D場景進行繪制，是嵌入式圖形處理器亟需解決的問題.幀渲染時間和存儲器帶寬是影響嵌入式GPU速度和功耗的兩個重要的性能指標，雖然半導體技術的高速發展帶來了速度和性能的極大提升，但是渲染的時間和存儲器的訪問依舊成為瓶頸.并行或離線渲染不同的幀可以有效地縮短渲染時間，但是需要很大的芯片面積和存儲面積，不適合應用于嵌入式系統，而且在繪制一幀時并不能做到并行渲染，所以盡可能快速地分辨每幀處理像素點的有效性，能夠間接地提高渲染速度.另一方面，存儲器的帶寬是有限的，在圖形系統繪制流水線的像素處理階段，存在5種類型的存儲器訪問，深度值的讀取、深度值的寫回、顏色值的讀取、顏色值的寫回和紋理值的讀取，而有關深度數據讀寫的帶寬需求至少占據40%^[1]，所以通過深度預測試及早判斷像素點的有效性，減少不必要的存儲器的訪問，不僅可以加快處理速度，而且能夠降低系統功耗.

許多利用深度預測試以節省存儲器帶寬的方法在以往的資料中被提出，大體上可以分為3類，即Z_max算法、Z_min算法和混合型算法.利用Z_max算法，能夠及早剔除被遮擋的像素點，有效地避免了不必要的存儲器訪問.HZbuffer算法采取了減小深度緩存分辨率的方式，在紋理讀取等操作之前剔除了不可見的像素點，避免了5種類型的存儲器訪問.但是需要較大的片上存儲空間，而且更新繁瑣，后來被ATI結合深度壓縮等方法用于商用^[1]，但并不適用于嵌入式系統.Depth Filter的算法^[2]在繪制每幀時，采用一個或幾個確定的平面，通過mask值記錄每一個像素點之前繪制的歷史信息，用以剔除不可見的像素點，剔除的效果與平面的數量成正比，但是面積也會隨之增大.雖然平面的位置會有更新，但是確定位置的方法比較苛刻，而且對場景有著很大的依賴性，所以性能不會一直有保證.Midtexturing的算法^[3]分別是在紋理讀取之前和之后進行兩次深度測試，但只剔除了不必要的紋理的讀取，而且兩次深度測試之間過長的流水線引起的訪存一致性問題，會降低深度緩存（Z cache）的命中率，采取對應的改善措施后效果也不顯著.后來他們對這種算法進行了改進^[4]，依據相鄰像素間的一致性，通過判斷標志位，預測出將要處理的像素點的可見性，可以選擇性地將其中一次深度測試設置為有效，而不是讓兩次都進行處理，但是兩次深度測試之間的流水線長度決定了標志位的更新不會很及時，可能需要較長時間的等待，而且在沒有或者很少紋理映射的情況下，會適得其反.

Z_min算法是Mller提出的與Z_max剔除不可見像素點截然相反的想法^[5]，對于當前處理的像素塊，計算出內部包含所有像素點的最大值Zmax_curruent，與從片外取來的對應像素塊的最小值Zmin_previous比較，若Zmax_curruent

第三種為混合型算法，其主要思想就是將Z_max算法和Z_min算法相結合，其效率要比單純地采用一種方法好得多.Tsao等人最初提出一種自適應塊的深度濾波（ATDF）算法^[6]，通過采用像素塊的Z_max和Z_min平面，把整個繪制空間分為完全可見區域、完全剔除區域和不確定區域，采用一個mask平面用來標識待處理的像素點是否被渲染過，以確定像素點的可見性，但是一旦像素塊內部包含的像素點都被渲染過一次，mask就不再起作用，而且在繪制一幀的過程中，Z_max和Z_min平面的位置是固定的，性能更會大打折扣.Kim等人提出一種U-EZT的方法^[7]，針對處理過的每一個像素點可以對Z_max和Z_min平面進行實時更新，采用的mask平面與ATDF不同的是，可以反復更新mask值用來支持Z_max和Z_min平面的移動，但是帶來的后果是，可能會使一些原本完全可見或者完全剔除的像素點被認為無法確定，需要重新判斷.

此外，文獻[8-12]也從不同方面進行了深度預測試，具有一定成效.

本文基于像素塊的光柵掃描方式，結合Z_max算法和Z_min算法，主要從降低幀渲染時間的角度出發，提出了一種快速分層的深度預測試方法.分別從像素塊和像素點兩個不同層次，通過合理設置和共享TileZcache以有效地提高命中率，加快了深度預測試的速度，減少了渲染場景所需的時間.同時以平均每個像素點兩位的存儲代價，動態更新像素塊，提高了深度預測試的效率.文章的組織結構如下：第1節描述了本文所提出的算法的基本思想；第2節描述了仿真結果并對仿真結果進行了分析；第3節為結論.

1 快速分層的深度預測試

圖1顯示了在傳統渲染管線的基礎上添加快速分層深度預測試（FH-EZT）的結構示意圖，在基于像素塊的光柵掃描過程中^[13]，實現了本文提出的這一算法（圖中深色區域）.

進入光柵階段，Tile-Scan首先接收來自Tri-Setup傳遞過來的三角形頂點位置和計算好的掃描轉換或深度預測試需要用到的若干參數，以像素塊大小為單位進行塊間掃描.對于掃描到的待處理的像素塊，送入Tile-EZT，與從TileZcache或片外像素塊存儲空間（TileZbuffer）中讀取的相應像素塊之前的位置進行粗略層次的比較，從而預判斷出當前像素塊的可見性.若判斷為完全不可見，則直接剔除當前的像素塊，此時認為內部包含的所有像素點是完全不可見的，從而避免了如前所述5種類型的針對每個像素點的操作；若無法判斷可見性，則Tile-EZT對于當前像素塊測試失敗，會將其送入接下來的Tile-FIFO，等待Pixel-Scan的處理.Pixel-Scan掃描出像素塊內部有效的像素點，并將它們仍然以像素塊為單位送入Pixel-EZT進行逐個像素點的深度預測試.對于每個有效的像素點來說，只需要與從TileZcache或片外TileZbuffer中讀取的相應像素塊之前的最大值和最小值進行細致層次的比較，從而預判斷出每個像素點的可見性.若判斷為完全可見，則避免了深度值的讀取；若判斷為完全不可見，則將其直接剔除，避免了如前所述5種類型的讀寫操作；若無法判斷可見性，則Pixel-EZT對于當前像素點測試失敗，會將其送入后續的Pre-pixel Process階段.Tile-EZT和Pixel-EZT共享TileZcache，通過合理設計TileZcache的結構，有效地提高了命中率.

1.1 Tile-EZT

Tile-EZT結合了Z_max算法的基本思想，主要目的在于快速地預剔除完全不可見的像素塊，減少幀繪制時間，實現的功能如算法1和圖2所描述.

算法1 Tile Early Z-Test Alg orithm（Tile- EZT）

input Zmin _tri， Zmax _previous

1： if（Zmin _tri>Zmax _previous）

then Tilei is defined as absolutely occluded，

go to step 2.

else

then Tilei is defined as uncertain，

go to step 2.

2：move to the next tile， go to step 1.

在Tri-Setup中預先計算出當前處理的三角形3個頂點深度的最小值Zmin_tri，可以將其看作光柵掃描到的每個待處理像素塊的最小值，與從TileZcache或者片外的TileZbuffer中讀取當前處理像素塊之前的最大值Zmax_previous作比較，若Zmin_tri>Zmax_previous，則判斷出當前像素塊（或者整個三角形，當三角形完全在一個像素塊內部時）可以被完全剔除；否則認為其無法判定，將其送入后續的流水線階段進行處理.該流水線階段對于TileZcache的訪問是只讀的，對Zmax_previous值不必進行更新寫回，具體TileZcache的設計及其原因詳見第2.3節.

這種基于像素塊的深度預測試粗粒度地判定了像素塊可能存在的位置，只需一個周期的處理時間，而不是針對逐個像素點進行處理所用的M（像素塊包含的有效像素點數量）個周期，通過增加很少的預計算量，有效地節省了存儲器帶寬的同時，也極大地縮短了每幀渲染的時間.

1.2 Pixel-EZT

Pixel-EZT結合了混合型算法的基本思想，實現的功能如算法2和圖3所描述.對于Tile-EZT測試失敗的像素塊，通過Pixel-Scan的掃描，將像素塊內部有效的像素點仍以該像素塊為集合送入到Pixel-EZT階段.針對每個像素點的深度值Z_pixel，逐一與從TileZcache或者片外的TileZbuffer中讀取當前處理像素塊之前的最大值Zmax_previous和最小值Zmin_previous作比較，若Z_pixel < Zmin_previous，則判斷出當前像素點為可見的；若Z_pixel> Zmax_previous，則判斷出當前像素點為不可見的；否則認為其無法判定，將其送入后續的流水線階段進行處理.

算法2 Pixel Early Z-Test Alg orithm（Pixel-EZT） input： Z_pixel，Zmin _previous， Zmax _previous

1： initialize Zmin _current，Zmax _current.

Zmin _current=1.0， Zmax _current=1.0

2： if（Z_pixel

then Pixeli is defined as absolutely visible，

go to step 3.

else if（Z_pixel>Zmax _previous）

then Pixeli is defined as absolutely occluded，

go to step 3.

else

then Pixeli is defined as uncertain，

go to step 3.

3：traverse the next valid pixel.

if there are pixels valid next， go to step 2.

esle update to Zmin _previous，Zmax _previous.

Zmin _previous=Zmin _current，

Zmax _previous=Zmax _current.

4：move to the next tile， go to step 1.

該流水階段對于TileZcache的訪問是可讀可寫的，對Zmax_previous值和Zmin_previous值需要不斷進行更新寫回，以保證深度預測試的效率.對于Zmax_previous值，只有在當前像素塊內所有像素點的深度值均小于Zmax_previous且全部判斷完時，才對其進行更新，把其中所有像素點的最大值寫回TileZcache，成為新的Zmax_previous值，如圖3中的點a.因為Zmax_previous值的更新是要不斷往視點的方向移動，若非像素塊內部的所有像素點都有效，則更新后的Zmax_previous值可能使得那些無效像素點的位置由原來不確定的區域變成完全剔除的區域，實施了錯誤的剔除.而對于Zmin_previous值，只需要在當前像素塊內所有有效的像素點全部判斷完后，就可以對其進行更新，把其中所有有效像素點的最小值寫回TileZcache，成為新的Zmin_previous值，如圖3中的點b.因為Zmin_previous值的更新也是要不斷往視點的方向移動，但是更新后的Zmin_previous值并不能影響原來像素塊內部那些無效像素點的可見性，可能只不過是由原本完全可見的區域變成了不確定的區域，但不會產生繪制的錯誤.

這種基于像素點的深度預測試細粒度地判定了像素點可能存在的位置，不借助額外的標志位等輔助信息，通過保守地動態更新所在像素塊的最大值和最小值，使得深度預測試以更小的代價實現了較好的性能.可以簡單地證明，一個包含有m×n大小的像素塊只需要一個最大深度值和一個最小深度值的位寬存儲開銷，以深度值的精度為32位、m×n取32為例，平均每個像素點只需要兩位的存儲代價，即可滿足功能的需求.

1.3 共享TileZcache

Tile-EZT和Pixel-EZT兩個層次的深度預測試階段形成了流水線式的處理，對于Tile-EZT階段測試失敗的像素塊將會流水到Pixel-EZT階段，因此需要重復讀取同一像素塊的最大值或最小值，此時共享的TileZcache的設計是必要的，可盡量減少冗余的訪存.

Tile-EZT階段只涉及TileZcache中Zmax_previous值的讀取，因為此時并不確定與之作比較的當前處理的像素塊真正的最小值，硬性地寫回可能會對下一次相同位置像素塊是否剔除產生錯誤的判斷.同時對于像素塊是否完全可見的快速預判斷并不支持，而且也無必要，即無需讀取TileZcache中Zmin_previous值，原因是后面Pixel-EZT階段會不定時地更新TileZcache，可能使得前面Tile-EZT階段讀取下一次相同位置像素塊的Zmin_previous值并不及時，引起TileZcache的一致性問題，從而導致判斷的失誤.即使增加復雜的邏輯判斷或流水線等待以避免這一問題，也會因為已經判定為完全可見的像素塊也要送入Pixel-Scan中進行逐個像素的光柵掃描處理，并不能節省處理的周期時間.

Pixel-EZT階段會重復讀寫從Tile-EZT階段接收過來的同一像素塊的最大值或最小值，添加的TileZcache實現兩個階段的共享，可以有效地減少訪問存儲器的次數，進一步縮短了深度預測試所需的周期時間.為了有效地提高讀寫TileZcache的命中率，可以采取以下兩個措施：一是將TileZcache設計成先進先出（FIFO）的替換策略，使得當前處理的像素塊與存儲在緩存中的相應的最大值和最小值信息保持同步的流水；二是使設計的TileZcache的尺寸不小于兩個階段之間的最大流水線級數，主要是由緩存待處理像素塊（Tile-FIFO）的深度決定的.綜合以上兩點，能夠最大程度地保證兩個階段讀寫同一像素塊的最大值和最小值在TileZcache中停留的時間最長，以便最大概率地直接獲取.

2 仿真結果及分析

為了評估所提出結構的性能，我們在ATTILA GPU仿真器上對比實現了不同的深度預測試算法，包括HZbuffer算法、混合算法、U-EZT算法和所提出的算法，并深入分析了主要的性能指標.ATTILA是一個周期性精確的、功能強大的模擬GPU架構的開源仿真器，為我們統計各種實驗數據提供了方便.我們使用了較受歡迎的具有復雜深度的常用測試用例——Quake4，隨機地測試了不同幀的場景，分辨率為640×480，其中在考慮帶寬、剔除率和面積等綜合因素下，處理的像素塊單位采用8×4的大小最為適宜^[7].

2.1 幀渲染時間

為了驗證本文提出的以像素塊整體為單位代替逐個像素點形式的深度預測試算法的有效性，針對各種算法的每幀繪制時間（CPF）進行了隨機的數據統計，假設每個像素點經過流水線的處理過程和處理時間是不變的，每次緩存未命中引起的訪存時間設定為10個cycles[3-4]，TileZcache大小取16行、每行64 B.

圖4表示了實現各種算法的CPF統計，包括在兩次讀取TileZcache之間不同流水線長度的情況下實現的本文的算法，可以看出本文所提出的結構在具有復雜深度的場景中使用了最小的幀渲染時間，性能最佳.這是因為其他幾種結構CPF的計算公式可以表示為：

CPF=Nfragments+10×Nmem_access. （1）

式中：Nfragments表示每幀的渲染的像素點數量；Nmem_access表示每幀訪問存儲器的次數（包括TileZcache，Z cache和Texture cache未命中引起的訪存，由于color讀寫都是一樣的，所以不計入比較）.而本文提出的結構的方法CPF的計算公式為：

CPF=Ntiles+Npixels+10×N′mem_access. （2）

式中：Ntiles表示被Tile-EZT剔除的像素塊數量；Npixels表示沒有被Tile-EZT剔除的像素點數量；N′mem_access表示每幀訪問存儲器的次數.這里有Ntiles×Neff_pixel+Npixels=Nfragments，其中Neff_pixel表示像素塊內包含的平均有效像素點數量，而由于共享的TileZcache的設計，使得N′mem_access與Nmem_access相比不會明顯增加.設定每處理一個像素塊的時間為一個周期，如果該像素塊被剔除，顯然比逐個處理每個像素點所用的時間要少得多.而測試的第一幀場景中并無遮擋存在，所以像素塊級別的預測試Tile-EZT沒有發揮作用，反而使性能略有下降.

此外，另一個影響CPF的主要因素是兩次讀取TileZcache之間流水線的長度（Latency）.如果Latency越長，TileZcache 未命中的概率越大，需要的訪存次數或總的訪存時間增加，必然使CPF增大.所以，在保證基本功能的前提下，Latency設計得越小，本文所提出的方法帶來的性能越好. ＼

2.2 帶寬需求

針對本文提出的結構，為了統計帶寬需求，我們采取的計算公式如下：

BW=fillrate×{MissEZT×（Lread+Lwrite）+

（1-RrejEZT）×Misstex×Lread+

（1-RrejEZT-RaccEZT）×Missz×（Lread+Lwrite）+

（1-RrejZT）×Missz×Lwrite+

（1-RrejZT）×Misscolor×（Lread+Lwrite）+

（1-RrejZT）×Misscolor×Lwrite}.

其中fillrate表示每秒鐘處理像素點的個數，這里取166 M/s，Miss表示每種緩存的未命中率，R

表示所有剔除或者接受的像素點占總的繪制像素點的百分比，L表示訪存時讀或者寫的數據寬度.

圖5表示了實現各種算法的帶寬統計（由于color的讀寫產生的帶寬都是一樣的，所以不計入比較），相比U-EZT算法，FH-EZT的帶寬需求稍有增加，但是避免了每個像素對應的額外的mask值，在采取8×4像素塊大小的情況下，FH-EZT實現了平均每個像素只需兩位的存儲空間，使得存儲帶寬的節省（BW_reduction，和Non-EZT算法相比較）與每個像素點需要的存儲代價（Mpp）的比值（這里參考了文獻[7]中的資料）最大提升了43.8%，如表1所示.

3 結 論

本文提出了一種快速分層的深度預測試方法.結合Z_max和Z_min算法，以像素塊為單位進行的預測試，快速地剔除了無需繪制的大量的像素點，加快了深度預測試的速度；以像素點為單位進行的預測試，以更小的硬件代價動態更新像素塊的位置，提高了深度預測試的效率.同時通過合理設置和共享TileZcache以有效地提高命中率，進一步減少了渲染場景所需的時間.結果表明，對于隨機測試的每幀場景，渲染時間被縮短了12.5%～25.6%，訪存的帶寬節省與每個像素點的存儲面積比最大增加了43.8%，顯示了所提出算法的優異性能.

參考文獻

[1] MOREIN S. ATI Radeon HyperZ technology[C]//ACMSIGGRAPH/ Eurographics Workshop on Graphics Hardware. Switzerland， August 2000.

[2] YU C H， KIM D， KIM L S. An area efficient early Z-test method for 3D graphics rendering hardware[J]. IEEE Transactions on Circuits and Systems， 2008， 55（7）： 1929-1938.

[3] PARK W C， LEE K W， KIM I S， et al. An effective pixel rasterization pipeline architecture for 3D rendering processors[J]. IEEE Transactions on Computers， 2003， 52（11）： 173-182.

[4] PARK J ， KIM I S， PARK W C， et al. A pixel pipeline architecture with selective z-test scheme for 3D graphics processors[J]. Microprocessors and Microsystems， 2013， 37（3）： 373-380.

[5] AKENINE-M LLER T， STRM J. Graphics for the masses： a hardware rasterization architecture for mobile phones[J]. ACM Transactions on Graphics， 2003， 22（3）：801–808.

[6] TSAO Y M， WU C L， CHIEN S Y， et al. Adaptive tile depth filter for the depth buffer bandwidth minimization in the low power graphics systems[C]//Proceedings of 2006 IEEE International Symposium on Circuits and Systems. New York： IEEE， 2006：5023-5026.

[7] KIM H Y， YU C H， KIM L S. A memory-efficient unified early z-test[J]. IEEE Transactions on Visualization and Computer Graphics， 2011， 17（9）： 1286-1294.

[8] KIM D， CHUNG K， YU C H， et al. An SoC with 1.3 Gtexels/s 3-D graphics full pipeline engine for consumer applications[J]. IEEE J Solid-State Circuits， 2006， 41（1）：71-84.

[9] 高可，楊珂，石教英，等. Coarse-Z Filter：降低深度帶寬的圖形流水單元[J].計算機輔助設計與圖形學學報，2006，18（11）：1658-1663.

GAO Ke， YANG Ke， SHI Jiao-ying， et al. Coarse-Z Filter： a graphics pipeline unit to reduce depth bandwidth[J]. Journal of Computer-Aided Design Computer Graphics， 2006， 18（11）：1658- 1663.（In Chinese）

[10]鐘偉，郭立，楊毅. 基于Cache和層次Z緩存算法的3維圖形深度消隱硬件設計和實現[J].中國圖像圖形學報，2009，14（1）：1392-1398.

ZHONG Wei， GUO Li， YANG Yi. Design and implementation of hidden surface removal hardware based on cache and hierarchical Z-buffer algorithm for 3D graphics[J]. Journal of Image and Graphics， 2009， 14（1）：1392-1398. （In Chinese）

[11]YOON J S， YU C H， KIM D， et al. Triangle-level depth filter method for bandwidth reduction in 3D graphics hardware[C]//Proceedings of IEEE International Symposium on Circuits and Systems. New York： IEEE， 2007：765-768.

[12]HSIAO C C， CHU S L. A hierarchical triangle-level culling technique for tile-based rendering[C].//Proceedings of Fifth International Symposium on Parallel Architectures， Algorithms and Programming. New York： IEEE， 2012：119-125.

[13]MCCORMACK J， MCNAMARA R. Tiled polygon traversal using half-plane edge functions [C]//Proceedings of the ACM SIGGRAPH/ EUROGRAPHICS Workshop on Graphics Hardware. New York： ACM， 2000：15-21.