這篇文章是Intel在2016年輸出的軟件光柵化技術(shù)方案，很多項(xiàng)目的軟件光柵化實(shí)現(xiàn)都是以這個(gè)方案為基礎(chǔ)開發(fā)的，參考文獻(xiàn)[1]中給出了原文鏈接，有興趣了解詳情的同學(xué)可以前往一探究竟。

在深入論文細(xì)節(jié)之前，我們需要帶著幾個(gè)問題前行：

1. 什么是軟件光柵化？

• 是一種在CPU上對(duì)面片進(jìn)行光柵化以實(shí)現(xiàn)物件上傳到GPU之前就完成遮擋剔除

2. 為什么要用軟件光柵化（CPU）而不用硬件光柵化（GPU）

• 硬件光柵化的遮擋剔除因?yàn)镚PU/CPU之間的傳輸時(shí)延，導(dǎo)致使用這種方式進(jìn)行遮擋剔除性能較差

3. 軟件光柵化的具體實(shí)施方案與流程是怎么樣的？

• 這個(gè)后面會(huì)細(xì)說(shuō)，簡(jiǎn)要流程描述直接看后面conclusion部分

4. 軟件光柵化的性能表現(xiàn)與使用局限又是怎么樣的？

• 性能上從測(cè)試數(shù)據(jù)來(lái)看，已經(jīng)遠(yuǎn)遠(yuǎn)超出純粹frustum culling的性能表現(xiàn)（也就是說(shuō)有了occlusion culling之后，就不需要frustum culling了），使用局限暫不清楚。

以下是原文正文核心點(diǎn)的抽離與分析。

0. Abstract

要想避免高頻Overdraw帶來(lái)的渲染消耗，高效的動(dòng)態(tài)遮擋剔除就變得十分重要了。Intel受到硬件光柵化的啟發(fā)，借用CPU的SIMD特性（下圖給出了Intel的CPU并行架構(gòu)發(fā)展歷程圖。），給出了一套軟件光柵化技術(shù)方案，這個(gè)方案可以剔除掉全分辨率深度貼圖下硬件光柵化剔除結(jié)果98%的物件，相比此前的軟件光柵化方案，性能還提升了3x以上，整個(gè)方案支持interleaving式的遮擋體光柵化（具體含義不明，等待補(bǔ)充）以及毫無(wú)消耗的遮擋查詢，因此使用起來(lái)十分方便。

1. Introduction

為了增強(qiáng)沉浸感，現(xiàn)代游戲中場(chǎng)景的動(dòng)態(tài)要素越來(lái)越多，而這也對(duì)剔除方案帶來(lái)了越來(lái)越高的要求。因此傳統(tǒng)如PVS的預(yù)計(jì)算遮擋剔除方案就逐漸滿足不了需求，在這種情況下，眾多的廠商開始將目標(biāo)轉(zhuǎn)向如HZB、硬件光柵遮擋剔除、軟件光柵遮擋剔除等方案。

軟件光柵遮擋剔除的基本做法，就是在每一幀update完成之后，在CPU側(cè)對(duì)場(chǎng)景進(jìn)行一遍光柵化，輸出一個(gè)depth buffer，之后使用這個(gè)depth buffer對(duì)場(chǎng)景物件進(jìn)行剔除，避免將那些不可見的數(shù)據(jù)塞入渲染列表，從而減輕渲染壓力。

在軟光柵方案中，剔除精度與性能是一對(duì)冤家，沒有辦法同時(shí)兼顧，因此通常需要在算法上做一個(gè)平衡。Andersson [And09] 跟Collin [Col11]的軟光柵方案采用了一個(gè)低分辨率的depth buffer來(lái)降低消耗，但是這種做法在精度上就會(huì)存在問題，為了降低精度不足導(dǎo)致的問題，這個(gè)方案的做法是采用inner-conservative（將原始mesh逐像素的向內(nèi)坍縮以形成一個(gè)極簡(jiǎn)的遮擋mesh）的mesh來(lái)作為遮擋體生成遮擋depth buffer，但是inner-conservative mesh的生成十分困難，可能會(huì)導(dǎo)致false-negative（即將一些可見的物件剔除）的情況出現(xiàn)，此外對(duì)于美術(shù)同學(xué)建模也有一定要求，顯然十分的影響開發(fā)效率。Intel的方案采用的是全精度的depth buffer，但是在性能上就相對(duì)更低一點(diǎn)。

本文給出的方案相對(duì)于此前的軟光柵方案的特點(diǎn)在于，輸出的coverage數(shù)據(jù)（即那些區(qū)域被遮擋，遮擋的具體數(shù)值是多少）不再是depth buffer，而是經(jīng)過編碼的其他數(shù)據(jù)。為了提升處理效率，降低時(shí)間消耗，此方案處理的最小單位不再是pixel，而是tile（每個(gè)tile的尺寸為32 x 8個(gè)pixels），給出了一種快速計(jì)算某個(gè)tile的coverage數(shù)據(jù)的算法，從而才使得此方案在保持較高計(jì)算精度的情況下，其消耗并沒有相應(yīng)的大幅增加。

這個(gè)方案是在[AHAM15]的硬件masked depth culling方案的基礎(chǔ)上經(jīng)過如下擴(kuò)展得到的：

1. 給出了一個(gè)通過少數(shù)幾條SIMD指令就能夠?qū)崿F(xiàn)多個(gè)tile的coverage數(shù)據(jù)的并行生成的算法
2. 在[AHAM15]的depth更新算法的基礎(chǔ)上進(jìn)行了一定程度的修正，以一定的精度損失來(lái)?yè)Q取性能的增幅
3. 給出了一個(gè)對(duì)SIMD指令友好的depth層級(jí)結(jié)構(gòu)，這個(gè)結(jié)構(gòu)是專為Occlusion Culling設(shè)計(jì)的，具有較低的內(nèi)存消耗
4. 設(shè)計(jì)了一個(gè)高性能的Occluder渲染算法與遮擋查詢方案，以實(shí)現(xiàn)對(duì)場(chǎng)景簡(jiǎn)潔而高效的遍歷訪問。

遮擋剔除后結(jié)果

場(chǎng)景頂視圖，灰色區(qū)域表示被剔除的場(chǎng)景物件

層級(jí)depth buffer，越遠(yuǎn)越黑

2. Previous Work

對(duì)于靜態(tài)場(chǎng)景而言，常用的做法是預(yù)計(jì)算的PVS或者portal/mirror算法，但是隨著場(chǎng)景中的動(dòng)態(tài)元素越來(lái)越多，這種算法已經(jīng)難堪重任。

[GKM93,Gre96]提出了第一個(gè)使用層級(jí)depth結(jié)構(gòu)的算法，且這個(gè)算法對(duì)后續(xù)硬件的發(fā)展產(chǎn)生了很大的影響。[ZMHH97]則第一次提出了層級(jí)遮擋貼圖（occlusion maps）算法，基于其創(chuàng)建層級(jí)遮擋貼圖的方式，還給出了近似的遮擋查詢方案。[Mor00]則給出了層級(jí)Z算法（HiZ，這個(gè)算法是伴隨一個(gè)叫做HyperZ的芯片架構(gòu)給出的，HyperZ架構(gòu)包含三項(xiàng)特性：1. Z Compression，給出了一種無(wú)損的Depth壓縮算法，可以降低Depth的讀寫帶寬消耗；2. Fast Z Clear，通過將Depth Block整個(gè)標(biāo)記成Cleared來(lái)避免此前通過大量帶寬消耗實(shí)現(xiàn)的Depth Write；3. HiZ，與傳統(tǒng)pixel 沙丁完成后再進(jìn)行depth test（late depth test）不同，新的架構(gòu)允許在光柵化時(shí)通過一張HiZ來(lái)提前進(jìn)行Depth Test，詳情參考文獻(xiàn)[2]中的wiki鏈接），這個(gè)算法的Hierarchy只包含一個(gè)Level（那為什么叫層級(jí)，是指單個(gè)mip嗎？指的是從全分辨率的depth buffer中構(gòu)建出一個(gè)hierarchical depth buffer，算上全分辨率depth buffer，就有兩個(gè)level，但是由于只使用后面生成的這個(gè)hierarchical depth buffer，因此準(zhǔn)確來(lái)說(shuō)只包含一個(gè)level），這個(gè)算法充分考慮到了硬件的設(shè)計(jì)架構(gòu)，因此具有很多的優(yōu)點(diǎn)，后續(xù)很多GPU硬件的設(shè)計(jì)都添加了類似于HiZ的遮擋剔除方案。

[AM04]通過將眾多的遮擋剔除方案集成到一起，給出了所謂的dPVS（dynamic PVS）方案，以實(shí)現(xiàn)對(duì)大量具有眾多動(dòng)態(tài)物件場(chǎng)景的剔除支持（剔除界的要你命三千？）。早期的Umbra Engine [SSMT11]是能夠支持CPU & GPU支持的，不過目前就只剩下CPU方案了。[BWPP04]基于硬件遮擋查詢構(gòu)建了一個(gè)方案，在這個(gè)方案中，要想得到更好的剔除效果，就需要對(duì)場(chǎng)景按照從前到后的順序進(jìn)行遍歷，此外還需要對(duì)此前可見（上一幀？）的物件的繪制結(jié)果與查詢結(jié)果進(jìn)行interleaving（從后面interleaving的含義推測(cè)，這個(gè)地方指的是需要在將查詢跟渲染放到一起，一次性完成處理？）。

由于硬件提供了predicted rendering（只有當(dāng)occlusion query成功之后，才會(huì)執(zhí)行對(duì)應(yīng)的draw call，這種做法可以盡量減少GPU/CPU之間的通信消耗）功能，使用近似遮擋查詢（比如使用GPU的HiZ buffer）加上“any fragments”優(yōu)化（在這個(gè)優(yōu)化開啟時(shí)，只要找到任意一個(gè)可見的像素，那么就認(rèn)為此物件可見，終止后續(xù)的查詢），就能使得硬件遮擋查詢成為一項(xiàng)可用的技術(shù)。

說(shuō)到軟件光柵化方案，[Val11]繪制了一張全精度的depth buffer，并按照一定的算法對(duì)齊進(jìn)行下采樣以實(shí)現(xiàn)對(duì)遮擋測(cè)試的加速。[Per12]則是從inner conservative occluder boxes中生成凸遮擋體，并將那些完全被這些凸遮擋體完全包裹的物件剔除來(lái)實(shí)現(xiàn)加速。

還有一些算法如[KSS11, HA15]則是通過將上一幀GPU生成的depth貼圖經(jīng)過下采樣與reprojection，之后按照一定的補(bǔ)洞邏輯填補(bǔ)上reprojection產(chǎn)生的數(shù)據(jù)缺失來(lái)實(shí)現(xiàn)遮擋貼圖的創(chuàng)建。然而這類算法的問題在于可能會(huì)有一些錯(cuò)誤的剔除，此外對(duì)于兩幀之間的變化幅度有一定限制（不能出現(xiàn)較大的變化，比如快速移動(dòng)的動(dòng)態(tài)物件就是一個(gè)非常大的問題），因此使用起來(lái)非常不方便。

3. Algorithm and Implementation

先來(lái)介紹一下Intel的軟件遮擋剔除框架[CMK*16]，本文介紹的這個(gè)方案最開始就是在這個(gè)框架中實(shí)現(xiàn)的。

Intel框架的遮擋剔除主體包括兩個(gè)pass：

第一個(gè)pass會(huì)對(duì)場(chǎng)景物件進(jìn)行篩選，取出一系列比較重要的（屏占比高）、大尺寸的遮擋體物件，同時(shí)對(duì)這些物件進(jìn)行frustum & backface culling，那些沒有被剔除的物件就會(huì)進(jìn)行變換以及軟件光柵化，結(jié)果會(huì)被存入到一張全分辨率depth buffer中，這個(gè)buffer之后會(huì)以8 x 8個(gè)像素（對(duì)應(yīng)一個(gè)pixel cache line size）為一個(gè)tile，對(duì)每個(gè)tile中的像素的depth取最大值，來(lái)得到一張降分辨率的depth buffer，從而如[GKM93, Mor00]一般，得到一張單層的Hierarchical Depth Buffer（one-level hierarchical depth buffer，每個(gè)像素對(duì)應(yīng)全分辨率下的一個(gè)tile）。

第二個(gè)pass，則會(huì)對(duì)場(chǎng)景中物件的bounding box執(zhí)行軟件遮擋查詢（CPU）。bounding box會(huì)先進(jìn)行frustum culling，通過之后經(jīng)過CPU轉(zhuǎn)換到屏幕空間，得到一個(gè)屏幕空間的rectangle，這個(gè)rectangle的最小depth，可以計(jì)算得到為，之后就以tile為處理單位，對(duì)上述rectangle進(jìn)行遍歷，對(duì)遍歷的各tile的最大depth 與進(jìn)行比對(duì)（越小表示越近，這個(gè)結(jié)論跟最前面展示的深度圖表現(xiàn)不太一樣，推測(cè)可能是使用了reverseZ邏輯），判斷在這個(gè)tile中，rectangle是否是可見的（ > 表示可見，否則不可見），如果所有tile都是不可見，那么這個(gè)物件就會(huì)被認(rèn)為是不可見了（從這個(gè)描述來(lái)看，單層的depth buffer指的就是每個(gè)像素對(duì)應(yīng)全分辨率中的一個(gè)tile的depth level，不像HiZ算法中的Depth Mipmap）。

本文給出的算法大致流程跟常見的兩層（two-level）hierarchy軟光柵算法相同，不同的地方主要有如下兩點(diǎn)：

1. 如上圖所示，整個(gè)2D圖像空間會(huì)被分割成一個(gè)個(gè)的tile，每個(gè)tile包含32 x 8個(gè)像素，本文算法會(huì)借助CPU的SIMD特性（8路SIMD，每路包含32個(gè)bits，后續(xù)SIMD并行能力如果升級(jí)，性能還可以進(jìn)一步提升）根據(jù)三角面片的邊緣數(shù)據(jù)對(duì)同一個(gè)tile中的多個(gè)像素進(jìn)行并行計(jì)算，一次性輸出整個(gè)tile的coverage masks。
2. 本文所使用的depth數(shù)據(jù)表達(dá)方式跟傳統(tǒng)的不太一樣（具體后面會(huì)細(xì)說(shuō)），在這種表達(dá)方式下，可以無(wú)需使用全精度的depth buffer就能得到較高的裁剪精度，且同時(shí)還可以實(shí)現(xiàn)depth數(shù)據(jù)與coverage mask的解耦（作用是可以用較低分辨率的depth buffer來(lái)進(jìn)行遮擋剔除查詢），在這種表達(dá)方式下，最終的coverage數(shù)據(jù)消耗的內(nèi)存要比depth buffer低一個(gè)數(shù)量級(jí)。

下面給出了本算法的大致流程圖：

總體來(lái)說(shuō)分成兩大塊，其中triangle setup對(duì)應(yīng)的是scanline的遍歷邏輯，而tile traversal部分對(duì)應(yīng)的則是depth buffer的遮擋查詢與軟光柵更新。

下面借用參考文獻(xiàn)[5]中的圖來(lái)逐一介紹各個(gè)階段的功能邏輯：

Transform & Clip階段主要是對(duì)面片進(jìn)行空間變換，按照f(shuō)rustum culling完成面片的clip處理。

為每個(gè)三角面片，計(jì)算其屏幕空間的rectangle范圍，以32x8的tile作為最小的覆蓋單元。

可以只計(jì)算某個(gè)頂點(diǎn)的數(shù)值，之后根據(jù)平面斜率按照一定的策略直接增減某個(gè)數(shù)值來(lái)得到后續(xù)的覆蓋情況，可以參考后面scanline的處理邏輯。

覆蓋情況知道了之后，就是使用scanline對(duì)這個(gè)三角形進(jìn)行掃描并光柵化。

scanline處理是借助SIMD功能并行完成的，在那之前，先來(lái)看下AVX的寄存器布局，這里AVX包含8個(gè)SIMD處理單元，每個(gè)單元負(fù)責(zé)32x1或者8x4個(gè)像素的處理邏輯。

在三角形scanline處理的時(shí)候，使用的是32x1的處理模式。

三角形的每條邊，我們可以計(jì)算其對(duì)應(yīng)的斜率，這個(gè)計(jì)算只需要進(jìn)行一次。

3.1. Efficient Triangle Coverage

除了利用SIMD的并行計(jì)算特性來(lái)加速計(jì)算過程之外，本文在coverage計(jì)算上的算法流程跟[AW80]中的邊緣填充（edge fill）光柵化算法基本一致。

先考慮不需要并行計(jì)算的部分，三角形的光柵化過程是通過計(jì)算left event與right event來(lái)實(shí)現(xiàn)的，整個(gè)屏幕2D空間被一條條等間隔的水平scanline分割成一個(gè)個(gè)的Pixel/Fragment，而所謂的left event指的是三角形與某條scanline相交的左邊界，right event則是相交的右邊界，通常來(lái)說(shuō)left event是三角形某條邊跟scanline的交點(diǎn)，而right event則是另一條邊與scanline的交點(diǎn)，對(duì)于某條固定的邊而言，如果我們已經(jīng)找到了其最下端與scanline的交點(diǎn)，我們只需要計(jì)算出（斜率）即可隨著scanline序號(hào)的增加（即y增加一個(gè)）加上一個(gè)對(duì)應(yīng)的數(shù)值（比如是）即可得到對(duì)應(yīng)的新的scanline的交點(diǎn)，因此其計(jì)算過程十分簡(jiǎn)單。

這里的一個(gè)問題是，如果三角形某條邊（線段）在scanline序號(hào)遞增的過程中已經(jīng)到達(dá)了終點(diǎn)，從而需要另外更換一條新的邊進(jìn)行l(wèi)eft/right event的計(jì)算，這種情況就不能直接通過對(duì)一個(gè)數(shù)值進(jìn)行相加來(lái)得到了，而是應(yīng)該重新啟動(dòng)初始化過程（新的邊與scanline的初始交點(diǎn)計(jì)算過程）了，其實(shí)簡(jiǎn)單來(lái)說(shuō)，就是要以y方向上的中間頂點(diǎn)為界，畫一條水平線，將三角形拆成兩個(gè)三角形，top/bottom triangle。

對(duì)于某條scanline而言，如果已經(jīng)知道了left/right event，那么下一步就是計(jì)算這個(gè)三角形在這條scanline上的coverage情況了。這里的做法是為32個(gè)像素生成一個(gè)32bit的coverage mask，每個(gè)bit對(duì)應(yīng)一個(gè)像素（如果三角形的覆蓋數(shù)據(jù)超出32個(gè)像素，那么就會(huì)對(duì)應(yīng)多個(gè)coverage mask，每個(gè)coverage mask占用一次循環(huán)調(diào)用，處于一般性考慮，這里只考慮單個(gè)coverage mask能夠覆蓋的情況），之后整個(gè)coverage mask可以用一個(gè)register來(lái)表示，register在初始化時(shí)可以直接將每一位設(shè)置為1（表示有像素覆蓋），之后根據(jù)left/right event數(shù)據(jù)使用移位操作來(lái)清除left/right邊界之外的像素對(duì)應(yīng)bit上的數(shù)值（表示沒有像素覆蓋）：

// Compute coverage for the 32-pixels at pos. x,
// given the left and right triangle events
function coverage(x, left, right)
{
  return (~0 >> max(0, left - x)) & ~(~0 >> max(0, right - x));
}

每路SIMD對(duì)應(yīng)一個(gè)coverage mask，8路SIMD分別對(duì)應(yīng)水平坐標(biāo)一致的8個(gè)相鄰scanline上的coverage mask。這種做法的一個(gè)問題是什么呢，那就是對(duì)于某個(gè)scanline而言，我們只有兩個(gè)event需要追蹤，但是每個(gè)triangle卻有三條edge會(huì)對(duì)這兩個(gè)數(shù)據(jù)造成影響，因此使用上面的移位操作是不準(zhǔn)確的，更為恰當(dāng)?shù)淖龇☉?yīng)該是使用如下的函數(shù)進(jìn)行計(jì)算：

// Compute coverage for 32x8 pixel tile. Params
// are SIMD8 registers with 32 bits per lane
function coverageSIMD(x, e0, e1, e2, o0, o1, o2)
{
  m0 = (~0 >> max(0, e0 - x)) ^ o0;
  m1 = (~0 >> max(0, e1 - x)) ^ o1;
  m2 = (~0 >> max(0, e2 - x)) ^ o2;
  return m0 & m1 & m2;
}

上面這個(gè)算法可以理解成對(duì)每條邊，都clear掉其右側(cè)的像素區(qū)域（三角形按照逆時(shí)針設(shè)置每條邊的方向，如果對(duì)三角形的edge按照一定的順序進(jìn)行排序的話，還可以省掉上面的xor計(jì)算消耗），最后將clear結(jié)果進(jìn)行相交計(jì)算，以得到最終的mask結(jié)果，整個(gè)過程如下圖所示：

上面這個(gè)算法只是一個(gè)示意計(jì)算過程，實(shí)際上原文還給了一些指令優(yōu)化的實(shí)施方案，因?yàn)闊o(wú)助于整個(gè)算法框架的介紹，這里就不展開了。

Precision
因?yàn)樯厦孢@個(gè)coverage算法并沒有依賴于具體的edge function（這是什么？三角形每條邊的坐標(biāo)公式嗎？），因此其最終光柵化的結(jié)果跟DX光柵化規(guī)則作用下的結(jié)果可能不太一樣。比如前面說(shuō)過，left/right event的計(jì)算是根據(jù)對(duì)初始交點(diǎn)進(jìn)行遞增來(lái)實(shí)現(xiàn)的，而計(jì)算結(jié)果并不是十分精確的（比如經(jīng)過四舍五入，會(huì)有精度損失；又比如假設(shè)三角形某條邊接近水平，這個(gè)數(shù)值將變得十分巨大，其精度將進(jìn)一步下降（浮點(diǎn)數(shù)越靠近零點(diǎn)，精度越高）），因此使得在光柵化的過程中會(huì)有累計(jì)誤差的存在。而這種不精確的光柵化結(jié)果會(huì)使得遮擋剔除出現(xiàn)false positive（某個(gè)物件被判定為可見，實(shí)際上是不可見的，導(dǎo)致渲染消耗的浪費(fèi)，倒并不會(huì)導(dǎo)致渲染結(jié)果的異常）問題，不過從此前的軟件光柵化方案來(lái)看，各個(gè)方案或多或少都有這樣的問題，因此也并不是不能容忍。

如果要想做得更好，也可以按照[Bre65]中介紹的Bresenham插值算法來(lái)實(shí)現(xiàn)一個(gè)遵循DX光柵化規(guī)則的對(duì)應(yīng)算法版本，從而消除上面提到的精度誤差，原文說(shuō)到Intel做了一個(gè)demo版本，經(jīng)過測(cè)試在大量的隨機(jī)三角形輸入下，都能取得跟GPU光柵化一致的結(jié)果，不過SIMD優(yōu)化版本還沒搞定，因此這里就不介紹具體性能數(shù)據(jù)了。

之后只需要得到這條邊上的第一個(gè)交點(diǎn)，根據(jù)斜率就可以推算出其他的交點(diǎn)，因?yàn)槭褂昧薃VX，我們可同時(shí)完成8個(gè)scanline的處理。

之后就是對(duì)三角形的left/right event進(jìn)行處理，得到三角形的coverage mask，具體邏輯后面有詳細(xì)描述。

先將整個(gè)tile設(shè)置成完全被覆蓋的，之后對(duì)每條scanline找到三角形與之相交的left/right event

得到最終結(jié)果

3.2. Hierarchical Depth Buffer

上一節(jié)我們介紹過，經(jīng)過coverage計(jì)算后，每路SIMD的mask包含32個(gè)bits，8路SIMD對(duì)應(yīng)32 x 8個(gè)bits，出于計(jì)算效率的考慮，depth test & update就不再適用與32 x 1這樣的長(zhǎng)條狀processing unit，因此這一節(jié)會(huì)對(duì)SIMD的覆蓋區(qū)域進(jìn)行重新劃分，將32 x 8個(gè)bits分成8 x 4為一個(gè)tile的4 x 2個(gè)tiles array，每個(gè)tile（注意不是每個(gè)像素）會(huì)分配兩個(gè)浮點(diǎn)數(shù)（表示depth）以及一個(gè)32bits的mask，這個(gè)mask用于指示這個(gè)tile中的每個(gè)像素使用的是上面兩個(gè)浮點(diǎn)數(shù)中的哪個(gè)浮點(diǎn)數(shù)。

如下圖所示，為了后面計(jì)算方便，coverage mask計(jì)算完成后需要對(duì)SIMD lane覆蓋的方式進(jìn)行一下調(diào)整與重排，在調(diào)整之前，每條lane對(duì)應(yīng)一個(gè)scanline

調(diào)整后，每條SIMD lane對(duì)應(yīng)一個(gè)8x4的tile，結(jié)果如下圖

4 x 2個(gè)tiles就有8個(gè)struct，從而組成一個(gè)Struct of Array（Struct包含三個(gè)Array，對(duì)應(yīng)上面的三個(gè)數(shù)據(jù)），之后通過使用AVX2指令，就可以實(shí)現(xiàn)對(duì)8個(gè)tiles的depth test & update的并行計(jì)算。

如上圖所示，左側(cè)小圖表示的是一個(gè)8 x 4個(gè)像素組成的一個(gè)tile，前面說(shuō)過，每個(gè)tile分配了三個(gè)數(shù)據(jù)，從右圖可以看出，表示的是較遠(yuǎn)的一個(gè)depth值，而表示的則是較近的一個(gè)depth值。即左圖中黃色三角形距離相機(jī)更近，而藍(lán)色三角形距離相機(jī)較遠(yuǎn)，另外剩下的32bits的mask則表示的是tile中每個(gè)像素所對(duì)應(yīng)的depth數(shù)值，因?yàn)橹挥袃蓚€(gè)depth可選，因此只需要一個(gè)bit表示。

Depth Buffer Update
由于整個(gè)場(chǎng)景中不止一個(gè)三角面片，而多個(gè)三角面片之間是有重疊的，因此我們需要一個(gè)算法來(lái)對(duì)被三角面片所覆蓋的tile數(shù)據(jù)進(jìn)行更新，精確的可供參考的算法有[AHAM15]，但是這個(gè)算法太過復(fù)雜，因此Intel又參考[FBH*10]的quad fragment merging算法寫了一個(gè)相對(duì)簡(jiǎn)單但是結(jié)果不那么精確的算法，相對(duì)于原算法而言，這里對(duì)渲染順序的要求更為嚴(yán)格，實(shí)際上，我們?cè)谧鰋cclusion culling的時(shí)候，最好使用經(jīng)過良好排序的物件列表（即距離近的優(yōu)先處理），這樣得到的性能最高。

function updateHiZBuffer(tile, tri)
{
  // Discard working layer heuristic
  // zMax1 < zMax0, zMax1 -> More Near
  dist1t = tile.zMax1 - tri.zMax;
  dist01 = tile.zMax0 - tile.zMax1;//positive
  // Not Occluded And Far From Tile, Using Cur Triangle As New Near Plane
  if (dist1t > dist01)
  {
    tile.zMax1 = 0;// Reset The Near Plane
    tile.mask = 0;// Reset The Tile PixelDepth Selection Data
  }

  // Merge current triangle into working layer
  // dist1t > dist01, Not Occluded, Using tri.zMax, Near One
  // dist1t < dist01, but dist1t >= 0, Not Occluded, Using tile.zMax1, Far One?
  // dist1t < 0, Occluded, Using tri.zMax, Far One?
  tile.zMax1 = max(tile.zMax1, tri.zMax);
  // dist1t > dist01, Coverage Area Select zMax1, Other zMax0
  // dist1t > 0, Union Older zMax1 Area, Using zMax1
  // dist1t <= 0, Union Older zMax1 Area, Using zMax1?
  tile.mask |= tri.coverageMask;
  // Overwrite ref. layer if working layer full
  if (tile.mask == ~0)
  {
    tile.zMax0 = tile.zMax1;
    tile.zMax1 = 0;
    tile.mask = 0;
  }
}

tile中的兩個(gè)深度數(shù)值，近的我們成為working layer，遠(yuǎn)的，我們成為reference layer，偽代碼中的邏輯總的來(lái)說(shuō)可以分成三部分：

1. 如果當(dāng)前triangle在這個(gè)tile范圍內(nèi)的最大深度遠(yuǎn)遠(yuǎn)小于working layer深度：那么這個(gè)時(shí)候就將working layer重置到近平面處，并同時(shí)將tile中所有像素的深度設(shè)置為reference layer的深度（這個(gè)更新邏輯是基于什么考慮？這是因?yàn)?，?dāng)depth出現(xiàn)一個(gè)較大的不連續(xù)性，比如下圖中下方小圖中右邊的triangle的depth遠(yuǎn)遠(yuǎn)小于當(dāng)前tile的兩個(gè)參考depth，就表明目前參與光柵化的是一個(gè)新的物件，這個(gè)triangle只是先遣部隊(duì)，后續(xù)的triangle會(huì)逐步將整個(gè)tile覆蓋住的，所以可以直接放棄之前的working layer的積累，迎接全新的數(shù)據(jù)的到來(lái)。上方小圖左側(cè)對(duì)應(yīng)的是不做這個(gè)處理的HiZ，右側(cè)對(duì)應(yīng)的是做完這個(gè)處理的HiZ，原文中說(shuō)是會(huì)存在背景物件輪廓處的depth泄露，我的理解是如果不做這個(gè)處理的話，考慮到后面working layer的合并邏輯，最終tile的working layer深度會(huì)更多的使用前一個(gè)物件的depth，導(dǎo)致當(dāng)前更近物件的depth無(wú)法覆蓋上去，從而使得working layer depth相對(duì)更遠(yuǎn)一點(diǎn)（更黑一點(diǎn)））；其他情況則維持tile數(shù)據(jù)不變。

2. 在working layer depth與中取較大（較遠(yuǎn)）的作為新的working layer depth（這個(gè)是基于什么考慮呢？首先，當(dāng)前參與tile參數(shù)更新的triangle需要是能夠通過當(dāng)前tile的depth test的，不然這樣一更新，可能就會(huì)使得working layer比reference layer還遠(yuǎn)，這是不符合設(shè)定的；其次，如果working layer depth小于triangle的max depth，那么如果以擴(kuò)大coverage mask為目的，為了避免更新后的誤剔除，就應(yīng)該以較遠(yuǎn)的一個(gè)為準(zhǔn)，從而保證在大于這個(gè)深度的數(shù)據(jù)是肯定會(huì)被遮擋住的，而以較近的為準(zhǔn)，就沒有做出絕對(duì)正確的判斷了），并合并當(dāng)前triangle的coverage mask到tile中。
3. 如果當(dāng)前tile的coverage mask已經(jīng)滿了，這個(gè)時(shí)候就需要用近的working layer depth來(lái)替換遠(yuǎn)的reference layer，從而保證tile的遮擋面片是不斷向前推進(jìn)的，這個(gè)過程可以參考下圖示意。

為了對(duì)這個(gè)過程有一個(gè)更為直觀的認(rèn)識(shí)，借用參考文獻(xiàn)[5]中的幾張圖來(lái)說(shuō)明：

depth test是與depth update同步進(jìn)行的，這里介紹了兩種用于對(duì)depth進(jìn)行更新的方法，后者雖然精度上有所下降，但是速度上有很大提升。

每個(gè)tile有兩個(gè)代表不同深度的浮點(diǎn)數(shù)：

1. 是reference layer，指的是整個(gè)tile的最大深度（最遠(yuǎn)距離）
2. 是working layer，表示的是tile中部分區(qū)域的最大深度（更近一點(diǎn)的遮擋面），這是depth update的焦點(diǎn)，會(huì)按照如下模式進(jìn)行更新
   2.1 ，取三角形的最大深度與當(dāng)前深度的最大值
   2.2 新的selection mask取三角形的coverage mask與原始tile的selection mask的并集
3. 當(dāng)working layer對(duì)應(yīng)的selection mask已經(jīng)被填滿了，此時(shí)就可以將reference layer往前提到working layer上，并重置working layer的數(shù)據(jù)

如下圖所示，如果有一個(gè)面片完全覆蓋了整個(gè)tile，那么沒說(shuō)的，直接修正reference layer

如果是部分覆蓋（通過了depth test），那么就修正下working layer，同時(shí)修改selection mask

而有一個(gè)新的面片通過了depth test的話，與之前的working layer depth取其中最大的數(shù)值，同時(shí)對(duì)mask求并

經(jīng)過并集之后，如果working layer已經(jīng)滿了，就將reference layer拉上來(lái)

開始下一輪的重新處理

這里有一個(gè)特殊的處理策略，即當(dāng)新的三角面片遠(yuǎn)遠(yuǎn)超過兩個(gè)layer之間的深度差，會(huì)直接考慮清掉working layer的數(shù)據(jù)，使用新面片的數(shù)據(jù)，這是因?yàn)楫?dāng)發(fā)生這種情況時(shí)，通常意味著一個(gè)新的物件的處理流程的開始，還使用老的一套數(shù)據(jù)，會(huì)導(dǎo)致一些新的面片數(shù)據(jù)被老的數(shù)據(jù)所遮蓋，使得新物件的遮擋效果被削弱。

在這個(gè)基礎(chǔ)上繼續(xù)進(jìn)行后續(xù)處理。

完全覆蓋的情況，前面已經(jīng)說(shuō)過了，直接修改reference layer，并重置working layer。

效果驗(yàn)證，update、test都比之前的方法要快。

Hierarchical Depth Test
正如前面所說(shuō)，在進(jìn)行過光柵化的時(shí)候還會(huì)同時(shí)對(duì)triangle進(jìn)行depth test，目的不是查詢當(dāng)前triangle是否可見，而是為了對(duì)光柵化邏輯進(jìn)行性能優(yōu)化，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=z_%7Bmax%7D%5E0%20%3E%20z_%7Bmax%7D%5E1" alt="z_{max}^0 > z_{max}^1" mathimg="1">，因此這里只需要檢測(cè)與（用是不是更準(zhǔn)確？后面Discussion有說(shuō)）兩者誰(shuí)更大，如果后者更大，說(shuō)明當(dāng)前triangle至少部分是被tile所遮擋的（存在較大概率全部被遮擋？），這時(shí)候就放棄使用triangle對(duì)tile的更新。實(shí)踐證明，雖然這個(gè)做法非常簡(jiǎn)單，但是卻可以極大的加速光柵化流程。

雖然這種做法十分合理，但很多軟光柵算法都沒有使用。

depth test是逐tile進(jìn)行的，每個(gè)tile包含兩個(gè)代表一前一后深度的浮點(diǎn)數(shù)以及表示8x4個(gè)像素所對(duì)應(yīng)的深度的uint32 mask。

Discussion
本文給出的算法跟[AHAM15]的很像，不同的是，本文算法放棄了參數(shù)的使用，而這個(gè)參數(shù)通常會(huì)被用于判斷triangle是否完全被遮擋，不過通常來(lái)說(shuō)，可見物件的遮擋查詢消耗都不會(huì)很高（因?yàn)橹灰l(fā)現(xiàn)一個(gè)像素可見，就可以隨時(shí)終止查詢，對(duì)于可見物件而言，這個(gè)過程會(huì)很快），因此完全遮擋情況下的跳過后續(xù)的遮擋查詢?cè)趖ile模式下可能作用不大，后續(xù)在使用中再判斷是否需要保留這個(gè)數(shù)值。

4. Results

上圖給出了HiZ算法與本文的Mask算法的性能對(duì)比，實(shí)線表示的是單幀繪制總消耗，虛線表示的是遮擋剔除的時(shí)間消耗，雖然Mask算法剔除的triangle數(shù)量相對(duì)于HiZ少了2%，但是其表現(xiàn)還是要遠(yuǎn)遠(yuǎn)超出HiZ算法。作為對(duì)比，不使用任何軟光柵時(shí)的單幀消耗用紅線的Frustum來(lái)表示（軟光柵可以極大的提升渲染性能，不只是因?yàn)闇p少了CPU/GPU之間的數(shù)據(jù)傳輸，同時(shí)也降低了CPU一側(cè)的消耗；不過需要注意的是，如果場(chǎng)景很復(fù)雜，瓶頸處在GPU側(cè)，那么軟光柵的作用就沒有那么明顯了，因?yàn)镃PU優(yōu)化并不能降低瓶頸位置的消耗）。上述測(cè)試是在提交順序按照物件從近到遠(yuǎn)的條件下完成的。

為了單純的比對(duì)算法的效率，這里測(cè)試使用的是單線程模式（原文描述說(shuō)單線程就夠了，其他線程可以分配給其他工作，且就線程模式來(lái)說(shuō)的話，這個(gè)算法不比任何其他算法差。。）。當(dāng)前算法已經(jīng)放入到Intel的Software Occlusion Culling Framework中。

4.1. Intel Software Occlusion Culling Framework

2016年1月份的Framework版本已經(jīng)集成了經(jīng)過AVX2指令優(yōu)化后的HiZ算法版本，這個(gè)算法使用了兩個(gè)pass完成遮擋剔除：

1. 首先將遮擋體軟光柵到一個(gè)全分辨率的depth buffer中，之后以8 x 8為一個(gè)tile統(tǒng)計(jì)出這個(gè)tile中的最大depth，得到一個(gè)降分辨率的depth buffer（HiZ Buffer）
2. 使用降分辨率的Depth Buffer進(jìn)行遮擋查詢，以確定哪些物件需要被剔除。

本文算法對(duì)上述算法做了兩個(gè)改進(jìn)：

1. 放棄了此前對(duì)物件進(jìn)行遮擋查詢時(shí)使用的對(duì)物件的bounding box進(jìn)行像素級(jí)別的軟光柵，只是保留了一個(gè)粗糙的遮擋查詢，即使用屏幕空間的bounding rectangle來(lái)進(jìn)行查詢。
2. 將場(chǎng)景中需要參與查詢的物件組織成一棵與坐標(biāo)系平齊的AABB樹。因?yàn)閳?chǎng)景中存在較多的小物件，單個(gè)單個(gè)查詢費(fèi)時(shí)費(fèi)事，組織成樹狀結(jié)構(gòu)就可以分層進(jìn)行查詢，先粗糙后精細(xì)，通過這種方式可以極大節(jié)省算法開銷。

經(jīng)過上述兩個(gè)優(yōu)化后，每幀消耗得到了極大提升。

上圖給出了兩種算法在各個(gè)子項(xiàng)上的性能數(shù)據(jù)對(duì)比。

4.2. Interleaved Rasterization and Queries（將光柵化流程跟遮擋查詢流程放在一起處理）

Intel還對(duì)本文給出的算法做了一個(gè)stand-alone的實(shí)現(xiàn)，在這個(gè)實(shí)現(xiàn)中，場(chǎng)景是按照AABB樹的格式存儲(chǔ)的，并使用一個(gè)堆（heap）實(shí)現(xiàn)場(chǎng)景節(jié)點(diǎn)接近front-to-back順序的遍歷，在遍歷的過程中會(huì)對(duì)節(jié)點(diǎn)進(jìn)行frustum culling & occlusion query，從而在當(dāng)前節(jié)點(diǎn)被判定不可見的時(shí)候，可以跳過其子節(jié)點(diǎn)的遍歷流程，下面給出的是節(jié)點(diǎn)遍歷的偽代碼：

function traverseSceneTree(worldToClip)
{
  heap = rootNode
  while !heap.empty()
  {
    node = heap.pop()
    if node.isLeaf()
    {
      rasterizeOccluders(node.triangles)
      node.visible = true
    }
    else:
    {
      for c in node.children
      {
        culled = frustumCull(c.AABB)
        clipBB = transform(worldToClip, c.AABB)
        rect = screenspaceRect(clipBB)
        culled |= isOccluded(rect, clipBB.minZ)
        if !culled:
          heap.push(c, clipBB.minZ)
      }
    }
  }
}

雖然上面的代碼看起來(lái)就跟隨便從哪個(gè)關(guān)于軟光柵的教科書上抄過來(lái)的一樣，但實(shí)際上這里需要注意的是，傳統(tǒng)算法中，將節(jié)點(diǎn)遍歷（光柵化）跟遮擋剔除像這樣一樣放到一起是會(huì)產(chǎn)生問題的。

比如HiZ之類的軟光柵方案，因?yàn)镠ierarchical Depth Buffer的生成消耗很高（參見后面的性能消耗表格），因此想要將光柵化邏輯跟遮擋查詢邏輯放在一起是不現(xiàn)實(shí)的（光柵化的過程會(huì)對(duì)Hierarchical Depth Buffer進(jìn)行更新，如果放在一起，就會(huì)導(dǎo)致整個(gè)流程效率的低下？）。

同樣，對(duì)于采用GPU實(shí)現(xiàn)的硬件光柵化算法，如果希望用硬件光柵化的結(jié)果（depth buffer）像上面代碼中一樣直接用來(lái)對(duì)節(jié)點(diǎn)進(jìn)行遮擋查詢的話，由于數(shù)據(jù)讀取的延遲，同樣會(huì)造成同步以及阻塞等問題。

本文使用的軟光柵方案可以在同一個(gè)Hierarchical Depth Buffer上讀取數(shù)據(jù)對(duì)節(jié)點(diǎn)的可見性進(jìn)行判斷（遮擋查詢），同時(shí)還可以將通過遮擋查詢的節(jié)點(diǎn)通過軟光柵對(duì)這個(gè)Buffer進(jìn)行更新，而這種做法不會(huì)存在任何的性能問題，因此使得對(duì)場(chǎng)景的遍歷算法變得更為簡(jiǎn)單，而且由于只需要對(duì)那些可見的節(jié)點(diǎn)進(jìn)行光柵化，因此效率也比其他算法要高一些。

上圖是本文算法的測(cè)試場(chǎng)景以及對(duì)應(yīng)的測(cè)試數(shù)據(jù)，測(cè)試過程中添加了一個(gè)較短的相機(jī)動(dòng)畫。整個(gè)場(chǎng)景包含了大概73M個(gè)面片，不過這些面片并不會(huì)全部參與到Hierarchical Depth Buffer的生成中（畢竟生成與更新也是有代價(jià)的），作為遮擋體的面片數(shù)目為143K（這些面片來(lái)自于architectural mesh，這種mesh有什么特征？）。

跟此前Intel的Demo場(chǎng)景相比，這個(gè)測(cè)試場(chǎng)景更為復(fù)雜，且遮擋體包含了數(shù)目眾多的大而細(xì)長(zhǎng)（sliver）的三角面片，而這類面片由于具有較大的屏幕空間rectangle而會(huì)導(dǎo)致計(jì)算效率的下降，同時(shí)也并沒有提供相對(duì)應(yīng)的遮擋剔除貢獻(xiàn)，但是即使在這種情況下，比對(duì)本文算法與此前Intel算法在worst case上的表現(xiàn)，還是可以得到遠(yuǎn)超此前算法的性能，且跟純粹的frustum culling算法比起來(lái)，只在一些極難遇到的情況下才會(huì)得到稍差的表現(xiàn)（即這個(gè)算法可以完全取代frustum culling了），而在這些情況下，幀率都是非常高的，不會(huì)造成問題。

上圖是本文算法應(yīng)用的第二個(gè)測(cè)試場(chǎng)景，這個(gè)場(chǎng)景包含了7M面片，且這一次直接將所有面片都用于計(jì)算hierarchical depth buffer，因此但從遮擋體復(fù)雜度來(lái)說(shuō)，這應(yīng)該是整篇文章中最復(fù)雜的測(cè)試場(chǎng)景了。

從這種設(shè)定來(lái)看，軟光柵的性能可能很難超過純粹的frustum culling算法，當(dāng)然，如果將場(chǎng)景渲染的pixel shader設(shè)計(jì)得復(fù)雜一點(diǎn)，場(chǎng)景材質(zhì)做得更多一點(diǎn)，那么frustum culling所需要承擔(dān)的高額overdraw的消耗就會(huì)更高，軟光柵算法的數(shù)據(jù)會(huì)漂亮一點(diǎn)，但是出于公平考慮，這里整個(gè)場(chǎng)景只使用一個(gè)簡(jiǎn)單的材質(zhì)，且從頭到尾不需要進(jìn)行renderstates切換，且軟光柵只使用單個(gè)CPU核來(lái)完成相關(guān)計(jì)算，但是即使在這種設(shè)定下，本文算法的性能表現(xiàn)依然很好，只在少數(shù)一些相機(jī)位置的表現(xiàn)不如frustum culling算法，且總體的時(shí)間消耗都可以控制在5ms以下。

上圖還給出了不同算法最終提交到GPU的面片數(shù)目，本文算法基本上跟HiZ表現(xiàn)一樣，在一些情況下其Culling力度甚至超越了HiZ（這是因?yàn)镠iZ的Depth Buffer并不是每幀更新的，因?yàn)闀r(shí)間消耗的關(guān)系，是每隔幾幀才更新一次）。

有限時(shí)間預(yù)算
遮擋剔除算法可以通過選擇合適的遮擋體來(lái)進(jìn)行加速，本文是通過將場(chǎng)景物件按照從前往后排序來(lái)實(shí)現(xiàn)這個(gè)過程的，因此遮擋效力最強(qiáng)的面片通常都是最先被光柵化的，而如果分配給軟光柵的時(shí)間是有限的，那么這里可以在軟光柵的時(shí)候開啟一個(gè)計(jì)時(shí)器，當(dāng)時(shí)間到了就停止軟光柵，不過即使這樣，遮擋查詢過程還是會(huì)有一些消耗，從而使得最終的消耗超出預(yù)算，但是也算是一種比較有效的平衡CPU/GPU消耗的方案了。下圖給出了在MPI informatics building場(chǎng)景中遮擋剔除所花費(fèi)的時(shí)間以及對(duì)應(yīng)的物件、面片剔除數(shù)量之間的關(guān)系（看起來(lái)似乎是一個(gè)分段的遞減關(guān)系）：

4.3 Scaling

為了驗(yàn)證本文算法的scaling表現(xiàn)，使用了一個(gè)使用程序生成的測(cè)試場(chǎng)景，這個(gè)場(chǎng)景中包含了32k個(gè)等腰（isosceles）直角（right-angled）三角形，這些三角形的位置跟朝向都是隨機(jī)的，且都是按照從后往前的順序進(jìn)行渲染的，從而避免數(shù)據(jù)被early test干掉。

以HiZ算法作為比對(duì)參考，從上圖中上面一個(gè)小圖可以看到，本文算法在三角形尺寸較大的時(shí)候，性能要遠(yuǎn)遠(yuǎn)優(yōu)于HiZ，而在三角形尺寸較小的時(shí)候，性能則跟HiZ比較接近。

需要說(shuō)明的是，使用低分辨率的Depth Buffer的問題是，可能會(huì)導(dǎo)致剔除精度的下降，從而導(dǎo)致錯(cuò)誤的剔除結(jié)果，上圖中的下面一個(gè)小圖給出了每個(gè)光柵化像素對(duì)應(yīng)的CPU時(shí)鐘周期消耗，可以看到，不論在哪種三角形尺寸下，本文算法的消耗都要小于HiZ算法。

5. Conclusion

本文給出的軟光柵剔除方案不論是性能表現(xiàn)還是剔除精度上都有不錯(cuò)的表現(xiàn)。

再來(lái)回顧一下算法的框架：

1. 使用的depth buffer是一種特殊的按照tile劃分的組織結(jié)構(gòu)，每個(gè)tile包含兩個(gè)一前一后兩個(gè)深度浮點(diǎn)數(shù)，以及一個(gè)表征各個(gè)像素從屬深度的uint32 mask
2. 三角形的光柵化是通過SIMD edge fill算法完成，先找到第一個(gè)scanline的left/right event，之后每一個(gè)新增的scanline只需要在這個(gè)基礎(chǔ)上按照斜率進(jìn)行疊加即可得到對(duì)應(yīng)的left/right event，之后就可以根據(jù)這個(gè)來(lái)計(jì)算三角形覆蓋的屏幕空間像素了。
3. 本文算法所使用的depth更新是仿造quad fragment merging算法完成的，通過對(duì)三角面片的coverage mask以及來(lái)實(shí)現(xiàn)tile的的向前推進(jìn)，從而實(shí)現(xiàn)最終depth buffer的構(gòu)造，而occlusion query跟depth update是放在一起進(jìn)行的

參考文獻(xiàn)

[1] Masked Software Occlusion Culling
[2]. HyperZ
[3]. ATI Radeon HyperZ Technology
[4] 本文算法源碼地址
[5] 本文對(duì)應(yīng)PPT地址