空間劃分及可見性算法

http://blog.csdn.net/cainiao_liu/article/details/5235977

最簡單的流水線可見性處理如下：

對每個物體轉換到世界坐标，然後進行視椎體剔除，其次是背面消隐，最總通過空間剪裁和光栅化期間的圖像空間裁剪得到最終的要繪制的圖像。

在場景很簡單，物體很少的情況，上述方法是可行的。但考慮到現代遊戲的場景複雜程度，如果還采用上面的流水線來提出多邊形，就顯得力不從心了，因為這意味着在每次移動錄影機的時候都要對場景中的所有的物體進行視椎體的剔除及背面消隐，而這根本是不肯能的。

是以，就迫切一種方法，能快速的對大部分場景進行剔除操作。進一步說就是，能根據目前視點位置快速得到目前可見的多邊形集合。

而這就需要對空間進行有效的劃分，即對物體要有一個有效的管理。

常見空間劃分算法有：

BSP、BHV、OCTREE等

常見的可見性算法有：

PVS、OC、portal等

下面先對最重要的BSP算法進行簡單的分析：

BSP樹的原理：使用分割面将空間劃分成凸形子空間構成的二叉樹。

BSP樹的應用：

<1>大規模剔除物體。

<2>碰撞檢測。

<3>可以根據視點的位置很快的确定目前正确的渲染順序（從後到前或從前到後）。（注：現在的遊戲99%都不采用該方法進行渲染）

根據BSP樹的原理，很容易聯想到，如果把多邊形自身作為分割面，則有可能在擁有很多房間或關卡的室内場景遊戲中發揮作用。

具體來說就是以多邊形連結清單作為輸入提供給空間劃分系統來建立BSP樹。

步驟：

<1>選擇第一個多邊形作為分割面。如果連結清單中隻剩一個多邊形或沒有多邊形則算法結束；

<2>判斷下一個多邊形在分割面的前面還是後面，分别添加到front和back連結清單中；

<3>遞歸處理front和back連結清單；

顯示和通路BSP以根據目前視點獲得正确的繪制順序由于應用不多，在此就不在詳細介紹了。

建立BSP樹對時間是不敏感的，因為将通過某種模組化工具生成模型及對應的BSP數并儲存到磁盤中，即建立樹的過程是離線的。

（留個問題以後詳述：什麼工具可以生成BSP，怎麼生成，以什麼格式儲存，在使用時又是如何加載？）

BSP樹的局限性：隻适合半靜态場景，如果多邊形在本超平面内平移，BSP樹是不會改變的，但是如果旋轉多邊形則需要重新生産BSP樹。

下面讨論一下BSP在剔除上的應用：

凸形子空間特性和便利的線性時間複雜度使BSP樹非常适合于大規模剔除操作。

下次主要讨論：

<1>背面消隐

<2>視景體剔除

先來複習一下背面消隐：

      前提為左手坐标系，每個三角形都會以一定順序存儲三個頂點，按照這個順序觀察三角形，如果是順時針方向則該面為三角形的正面，另一個面為三角形的背面。有了該假設，我們就可以計算三角形的面法線了，該法線垂直三角形面并指向三角形的正面。選擇三角形面上的一點為起點，視點為終點構造一個向量，起名叫做視點向量。根據法線向量和視向量的點積的符号很容易計算該面是否是正面朝向的，即是否可以被消隐。如果啟動了背面消隐則三角形隻有一面是可見的，如果要求三角形兩面都可見則應該禁用背面消隐。

      禁用背面消隐：g_pd3dDevice->SetRenderState( D3DRS_CULLMODE, D3DCULL_NONE );

      通過背面消隐可以消除一部分三角形，但是普通的背面消隐存在局限性：

      <1>由于它沒有考慮觀察向量方向，是以可能會産生誤差。比如，通過普通背面消隐判斷為可見的三角形，由于觀察方向向量會導緻三角形實際是不可見的。

      <2>在室内環境中有很多面都是雙面可見的，這時普通的背面消隐就失去了存在的意義。

     是以必須把觀察向量考慮進來，産生一種新的更嚴格的背面消隐算法，具體算法就不在贅述了。

     有了上述的背面消隐算法，結合BSP樹會在視景體剔除中發揮極大作用。因為如果根據背面消隐算法知道目前分割面相對視點是否可見，如果不可見，并且視點在分割面的背面則可以判斷出，在該分割面前面的所有的面都是不可見的。同理，如果視點在分割面的前面，且該分割面是不可見的，則可判斷在該分割面後面的所有的面都是不可見的。這樣就可以迅速的剔除視椎體以外的大量三角形。

     到此為止，簡單的介紹了使用BSP樹對視椎體進行剔除的算法。但是，到目前為止，插入到渲染清單中的的三角形在實際情形中還是有很多是不可見的，也就是備援的。為了剔除這些備援三角形，就出現了PVS算法。

    PVS（潛在可見集），可以手動建立，也可以使用工具建立，可以存儲成數組，也可以存儲成矩陣，也存在很多編碼方式，在此不再贅述。總之是離線建立的。在插入到渲染清單之前在使用PVS來提取備援三角形。

    Portal（入口），是一種實時的PVS，它根據Portal的大小對視椎體進行裁剪，根據新的視椎體來确定PVS。具體怎麼實作以後再介紹。

    明天再介紹，BHV和8叉樹。

前面讨論的BSP和Portal大多數情況會被用于室内場景的管理，更确切的說是在充滿分割面的場景中。在室外場景管理中一般會用到BHV（包圍體層次結構）或八叉樹（num_division = 2的一種特殊的BHV）。

關于如何建立BHV及如何周遊BHV樹利用視椎體進行剔除就不在贅述了。但需要認識到以下幾點：

<1>BHV樹也是需要離線建立的。

<2>層數的限制很自由，至少有以下選擇：

      (1)在節點的大小達到特定值時；

      (2)在達到特定層數時；

      (3)在每個節點包含的多邊形的數目達到特定值時；

<3>8叉樹比較常用，是因為它能很好的模拟3D坐标系有8個象限組成的特性。

最後，讓我們來探讨一下OC（遮掩剔除）：

      在實際應用中，有時候不想使用有關可見性的靜态解決方案，因為遊戲世界可能頻繁變換，PVS、BSP、BHV都不适合。

      可喜的是，我們發現在遊戲中經常會有一些很大的物體，它們會遮掩大部分場景，這就為OC提供了可能性。

      OC技術的步驟如下：

<1>周遊完全位于視椎體内的且可見的所有的物體，選擇n個最近、最大的物體。

<2>将物體投影到螢幕空間，并計算投影區域的面積。從中選擇m個投影面積較大的物體，然後計算每個遮掩物的内接矩形。

<3>将遮掩矩形加入到遮掩體中，然後根據遮掩體對所有多邊形和物體進行檢測，剔除所有被遮掩的物體。

下面是使用OC需要注意的幾點：

<1>可以離線選擇一部分遮掩物，在運作階段根據潛在的遮掩物進行選擇，速度會很快。

<2>一般結合BSP、Portal、8叉樹等場景管理，才能使效率很高。

到此為止，關于空間劃分和可見性算法基本介紹完畢。後面會結合具體引擎，關于該專題進行深入分析，并對以前留下的問題進行闡述。