BSP技術(shù)詳解1

eXtreme3D

翻譯自一篇老外的文章<Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering>,最后一點(diǎn)沒有翻譯完,呵呵,不太好意思!!!!!
BSP技術(shù)作為室內(nèi)引擎渲染的主流技術(shù)雖然已經(jīng)存在多年,但是生命力仍然非常頑強(qiáng),最新的DOOM3,HL2仍然將它作為渲染的主流技術(shù),但是在網(wǎng)上對它介紹文章雖然多卻非常淺顯,大多是使用Q3的BSP文件進(jìn)行渲染,而BSP文件如何產(chǎn)生則介紹非常少,蓋因?yàn)檫@一部分是場景編輯器的工作,而完成一個(gè)這樣的BSP編輯器是非常困難的,需要掌握的知識非常多.下面我將對BSP編輯器這一部分需要用到的BSP知識進(jìn)行一下介紹,這只是一些很初步的知識,如希望了解更多的內(nèi)容,Q2開源代碼中有一個(gè)BSP編輯器的代碼是你研究的重點(diǎn),還有就是HL2泄露代碼中的編輯器代碼,(一個(gè)痛苦的研究過程,可能要花費(fèi)你幾個(gè)月甚至一年的時(shí)間,不過這是值得的,如果你想完成一個(gè)主流的射擊游戲引擎的話,沒有BSP編輯器是不可想象的).

第一節(jié) BSP Trees
BSP Trees英文全稱為Binary Space Partioning trees，二維空間分割樹，簡稱為二叉樹。它于1969年被Shumacker在文章《Study for Applying Computer-Generated Images to Visual Simulation》首次提出，并被ID公司第一次使用到FPS游戲Doom中，Doom的推出獲得了空前的成功，不僅奠定了ID公司在FPS游戲開發(fā)的宗師地位，也使BSP技術(shù)成為室內(nèi)渲染的工業(yè)標(biāo)準(zhǔn)，從BSP產(chǎn)生到現(xiàn)在已經(jīng)有30多年了，其間雖然產(chǎn)生了大量的室內(nèi)渲染的算法，但卻無人能撼動(dòng)它的地位，對于以摩爾定律發(fā)展的計(jì)算機(jī)業(yè)來說這不能不是一個(gè)奇跡。
為什么使用BSP Trees
一個(gè)BSP Trees如同它的名字一樣是一個(gè)層次樹的結(jié)構(gòu)，這個(gè)樹的葉節(jié)點(diǎn)保存了分割室內(nèi)空間所得到的圖元集合。現(xiàn)在隨著硬件加速Z緩沖的出現(xiàn)，我們只需要用很小的代價(jià)就可以對空間中的圖元進(jìn)行排序，但是在90年代初由于硬件的限制，使用BSP的主要原因是因?yàn)樗梢詫臻g中的圖元進(jìn)行排序來保證渲染圖元的順序是按照由后至前進(jìn)行的，換句話說，Z值最小的物體總是最后被渲染。當(dāng)然還有其他的算法可以完成這個(gè)功能，例如著名的畫家算法，但是它與BSP比較起來速度太慢了，這是因?yàn)锽SP通常對圖元排序是預(yù)先計(jì)算好的而不是在運(yùn)行時(shí)進(jìn)行計(jì)算。從某種意義上說BSP技術(shù)實(shí)際上是畫家算法的擴(kuò)展，正如同BSP技術(shù)的原始設(shè)計(jì)一樣，畫家算法也是使用由后至前的順序?qū)鼍爸械奈矬w進(jìn)行渲染。但是畫家算法有以下的缺點(diǎn)：
l 如果一個(gè)物體從另一個(gè)物體中穿過時(shí)它不能被正確的渲染；
l 在每一幀對被渲染的物體進(jìn)行排序是非常困難的，同時(shí)運(yùn)算的代價(jià)非常大；
l 它無法管理循環(huán)覆蓋的情況，如圖所示

          圖1.1
BSP原理
建立BSP Trees的最初想法是獲得一個(gè)圖元的集合，這個(gè)集合是場景的一部分，然后分割這個(gè)圖元集合為更小的子集合，這里必須注意子集合必須為“凸多邊形”。這意味著子集合中任一個(gè)多邊形都位于相同集合中其它多邊形的“前面”。是不是有點(diǎn)難以理解呢，舉一個(gè)例子，如果多邊形A的每一個(gè)頂點(diǎn)都位于由多邊形B所組成的一個(gè)面的正面，那么可以說多邊形A位于多邊形B的“前面”，參考左圖。我們可以想象一下，一個(gè)盒子是由6個(gè)面組成的，如果所有的面都朝向盒子的內(nèi)部，那么我們可以說盒子是一個(gè)“凸多邊形”，如果不是都朝向盒子的內(nèi)部，那么盒子就不是“凸多邊形”。                                               

圖1.2
下面讓我們看一下如何確定一個(gè)圖元集合是否是一個(gè)“凸多邊形”，偽算法如下：
l 函數(shù)CLASSIFY-POINT
l 參數(shù):
l Polygon – 確定一個(gè)3D空間中點(diǎn)相對位置的參考多邊形。
l Point – 待確定的3D空間中的點(diǎn)。
l 返回值:
l 點(diǎn)位于多邊形的哪一邊。
l 功能:
l 確定一個(gè)點(diǎn)位于被多邊形定義的面的哪一邊。
CLASSIFY-POINT (Polygon, Point)
1 Sidevalue = Polygon.Normal * Point
2 if (Sidevalue == Polygon.Distance)
3 then return COINCIDING
4 else if (Sidevalue < Polygon.Distance)
5 then return BEHIND
6 else return INFRONT
l 函數(shù) POLYGON-INFRONT
l 參數(shù):
l Polygon1 – 用來確定其它多邊形是否在其“前面”的多邊形。
l Polygon2 – 檢測是否在第一個(gè)多邊形“前面”的多邊形。
l 返回值:
l 第二個(gè)多邊形是否在第一個(gè)多邊形的“前面”。
l 功能:
l 檢測第二個(gè)多邊形的每一個(gè)頂點(diǎn)是否在第一個(gè)多邊形的“前面”。
POLYGON-INFRONT (Polygon1, Polygon2)
1 for each point p in Polygon2
2 if (CLASSIFY-POINT (Polygon1, p) <> INFRONT)
3 then return false
4 return true
l 函數(shù) IS-CONVEX-SET
l 參數(shù):
l PolygonSet – 用來檢測是否為“凸多邊形”的圖元集合。
l 返回值:
l 集合是否為“凸多邊形”。
l 功能:
l 相對于集合中的其它多邊形檢查每一個(gè)多邊形，看是否位于其它多邊形的“前面”，如果有任意兩個(gè)多邊形不滿足這個(gè)規(guī)則，那么這個(gè)集合不為“凸多邊形”。
IS-CONVEX-SET (PolygonSet)
1 for i = 0 to PolygonSet.Length ()
2 for j = 0 to PolygonSet.Length ()
3 if(i != j && not POLYGON-INFRONT(PolygonSet, PolygonSet[j]))
4 then return false
5 return true

在函數(shù)POLYGON-INFRONT中并沒有進(jìn)行對稱的比較，這意味著如果多邊形A位于多邊形B的“前面”你并不能想當(dāng)然的認(rèn)為多邊形B一定位于多邊形B的“前面”。下面的例子簡單的顯示了這一點(diǎn)。
     
                圖1.3
在圖1.3中我們可以看到多邊形1位于多邊形2的“前面”，這是因?yàn)轫旤c(diǎn)p3、p4位于多邊形2的“前面”，而多邊形2卻沒有位于多邊形1的“前面”，因?yàn)轫旤c(diǎn)p2位于多邊形1的“后面”。
對于一個(gè)BSP層次樹來說可以用下面結(jié)構(gòu)來定義：
class BSPTree
{
BSPTreeNode RootNode // 樹的根節(jié)點(diǎn)
}
class BSPTreeNode
{
BSPTree Tree // 接點(diǎn)所屬的層次樹
BSPTreePolygon Divider // 位于兩個(gè)子樹之間的多邊形
BSPTreeNode *RightChild // 節(jié)點(diǎn)的右子樹
BSPTreeNode *LeftChild // 節(jié)點(diǎn)的左子樹
BSPTreePolygon PolygonSet[] // 節(jié)點(diǎn)中的多邊形集合
}
class BSPTreePolygon
{
3DVector Point1 // 多邊形的頂點(diǎn)1
3DVector Point3 // 多邊形的頂點(diǎn)2
3DVector Point3 // 多邊形的頂點(diǎn)3
}
現(xiàn)在你可以看見每一個(gè)多邊形由3個(gè)頂點(diǎn)來定義，這是因?yàn)橛布铀倏ㄊ褂萌切蝸韺Χ噙呅芜M(jìn)行渲染。將多邊形集合分割為更小的子集合有很多方法，例如你可以任意選擇空間中的一個(gè)面然后用它來對空間中的多邊形進(jìn)行分割，把位于分割面正面的多邊形保存到右子樹中而位于反面的多邊形保存到左子樹中。使用這個(gè)方法的缺點(diǎn)非常明顯，那就是如果想選擇一個(gè)將空間中的多邊形分割為兩個(gè)相等的子集合的面非常困難，這是因?yàn)樵趫鼍爸杏袩o數(shù)個(gè)可選擇的面。如何在集合中選擇一個(gè)最佳的分割面呢？下面我將對這個(gè)問題給出一個(gè)比較適當(dāng)?shù)慕鉀Q方案。
我們現(xiàn)在已經(jīng)有了一個(gè)函數(shù)POLYGON-INFRONT，它的功能是確定一個(gè)多邊形是否位于其它多邊形的正面。現(xiàn)在我們要做的是修改這個(gè)函數(shù)，使它也能夠確定一個(gè)多邊形是否橫跨過其它多邊形定義的分割面。算法如下：
l 函數(shù) CALCULATE-SIDE
l 參數(shù) :
l Polygon1 – 確定其它多邊形相對位置的多邊形。
l Polygon2 – 確定相對位置的多邊形。
l 返回值:
l 多邊形2位于多邊形1的哪一邊
l 功能:
l 通過第一個(gè)多邊形對第二個(gè)多邊形上的每一個(gè)頂點(diǎn)進(jìn)行檢測。如果所有的頂點(diǎn)位于第二個(gè)多邊形的正面，那么多邊形2被認(rèn)為位于多邊形1的“前面”。如果第二個(gè)多邊形的所有頂點(diǎn)都位于第一個(gè)多邊形的反面，那么多邊形2被認(rèn)為位于多邊形1的“后面”。如果第二個(gè)多邊形的所有頂點(diǎn)位于第一個(gè)多邊形之上，那么多邊形2被認(rèn)為位于多邊形1的內(nèi)部。最后一種可能是所有的頂點(diǎn)即位于正面有位于反面，那么多邊形2被認(rèn)為橫跨過多邊形1。
CALCULATE-SIDE (Polygon1, Polygon2)
1 NumPositive = 0, NumNegative = 0
2 for each point p in Polygon2
3 if (CLASSIFY-POINT (Polygon1, p) = INFRONT)
4 then NumPositive = NumPositive + 1
5 if (CLASSIFY-POINT (Polygon1, p) = BEHIND)
6 then NumNegative = NumNegative + 1
7 if (NumPositive > 0 && NumNegative = 0)
8 then return INFRONT
9 else if(NumPositive = 0 && NumNegative > 0)
10 then return BEHIND
11 else if(NumPositive = 0 && NumNegative = 0)
12 then return COINCIDING
13 else return SPANNING
上面的算法也給我們解答了一個(gè)問題，當(dāng)一個(gè)多邊形橫跨過分割面時(shí)如何進(jìn)行處理，上面的算法中將多邊形分割為兩個(gè)多邊形，這樣就解決了畫家算法中的兩個(gè)問題：循環(huán)覆蓋和多邊形相交。下面的圖形顯示了多邊形如何進(jìn)行分割的。
           

圖1.4
如圖1.4所示，多邊形1為分割面，而多邊形2橫跨過多邊形1，如圖右邊所示，多邊形被分割為2、3兩部分，多邊形2位于分割面的“前面”而多邊形3位于分割面的“后面”。
當(dāng)建立一個(gè)BSP樹時(shí)，首先需要確定的問題是如何保證二叉樹的平衡，這意味著對于每一個(gè)葉節(jié)點(diǎn)的分割深度而言不能有太大的差異，同時(shí)每一個(gè)節(jié)點(diǎn)的左、右子樹需要限制分割的次數(shù)。這是因?yàn)槊恳淮蔚姆指疃紩?huì)產(chǎn)生新的多邊形，如果在建立BSP樹時(shí)產(chǎn)生太多的多邊形的話，在圖形加速卡對場景渲染時(shí)會(huì)加重渲染器的負(fù)擔(dān)，從而降低幀速。同時(shí)一個(gè)不平衡的二叉樹在進(jìn)行遍歷時(shí)會(huì)耗費(fèi)許多無謂的時(shí)間。因此我們需要確定一個(gè)合理的分割次數(shù)以便于獲得一個(gè)較為平衡的二叉樹，同時(shí)可以減少新多邊形的產(chǎn)生。下面的代碼顯示了如何通過循環(huán)多邊形集合來獲得最佳的分割多邊形。
l 函數(shù) CHOOSE-DIVIDING-POLYGON
l 參數(shù):
l PolygonSet – 用于查找最佳分割面的多邊形集合。
l 返回值:
l 最佳的分割多邊形。
l 功能:
l 對指定的多邊形集合進(jìn)行搜索，返回將其分割為最佳子集合的多邊形。如果指定的集合是一個(gè)“凸多邊形”則返回。
CHOOSE-DIVIDING-POLYGON (PolygonSet)
1 if (IS-CONVEX-SET (PolygonSet))
2 then return NOPOLYGON
3 MinRelation = MINIMUMRELATION
4 BestPolygon = NOPOLYGON
5 LeastSplits = INFINITY
6 BestRelation = 0
l 循環(huán)查找集合的最佳分割面。
7 while(BestPolygon = NOPOLYGON)
8 for each 多邊形P1 in PolygonSet
9 if (多邊形P1在二叉樹建立過程中沒有作為分割面)
l 計(jì)算被當(dāng)前多邊形定義的分割面的正面、反面和橫跨過分割面的多邊形的數(shù)量。
10 NumPositive = 0, NumNegative = 0, NumSpanning = 0
11 for each 多邊形P2 in PolygonSet except P1
12 value = CALCULATE-SIDE(P1, P2)
13 if(value = INFRONT)
14 NumPositive = NumPositive + 1
15 else if(value = BEHIND)
16 NumNegative = NumNegative + 1
17 else if(value = SPANNING)
18 NumSpanning = NumSpanning + 1
l 計(jì)算被當(dāng)前多邊形分割的兩個(gè)子集合的多邊形數(shù)量的比值。
19 if (NumPositive < NumNegative)
20 Relation = NumPositive / NumNegative
21 else
22 Relation = NumNegative / NumPositive
l 比較由當(dāng)前多邊形獲得的結(jié)果。如果當(dāng)前多邊形分割了較少的多邊形同時(shí)分割后的子集合比值可以接受的話，那么保存當(dāng)前的多邊形為新的候選分割面。
l 如果當(dāng)前多邊形和最佳分割面一樣分割了相同數(shù)量的多邊形而分割后的子集合比值更大的話，將當(dāng)前多邊形作為新的候選分割面。
23 if (Relation > MinRelation &&
(NumSpanning < LeastSplits ||
(NumSpanning = LeastSplits &&
Relation > BestRelation))
24 BestPolygon = P1
25 LeastSplits = NumSpanning
26 BestRelation = Relation
l 通過除以一個(gè)預(yù)先定義的常量來減少可接受的最小比值。
27 MinRelation = MinRelation / MINRELATIONSCALE
28 return BestPolygon
算法分析
對于上面的函數(shù)來說，根據(jù)場景數(shù)據(jù)大小的不同它可能花費(fèi)很長一段時(shí)間。常量MINRELATIONSCALE用來確定在每次循環(huán)時(shí)所分割的子集合多邊形數(shù)量的比值每次減少多少，為什么要使用這個(gè)常量呢，考慮一下，對于給定的MinRelation如果我們找不到最佳的分割面，通過除以這個(gè)常量將比值減少來重新進(jìn)行循環(huán)查找，這樣可以防止死循環(huán)的出現(xiàn)，因此當(dāng)這個(gè)比值足夠小時(shí)我們必定可以獲得可接受的最佳結(jié)果。最壞的事情是我們有一個(gè)包含N個(gè)多邊形的非“凸”集合，分割多邊形將集合分割為一個(gè)包含N-1個(gè)多邊形的部分和一個(gè)包含1個(gè)多邊形的部分。這個(gè)結(jié)果只有在最小比值小于1/(n-1)才是可以接受的（參考算法的19-23行）。這意味著MinRelation /MINRELATIONSCALEi < 1/(n-1)，這里i是循環(huán)重復(fù)的次數(shù)。讓我們假設(shè)MinRelation的初始化值為1，由于比值永遠(yuǎn)為0-1之間的值因此這是最可能的值（參考算法的19-22行）。我們有
1 / MINRELATIONSCALEi < 1/(n-1)
1 < MINRELATIONSCALEi/(n-1)
(n-1) < MINRELATIONSCALEi
logMINRELATIONSCALE (n-1) < i
這里的i沒有上邊界，但是因?yàn)閕非常接近于logMINRELATIONSCALE (n-1)，我們可以簡單的假設(shè)兩者是相等的。另外我們也假設(shè)MINRELATIONSCALE永遠(yuǎn)大于或等于2，因此我們可以有
logMINRELATIONSCALE (n-1) = i
MINRELATIONSCALE >= 2
i = logMINRELATIONSCALE (n-1) < lg(n-1) = O(lg n)
在循環(huán)的內(nèi)部，對多邊形的集合需要重復(fù)進(jìn)行兩次循環(huán)，因此對我們來說最壞的情況下這個(gè)算法的復(fù)雜度為O(n2lg n)，而通常情況下這個(gè)算法的復(fù)雜度接近于O(n2)。
在函數(shù)CHOOSE-DIVIDING-POLYGON的循環(huán)中看起來如果不發(fā)生什么事情的話好象永遠(yuǎn)不會(huì)停止，但是這不會(huì)發(fā)生，這是因?yàn)槿绻噙呅渭蠟榉?#8220;凸”集合的話總能找到一個(gè)多邊形來把集合分割為兩個(gè)子集合。CHOOSE-DIVIDING-POLYGON函數(shù)總是選擇分割集合的多邊形數(shù)量最少的多邊形，為了防止選擇并不分割集合的多邊形，分割后的子集合的多邊形數(shù)量之比必須大于預(yù)先定義的值。為了更好的理解我上面所講解的內(nèi)容，下面我將舉一個(gè)例子來說明如何選擇一個(gè)多邊形對一個(gè)很少數(shù)量多邊形的集合進(jìn)行分割。

      圖1.5
在上面的例子中無論你選擇多邊形1、6、7還是多邊形8進(jìn)行渲染時(shí)都不會(huì)分割任何其它的多邊形，換句話說也就是所有的其它多邊形都位于這些多邊形的“正面”。
關(guān)于分割時(shí)選擇產(chǎn)生多邊形最少的分割面另外一個(gè)不太好的原因是大多數(shù)時(shí)候它所產(chǎn)生的層次樹通常是不平衡的，而一個(gè)平衡的層次樹在運(yùn)行的時(shí)候通常比不平衡的層次樹性能更好。
當(dāng)獲得最佳的分割面后伴隨著必然產(chǎn)生一些被分割的多邊形，如何對被分割的多邊形進(jìn)行處理呢，這里有兩個(gè)方法：
1. 建立一個(gè)帶葉節(jié)點(diǎn)的二叉樹，這意味著每一個(gè)多邊形將被放在葉節(jié)點(diǎn)中，因此每一個(gè)被分割的多邊形也將被分開放在二叉樹的一邊。
2. 另外一個(gè)方法是將被分割的多邊形保存到公共節(jié)點(diǎn)中，對每一個(gè)子樹重復(fù)這個(gè)過程直到每一個(gè)葉節(jié)點(diǎn)都包含了一個(gè)“凸”多邊形集合為止。
產(chǎn)生帶葉節(jié)點(diǎn)的BSP樹的算法如下：
l 函數(shù)GENERATE-BSP-TREE
l 參數(shù):
l Node – 欲建立的類型為BSPTreeNode的子樹。
l PolygonSet – 建立BSP-tree的多邊形集合。
l 返回值:
l 保存到輸入的父節(jié)點(diǎn)中的BSP-tree。
l 功能:
l 對一個(gè)多邊形集合產(chǎn)生一個(gè)BSP-tree。
GENERATE-BSP-TREE (Node, PolygonSet)
1 if (IS-CONVEX-SET (PolygonSet))
2 Tree = BSPTreeNode (PolygonSet)
3 Divider = CHOOSE-DIVIDING-POLYGON (PolygonSet)
4 PositiveSet = {}
5 NegativeSet = {}
6 for each polygon P1 in PolygonSet
7 value = CALCULATE-SIDE (Divider, P1)
8 if(value = INFRONT)
9 PositiveSet = PositiveSet U P1
10 else if (value = BEHIND)
11 NegativeSet = NegativeSet U P1
12 else if (value = SPANNING)
13 Split_Polygon10 (P1, Divider, Front, Back)
14 PositiveSet = PositiveSet U Front
15 NegativeSet = NegativeSet U Back
16 GENERATE-BSP-TREE (Tree.RightChild, PositiveSet)
17 GENERATE-BSP-TREE (Tree.LeftChild, NegativeSet)
算法分析
函數(shù)CHOOSE-DIVIDING-POLYGON的時(shí)間復(fù)雜度為O(n2 lg n)，除非出現(xiàn)遞歸調(diào)用否則它將控制其它的函數(shù)，如果我們假設(shè)對多邊形集合的分割是比較公平的話，那么我們可以通過公式來對函數(shù)GENERATE-BSP-TREE的復(fù)雜度進(jìn)行表達(dá)：
T(n) = 2T(n/2) + O(n2 lg n)
通過公式我們可以知道這個(gè)函數(shù)的復(fù)雜度為Q (n2 lg n)。這里n為輸入的多邊形集合的多邊形數(shù)量。
下面我要用一個(gè)例子來演示如何產(chǎn)生一個(gè)BSP-tree。下面的結(jié)構(gòu)是一個(gè)多邊形的原始集合，為了表示方便對每一個(gè)多邊形都進(jìn)行了編號，這個(gè)多邊形集合將被分割為一個(gè)BSP-tree。

            圖1.6
為了能夠運(yùn)行這個(gè)算法我們必須對常量MINIMUMRELATION和MINRELATIONSCALE進(jìn)行賦值，在實(shí)際運(yùn)行中我們發(fā)現(xiàn)當(dāng)MINIMUMRELATION=0.8而MINRELATIONSCALE=2時(shí)可以獲得比較好的結(jié)果。但是你也可以對這些數(shù)值進(jìn)行試驗(yàn)來比較一下，通常當(dāng)常數(shù)MINIMUMRELATION比較大時(shí)獲得的層次樹會(huì)比較平衡但同時(shí)分割產(chǎn)生的多邊形也會(huì)大量增加。在上圖顯示的多邊形集合并不是一個(gè)“凸”的，因此首先我們需要選擇一個(gè)合適的分割面。在快速的對上面的結(jié)構(gòu)進(jìn)行一下瀏覽后我們可以知道多邊形（1、2、6、22、28）不能被用來作為分割面，這是因?yàn)樗鼈兌x了包含所有多邊形集合的外形。但是其它的多邊形都可以作為候選的分割面。分割產(chǎn)生的多邊形最少同時(shí)分割為兩個(gè)子集合的多邊形數(shù)目之比為最佳的多邊形是16與17，它們位于同一條直線上同時(shí)并不會(huì)分割任何的多邊形。而分割后的子集合的多邊形數(shù)目也是一樣的，都是“正面”為13而“反面”為15。讓我們選擇多邊形16作為分割面，那么分割后的的結(jié)構(gòu)如下：
                       

圖1.7
現(xiàn)在從圖1.7我們可以看到無論是左子樹還是右子樹都沒有包含“凸”多邊形集合，因此需要對兩個(gè)子樹繼續(xù)進(jìn)行分割。
在左子樹中多邊形1、2、6、7作為多邊形集合的“凸邊”不能用做分割面，而多邊形4、10在同一條直線上同時(shí)沒有分割任何多邊形，而分割后的多邊形子集合：“正面”為8而“反面”為7非常的平衡，我們選擇多邊形4為分割面。
在右子樹中多邊形16、17、22、23、28不能作為分割面，而多邊形18、19、26、27雖然沒有分割任何多邊形但是分割后的多邊形子集合：“正面”為11而“反面”為3，3/11這個(gè)比值小于最小比值0.5因此我們需要尋找其它更適合的多邊形。多邊形20、21、24、25都只分割了一個(gè)多邊形，但是多邊形21看起來分割后的結(jié)果更合理，在分割過多邊形22后多邊形子集合的結(jié)果為：“正面”為8而“反面”為6。
下圖顯示了操作后的結(jié)果：

                圖1.8
在圖中每一個(gè)子集合還不是一個(gè)“凸”集合，因此需要繼續(xù)進(jìn)行分割，按照上面的法則對圖1.8所示的結(jié)構(gòu)進(jìn)行分割后，結(jié)果如下：
                     

圖1.9
上圖顯示了最后的結(jié)果，這可能不是最優(yōu)的結(jié)果但是我們對它進(jìn)行處理所花費(fèi)的時(shí)間并不太長。
渲染BSP
現(xiàn)在我們已經(jīng)建立好一個(gè)BSP樹了，可以很容易對樹中的多邊形進(jìn)行正確的渲染，而不會(huì)產(chǎn)生任何錯(cuò)誤。下面的算法描述了如何對它進(jìn)行渲染，這里我們假設(shè)函數(shù)IS-LEAF的功能為給定一個(gè)BSP節(jié)點(diǎn)如果為葉節(jié)點(diǎn)返回真否則返回假。
函數(shù)DRAW-BSP-TREE
參數(shù):
l Node – 被渲染的節(jié)點(diǎn)。
l Position – 攝象機(jī)的位置。
l 返回值:
l None
l 功能:
l 渲染包含在節(jié)點(diǎn)及其子樹中的多邊形。
DRAW-BSP-TREE (Node, Position)
1 if (IS-LEAF(Node))
2 DRAW-POLYGONS (Node.PolygonSet)
3 return

l 計(jì)算攝象機(jī)包含在哪一個(gè)子樹中。
4 Side = CLASSIFY-POINT (Node.Divider, Position)
l 如果攝象機(jī)包含在右子樹中先渲染右子樹再渲染左子樹。
5 if (Side = INFRONT || Side = COINCIDING)
6 DRAW-BSP-TREE (Node.RightChild, Position)
7 DRAW-BSP-TREE (Node.LeftChild, Position)

l 否則先渲染左子樹。
8 else if(value = BEHIND)
9 DRAW-BSP-TREE (Node.LeftChild, Position)
10 DRAW-BSP-TREE (Node.RightChild, Position)
用這個(gè)方法進(jìn)行渲染并沒有減少渲染到屏幕上的多邊形數(shù)量，由于一個(gè)場景可能包含成百上千個(gè)多邊形因此這個(gè)方法并不是很好的解決方案。通常情況下有大量的節(jié)點(diǎn)和多邊形并沒有處于攝象機(jī)的視野范圍之內(nèi)，它們并不需要被渲染到屏幕上，如何查找這些不可見的節(jié)點(diǎn)和多邊形防止它們渲染到屏幕上呢，隱藏面剔除就是為了解決這個(gè)問題而提出一項(xiàng)技術(shù)，在下一節(jié)中我們將對這項(xiàng)技術(shù)進(jìn)行詳細(xì)的闡述。
BSP技術(shù)詳解2

eXtreme3D

第二節(jié) 隱藏面剔除
    對不可見物體進(jìn)行剔除是游戲行業(yè)為了滿足提高畫面渲染速度的要求而產(chǎn)生的一項(xiàng)技術(shù)，就是在硬件加速技術(shù)飛躍發(fā)展的今天，雖然現(xiàn)在已經(jīng)可以完成許多在過去被認(rèn)為是不可能實(shí)現(xiàn)的工作，但是對于隱藏面進(jìn)行剔除仍是加速圖形渲染的一項(xiàng)重要技術(shù)。通常當(dāng)一個(gè)游戲運(yùn)行的時(shí)候，它最少需要以每秒30幀的速度運(yùn)行。在幾年前這意味著如果每一幀你渲染的帶紋理的多邊形數(shù)量超過5000個(gè)就被認(rèn)為是不可接受的，而現(xiàn)在幾乎所有的商業(yè)顯卡每一秒都可以渲染幾千萬個(gè)多邊形。可是現(xiàn)在仍然需要使用隱藏面剔除這項(xiàng)技術(shù)，這是為什么呢？顯而易見，對不可見物體渲染以后將會(huì)被可見物體遮擋住，這樣做無謂的浪費(fèi)了顯卡的帶寬，但是同時(shí)它也增加了場景的細(xì)節(jié)，使游戲畫面看起來更加吸引人。現(xiàn)在的問題是多大程度上來剔除隱藏的多邊形，象view frustum culling和portal渲染這樣的技術(shù)來剔除一個(gè)不可見多邊形是非常耗費(fèi)時(shí)間的，用來去做這些計(jì)算的CPU時(shí)間可以用來完成其它諸如AI或碰撞檢測這樣的工作，因此開發(fā)一個(gè)隱藏面剔除算法必須注意到這一點(diǎn)。對于現(xiàn)在的游戲來說幾乎沒有一個(gè)是將每一個(gè)隱藏的多邊形都進(jìn)行剔除，而是剔除一個(gè)多邊形的集合如一個(gè)節(jié)點(diǎn)或一個(gè)物體等等。對于一個(gè)單獨(dú)的多邊形它并不進(jìn)行剔除，因此一個(gè)正確的隱藏面剔除方案是允許一定的重復(fù)渲染來適當(dāng)?shù)臏p少計(jì)算量。
    當(dāng)建立一個(gè)FPS游戲時(shí)進(jìn)行隱藏面剔除最通常的方法是使用portal渲染。這項(xiàng)技術(shù)可以非常充分的利用BSP的優(yōu)點(diǎn)，但是請注意portal技術(shù)并不僅僅只能用于BSP中。Portal技術(shù)還可以用來產(chǎn)生一些特效如鏡子和監(jiān)視器等等。
Portal渲染
在這里我將介紹一下portal技術(shù)的原理，通常對于一個(gè)室內(nèi)場景來說它可以被描述為由一個(gè)個(gè)“洞口”相互連接的“房間”組成，這里“洞口”被稱為portal而“房間”被稱為sector，通常sector被定義為一個(gè)“凸”的“閉合”的多邊形集合，定義中的“凸”閱讀過前面的內(nèi)容你應(yīng)當(dāng)已經(jīng)能很好的理解了，而“閉合”是什么意思呢？它意味著在sector內(nèi)部任意連接兩個(gè)頂點(diǎn)做一條線段，這條線段不會(huì)和其它的多邊形相交。換句話說如果你想在sector內(nèi)部任意畫一條線段通到sector的外部必定與組成sector的多邊形相交。這也意味著連接每一個(gè)sector的“洞口”必須被一個(gè)組成portal的多邊形所填充，而對于放置portal多邊形來說你既可以手工放置也可以由程序自動(dòng)產(chǎn)生，在我講解這項(xiàng)技術(shù)之前我必須提醒一下，由于硬件加速Z緩沖的出現(xiàn)對sector必須為“凸”的限制已經(jīng)消除，因此有許多游戲引擎已經(jīng)不再遵守這個(gè)標(biāo)準(zhǔn)，但是在這里我還是要對過去的方法進(jìn)行一下介紹。
一個(gè)portal引擎的基本方法是當(dāng)你通過一個(gè)指定觀察位置的可視平截體（view frustum）進(jìn)行渲染時(shí)，如果一個(gè)portal出現(xiàn)在可視范圍內(nèi)，那么portal將對可視平截體進(jìn)行剪切，這樣與其相連的sector將會(huì)通過一個(gè)觀察位置相同但已經(jīng)改變過的可視平截體進(jìn)行渲染。這是一個(gè)非常簡單而且非常適合進(jìn)行遞歸調(diào)用的方法，由于可視平截體被portal進(jìn)行了精確的限制，因此被隱藏的物體可以很簡單進(jìn)行剔除。下面的例圖顯示了一個(gè)portal引擎中的可視平截體是如何被剪切的。
               
圖6.10
在圖6.10中觀察者的位置位于V，而初始的可視平截體為F1，當(dāng)它通過一個(gè)portal多邊形P1后被P1剪切產(chǎn)生新的可視平截體F2，接著當(dāng)它通過portal多邊形P2、P3后F2被剪切為F3、F4，而F3通過P4后被剪切為F5而F4被剪切為F6。觀察這個(gè)過程我們可以發(fā)現(xiàn)portal技術(shù)非常適合進(jìn)行遞歸調(diào)用。
接著需要考慮的是如何對物體進(jìn)行揀選剔除，通常對于所有的3D引擎來說都需要通過一系列步驟來加速這個(gè)處理過程，回憶一下前面講解的內(nèi)容，這個(gè)過程首先要計(jì)算出物體的“最大包圍球”或是“最大包圍盒”，它是包含了物體所有頂點(diǎn)的最小包圍體，接著用包圍體來和“可視平截體”每一個(gè)剪切面進(jìn)行碰撞檢測，如果包圍體位于每一個(gè)剪切面的“反面”那么物體將不會(huì)進(jìn)行渲染，下圖顯示了這個(gè)過程：
       
圖6.11
圖中物體1位于右剪切面的“正面”但位于左剪切面的“反面”因此它將不會(huì)被渲染，而物體2不僅位于左剪切面的“正面”而且有一部分位于右剪切面的“正面”因此將會(huì)被渲染出來。
Portal技術(shù)最初的想法是通過剪切多邊形來保證只有物體可見的部分被渲染出來，也就是無效渲染的多邊形數(shù)量為0。但是現(xiàn)在這種想法被認(rèn)為不是很理想，因?yàn)樗鼰o謂的浪費(fèi)了處理時(shí)間。但是由于一個(gè)多邊形在遞歸循環(huán)過程中將被遍歷多次因此我們需要知道在渲染場景時(shí)它是否已經(jīng)被渲染過，一個(gè)較好的方法是使用一個(gè)幀數(shù)來標(biāo)識這個(gè)多邊形，這樣可以很容易的來描述這個(gè)多邊形在上一幀是否被渲染過。再看一下圖6.10中最右邊的墻，它同時(shí)通過F5和F6來進(jìn)行渲染，通過對它進(jìn)行標(biāo)識我們可以知道它是否被渲染過，否則就會(huì)產(chǎn)生Z緩沖錯(cuò)誤。
為了便于在portal引擎中進(jìn)行渲染我們需要對“可視平截體”進(jìn)行一下定義，一個(gè)“可視平截體”是一個(gè)保存了多個(gè)剪切面的結(jié)構(gòu)，每一個(gè)剪切面的法線都將指向“可視平截體”的內(nèi)部，因此在它內(nèi)部將產(chǎn)生一個(gè)閉合的錐體。下面的算法顯示了如何計(jì)算一個(gè)多邊形是否包含在“可視平截體”的內(nèi)部。在這個(gè)算法中我們使用了一個(gè)函數(shù)CLASSIFY-POINT，它使用一個(gè)剪切面和一個(gè)點(diǎn)作為輸入?yún)?shù)。
l 函數(shù)INSIDE-FRUSTUM
l 參數(shù):
l Frustum – 用于檢測多邊形是否位于其中的“可視平截體”。
l Polygon – 用于檢測的多邊形。
l 返回值:
l 多邊形是否位于“可視平截體”的內(nèi)部。
l 功能:
l 使用“可視平截體”的每一個(gè)剪切面來對多邊形的每一個(gè)頂點(diǎn)進(jìn)行檢測，如果所有的頂點(diǎn)都位于所有剪切面的“正面”，那么多邊形處于“可視平截體”的內(nèi)部。

INSIDE-FRUSTUM (Frustum, Polygon)
1 for each point Pt in Polygon
2 Inside = true
3 for each plane Pl in Frustum
4 if (CLASSIFY-POINT (Pl, Pt) <> INFRONT)
5 Inside f false
6 if (Inside)
7 return true
8 return false
在一個(gè)portal引擎中它的主渲染函數(shù)可以簡單的用下面的方法來實(shí)現(xiàn)。
函數(shù)RENDER-PORTAL-ENGINE
參數(shù):
Sector – 觀察者所處的sector。
ViewFrustum – 當(dāng)前的“可視平截體”。
返回值:
None
功能:
渲染portal引擎中的多邊形，場景被描述為由多個(gè)portal連接的sectors所組成。
RENDER-PORTAL-ENGINE (Sector, ViewFrustum)
1 for each polygon P1 in Sector
2 if (P1是一個(gè)portal and INSIDE-FRUSTUM (ViewFrustum, P1))
3 NewFrustum = CLIP-FRUSTUM (ViewFrustum, P1)
4 NewSector = 獲得由當(dāng)前sector通過portal P1相連接的sector
5 RENDER-PORTAL-ENGINE (NewSector, NewFrustum)
6 else if (P1任然沒有被渲染)
7 draw P1
8 return
如何放置portal
正如我前面提到的在一個(gè)portal引擎中最大的問題就是如何放置portal，如果手工來放置它的話非常花費(fèi)時(shí)間，同時(shí)要求地圖的設(shè)計(jì)者有熟練的技巧。因此一個(gè)良好的自動(dòng)放置portal的算法非常有必要，在這里我將要介紹一下關(guān)于這方面的幾個(gè)解決方案，這些方案都使用了BSP。
我介紹的第一個(gè)解決方案是由瑞典DICE公司的Andreas Brinck提出的，它的原理非常簡單，觀察一下一個(gè)完整的BSP層次樹，可以發(fā)現(xiàn)這樣一個(gè)現(xiàn)象，對于每一個(gè)portal來說它必定與BSP層次樹中由分割多邊形定義的分割面位置相同，因此在相同的位置上我們可以在分割面之外建立一個(gè)portal多邊形，portal多邊形被初始化為一個(gè)矩形，這個(gè)矩形的大小將超過portal所處的BSP節(jié)點(diǎn)的“最大包圍盒”的大小，接著將portal多邊形放入包含它的節(jié)點(diǎn)所位于的子樹中，當(dāng)節(jié)點(diǎn)不是葉節(jié)點(diǎn)時(shí)，那么portal將繼續(xù)被傳送到節(jié)點(diǎn)的子樹中，這樣子節(jié)點(diǎn)中的分割面將對它進(jìn)行分割，而當(dāng)包含它的節(jié)點(diǎn)為葉節(jié)點(diǎn)時(shí)，它也會(huì)被節(jié)點(diǎn)中的多邊形進(jìn)行剪切，因?yàn)閜ortal初始化的大小超過了節(jié)點(diǎn)的范圍。當(dāng)portal被分割后，被分割的兩個(gè)部分會(huì)繼續(xù)傳送到最頂層的節(jié)點(diǎn)重復(fù)這個(gè)過程，而當(dāng)portal不需要進(jìn)行分割時(shí)，根據(jù)它所處于分割面的位置來放置到相應(yīng)的子節(jié)點(diǎn)中，如果位于分割面的“正面”它將被放置在右子樹中，而當(dāng)它位于分割面的“反面”將被放置于左子樹中。如果portal正好位于分割面之上它將同時(shí)放在左右子樹中。
為了方便方便將所有的portal放置到BSP中我們需要定義如何對一個(gè)多邊形進(jìn)行分割，為了方便使用我們假設(shè)完成這個(gè)功能的函數(shù)為INTERSECTION-POINT，它將返回一個(gè)面與一個(gè)線段的交點(diǎn)。
l 函數(shù)CLIP-POLYGON
l 參數(shù):
l Clipper – 去分割其它多邊形的多邊形或面。
l Polygon – 被分割的多邊形。
l 返回值:
l 被分割后的兩個(gè)部分。
l 功能:
l 由指定的分割面來分割多邊形。如果多邊形沒有被分割將會(huì)返回一個(gè)空的多邊形。
CLIP-POLYGON (Clipper, Polygon)
1 RightPart = {}
2 LeftPart = {}
3 for each point edge E in Polygon
4 Side1 = CLASSIFY-POINT (Clipper, E.Point1)
5 Side2 = CLASSIFY-POINT (Clipper, E.Point2)
6 if (Side1 <> Side2 and
Side1 <> COINCIDING and
Side2 <> COINCIDING)
7 Ip = INTERSECTION-POINT (Clipper, E)
8 if (Side1 = INFRONT)
9 RightPart = RightPart U E.Point1
10 RightPart = RightPart U Ip
11 LeftPart = LeftPart U Ip
12 LeftPart = LeftPart U E.Point2
13 if (Side1 = BEHIND)
14 LeftPart = LeftPart U E.Point1
15 LeftPart = LeftPart U Ip
16 RightPart = RightPart U Ip
17 RightPart = RightPart U E.Point2
18 else
19 if (Side1 = INFRONT or Side2 = INFRONT or
Side1 = COINCIDING and Side2 = COINCIDING)
20 RightPart = RightPart U E.Point1
21 RightPart = RightPart U E.Point2
22 if (Side1 = BEHIND or Side2 = BEHIND)
23 LeftPart = LeftPart U E.Point1
24 LeftPart = LeftPart U E.Point2
25 return (RightPart, LeftPart)
現(xiàn)在我們可以定義如何在一個(gè)BSP層次樹中對portal進(jìn)行分配了，在算法中portal被初始化為一個(gè)大于BSP根節(jié)點(diǎn)“最大包圍盒”的多邊形。
l 函數(shù)PLACE-PORTALS
l 參數(shù):
l PortalPolygon – 放置到BSP中的多邊形。
l Node – 我們當(dāng)前遍歷的節(jié)點(diǎn)。
l 返回值:
l None
l 功能:
l 放置一個(gè)portal多邊形到BSP層次樹中，如果需要的話對它進(jìn)行剪切。這個(gè)函數(shù)將會(huì)產(chǎn)生一個(gè)節(jié)點(diǎn)將由portal連接而每一個(gè)節(jié)點(diǎn)將包含一個(gè)portal多邊形列表的BSP層次樹。
PLACE-PORTALS (PortalPolygon, Node)
1 if (IS-LEAF (Node))

l 將portal和節(jié)點(diǎn)中的每一個(gè)多邊形進(jìn)行檢測。當(dāng)portal所包含的多邊形和由一個(gè)多邊形定義的面相交時(shí)它將被這個(gè)面進(jìn)行分割，分割后的兩個(gè)部分將被重新傳送到最頂層的節(jié)點(diǎn)中繼續(xù)進(jìn)行檢測。
2 for (each polygon P2 in Node)
3 IsClipped = false
4 if (CALCULATE-SIDE (P2, PortalPolygon) = SPANNING)
5 IsClipped = true
6 (RightPart, LeftPart) = CLIP-POLYGON (P2, PortalPolygon)
7 PLACE-PORTALS (RightPart, RootNode)
8 PLACE-PORTALS (LeftPart, RootNode)
9 if (not IsClipped)
10 從當(dāng)前節(jié)點(diǎn)中將portal的多邊形剔除，因?yàn)樗奈恢煤凸?jié)點(diǎn)中一個(gè)多邊形的位置相同。
l 參考下面的描述。
11 添加當(dāng)前節(jié)點(diǎn)到portal多邊形所連接的節(jié)點(diǎn)集合中。
12 else
13 if (當(dāng)前節(jié)點(diǎn)的分割多邊形沒有放置在樹中)
14 建立一個(gè)多邊形P，它的大小將超過包含當(dāng)前節(jié)點(diǎn)所有多邊形的最大包圍盒的范圍，并且和分割多邊形的位置相同。
15 PLACE-PORTALS (P, Node.LeftChild)
16 PLACE-PORTALS (P, Node.RightChild)
17 Side = CALCULATE-SIDE (Node.Divider, PortalPolygon)
18 if (Side = POSITIVE)
19 (RightPart, LeftPart) = CLIP-POLYGON(P2, PortalPolygon)
20 PLACE-PORTALS (RightPart, RootNode)
21 PLACE-PORTALS (LeftPart, RootNode)
22 if (Side = POSITIVE or COINCIDING)
23 PLACE-PORTALS (PortalPolygon, Node.RightChild)
24 if (Side = NEGATIVE or COINCIDING)
25 PLACE-PORTALS (PortalPolygon, Node.LeftChild)
下面我將對算法中的第10行進(jìn)行一下解釋，當(dāng)剔除和當(dāng)前節(jié)點(diǎn)中一個(gè)多邊形位置相同的portal多邊形部分將會(huì)產(chǎn)生什么樣的結(jié)果。參考一下圖6.12。

圖6.12
在圖6.12中一個(gè)portal已經(jīng)到達(dá)了一個(gè)葉節(jié)點(diǎn)，圖中灰色的區(qū)域是是portal多邊形在遍歷BSP樹過程中被剔除的區(qū)域稱它為1。而圖中標(biāo)注為2、3、4的亮灰色部分是和portal多邊形位置相重疊的多邊形，因此這一部分的portal多邊形也將會(huì)被剔除，而剩下的部分5將被用來做為一個(gè)portal。
在上面的算法第一次看的話會(huì)覺的非常復(fù)雜，但實(shí)際上它非常簡單和容易理解，最終的結(jié)果就是每一個(gè)portal將會(huì)在兩個(gè)節(jié)點(diǎn)上結(jié)束而對于任一個(gè)portal來說它必定可以和一個(gè)portal之間相互可見。在下面我將用一個(gè)實(shí)際的例子來解釋一下這個(gè)算法。

圖6.13
對于圖6.13中的結(jié)構(gòu)，需要進(jìn)行下面的幾步：
第一步，portal多邊形s1進(jìn)入節(jié)點(diǎn)n1中。

    在節(jié)點(diǎn)n1中portal多邊形s1將會(huì)被分割，因?yàn)樗囊徊糠趾凸?jié)點(diǎn)中間的一個(gè)多邊形位置相同，因此portal多邊形s1將會(huì)被分割為兩部分分別為p1、p2，重疊的部分被剔除。
第二步，p1、p2進(jìn)入節(jié)點(diǎn)s2中。
在節(jié)點(diǎn)s2中由于p1位于分割面s2的“正面”，因此將和分割面s2一起被送入到節(jié)點(diǎn)n2中，而p2由于位于分割面s2的“反面”，因此將和分割面s2一起被送入到節(jié)點(diǎn)s3中。由于p1、p2沒有和分割面相交因此這一步?jīng)]有出現(xiàn)分割操作。
第三步，p1、s2進(jìn)入節(jié)點(diǎn)n2中。

在節(jié)點(diǎn)n2中n2被認(rèn)可作為一個(gè)portal，因此在節(jié)點(diǎn)n1和n2中它不會(huì)再發(fā)生任何變化。而多邊形p3的一部分將會(huì)被剔除，因?yàn)樗囊徊糠趾凸?jié)點(diǎn)中間的一個(gè)多邊形位置相同，在上一步中多邊形s2也被送入到節(jié)點(diǎn)s3中，而在這里它又被稱為p3。

第四步，p3和s3進(jìn)入節(jié)點(diǎn)n3中。

在節(jié)點(diǎn)n3中多邊形p3被認(rèn)可為一個(gè)portal，而多邊形s3的一部分因?yàn)楹蜕厦娴脑蛞粯颖惶蕹瑫r(shí)在這里它又被稱為p4。

第五步，p2和p4進(jìn)入節(jié)點(diǎn)s4中。
沒有任何多邊形要進(jìn)行分割，因此多邊形p2和p4將與s4一起被送入節(jié)點(diǎn)n4中，而s4將被單獨(dú)送入節(jié)點(diǎn)n5中。
第六步，p2、p4和s4一起進(jìn)入節(jié)點(diǎn)n4中。

無論是p2還是p4都不需要分割，但是由于s4和中間的一個(gè)多邊形完全重疊因此將會(huì)被剔除。

第七步，結(jié)束，沒有任何多邊形進(jìn)入節(jié)點(diǎn)n5中。
這個(gè)節(jié)點(diǎn)將沒有portal，因?yàn)閷τ谌魏喂?jié)點(diǎn)來說它都是不可見的，而從這個(gè)節(jié)點(diǎn)位置上將不會(huì)看見任何一個(gè)節(jié)點(diǎn)。
結(jié)果：
portal p1同時(shí)位于節(jié)點(diǎn)n1和n2中；
portal p2同時(shí)位于節(jié)點(diǎn)n1和n4中；
portal p1同時(shí)位于節(jié)點(diǎn)n2和n3中；
portal p1同時(shí)位于節(jié)點(diǎn)n3和n4中。

上面我所講解的內(nèi)容是建立一個(gè)簡單的portal引擎所必備的功能，它能給我們提供一個(gè)較高的運(yùn)行幀速。
PVS
    一個(gè)portal引擎雖然能夠提供許多非常好的特性，但是它的結(jié)構(gòu)太復(fù)雜。當(dāng)你使用portal技術(shù)來構(gòu)建一個(gè)游戲引擎時(shí)你會(huì)發(fā)現(xiàn)它存在許多問題，最大的一個(gè)問題是在渲染場景的每一幀都需要進(jìn)行可視性檢測，這會(huì)產(chǎn)生大量的多邊形剪切操作，在場景非常復(fù)雜的情況下，運(yùn)算的費(fèi)用會(huì)非常的高，因此需要尋找一種技術(shù)來對場景中可視性檢測進(jìn)行預(yù)計(jì)算而不是在運(yùn)行期間進(jìn)行計(jì)算。PVS（Potentially Visible Set）可視性集合，就是為了解決這個(gè)問題而出現(xiàn)的一項(xiàng)技術(shù)，可以通過對BSP中每一個(gè)葉節(jié)點(diǎn)設(shè)置一個(gè)PVS，這個(gè)PVS保存了從第一個(gè)葉節(jié)點(diǎn)開始看到的葉節(jié)點(diǎn)集合，它不僅可以用來幫助加速場景渲染，還可以用來加速場景中光照運(yùn)算和進(jìn)行網(wǎng)絡(luò)優(yōu)化。
PVS是在場景進(jìn)行預(yù)渲染時(shí)計(jì)算出來的，每一個(gè)BSP的葉節(jié)點(diǎn)都保存一個(gè)可視節(jié)點(diǎn)的集合，當(dāng)對場景進(jìn)行渲染時(shí)，攝象機(jī)所在的葉節(jié)點(diǎn)將被渲染，同時(shí)保持在PVS中的葉節(jié)點(diǎn)也將會(huì)被渲染出來，這里需要一些算法來避免場景重復(fù)渲染，由于今天硬件加速卡的發(fā)展，它所提供的硬件Z緩沖的大小已經(jīng)可以方便的解決這個(gè)問題。
計(jì)算PVS
如果要求PVS必須在BSP的葉節(jié)點(diǎn)之間進(jìn)行標(biāo)準(zhǔn)的光線跟蹤計(jì)算，來查找一下在一個(gè)葉節(jié)點(diǎn)中任一個(gè)點(diǎn)是否在其它葉節(jié)點(diǎn)中可見。為了加速光線跟蹤的計(jì)算，在每一個(gè)葉節(jié)點(diǎn)中必須指出一些典型的位置點(diǎn)來避免無謂的計(jì)算，現(xiàn)在的問題就是如何放置這些典型的點(diǎn)。
對于一個(gè)portal引擎的portal來說，典型點(diǎn)可以沿著樹的分割面放置，這是因?yàn)橹挥性趦蓚€(gè)portal是相互開放的情況下才可以進(jìn)行可視化檢測。如果位于一個(gè)葉節(jié)點(diǎn)中間的一個(gè)點(diǎn)被從另一個(gè)葉節(jié)點(diǎn)發(fā)射出來的光線認(rèn)為是可見的話，那么這條光線必然通過連接兩個(gè)節(jié)點(diǎn)的portal，參考下圖：

圖6.14
在圖6.14中我們可以看見如果在一個(gè)節(jié)點(diǎn)中的一個(gè)點(diǎn)可以從其它節(jié)點(diǎn)看見，那么視線必然通過兩個(gè)節(jié)點(diǎn)相互連通的區(qū)域。這是非常明顯的，如果視線被物體阻斷的話那么兩點(diǎn)之間必定不可見。因此將典型點(diǎn)放置在兩個(gè)節(jié)點(diǎn)之間所開放的區(qū)域是非常合適的，下面描述的算法將在一個(gè)BSP樹上放置典型點(diǎn)。對于這個(gè)函數(shù)需要一組幫助函數(shù)來把點(diǎn)放置在一個(gè)節(jié)點(diǎn)上，它們是
l DISTRIBUTE-POINTS (Node) 這個(gè)函數(shù)將按照一定的間隔沿著給定節(jié)點(diǎn)的分割面來放置點(diǎn)，點(diǎn)的位置會(huì)處于節(jié)點(diǎn)包圍盒的內(nèi)部。它將返回一個(gè)點(diǎn)的集合，復(fù)雜度為O(xy)，這里x為節(jié)點(diǎn)包圍盒內(nèi)分割面的寬度，而y為高度。
l CLEANUP-POINTS (Node, PointSet) 從點(diǎn)的集合中剔除不合格的點(diǎn)，這些點(diǎn)可能和節(jié)點(diǎn)中的一個(gè)多邊形位置相同，也可能是位于節(jié)點(diǎn)包圍盒的外部。函數(shù)的復(fù)雜度為O(np)，這里n為節(jié)點(diǎn)中多邊形的數(shù)量而p為集合中點(diǎn)的數(shù)量。
l 函數(shù) DISTRIBUTE-SAMPLE-POINTS
l 參數(shù):
l Node – 當(dāng)前我們遍歷的節(jié)點(diǎn)。
l PointSet – 放置到給定節(jié)點(diǎn)子樹中的點(diǎn)的集合。
l 返回值:
l None
l 功能：
l 沿著給定節(jié)點(diǎn)的分割面放置點(diǎn)。它將按照分割面的位置來對輸入的點(diǎn)進(jìn)行檢測，如果這些點(diǎn)和節(jié)點(diǎn)中的一個(gè)多邊形位置相同，或者位于節(jié)點(diǎn)包圍盒的外部那么將會(huì)被剔除。新產(chǎn)生的點(diǎn)將會(huì)被添加到左、右兩個(gè)集合中，當(dāng)一個(gè)點(diǎn)的集合遍歷到一個(gè)葉節(jié)點(diǎn)時(shí)那么它就是這個(gè)葉節(jié)點(diǎn)的典型點(diǎn)。
DISTRIBUTE-SAMPLE-POINTS (Node, PointSet)
1 CLEANUP-POINTS (Node, PointSet)
2 if (IS-LEAF (Node))
3 設(shè)置點(diǎn)的集合為當(dāng)前節(jié)點(diǎn)的典型點(diǎn)。
4 else
5 RightPart = NewPoints
6 NewPoints = DISTRIBUTE-POINTS (Node)
7 RightPart = NewPoints
8 LeftPart = NewPoints
9 for each point P in PointSet
10 Side = CLASSIFY-POINT (Node.Divider, P)
11 if (Side = COINCIDING)
12 RightPart = RightPart U P
13 LeftPart = LeftPart U P
14 if (Side = INFRONT)
15 RightPart = RightPart U P
16 if (Side = BEHIND)
17 LeftPart = LeftPart U P
18 DISTRIBUTE-SAMPLE-POINTS (Node.LeftChild, LeftPart)
19 DISTRIBUTE-SAMPLE-POINTS (Node.RightChild, RightPart)
算法分析
    每一次調(diào)用這個(gè)函數(shù)的復(fù)雜度為O(np + xy)（參考函數(shù)CLEANUP-POINTS和
DISTRIBUTE-POINTS），為了計(jì)算完整的復(fù)雜度我們可以用下面的公式來表示（我們假設(shè)典型點(diǎn)的集合同時(shí)分布在兩個(gè)集合之中）：
T(n) = 2T(n/2) + O(np + xy)
這個(gè)函數(shù)第一次調(diào)用時(shí)將會(huì)從BSP樹的根節(jié)點(diǎn)開始并會(huì)傳入一個(gè)空的集合。換句話說它是按照下面的方法進(jìn)行的，它是從被BSP樹根節(jié)點(diǎn)所定義的分割面上的點(diǎn)開始的，由于一個(gè)面的大小沒有限制因此也會(huì)有無限個(gè)典型點(diǎn)，因此就需要對典型點(diǎn)進(jìn)行限制，這個(gè)現(xiàn)在就是根節(jié)點(diǎn)的包圍盒。
在根節(jié)點(diǎn)上獲得合格的典型點(diǎn)后需要把所有的點(diǎn)發(fā)送到根節(jié)點(diǎn)的兩個(gè)子樹中，當(dāng)一個(gè)典型點(diǎn)的集合進(jìn)入一個(gè)節(jié)點(diǎn)后會(huì)被分割為兩個(gè)部分，一個(gè)部分包含了所有位于節(jié)點(diǎn)分割面的“正面”的點(diǎn)，而另一部分包含了所有位于節(jié)點(diǎn)分割面的“反面”的點(diǎn)。而位于分割面上的點(diǎn)將會(huì)同時(shí)放在兩個(gè)集合中。接著“正面”集合將會(huì)被傳入到右子樹中而“反面”集合將會(huì)被傳入到左子樹中。重復(fù)這個(gè)過程直到進(jìn)行到葉節(jié)點(diǎn)時(shí)結(jié)束，在這些操作后每一個(gè)葉節(jié)點(diǎn)將包含一個(gè)典型點(diǎn)的集合，這些點(diǎn)都位于節(jié)點(diǎn)所連通的地方。
如果我們現(xiàn)在在這個(gè)階段對每一個(gè)節(jié)點(diǎn)進(jìn)行光線跟蹤那么是非常耗費(fèi)時(shí)間的，但是如果我們知道葉節(jié)點(diǎn)是與哪一個(gè)節(jié)點(diǎn)相連的，那么這個(gè)過程將會(huì)變的簡單，因?yàn)檫@樣可以減少一些不必要的光線跟蹤運(yùn)算。查找相互連接的葉節(jié)點(diǎn)非常簡單，可以通過檢測每一個(gè)葉節(jié)點(diǎn)的典型點(diǎn)來查找，如果同時(shí)有兩個(gè)節(jié)點(diǎn)共享一個(gè)點(diǎn)那么這兩個(gè)節(jié)點(diǎn)必然是相互連通的，因?yàn)樵诒闅vBSP樹放置典型點(diǎn)的過程中，點(diǎn)不是沒有放置到節(jié)點(diǎn)上就是同時(shí)放置在兩個(gè)節(jié)點(diǎn)上。當(dāng)我們知道哪些節(jié)點(diǎn)是相互連通的，就可以定義進(jìn)行光線跟蹤的算法了，不過首先我們需要定義一些幫助函數(shù)。
為了方便進(jìn)行光線跟蹤我們需要一些基本的光線跟蹤函數(shù)，BSP樹是非常適合進(jìn)行光線跟蹤的結(jié)構(gòu)，因?yàn)榇蟛糠植豢梢姷膮^(qū)域通過BSP樹可以很簡單的剔除掉，不用進(jìn)行遍歷，因此花費(fèi)的時(shí)間也非常少。我們需要的函數(shù)如下：
POLYGON-IS-HIT (Polygon, Ray) 返回光線是否和多邊形相交。
RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray) 返回光線是否和節(jié)點(diǎn)中的子樹相交。
INTERSECTS-SPHERE (Sphere, Ray) 返回光線是否和球體相交。
CREATE-RAY (Point1, Point2) 通過兩個(gè)點(diǎn)來建立一條光線。
上面的函數(shù)RAY-INTERSECTS-SOMETHING-IN-TREE是一個(gè)非常有趣的函數(shù)，因?yàn)樗@示了一些BSP樹的優(yōu)點(diǎn)，同時(shí)也顯示了如何使用BSP樹來加速光線跟蹤的處理。它是一個(gè)遞歸函數(shù)，首先在樹的根節(jié)點(diǎn)上使用，偽算法如下：
l 函數(shù)RAY-INTERSECTS-SOMETHING-IN-TREE
l 參數(shù)：
l Node – 用來進(jìn)行跟蹤的節(jié)點(diǎn)。
l Ray – 用來進(jìn)行求交的光線。
l 返回值：
l 光線是否和節(jié)點(diǎn)中的物體相交。
l 功能：
l 檢測光線是否與給定節(jié)點(diǎn)極其子樹中的物體相交。
RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray)
1 for each polygon P in Node
2 POLYGON-IS-HIT (P, Ray)
3 startSide = CLASSIFY-POINT (Ray.StartPoint, Node.Divider)
4 endSide = CLASSIFY-POINT (Node.EndPoint, Node.Divider)
l 如果光線和節(jié)點(diǎn)的分割面相交或和分割面的位置重疊，對節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)進(jìn)行檢測。
5 if ((startSide = COINCIDING and endSide = COINCIDING) or
startSide <> endSide and startSide <> COINCIDING and
endSide <> COINCIDING)
6 if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
7 return true
8 if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
9 return true
l 如果光線只位于分割面的“正面”對節(jié)點(diǎn)的右子樹進(jìn)行檢測。在if語句中使用or操作符是因?yàn)楣饩€的一個(gè)端點(diǎn)可能與分割面的位置重疊。
10 if (startSide = INFRONT or endSide = INFRONT)
11 if(RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
12 return true
l 如果光線只位于分割面的“反面”對節(jié)點(diǎn)的左子樹進(jìn)行檢測。在if語句中使用or操作符是因?yàn)楣饩€的一個(gè)端點(diǎn)可能與分割面的位置重疊。
13 if (startSide = BEHIND or endSide = BEHIND)
14 if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
15 return true
l 光線沒有和任何物體相交，返回到上一層。
16 return false
算法分析
最壞的情況是光線遍歷了BSP樹中每一個(gè)節(jié)點(diǎn)，這樣光線將與節(jié)點(diǎn)中每一個(gè)單獨(dú)的多邊形進(jìn)行檢測，這時(shí)函數(shù)的復(fù)雜度將為O(n)，這里n為BSP樹中所有多邊形的數(shù)量。一般情況下光線并不會(huì)檢測樹中的每一個(gè)節(jié)點(diǎn)，這樣將會(huì)大大減少進(jìn)行檢測的多邊形數(shù)量。最佳的情況是光線被限制在一個(gè)節(jié)點(diǎn)中，這時(shí)函數(shù)的復(fù)雜度接近于Ｏ(lg n)．這取決于BSP樹的結(jié)構(gòu)大小。
l 函數(shù)CHECK-VISIBILITY
l 參數(shù)：
l Node1 – 開始處的節(jié)點(diǎn)。
l Node2 – 結(jié)束處的節(jié)點(diǎn)。
l 返回值：
l Node2是否可以被node1看見。
l 功能：
l 在兩個(gè)葉節(jié)點(diǎn)的典型點(diǎn)之間進(jìn)行跟蹤，檢測兩個(gè)節(jié)點(diǎn)之間是否可見。
CHECK-VISIBILITY (Node1, Node2)
1 Visible = false
2 for each 典型點(diǎn)P1 in Node1
3 for each 典型點(diǎn)P2 in Node2
4 Ray = CREATE-RAY (P1, P2)
5 if(not RAY-INTERSECTS-SOMETHING-IN-TREE(Node1.Tree.RootNode,
Ray)
6 Visible = true
7 return Visible
算法分析
函數(shù)CHECK-VISIBILITY非常耗費(fèi)時(shí)間，當(dāng)我們在兩個(gè)葉節(jié)點(diǎn)之間進(jìn)行光線跟蹤來檢測兩者之間是否可見時(shí)，我們不得不從Node1的每一個(gè)典型點(diǎn)開始對Node2的每一個(gè)典型點(diǎn)進(jìn)行跟蹤，最壞的情況是每一次跟蹤都將對樹中所有的多邊形進(jìn)行檢測，這時(shí)函數(shù)的復(fù)雜度O(s1 s2 p)，這里s1為Node1中典型點(diǎn)的數(shù)量，s2為Node2中典型點(diǎn)的數(shù)量，p為樹中多邊形的數(shù)量。通常它的性能是比較好的，接近于O(s1 s2 lg p)。
l 函數(shù)TRACE-VISIBILITY
l 參數(shù)：
l Tree – 去進(jìn)行光線跟蹤的BSP-tree。
l 返回值：
l None
l 功能：
l 對于樹中每一個(gè)葉節(jié)點(diǎn)，它將進(jìn)行光線跟蹤運(yùn)算來檢測和它相連的節(jié)點(diǎn)的可見性。每一個(gè)被發(fā)現(xiàn)是可見的節(jié)點(diǎn)將會(huì)被添加到當(dāng)前節(jié)點(diǎn)的PVS中。當(dāng)一個(gè)葉節(jié)點(diǎn)發(fā)現(xiàn)是可見的，我們還要對和它相連的節(jié)點(diǎn)進(jìn)行光線跟蹤運(yùn)算來檢測可見性。
TRACE-VISIBILITY (Tree)
1 for (each 樹中的葉節(jié)點(diǎn)L)
2 for (each 和葉節(jié)點(diǎn)L相連的葉節(jié)點(diǎn)C)
3 添加節(jié)點(diǎn)C到節(jié)點(diǎn)L的PVS中
4 for (each 樹中的葉節(jié)點(diǎn)L1)
5 while (在葉節(jié)點(diǎn)L的PVS中存在一個(gè)葉節(jié)點(diǎn)L2，它所連接的節(jié)點(diǎn)沒有進(jìn)行可見性檢測)
5 for (each 連接到節(jié)點(diǎn)L2中的葉節(jié)點(diǎn)C)
6 if (節(jié)點(diǎn)C沒有位于節(jié)點(diǎn)L1的PVS中 and
CHECK-VISIBILITY (L1, C))
7 添加節(jié)點(diǎn)C到節(jié)點(diǎn)L1的PVS中
7 添加節(jié)點(diǎn)L1到節(jié)點(diǎn)C的PVS中
算法分析
如果我們沒有使用根據(jù)葉節(jié)點(diǎn)的相連情況來進(jìn)行處理的優(yōu)化技術(shù)，那么必須對樹中的每一個(gè)葉節(jié)點(diǎn)進(jìn)行檢測，這時(shí)函數(shù)的復(fù)雜度為O(n2)，這里n為樹中葉節(jié)點(diǎn)的數(shù)量。要對上面的算法估計(jì)一個(gè)對處理過程提高了多少性能的具體數(shù)值非常困難，因?yàn)樗蕾囉谒幚淼慕Y(jié)構(gòu)的大小。對于每一個(gè)葉節(jié)點(diǎn)與其它節(jié)點(diǎn)都是可見的結(jié)構(gòu)，這個(gè)算法不會(huì)做任何優(yōu)化。對于每一個(gè)葉節(jié)點(diǎn)只有一到二個(gè)可見的節(jié)點(diǎn)的結(jié)構(gòu)，這個(gè)算法將會(huì)產(chǎn)生非常大優(yōu)化，它的復(fù)雜度接近與O(n)。
現(xiàn)在在一個(gè)設(shè)計(jì)良好的地圖上所產(chǎn)生的結(jié)構(gòu)在每一幀上將會(huì)避免檢測大量的多邊形。一個(gè)設(shè)計(jì)良好的地圖在建立時(shí)將會(huì)考慮物體的可見性，這意味著應(yīng)盡可能的在地圖中放入一些能障礙視線的物體，如墻壁等。如果在地圖中包含一個(gè)有大量細(xì)節(jié)的大房間，那么在上面的算法中（或在一個(gè)portal引擎中）進(jìn)行的隱藏面剔除工作對它不會(huì)產(chǎn)生任何效果。這時(shí)我們需要使用其它類似于LOD這樣的技術(shù)來進(jìn)行多邊形剔除。

靜態(tài)物體
考慮一下這樣的場景，一個(gè)球體位于一個(gè)立方體的中心，如果用BSP對它進(jìn)行渲染那么將會(huì)產(chǎn)生大量的節(jié)點(diǎn)，并會(huì)產(chǎn)生大量的分割多邊形，這是因?yàn)樵谇蝮w上的每一個(gè)多邊形都會(huì)送入到葉節(jié)點(diǎn)中。如果球體有200個(gè)多邊形當(dāng)渲染時(shí)就會(huì)產(chǎn)生200個(gè)葉節(jié)點(diǎn)的BSP樹。這樣做非常影響運(yùn)行的速度，因此必須尋找一個(gè)方法來避免這種現(xiàn)象的發(fā)生。
為了解決這個(gè)問題地圖的設(shè)計(jì)者可以選擇組成地圖的幾何體，在上面的例子中也就是立方體，接著將剩余的物體做為靜態(tài)物體，它們將不會(huì)用來對BSP樹進(jìn)行渲染或進(jìn)可見性檢測，但是它們會(huì)參與到地圖的光照運(yùn)算當(dāng)中去。當(dāng)進(jìn)行可見性運(yùn)算時(shí)每一個(gè)靜態(tài)物體會(huì)被添加到BSP樹中，每一個(gè)靜態(tài)物體的多邊形將會(huì)被添加到BSP樹中，這個(gè)過程如下：
l 函數(shù)PUSH-POLYGON
l 參數(shù)：
l Node – 多邊形當(dāng)前所在的節(jié)點(diǎn)。
l Polygon – 將被添加的多邊形。
l 返回值：
l None
l 功能：
l 將多邊形添加到樹中。如果多邊形的一些點(diǎn)與節(jié)點(diǎn)的分割面相交將會(huì)被分割。分割后的部分將會(huì)被繼續(xù)向下傳送。當(dāng)一個(gè)多邊形進(jìn)入一個(gè)葉節(jié)點(diǎn)后它將被添加到葉節(jié)點(diǎn)的多邊形集合中。
PUSH-POLYGON (Node, Polygon)
1 if (IS-LEAF (Node))
2 Node.PolygonSet = Node.PolygonSet U Polygon
3 else
4 value = CALCULATE-SIDE (Node.Divider, Polygon)
5 if (value = INFRONT or value = SPANNING)
6 PUSH-POLYGON (Node.RightChild, Polygon)
7 else if (value = BEHIND)
8 PUSH-POLYGON (Node.LeftChild, Polygon)
9 else if (value = SPANNING)
10 Split_Polygon28 (P1, Divider, Front, Back)
11 PUSH-POLYGON (Node.RightChild, Front)
12 PUSH-POLYGON (Node.LeftChild, Front)
PUSH-POLYGON是一個(gè)遞歸函數(shù)，它將一個(gè)多邊形添加到BSP樹中，這個(gè)函數(shù)對每一個(gè)靜態(tài)物體的每一個(gè)多邊形都會(huì)調(diào)用一次，
在這個(gè)過程處理之后葉節(jié)點(diǎn)可能不再成為一個(gè)“凸”集合，這在進(jìn)行碰撞檢測時(shí)可能會(huì)產(chǎn)生一些問題，后面的內(nèi)容將會(huì)對這個(gè)問題進(jìn)行闡述。
BSP技術(shù)詳解3

eXtreme3D

第三節(jié) 室內(nèi)場景中光照運(yùn)算
關(guān)于Radiosity的算法最早是由Goral、Cindy M、Torrance、Kenneth E、Greenberg、Donald P、Battaile和Bennett在論文《Modelling the interaction of light between diffuse surfaces》提出的。他們使用Radiosity來模擬能量在漫反射表面之間進(jìn)行傳送，漫反射表面對照到表面上的光線在所有的方向上都進(jìn)行相同的反射，和它相反的是鏡面反射表面，它只在反射方向上傳播反射光。由于漫反射表面的這個(gè)特性，這就意味著對于所有的觀察角度而言看起來表面都是相同的，這樣對于場景中的每一個(gè)表面只需要進(jìn)行一次光照運(yùn)算，而且可以在場景的預(yù)渲染時(shí)進(jìn)行，因此這項(xiàng)技術(shù)被大量的3D游戲所采用。
下面我再簡短的講解一下Radiosity是如何工作的，而將主要的精力放在如何使用BSP樹來加速Radiosity的計(jì)算，對于Radiosity的詳細(xì)介紹請參考前面的章節(jié)。Radiosity技術(shù)是設(shè)計(jì)用來使場景中光照看起來更加真實(shí)和光滑，如果我們使用一個(gè)一直向前傳播而不考慮反射的光照模型，那么當(dāng)場景中的燈光照亮場景中的物體時(shí)，并不會(huì)計(jì)算遠(yuǎn)處經(jīng)過反射過來的光線，這樣場景中的陰影看起來非常尖銳而物體表面也看起來非常不真實(shí)。為了使用radiosity技術(shù)我們需要把場景分割成一塊一塊很小的部分，每一部分我們稱它為patch，每一個(gè)patch都有一個(gè)初始化的能量級別，如果它不是一個(gè)燈光這樣的發(fā)光體的話通常為0，有許多方法來分配場景中的能量，這里我們將要使用的方法稱為交互式radiosity。這個(gè)方法的過程是我們從場景中未發(fā)送能量的級別最高的patch開始發(fā)送能量，能量經(jīng)過傳遞后將不再發(fā)送能量的patch的等級設(shè)為0，重復(fù)這個(gè)過程直到場景中的每一個(gè)patch的能量等級都小于一個(gè)預(yù)定值為止。
當(dāng)能量從一個(gè)patch（j）開始發(fā)送到另一個(gè)patch（i）時(shí)我們使用下面的公式：
Bi = Bi + Bj * Fij * Ai / Aj
這里Bi = patch（i）的能量級別    Bj = patch（j）的能量級別
    Ai= patch（i）的作用區(qū)域    Aj = patch（j）的作用區(qū)域
    Fij = patch（i）與patch（j）之間的系數(shù)
在公式中系數(shù)Fij是由以下公式來確定的：
Fij = (cos qi * cos qj) / d2 * Hij
這里Fij = patch（i）與patch（j）之間的系數(shù)
qi = patch（i）與patch（j）法線之間的夾角
qj = patch（i）與patch（j）法線之間的夾角
d = patch（i）與patch（j）之間的距離
Hij = patch（i）與patch（j）之間的可見性系數(shù)。如果在兩個(gè)patch之間只有一條光線可以跟蹤，這個(gè)值為1，如果沒有光線可以跟蹤為0。一般情況下由于每一個(gè)patch都不是一個(gè)點(diǎn)而是一個(gè)區(qū)域，因此光線有很多條。
從上面的公式中我們可以看到在場景中進(jìn)行radiosity計(jì)算是非常耗費(fèi)時(shí)間的。這個(gè)函數(shù)的復(fù)雜度為O(n3)，這里的n為場景中patch的數(shù)量。由于對于場景中每一個(gè)patch你需要發(fā)送最少一條光線到其它patch上，因此需要對場景中的幾乎所有的多邊形都進(jìn)行光線跟蹤計(jì)算。在上面的公式中系數(shù)H的計(jì)算非常耗費(fèi)時(shí)間，下面我們將看一下如何在BSP樹中對它的計(jì)算進(jìn)行優(yōu)化。

    BSP樹中的radiosity計(jì)算
在進(jìn)行場景中的光照計(jì)算之前需要把場景中的面分割為patch，一個(gè)方法是在開始的時(shí)候設(shè)定每一個(gè)patch為預(yù)定的大小，當(dāng)計(jì)算每一個(gè)patch的能量時(shí)，如果在patch上的能量足夠大，對這個(gè)patch進(jìn)行分割。不過這個(gè)方法是非常耗費(fèi)時(shí)間的，因此必須尋找一個(gè)更好的方法來通過BSP樹對計(jì)算進(jìn)行優(yōu)化。
在radiosity的一般算法中場景中的每一個(gè)光源都被看作為一個(gè)或多個(gè)patch，這里我們可以改進(jìn)一下，將每一個(gè)光源放在它所位于的葉節(jié)點(diǎn)中，接下來每一個(gè)光源都發(fā)送自己的能量到場景中所有的patch上，當(dāng)這個(gè)過程完成后radiosity計(jì)算也就結(jié)束了。為了使最后的結(jié)果看起來更好可以使用一種稱為“漸進(jìn)精選”（progressive refinement）的技術(shù)來對這個(gè)方法進(jìn)行很小的修改。在每一次過程中，葉節(jié)點(diǎn)中具有高能量的patch將發(fā)送能量到其它低能量的patch上，這樣做的結(jié)果是高亮度的patch將發(fā)送能量到處于陰影中patch上。這是因?yàn)樵趯?shí)際生活中并沒有真正黑暗的地方，它多多少少要獲得一些其它物體反射過來的光亮。
由于計(jì)算非常耗費(fèi)時(shí)間需要做一下優(yōu)化，使用渲染BSP樹時(shí)獲得的PVS信息可以在選擇哪些patch將接受能量時(shí)剔除一些無用的計(jì)算。因?yàn)樵谟?jì)算PVS時(shí)使用了相同的方法來進(jìn)行光線跟蹤。
通過場景來分配能量的算法如下：
l 函數(shù)RADIOSITY
l 參數(shù)：
l Tree – 進(jìn)行radiosity計(jì)算的BSP樹。
l 返回值：
l None
l 功能：
l 在場景中的patch之間發(fā)送能量。
RADIOSITY (Tree)
1 for(each leaf L in Tree)
2 for(each light S in L)
3 for(each leaf V that is in L’s PVS)
4 Send S’s energy to the patches in V
l 下面語句5是為了讓地圖編輯者在任何時(shí)候都可以檢查場景渲染的效果，如果他感到看起來已經(jīng)足夠好了可以中斷能量的傳播。
5 while(not looks good enough)
6 for(each leaf L in Tree)
7 for(each leaf V that is in L’s PVS)
8 Send energy from the patch with the most unsent energy in L
to all patches in V.
復(fù)雜度分析
這個(gè)函數(shù)的運(yùn)算費(fèi)用實(shí)在是太高昂了，可以稱為時(shí)間殺手，在最壞的情況下每一條光線將不得不檢測場景中的每一個(gè)多邊形，此時(shí)復(fù)雜度為O(n3)，這里n為樹中patch的數(shù)量。一般情況下由于進(jìn)行了優(yōu)化可以減少大量的計(jì)算，但是減少多少并不能計(jì)算出來，因?yàn)檫@依賴于樹結(jié)構(gòu)的復(fù)雜度。
上面的函數(shù)給出了一個(gè)充分利用BSP樹的優(yōu)點(diǎn)來加速場景光照運(yùn)算的方法，尤其是可以顯著的減少光線跟蹤的計(jì)算量，而且地圖設(shè)計(jì)者可以來決定當(dāng)場景渲染時(shí)如果渲染的效果可以接受中斷渲染循環(huán)。這對地圖的預(yù)渲染實(shí)在是太方便了，運(yùn)行的時(shí)間可以根據(jù)渲染的效果來決定。
第四節(jié) BSP樹的預(yù)渲染
現(xiàn)在我們需要完成一個(gè)完整BSP引擎的預(yù)處理過程，下面的算法顯示如何將場景渲染到BSP樹中。
l 函數(shù)RENDER-SCENE
l 參數(shù)：
l Scene – 被渲染的場景
l 返回值：
l 一個(gè)BSP樹。
l 功能
l 預(yù)渲染來獲得一個(gè)包含場景信息的BSP樹。
RENDER-SCENE (Scene)
l 使用描述場景中圖元的物體來渲染BSP樹。
1 GeometryPolygons = {}
2 for (每一個(gè)包含場景圖元的物體object O)
3 GeometryPolygons = GeometryPolygons U O.PolygonSet
4 GENERATE-BSP-TREE (Tree.RootNode, GeometryPolygons)
l 分配葉節(jié)點(diǎn)上的取樣點(diǎn)。
5 DISTRIBUTE-SAMPLE-POINTS (Tree.RootNode, {})
6 TRACE-VISIBILITY (Tree)
7 for 每一個(gè)場景中的靜態(tài)物體object O
8 for 物體O中每一個(gè)多邊形P
9 PUSH-POLYGON (Node, P)
l 函數(shù)CREATE-PATCHES是一個(gè)未定義的函數(shù)，由于我們的解決方案效率并不是太好，因此沒有對它進(jìn)行詳細(xì)的介紹。
10 CREATE-PATCHES (Tree)
11 RADIOSITY (Tree)
    復(fù)雜度分析
函數(shù)的復(fù)雜度如下：
函數(shù) 最壞情況 一般情況 描述
GENERATE-BSP-TREE O(n2 lg n) O(n2) n為場景中多邊形的數(shù)量
DISTRIBUTE-SAMPLE-POINTS Q (np + xy) Q (np + xy) n為樹中多邊形的數(shù)量，p為樹中典型點(diǎn)的數(shù)量，x和y為分割面的寬度和高度。
TRACE-VISIBILITY O(n2) O(n lg n), n為樹中多邊形的數(shù)量。
RADIOSITY O(n3) O(n2 lg n) n為樹中patch的數(shù)量
在一般情況這一列中顯示了算法通常所需運(yùn)行的時(shí)間，對算法時(shí)間影響最大的是函數(shù)RADIOSITY，它使整個(gè)算法的復(fù)雜度趨向于O(n3)。