游戲場(chǎng)景管理（二）視錐體剔除

作者：隱士低手

在學(xué)習(xí)場(chǎng)景管理之前，我們要先學(xué)習(xí)一下視錐體剔除(VFC)，因?yàn)闊o(wú)論你使用什么空間劃分算法，劃分的空間都要進(jìn)行視錐體剔除，被剔除的空間內(nèi)部的所有物件都會(huì)被拋棄以此來(lái)加速渲染或碰撞。這也是場(chǎng)景管理的核心目的。

1. 包圍體(BV)與視錐體

包圍體就是把一個(gè)模型或空間包住的最小幾何體，可以是球體，AABB包圍盒，OBB包圍盒。視錐體是一個(gè)被遠(yuǎn)近裁減面截?cái)嗟腻F體（6面體）。視錐體剔除就是判斷包圍體和視錐體的位置關(guān)系。不同的包圍體與視錐體進(jìn)行相交判斷，復(fù)雜度是不一樣的。這里的復(fù)雜度由低到高的順序是球體 < AABB < OBB。另外如果把視錐體變成一個(gè)AABB包圍體，那么相交判斷也會(huì)變的非常簡(jiǎn)單。所以這里有一個(gè)優(yōu)化點(diǎn)就是可以把復(fù)雜的包圍體外面再套一個(gè)簡(jiǎn)單的包圍體，比如AABB上面包裹一個(gè)球體，然后使用球體和視錐體進(jìn)行測(cè)試，如果球體在視錐體內(nèi)再做AABB測(cè)試。再比如可以把視錐體變成AABB然后進(jìn)行測(cè)試，如果在AABB中再進(jìn)行視錐體測(cè)試。這里只是提出一種優(yōu)化的可能性，并不代表性能一定會(huì)提升。這取決于場(chǎng)景，如果一個(gè)場(chǎng)景中有很多節(jié)點(diǎn)，并且大部分節(jié)點(diǎn)都在視錐體之外那么這個(gè)優(yōu)化應(yīng)該會(huì)有一定的提升。我們應(yīng)該注意到多一份包圍體，就會(huì)多一份內(nèi)存，天下沒(méi)有免費(fèi)的午餐，又一個(gè)空間換時(shí)間的優(yōu)化算法。

2. 位置關(guān)系

包圍體和視錐體有三種位置關(guān)系
① 包圍體在視錐體外部
② 包圍體在視錐體內(nèi)部
③ 包圍體部分在視錐體內(nèi)部（相交）

如果包圍體在視錐體外部，說(shuō)明這個(gè)節(jié)點(diǎn)下的全部物件都不在可視范圍內(nèi)，可以全部丟棄。

如果包圍體在視錐體內(nèi)部說(shuō)明全部物件都在視錐體內(nèi)部，這些物件都會(huì)傳遞到GPU中進(jìn)行渲染。這里有一個(gè)問(wèn)題，如果包圍體在視錐體內(nèi)部也就說(shuō)明所有包圍體中的物件都在視錐體內(nèi)部。物件進(jìn)入到GPU中被拆解成三角面片，這些圖元在GPU中做齊次空間裁剪，但這些三角面片其實(shí)是不需要做齊次空間裁剪的，因?yàn)樗鼈兊奈恢藐P(guān)系已經(jīng)確定了，一定是在視錐體內(nèi)部。GPU做了重復(fù)的工作。以前VFC和三角面片裁剪都在CPU中計(jì)算那么可以做標(biāo)記優(yōu)化，現(xiàn)在cpu和gpu按照流水線的方式工作，gpu并不知道這些三角面片不需要被裁剪，甚至gpu的設(shè)計(jì)就是喜歡蠻干并行處理，根本不管你邏輯是否已經(jīng)被剔除。如果能夠把VFC的工作交給gpu，一方面可以降低cpu的負(fù)擔(dān)，另一方面gpu也可以避免一些重復(fù)性的工作，是不是會(huì)更好，這些疑問(wèn)只有等到學(xué)習(xí)完Gpu driven rendering pipelines才能給出答案了。

包圍體部分在視錐體內(nèi)部，這說(shuō)明包圍體中的物件可能在視錐體中，可能在視錐體外，這時(shí)候我們需要做進(jìn)一步的判斷就是用每一個(gè)物件的包圍體進(jìn)行VFC。如果游戲的性能壓力在cpu端，通常我們不會(huì)做進(jìn)一步的測(cè)試。

3. 視錐體的六個(gè)面

視錐體的六個(gè)面由遠(yuǎn)近裁剪面，及上下左右四個(gè)面組成。

我們需要將這六個(gè)面用平面公式表示出來(lái)。

一個(gè)平面可以由平面上的三個(gè)點(diǎn)確定，也可以由平面法線和平面上的一個(gè)點(diǎn)確定。

我們只需要根據(jù)已知變量求解出上圖中的ntl,nbl,ntr,nbr,ftl,fbl,ftr,fbr這八個(gè)點(diǎn)就可以確定6個(gè)平面。

平面方程的確定我簡(jiǎn)單說(shuō)一下思路，具體細(xì)節(jié)網(wǎng)上有很多。

我們?cè)趗nity中確定一個(gè)相機(jī)的參數(shù)是遠(yuǎn)近裁剪面+FOV。

FOV是水平方向的視角，比如60度就是廣角攝像頭。其實(shí)還應(yīng)該有一個(gè)垂直方向的FOV才能確定一個(gè)錐體。如果水平方向和垂直方向的FOV角度相同，那么遠(yuǎn)近裁剪面就是一個(gè)正方形，視平面也是一個(gè)正方形。視平面是相機(jī)和近裁剪面之間的一個(gè)平面，它是用來(lái)接收投影變換的平面。這個(gè)平面的寬高比一定要和屏幕空間的寬高比一致，否則圖片會(huì)發(fā)生拉伸。unity之所以沒(méi)有讓我們?cè)O(shè)置垂直平面的FOV是因?yàn)閡nity會(huì)自動(dòng)根據(jù)屏幕的寬高比及水平FOV反推出垂直平面的FOV。簡(jiǎn)單的說(shuō)確定一個(gè)相機(jī)需要知道它的遠(yuǎn)近裁剪面，水平FOV以及屏幕的寬高比。

上面這些參數(shù)只是確定了一個(gè)視錐體的形狀，它在任何一個(gè)空間中還需要確定位置和朝向。比如我們求解的六個(gè)平面方程是在世界空間中，那么我們還需要知道相機(jī)在世界空間中的位置及朝向。

我們整理一下目前已知的變量
? ? ? 相機(jī)的位置
? ? ? 相機(jī)的朝向
? ? ? 相機(jī)的FOV
? ? ? 相機(jī)的寬高比
? ? ? 近裁剪距離
? ? ? 遠(yuǎn)裁剪面距離

我們根據(jù)這些信息可以推導(dǎo)出
? ? ? 相機(jī)的位置
? ? ? 相機(jī)的朝向（垂直與遠(yuǎn)近裁剪面中心的向量）
? ? ? 近裁剪面的距離
? ? ? 近裁剪面的高度
? ? ? 近裁剪面的寬度
? ? ? 遠(yuǎn)裁剪面的距離
? ? ? 遠(yuǎn)裁剪面的寬度
? ? ? 遠(yuǎn)裁剪面的高度

有了這些信息我們就可以推導(dǎo)出6個(gè)平面的方程了。

4. 如何判斷一個(gè)點(diǎn)是否在視錐體內(nèi)

這個(gè)很簡(jiǎn)單，只要這個(gè)點(diǎn)在6個(gè)平面中任意一個(gè)平面的外部那么這個(gè)點(diǎn)就在錐體外，反之這個(gè)點(diǎn)在所有平面的內(nèi)部那么它就在視錐體內(nèi)部。

如何判斷一個(gè)點(diǎn)在平面內(nèi)部還是外部，假定我們使用朝向錐體內(nèi)部的法線確定的平面方程。那么平面的前面就是法線的方向也就是錐體內(nèi)部。我們把點(diǎn)帶入平面方程，如果大于零，點(diǎn)在平面的前面，也就是錐體的內(nèi)部。

5. 如何判斷AABB包圍盒是否在視錐體內(nèi)部

我一開始也會(huì)很天真的以為如果AABB的8個(gè)點(diǎn)都在視錐體外部那么這個(gè)包圍體就在視錐體外部了，事實(shí)是這樣嗎？

事實(shí)是打臉的，圖中的黃色方塊，所有點(diǎn)都在外部，但是它和視錐體卻是相交的。

那如果所有點(diǎn)都在同一個(gè)平面的外部就一定在視錐體外部了吧。這個(gè)沒(méi)錯(cuò)，但是反之錯(cuò)了。

事實(shí)再一次打臉，圖中橙色的方塊，雖然所有點(diǎn)沒(méi)有在同一個(gè)面的外部，但是它卻在視錐體的外部。

我們做的是快速判斷，為了追求速度不能做更復(fù)雜的判斷了，二選一選一個(gè)吧，選哪一個(gè)呢？

當(dāng)然是選下面的方案了，上面的方案是錯(cuò)誤的因?yàn)橛行┪锛髅髟谝曞F體中卻不能顯示，這是一種錯(cuò)誤。而下面的方案雖然會(huì)額外傳遞一些無(wú)用的物件到gpu中但它至少是正確的，要先保證正確性才能考慮性能優(yōu)化。

6. 齊次空間裁剪

在投影變換后透視除法之前存在一個(gè)裁剪空間，這個(gè)空間就是齊次裁剪空間，在這個(gè)空間中的視錐體是一個(gè)以相機(jī)為原點(diǎn)，邊長(zhǎng)為1的立方體。如果點(diǎn)在世界空間中的坐標(biāo)為(x,y,z)，將這個(gè)點(diǎn)通過(guò)矩陣乘法變換到齊次裁剪空間中(x',y',z')，那么判斷(x',y',z')這點(diǎn)是否在視錐體內(nèi)會(huì)變得非常簡(jiǎn)單。

滿足上面條件的(x,y,z)就在視錐體內(nèi)。

這個(gè)方法實(shí)現(xiàn)簡(jiǎn)單，但是效率不高，因?yàn)閳?zhí)行一次坐標(biāo)變換需要16次乘法+12次加法。

但是如果使用平面方程只需要3次乘法+2次加法。

雖然可以使用sse指令集進(jìn)行優(yōu)化，但是平面方程計(jì)算也可以使用sse指令優(yōu)化比如方程為：

Ax + By + Cz + D = 0可以看成是向量（A,B,C,D)和向量(x,y,z,1)的點(diǎn)積，如果用sse4指令集一條指令就可以計(jì)算出結(jié)果。

因此把點(diǎn)轉(zhuǎn)換到齊次空間中進(jìn)行判斷實(shí)現(xiàn)簡(jiǎn)單，但是并不高效。

為什么這里要提到齊次裁剪空間呢，因?yàn)槲覀冊(cè)趯憇hader的時(shí)候會(huì)用到這個(gè)變換矩陣，如果代碼中可以拿到這個(gè)矩陣，我們就可以通過(guò)這個(gè)矩陣快速的反推出視錐體6個(gè)裁剪面的方程，具體實(shí)現(xiàn)就不介紹了，這里只是說(shuō)可以優(yōu)化求解平面方程的速度。

7. 每次都需要判斷8個(gè)點(diǎn)么？

有更快的算法，首先我們要找出長(zhǎng)方體的n點(diǎn)和p點(diǎn)，p點(diǎn)就是距離平面最近的頂點(diǎn)，n點(diǎn)就是最遠(yuǎn)對(duì)角線的頂點(diǎn)(距離p最遠(yuǎn)的頂點(diǎn))

如果p在平面外側(cè)那么可以判斷這個(gè)長(zhǎng)方體在平面外側(cè)。

如果p點(diǎn)在平面內(nèi)側(cè)，n點(diǎn)在平面外側(cè)，說(shuō)明它們相交。

如果p點(diǎn)和n點(diǎn)都在內(nèi)側(cè)，則說(shuō)明長(zhǎng)方體在平面內(nèi)側(cè)。

之前我們需要判斷8個(gè)點(diǎn)現(xiàn)在只需要判斷2個(gè)點(diǎn)，多么好的優(yōu)化。

如何求p點(diǎn)和n點(diǎn)如果是AABB包圍盒的話，求法很簡(jiǎn)單

p = (xmin,ymin,zmin) if (normal.x >= 0) p.x = xmax; if (normal.y >=0)) p.y = ymax; if (normal.z >= 0) p.z = zmax:

n = (xmax,ymax,zmax) if (normal.x >= 0) n.x = xmin; if (normal.y >=0)) n.y = ymin; if (normal.z >= 0) n.z = zmin:

這里的normal是平面的法線向量。

8. 還能再快么

這個(gè)算法在Game Programming Gems 5 中提到名字叫做Radar Approach - Testing Points 。它使用的算法和之前的算法完全不一樣，大體思路是這樣的。

首先我們?yōu)橄鄼C(jī)構(gòu)建一個(gè)坐標(biāo)系，這個(gè)坐標(biāo)系的原點(diǎn)就是相機(jī)的位置z軸就是相機(jī)的朝向。假定這個(gè)坐標(biāo)系的基向量為x,y,z。

圖中紅色的點(diǎn)p是被測(cè)試的點(diǎn)，藍(lán)色的點(diǎn)是p在z軸的投影。

v = p - cc

p.z = v ? z

v向量是p點(diǎn)的向量表示，z是單位基向量，所以p點(diǎn)的z坐標(biāo)的值就是v向量和z向量的點(diǎn)積。

如果近裁剪面 < p.z < 遠(yuǎn)裁剪面，那么這個(gè)點(diǎn)在z軸上就在視錐體中了。

同理我們可以求出p.x和p.y，然后拿這兩個(gè)值和一個(gè)平面的長(zhǎng)和寬做對(duì)比，這個(gè)平面就是通過(guò)p點(diǎn)且和視線垂直的平面，假想成和遠(yuǎn)近裁剪面平行的平面。

a為垂直方向的fov，那么h = p.z * 2 * tan(a/2)

-h/2 < pc.y < h/2

(這里的圖是h，如果是unity3d的話可以變成w = p.z * 2 * tan(a/2)那么-w/2

根據(jù)寬高比我們可以求出w = h * ratio;則-w/2 < p.x < w/2

這個(gè)方法和上面np點(diǎn)的算法到底誰(shuí)快，我沒(méi)有測(cè)試過(guò)。等到后面實(shí)現(xiàn)的時(shí)候可以做一下性能測(cè)試，但是測(cè)試的前提是我的demo能加載一個(gè)復(fù)雜的場(chǎng)景。。。

9. 還能再快么

對(duì)于基礎(chǔ)測(cè)試目前我掌握的信息就這些了，如果有大牛還請(qǐng)賜教更快的算法。如果把這些放到gpu計(jì)算是個(gè)不錯(cuò)的想法。

10. 平移旋轉(zhuǎn)一致性測(cè)試

這是邏輯上的優(yōu)化，不是算法層面上的優(yōu)化，我們假定相機(jī)移動(dòng)的很慢，如果一個(gè)AABB被一個(gè)平面拒絕，那么下一幀這個(gè)平面被拒絕的可能性就會(huì)很大，所以我們下次進(jìn)行測(cè)試的時(shí)候可以先從這個(gè)平面進(jìn)行。

11. 八分測(cè)試

這個(gè)算法就是把視錐體切成八部分，然后巴拉巴拉，我總覺(jué)得這個(gè)算法有把簡(jiǎn)單問(wèn)題復(fù)雜化的意思而且它還有限制所以就沒(méi)有仔細(xì)研究，限制如下圖：

使用八分測(cè)試來(lái)檢測(cè)包圍盒，需要包圍盒滿足它的中心到它的頂點(diǎn)距離必須小于視錐體中心到視錐體平面的最小距離。也就是圖中的d2要小于d1，我總覺(jué)得這個(gè)算法有把簡(jiǎn)單問(wèn)題復(fù)雜化的意思。所以就沒(méi)有仔細(xì)研究。