作者：隱士低手

在學習場景管理之前，我們要先學習一下視錐體剔除(VFC)，因為無論你使用什么空間劃分算法，劃分的空間都要進行視錐體剔除，被剔除的空間內部的所有物件都會被拋棄以此來加速渲染或碰撞。這也是場景管理的核心目的。

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

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

2. 位置關系

包圍體和視錐體有三種位置關系
① 包圍體在視錐體外部
② 包圍體在視錐體內部
③ 包圍體部分在視錐體內部（相交）

如果包圍體在視錐體外部，說明這個節點下的全部物件都不在可視范圍內，可以全部丟棄。

如果包圍體在視錐體內部說明全部物件都在視錐體內部，這些物件都會傳遞到GPU中進行渲染。這里有一個問題，如果包圍體在視錐體內部也就說明所有包圍體中的物件都在視錐體內部。物件進入到GPU中被拆解成三角面片，這些圖元在GPU中做齊次空間裁剪，但這些三角面片其實是不需要做齊次空間裁剪的，因為它們的位置關系已經確定了，一定是在視錐體內部。GPU做了重復的工作。以前VFC和三角面片裁剪都在CPU中計算那么可以做標記優化，現在cpu和gpu按照流水線的方式工作，gpu并不知道這些三角面片不需要被裁剪，甚至gpu的設計就是喜歡蠻干并行處理，根本不管你邏輯是否已經被剔除。如果能夠把VFC的工作交給gpu，一方面可以降低cpu的負擔，另一方面gpu也可以避免一些重復性的工作，是不是會更好，這些疑問只有等到學習完Gpu driven rendering pipelines才能給出答案了。

包圍體部分在視錐體內部，這說明包圍體中的物件可能在視錐體中，可能在視錐體外，這時候我們需要做進一步的判斷就是用每一個物件的包圍體進行VFC。如果游戲的性能壓力在cpu端，通常我們不會做進一步的測試。

3. 視錐體的六個面

視錐體的六個面由遠近裁剪面，及上下左右四個面組成。

我們需要將這六個面用平面公式表示出來。

一個平面可以由平面上的三個點確定，也可以由平面法線和平面上的一個點確定。

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

平面方程的確定我簡單說一下思路，具體細節網上有很多。

我們在unity中確定一個相機的參數是遠近裁剪面+FOV。

FOV是水平方向的視角，比如60度就是廣角攝像頭。其實還應該有一個垂直方向的FOV才能確定一個錐體。如果水平方向和垂直方向的FOV角度相同，那么遠近裁剪面就是一個正方形，視平面也是一個正方形。視平面是相機和近裁剪面之間的一個平面，它是用來接收投影變換的平面。這個平面的寬高比一定要和屏幕空間的寬高比一致，否則圖片會發生拉伸。unity之所以沒有讓我們設置垂直平面的FOV是因為unity會自動根據屏幕的寬高比及水平FOV反推出垂直平面的FOV。簡單的說確定一個相機需要知道它的遠近裁剪面，水平FOV以及屏幕的寬高比。

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

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

我們根據這些信息可以推導出
? ? ? 相機的位置
? ? ? 相機的朝向（垂直與遠近裁剪面中心的向量）
? ? ? 近裁剪面的距離
? ? ? 近裁剪面的高度
? ? ? 近裁剪面的寬度
? ? ? 遠裁剪面的距離
? ? ? 遠裁剪面的寬度
? ? ? 遠裁剪面的高度

有了這些信息我們就可以推導出6個平面的方程了。

4. 如何判斷一個點是否在視錐體內

這個很簡單，只要這個點在6個平面中任意一個平面的外部那么這個點就在錐體外，反之這個點在所有平面的內部那么它就在視錐體內部。

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

5. 如何判斷AABB包圍盒是否在視錐體內部

我一開始也會很天真的以為如果AABB的8個點都在視錐體外部那么這個包圍體就在視錐體外部了，事實是這樣嗎？

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

那如果所有點都在同一個平面的外部就一定在視錐體外部了吧。這個沒錯，但是反之錯了。

事實再一次打臉，圖中橙色的方塊，雖然所有點沒有在同一個面的外部，但是它卻在視錐體的外部。

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

當然是選下面的方案了，上面的方案是錯誤的因為有些物件明明在視錐體中卻不能顯示，這是一種錯誤。而下面的方案雖然會額外傳遞一些無用的物件到gpu中但它至少是正確的，要先保證正確性才能考慮性能優化。

6. 齊次空間裁剪

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

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

這個方法實現簡單，但是效率不高，因為執行一次坐標變換需要16次乘法+12次加法。

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

雖然可以使用sse指令集進行優化，但是平面方程計算也可以使用sse指令優化比如方程為：

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

因此把點轉換到齊次空間中進行判斷實現簡單，但是并不高效。

為什么這里要提到齊次裁剪空間呢，因為我們在寫shader的時候會用到這個變換矩陣，如果代碼中可以拿到這個矩陣，我們就可以通過這個矩陣快速的反推出視錐體6個裁剪面的方程，具體實現就不介紹了，這里只是說可以優化求解平面方程的速度。

7. 每次都需要判斷8個點么？

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

如果p在平面外側那么可以判斷這個長方體在平面外側。

如果p點在平面內側，n點在平面外側，說明它們相交。

如果p點和n點都在內側，則說明長方體在平面內側。

之前我們需要判斷8個點現在只需要判斷2個點，多么好的優化。

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

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. 還能再快么

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

首先我們為相機構建一個坐標系，這個坐標系的原點就是相機的位置z軸就是相機的朝向。假定這個坐標系的基向量為x,y,z。

圖中紅色的點p是被測試的點，藍色的點是p在z軸的投影。

v = p - cc

p.z = v ? z

v向量是p點的向量表示，z是單位基向量，所以p點的z坐標的值就是v向量和z向量的點積。

如果近裁剪面 < p.z < 遠裁剪面，那么這個點在z軸上就在視錐體中了。

同理我們可以求出p.x和p.y，然后拿這兩個值和一個平面的長和寬做對比，這個平面就是通過p點且和視線垂直的平面，假想成和遠近裁剪面平行的平面。

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

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

這個方法和上面np點的算法到底誰快，我沒有測試過。等到后面實現的時候可以做一下性能測試，但是測試的前提是我的demo能加載一個復雜的場景。。。

9. 還能再快么

對于基礎測試目前我掌握的信息就這些了，如果有大牛還請賜教更快的算法。如果把這些放到gpu計算是個不錯的想法。

10. 平移旋轉一致性測試

這是邏輯上的優化，不是算法層面上的優化，我們假定相機移動的很慢，如果一個AABB被一個平面拒絕，那么下一幀這個平面被拒絕的可能性就會很大，所以我們下次進行測試的時候可以先從這個平面進行。

11. 八分測試

這個算法就是把視錐體切成八部分，然后巴拉巴拉，我總覺得這個算法有把簡單問題復雜化的意思而且它還有限制所以就沒有仔細研究，限制如下圖：

使用八分測試來檢測包圍盒，需要包圍盒滿足它的中心到它的頂點距離必須小于視錐體中心到視錐體平面的最小距離。也就是圖中的d2要小于d1，我總覺得這個算法有把簡單問題復雜化的意思。所以就沒有仔細研究。