【遊戲場景剔除】剔除演算法綜述

之前在做場景最佳化的過程中，看了不少論文和部落格闡述不同剔除演算法的原理和過程，自己參照著演算法去實現了Hiz和軟體剔除。一直想寫一篇關於剔除演算法的綜述，來總結常用剔除演算法的實現原理和過程。

在遊戲執行中，引擎渲染出數以萬計的物體，場景複雜度往往是數千萬面的級別，同時還需要處理千計盞燈光和數百種材質。因此，如何有效地減少不必要的繪製就顯得格外重要。本文將就遊戲引擎中用到的各種剔除技術進行概述，會較少涉及細節，感興趣的同學可以去看文末的參考文獻，文獻中會有相關剔除演算法的原理和具體實現。

我們將分為以下四個方面來介紹：

1.場景剔除工作原理

2.常用剔除演算法

3.總結

4.參考文獻

一、場景剔除工作原理

對於場景物體的剔除一般分為可見性剔除和遮擋剔除：

1.可見性剔除

可見性剔除透過判斷物體與相機的距離（距離剔除）或者是否在相機的視錐體內（視錐體剔除）來對物體進行剔除。

如圖所示，不在相機視錐體內部的物體將被剔除不進行渲染。

2.遮擋剔除

遮擋剔除則是在相機可見範圍內透過判斷物體是否被其他物體遮擋來對物體進行剔除。遮擋剔除有基於整個物體是否被遮擋的剔除（Hiz、硬體遮擋查詢等），也有基於畫素級別的遮擋查詢（Early Z）。

圖中藍色虛線的物體被相機前方的物體遮擋，並將剔除不進行渲染。

二、常用剔除演算法

本文將大致介紹以下剔除演算法的原理和實現過程：

（1）。距離剔除

（2）。視錐體剔除

（3）。Occluder剔除（軟體剔除）

（4）。視口剔除

（5）。背面剔除

（6）。遮擋查詢（Occlusion Query）

（7）。Early Z Culling

（8）。Hiz Culling

（9）。PVS

1.距離剔除

剔除階段：應用程式階段。

透過物體和相機的距離進行判斷物體是否被剔除，原理比較簡單，剔除效率也相對較高。在UE4中可以透過物體屬性設定剔除的最大距離和最小距離（如下圖）：

2.視錐體剔除

剔除階段：應用程式階段。

即簡單的判斷一個物體是否位於視錐稜臺內。裁剪的依據主要是根據攝像機的視野（field of view）以及近裁減面和遠裁剪面的距離，將可視範圍外的物體排除出渲染。

上圖中1為近裁剪螢幕，2為裁剪截面體，3為遠裁剪平面

在實踐中，由於模型往往是比較複雜的，很難精確計算它和視錐體的交集，因此一般是用軸對齊包圍盒（AABB），有向包圍盒（OBB）或者包圍球（BSphere）代替模型本身進行相交計算。

視椎體剔除是減少渲染消耗的最有效手段之一，可以在不影響渲染效果的情況下大幅減少渲染涉及到的頂點數和麵數。

3.occluder剔除(軟體剔除)

剔除階段：應用程式階段。

這個方案的思路是，首先利用CPU構造一個低解析度的Z-Buffer，在Z-Buffer上繪製一些場景中較大的遮擋體：

在構造好的Z-Buffer上，繪製小物體的包圍盒，然後執行類似於occlusion query的操作，查詢當前物體是否被遮擋：

由於是純CPU的，整合起來也比較簡單，同時不會有GPU stall的問題。缺點是需要美術指定一些大的遮擋體，對CPU效能有一定的消耗。在UE4中透過物體actor的LOD For Occluder設定遮擋體。

4.視口剔除

剔除階段：投影變換之後螢幕對映之前。

發生在幾何階段（Geometry Stage）後期，投影變換之後螢幕對映之前，是渲染管線的必要一環。只有當圖元完全或部分存在於規範立方體內部的時候，才將其返送到光柵化階段。其中，對於完全位於規範立方體內部的圖元，則直接進行下一階段；完全處於規範立方外部的圖元則完全被捨棄；部分處於規範立方體內部圖元，則會根據視口進行對應的裁剪，在這一過程中可能會產生新的頂點。透過視口剔除可以將視口外的圖元捨棄掉，減小光柵化階段的消耗。

5.背面剔除

剔除階段：在光柵化階段進行。

當我們觀察場景中物件時，一般只能以一定角度來觀察，那麼物件的某些面我們是看不到的，例如你觀察一個立方體，最多隻能同時看到3個面，有時只能看到1個面，而我們繪製時如果不採取剔除背面的措施，則要繪製6個面，其中包括一些我們根本看不到的面。對於立方體這個面較少的幾何物件，效能開銷不明顯，但是對於複雜的模型，開啟背面剔除則能明顯改善渲染效能。 背面剔除，就是早點丟棄對觀察者來說是背面的片元的一種方法。

剔除的基本原理是先判定多邊形的朝向，並和當前的觀察方向進行比較。opengl中設定背面剔除相關函式：

glFrontFace（GL_CW）； 設定順時針或者逆時針為正面

glCullFace（GL_BACK）； 設定剔除正面或者背面

背面剔除在光柵化階段進行，執行在Vertex Shader 之後，在Fragment Shader片元著色器之前。

6..遮擋查詢（Occlusion Query）

剔除階段：在深度測試時得到待剔除物體，在應用程式階段執行。

參考步驟和程式碼：

https：//

developer。download。nvidia。cn

/books/HTML/gpugems/gpugems_ch29。html

https：//www。

cnblogs。com/mazhenyu/p/

5083026。html

簡單來說，occlusion query允許你在繪製命令執行之前，向GPU插入一條查詢，並且在繪製結束之後的某個時刻，從GPU將查詢結果回讀到系統記憶體裡。這條查詢命令得到的是某次DrawCall中透過Depth Test的Sample數量，當這個Sample的數量大於0時，就表示當前模型是部分可見的，否則當前模型完全被遮擋。

opengl中實現API介面：

//生成查詢物體ID

glGenQueries（GLsizei n， GLuint *ids）；

//開始遮擋查詢

glBeginQuery（GL_SAMPLES_PASSED， 1）；

//結束遮擋查詢

glEndQuery（GL_SAMPLES_PASSED）；

//根據Sample值param是否大於0判斷查詢號為id的物體是否被遮擋

glGetQueryObjectiv（GLenum id， GLenum pname， GLint *param）；

對於複雜的場景，一個顯而易見的最佳化策略就是用包圍盒代替模型本身去做渲染，為了更加精確，我們也可以用多個緊貼的包圍盒或者相對原模型更簡單的Proxy Mesh去做occlusion query。基於這些API，我們就可以得到一個比較簡單的遮擋剔除策略：

首先為這些物體生成查詢物件ID 呼叫glGenQueries

呼叫glBeginQuery開始遮擋查詢

渲染包圍體

呼叫glEndQuery 結束遮擋查詢

呼叫glGetQueryObjectiv，根據ID提取遮擋查詢的結果，並根據結果繪製相應的物體。

glDeleteQueries 刪除ID，回收資源。

Occlusion query的另一個缺點（也是最致命的缺點）是，它需要將查詢結果回讀到系統記憶體裡，這就意味著VRAM->System RAM的操作，走的是比較慢的PCI-E。

為了解決這個問題，比較常用的的方法是讓CPU回讀前一幀的occlusion query的結果，用來決定當前幀某個物體是否visible，對於相機運動較快的場景，用上一幀的結果可能會導致出錯，但由於一般是用包圍盒，本身就是保守的剔除，所以總體來說影響不明顯，UE4預設使用的就是這樣的遮擋剔除方案。

7.Early Z Culling

剔除階段：在光柵化階段後，片元shader執行前。

我們知道傳統的渲染管線中，深度測試是發生在Pixel/Fragment Shader之後的但是，如果我們仔細想下，在光柵化的時候我們已經知道了每個片斷（fragment）的深度，如果這個時候我們可以提前做測試就可以避免後面複雜的Pixel/Fragment Shader計算過程。

提到Early-Z就必須提對應的Late-Z：在圖形管線中，邏輯上Depth Test和Stencil Test是發生在Pixel Shader的執行之後的，因為Pixel Depth在Pixel Shader階段還有可能被修改，所以Pixel Shader->Depth Test的流程順序就是Late-Z。但由於Pixel Depth修改的需求非常少（基於深度混合的Impostor和某些粒子效果），所以絕大部分情況下，Pixel Depth在Rasterization之後、Pixel Shader執行之前就可以被確定下來，如果我們能夠把Depth Test放在Pixel Shader之前，對那些沒透過Depth Test的畫素不執行Pixel Shader，就能夠一定程度上減少SM的壓力，這就是Early-Z這個最佳化策略的初衷，現在已經是GPU的標配了。預設在Pixel Shader裡沒有修改Depth的操作時，這個最佳化就會開啟。

UE4在Prepass中生成earlyZ Depth，然後在光柵化後執行EarlyZ Culling

8.Hiz Culling

剔除階段：在幾何shader得到待剔除物體，在頂點shader執行。

參考步驟和程式碼：

https：//

github。com/nvpro-sample

s/gl_occlusion_culling

Hiz Culling同樣是基於GPU但不同於EarlyZ Culling的剔除演算法，Hiz Culling使用幾何著色器先生成對應物體的包圍盒，然後根據物體的包圍盒選擇對應層級的depth map。利用depth map 對應畫素值對包圍盒進行剔除，得到物體可見性並作標記。為了避免GPU返回標記到記憶體而造成時間消耗，通常使用Transform feedback將此資料流式傳回到頂點shader中，也就是常使用的2-pass。

具體演算法過程如下：

（1）拿到上一幀場景深度buffer，利用深度buffer構造分層深度影象，我們將其稱為Hi-Z map。這些分層的深度圖是對深度緩衝區進行mip-map得到，其中mip級別i中的每個畫素包含mip級別i-1中的對應畫素塊的最大深度。

（2）將當前待繪製的場景物體分為兩個集合：集合1。上一幀已有的物體集合（這裡不一定和上一幀已有物體數量相同，有可能上一幀在相機可視範圍而當前幀不在等情況）。集合2。當前幀新增的待渲染物體

（3）處理集合1：在構建Hi-Z map後，根據集合1物體的包圍盒大小取對應級別的Hi-Z map深度圖，並透過比較物體的包圍盒深度值和儲存在對應深度圖深度資訊來執行遮擋剔除，通常我們比較包圍盒六個頂點深度值與對應位置周圍的四個畫素的深度值判斷物體是否被遮擋。

（4）根據（3）剔除的結果繪製集合1，更新深度buffer

（5）處理集合2：利用新的深度buffer建立mipmap深度圖，對集合2進行剔除。

（6）繪製集合2中物體，更新深度buffer。

值得注意的是：我們對剔除的判斷是在幾何shader中進行，完成物體可見性判斷後，利用transform feedback 將可見性資料流傳回到頂點shader中，這樣可以避免資料從GPU寫回到記憶體。

9.PVS

剔除階段：應用程式階段。

像其他剔除方法一樣，預計算可視性體積用於實現中小型場景的效能最佳化，通常用於因為硬體問題而使動態遮擋剔除受到限制的移動平臺。預計算可視性體積根據玩家或攝像機的位置，將Actor位置的可視性狀態儲存在場景中。

由於預計算可視性是線上下生成的，因此可以省去用於硬體遮擋查詢的渲染執行緒時間，但代價是會增加執行時記憶體和照明構建時間。基於這一點，建議僅在玩家或攝像機可訪問區域放置體積來保持可視性剔除。

標準 PVS分為兩步：

1。 先求解簡易模型：減面，列舉模型上每個頂點，找到一個點使得刪除該頂點，模型變形最小，不停的尋找並刪除影響最小的點直到模型變形超過一定閥值。最終求解出簡易場景模型，為第二步計算做準備。

2。 劃分成小的三維格子，在格子裡面均勻或隨機選取 N個取樣點做為攝像機位置，每個取樣點 360度全方向做一定數量的射線出去，和場景中的模型判斷交點，求解出該取樣點的PVS，然後合併格子裡N個取樣點的結果為該格子的PVS。有離線計算好的，也有實時計算攝像機周圍空間未計算格子的，等攝像機移動到那裡時已經計算好了，無外乎精度不同。實際繪製時將所在格子的PVS提取出來再做一次視錐剔除就行。

三、總結

本文主要對當前引擎常用的一些剔除演算法做了綜述。剔除的本質是消耗少量的計算剔除儘可能多的物體，如果場景物體不復雜或者說互相遮擋不多，此時用一些計算複雜的剔除演算法反而可能使幀率降低。因此，需要根據不同的情況選擇合適的剔除方法，例如對於有大量植被例項場景可以考慮設定距離剔除，場景中有比較大的遮擋物則可以考慮occluder剔除，在手機平臺我們可以考慮基於預計算剔除PVS等，透過這些剔除演算法來提升遊戲場景幀率。

四、參考文獻

1。

https：//

docs。unrealengine。com/e

n-US/Engine/Rendering/VisibilityCulling/CullDistanceVolume/index。html

2。

https：//

blog。csdn。net/game_feng

xiaorui/article/details/79958722

3。

https：//

zhuanlan。zhihu。com/p/48

163037

4。

https：//

software。intel。com/en-u

s/articles/software-occlusion-culling

5。

https：//

bazhenovc。github。io/blo

g/post/gpu-driven-occlusion-culling-slides-lif/

6。

https：//

developer。nvidia。com/gp

ugems/GPUGems2/gpugems2_chapter06。html

7。

https：//www。

gamedev。net/articles/pr

ogramming/graphics/coverage-buffer-as-main-occlusion-culling-technique-r4103/

8。

https：//

gameinstitute。qq。com/co

mmunity/detail/119431

9。

https：//www。

khronos。org/opengl/wiki

/Early_Fragment_Test

10。

http：//

rastergrid。com/blog/201

0/10/hierarchical-z-map-based-occlusion-culling/

11。

https：//

zhuanlan。zhihu。com/p/47

615677

12。

https：//www。

zhihu。com/question/3806

0533