BSP技術詳解1
eXtreme3D
翻譯自一篇老外的文章<Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering>,最后一點沒有翻譯完,呵呵,不太好意思!!!!!
BSP技術作為室內引擎渲染的主流技術雖然已經存在多年,但是生命力仍然非常頑強,最新的DOOM3,HL2仍然將它作為渲染的主流技術,但是在網上對它介紹文章雖然多卻非常淺顯,大多是使用Q3的BSP文件進行渲染,而BSP文件如何產生則介紹非常少,蓋因為這一部分是場景編輯器的工作,而完成一個這樣的BSP編輯器是非常困難的,需要掌握的知識非常多.下面我將對BSP編輯器這一部分需要用到的BSP知識進行一下介紹,這只是一些很初步的知識,如希望了解更多的內容,Q2開源代碼中有一個BSP編輯器的代碼是你研究的重點,還有就是HL2泄露代碼中的編輯器代碼,(一個痛苦的研究過程,可能要花費你幾個月甚至一年的時間,不過這是值得的,如果你想完成一個主流的射擊游戲引擎的話,沒有BSP編輯器是不可想象的).
第一節 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游戲開發的宗師地位，也使BSP技術成為室內渲染的工業標準，從BSP產生到現在已經有30多年了，其間雖然產生了大量的室內渲染的算法，但卻無人能撼動它的地位，對于以摩爾定律發展的計算機業來說這不能不是一個奇跡。
為什么使用BSP Trees
一個BSP Trees如同它的名字一樣是一個層次樹的結構，這個樹的葉節點保存了分割室內空間所得到的圖元集合。現在隨著硬件加速Z緩沖的出現，我們只需要用很小的代價就可以對空間中的圖元進行排序，但是在90年代初由于硬件的限制，使用BSP的主要原因是因為它可以對空間中的圖元進行排序來保證渲染圖元的順序是按照由后至前進行的，換句話說，Z值最小的物體總是最后被渲染。當然還有其他的算法可以完成這個功能，例如著名的畫家算法，但是它與BSP比較起來速度太慢了，這是因為BSP通常對圖元排序是預先計算好的而不是在運行時進行計算。從某種意義上說BSP技術實際上是畫家算法的擴展，正如同BSP技術的原始設計一樣，畫家算法也是使用由后至前的順序對場景中的物體進行渲染。但是畫家算法有以下的缺點：
l 如果一個物體從另一個物體中穿過時它不能被正確的渲染；
l 在每一幀對被渲染的物體進行排序是非常困難的，同時運算的代價非常大；
l 它無法管理循環覆蓋的情況，如圖所示
圖1.1
BSP原理
建立BSP Trees的最初想法是獲得一個圖元的集合，這個集合是場景的一部分，然后分割這個圖元集合為更小的子集合，這里必須注意子集合必須為“凸多邊形”。這意味著子集合中任一個多邊形都位于相同集合中其它多邊形的“前面”。是不是有點難以理解呢，舉一個例子，如果多邊形A的每一個頂點都位于由多邊形B所組成的一個面的正面，那么可以說多邊形A位于多邊形B的“前面”，參考左圖。我們可以想象一下，一個盒子是由6個面組成的，如果所有的面都朝向盒子的內部，那么我們可以說盒子是一個“凸多邊形”，如果不是都朝向盒子的內部，那么盒子就不是“凸多邊形”。
圖1.2
下面讓我們看一下如何確定一個圖元集合是否是一個“凸多邊形”，偽算法如下：
l 函數CLASSIFY-POINT
l 參數:
l Polygon – 確定一個3D空間中點相對位置的參考多邊形。
l Point – 待確定的3D空間中的點。
l 返回值:
l 點位于多邊形的哪一邊。
l 功能:
l 確定一個點位于被多邊形定義的面的哪一邊。
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 函數 POLYGON-INFRONT
l 參數:
l Polygon1 – 用來確定其它多邊形是否在其“前面”的多邊形。
l Polygon2 – 檢測是否在第一個多邊形“前面”的多邊形。
l 返回值:
l 第二個多邊形是否在第一個多邊形的“前面”。
l 功能:
l 檢測第二個多邊形的每一個頂點是否在第一個多邊形的“前面”。
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 函數 IS-CONVEX-SET
l 參數:
l PolygonSet – 用來檢測是否為“凸多邊形”的圖元集合。
l 返回值:
l 集合是否為“凸多邊形”。
l 功能:
l 相對于集合中的其它多邊形檢查每一個多邊形，看是否位于其它多邊形的“前面”，如果有任意兩個多邊形不滿足這個規則，那么這個集合不為“凸多邊形”。
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
在函數POLYGON-INFRONT中并沒有進行對稱的比較，這意味著如果多邊形A位于多邊形B的“前面”你并不能想當然的認為多邊形B一定位于多邊形B的“前面”。下面的例子簡單的顯示了這一點。
圖1.3
在圖1.3中我們可以看到多邊形1位于多邊形2的“前面”，這是因為頂點p3、p4位于多邊形2的“前面”，而多邊形2卻沒有位于多邊形1的“前面”，因為頂點p2位于多邊形1的“后面”。
對于一個BSP層次樹來說可以用下面結構來定義：
class BSPTree
{
BSPTreeNode RootNode // 樹的根節點
}
class BSPTreeNode
{
BSPTree Tree // 接點所屬的層次樹
BSPTreePolygon Divider // 位于兩個子樹之間的多邊形
BSPTreeNode *RightChild // 節點的右子樹
BSPTreeNode *LeftChild // 節點的左子樹
BSPTreePolygon PolygonSet[] // 節點中的多邊形集合
}
class BSPTreePolygon
{
3DVector Point1 // 多邊形的頂點1
3DVector Point3 // 多邊形的頂點2
3DVector Point3 // 多邊形的頂點3
}
現在你可以看見每一個多邊形由3個頂點來定義，這是因為硬件加速卡使用三角形來對多邊形進行渲染。將多邊形集合分割為更小的子集合有很多方法，例如你可以任意選擇空間中的一個面然后用它來對空間中的多邊形進行分割，把位于分割面正面的多邊形保存到右子樹中而位于反面的多邊形保存到左子樹中。使用這個方法的缺點非常明顯，那就是如果想選擇一個將空間中的多邊形分割為兩個相等的子集合的面非常困難，這是因為在場景中有無數個可選擇的面。如何在集合中選擇一個最佳的分割面呢？下面我將對這個問題給出一個比較適當的解決方案。
我們現在已經有了一個函數POLYGON-INFRONT，它的功能是確定一個多邊形是否位于其它多邊形的正面。現在我們要做的是修改這個函數，使它也能夠確定一個多邊形是否橫跨過其它多邊形定義的分割面。算法如下：
l 函數 CALCULATE-SIDE
l 參數 :
l Polygon1 – 確定其它多邊形相對位置的多邊形。
l Polygon2 – 確定相對位置的多邊形。
l 返回值:
l 多邊形2位于多邊形1的哪一邊
l 功能:
l 通過第一個多邊形對第二個多邊形上的每一個頂點進行檢測。如果所有的頂點位于第二個多邊形的正面，那么多邊形2被認為位于多邊形1的“前面”。如果第二個多邊形的所有頂點都位于第一個多邊形的反面，那么多邊形2被認為位于多邊形1的“后面”。如果第二個多邊形的所有頂點位于第一個多邊形之上，那么多邊形2被認為位于多邊形1的內部。最后一種可能是所有的頂點即位于正面有位于反面，那么多邊形2被認為橫跨過多邊形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
上面的算法也給我們解答了一個問題，當一個多邊形橫跨過分割面時如何進行處理，上面的算法中將多邊形分割為兩個多邊形，這樣就解決了畫家算法中的兩個問題：循環覆蓋和多邊形相交。下面的圖形顯示了多邊形如何進行分割的。
圖1.4
如圖1.4所示，多邊形1為分割面，而多邊形2橫跨過多邊形1，如圖右邊所示，多邊形被分割為2、3兩部分，多邊形2位于分割面的“前面”而多邊形3位于分割面的“后面”。
當建立一個BSP樹時，首先需要確定的問題是如何保證二叉樹的平衡，這意味著對于每一個葉節點的分割深度而言不能有太大的差異，同時每一個節點的左、右子樹需要限制分割的次數。這是因為每一次的分割都會產生新的多邊形，如果在建立BSP樹時產生太多的多邊形的話，在圖形加速卡對場景渲染時會加重渲染器的負擔，從而降低幀速。同時一個不平衡的二叉樹在進行遍歷時會耗費許多無謂的時間。因此我們需要確定一個合理的分割次數以便于獲得一個較為平衡的二叉樹，同時可以減少新多邊形的產生。下面的代碼顯示了如何通過循環多邊形集合來獲得最佳的分割多邊形。
l 函數 CHOOSE-DIVIDING-POLYGON
l 參數:
l PolygonSet – 用于查找最佳分割面的多邊形集合。
l 返回值:
l 最佳的分割多邊形。
l 功能:
l 對指定的多邊形集合進行搜索，返回將其分割為最佳子集合的多邊形。如果指定的集合是一個“凸多邊形”則返回。
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 循環查找集合的最佳分割面。
7 while(BestPolygon = NOPOLYGON)
8 for each 多邊形P1 in PolygonSet
9 if (多邊形P1在二叉樹建立過程中沒有作為分割面)
l 計算被當前多邊形定義的分割面的正面、反面和橫跨過分割面的多邊形的數量。
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 計算被當前多邊形分割的兩個子集合的多邊形數量的比值。
19 if (NumPositive < NumNegative)
20 Relation = NumPositive / NumNegative
21 else
22 Relation = NumNegative / NumPositive
l 比較由當前多邊形獲得的結果。如果當前多邊形分割了較少的多邊形同時分割后的子集合比值可以接受的話，那么保存當前的多邊形為新的候選分割面。
l 如果當前多邊形和最佳分割面一樣分割了相同數量的多邊形而分割后的子集合比值更大的話，將當前多邊形作為新的候選分割面。
23 if (Relation > MinRelation &&
(NumSpanning < LeastSplits ||
(NumSpanning = LeastSplits &&
Relation > BestRelation))
24 BestPolygon = P1
25 LeastSplits = NumSpanning
26 BestRelation = Relation
l 通過除以一個預先定義的常量來減少可接受的最小比值。
27 MinRelation = MinRelation / MINRELATIONSCALE
28 return BestPolygon
算法分析
對于上面的函數來說，根據場景數據大小的不同它可能花費很長一段時間。常量MINRELATIONSCALE用來確定在每次循環時所分割的子集合多邊形數量的比值每次減少多少，為什么要使用這個常量呢，考慮一下，對于給定的MinRelation如果我們找不到最佳的分割面，通過除以這個常量將比值減少來重新進行循環查找，這樣可以防止死循環的出現，因此當這個比值足夠小時我們必定可以獲得可接受的最佳結果。最壞的事情是我們有一個包含N個多邊形的非“凸”集合，分割多邊形將集合分割為一個包含N-1個多邊形的部分和一個包含1個多邊形的部分。這個結果只有在最小比值小于1/(n-1)才是可以接受的（參考算法的19-23行）。這意味著MinRelation /MINRELATIONSCALEi < 1/(n-1)，這里i是循環重復的次數。讓我們假設MinRelation的初始化值為1，由于比值永遠為0-1之間的值因此這是最可能的值（參考算法的19-22行）。我們有
1 / MINRELATIONSCALEi < 1/(n-1)
1 < MINRELATIONSCALEi/(n-1)
(n-1) < MINRELATIONSCALEi
logMINRELATIONSCALE (n-1) < i
這里的i沒有上邊界，但是因為i非常接近于logMINRELATIONSCALE (n-1)，我們可以簡單的假設兩者是相等的。另外我們也假設MINRELATIONSCALE永遠大于或等于2，因此我們可以有
logMINRELATIONSCALE (n-1) = i
MINRELATIONSCALE >= 2
i = logMINRELATIONSCALE (n-1) < lg(n-1) = O(lg n)
在循環的內部，對多邊形的集合需要重復進行兩次循環，因此對我們來說最壞的情況下這個算法的復雜度為O(n2lg n)，而通常情況下這個算法的復雜度接近于O(n2)。
在函數CHOOSE-DIVIDING-POLYGON的循環中看起來如果不發生什么事情的話好象永遠不會停止，但是這不會發生，這是因為如果多邊形集合為非“凸”集合的話總能找到一個多邊形來把集合分割為兩個子集合。CHOOSE-DIVIDING-POLYGON函數總是選擇分割集合的多邊形數量最少的多邊形，為了防止選擇并不分割集合的多邊形，分割后的子集合的多邊形數量之比必須大于預先定義的值。為了更好的理解我上面所講解的內容，下面我將舉一個例子來說明如何選擇一個多邊形對一個很少數量多邊形的集合進行分割。
圖1.5
在上面的例子中無論你選擇多邊形1、6、7還是多邊形8進行渲染時都不會分割任何其它的多邊形，換句話說也就是所有的其它多邊形都位于這些多邊形的“正面”。
關于分割時選擇產生多邊形最少的分割面另外一個不太好的原因是大多數時候它所產生的層次樹通常是不平衡的，而一個平衡的層次樹在運行的時候通常比不平衡的層次樹性能更好。
當獲得最佳的分割面后伴隨著必然產生一些被分割的多邊形，如何對被分割的多邊形進行處理呢，這里有兩個方法：
1. 建立一個帶葉節點的二叉樹，這意味著每一個多邊形將被放在葉節點中，因此每一個被分割的多邊形也將被分開放在二叉樹的一邊。
2. 另外一個方法是將被分割的多邊形保存到公共節點中，對每一個子樹重復這個過程直到每一個葉節點都包含了一個“凸”多邊形集合為止。
產生帶葉節點的BSP樹的算法如下：
l 函數GENERATE-BSP-TREE
l 參數:
l Node – 欲建立的類型為BSPTreeNode的子樹。
l PolygonSet – 建立BSP-tree的多邊形集合。
l 返回值:
l 保存到輸入的父節點中的BSP-tree。
l 功能:
l 對一個多邊形集合產生一個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)
算法分析
函數CHOOSE-DIVIDING-POLYGON的時間復雜度為O(n2 lg n)，除非出現遞歸調用否則它將控制其它的函數，如果我們假設對多邊形集合的分割是比較公平的話，那么我們可以通過公式來對函數GENERATE-BSP-TREE的復雜度進行表達：
T(n) = 2T(n/2) + O(n2 lg n)
通過公式我們可以知道這個函數的復雜度為Q (n2 lg n)。這里n為輸入的多邊形集合的多邊形數量。
下面我要用一個例子來演示如何產生一個BSP-tree。下面的結構是一個多邊形的原始集合，為了表示方便對每一個多邊形都進行了編號，這個多邊形集合將被分割為一個BSP-tree。
圖1.6
為了能夠運行這個算法我們必須對常量MINIMUMRELATION和MINRELATIONSCALE進行賦值，在實際運行中我們發現當MINIMUMRELATION=0.8而MINRELATIONSCALE=2時可以獲得比較好的結果。但是你也可以對這些數值進行試驗來比較一下，通常當常數MINIMUMRELATION比較大時獲得的層次樹會比較平衡但同時分割產生的多邊形也會大量增加。在上圖顯示的多邊形集合并不是一個“凸”的，因此首先我們需要選擇一個合適的分割面。在快速的對上面的結構進行一下瀏覽后我們可以知道多邊形（1、2、6、22、28）不能被用來作為分割面，這是因為它們定義了包含所有多邊形集合的外形。但是其它的多邊形都可以作為候選的分割面。分割產生的多邊形最少同時分割為兩個子集合的多邊形數目之比為最佳的多邊形是16與17，它們位于同一條直線上同時并不會分割任何的多邊形。而分割后的子集合的多邊形數目也是一樣的，都是“正面”為13而“反面”為15。讓我們選擇多邊形16作為分割面，那么分割后的的結構如下：
圖1.7
現在從圖1.7我們可以看到無論是左子樹還是右子樹都沒有包含“凸”多邊形集合，因此需要對兩個子樹繼續進行分割。
在左子樹中多邊形1、2、6、7作為多邊形集合的“凸邊”不能用做分割面，而多邊形4、10在同一條直線上同時沒有分割任何多邊形，而分割后的多邊形子集合：“正面”為8而“反面”為7非常的平衡，我們選擇多邊形4為分割面。
在右子樹中多邊形16、17、22、23、28不能作為分割面，而多邊形18、19、26、27雖然沒有分割任何多邊形但是分割后的多邊形子集合：“正面”為11而“反面”為3，3/11這個比值小于最小比值0.5因此我們需要尋找其它更適合的多邊形。多邊形20、21、24、25都只分割了一個多邊形，但是多邊形21看起來分割后的結果更合理，在分割過多邊形22后多邊形子集合的結果為：“正面”為8而“反面”為6。
下圖顯示了操作后的結果：
圖1.8
在圖中每一個子集合還不是一個“凸”集合，因此需要繼續進行分割，按照上面的法則對圖1.8所示的結構進行分割后，結果如下：
圖1.9
上圖顯示了最后的結果，這可能不是最優的結果但是我們對它進行處理所花費的時間并不太長。
渲染BSP
現在我們已經建立好一個BSP樹了，可以很容易對樹中的多邊形進行正確的渲染，而不會產生任何錯誤。下面的算法描述了如何對它進行渲染，這里我們假設函數IS-LEAF的功能為給定一個BSP節點如果為葉節點返回真否則返回假。
函數DRAW-BSP-TREE
參數:
l Node – 被渲染的節點。
l Position – 攝象機的位置。
l 返回值:
l None
l 功能:
l 渲染包含在節點及其子樹中的多邊形。
DRAW-BSP-TREE (Node, Position)
1 if (IS-LEAF(Node))
2 DRAW-POLYGONS (Node.PolygonSet)
3 return
l 計算攝象機包含在哪一個子樹中。
4 Side = CLASSIFY-POINT (Node.Divider, Position)
l 如果攝象機包含在右子樹中先渲染右子樹再渲染左子樹。
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)
用這個方法進行渲染并沒有減少渲染到屏幕上的多邊形數量，由于一個場景可能包含成百上千個多邊形因此這個方法并不是很好的解決方案。通常情況下有大量的節點和多邊形并沒有處于攝象機的視野范圍之內，它們并不需要被渲染到屏幕上，如何查找這些不可見的節點和多邊形防止它們渲染到屏幕上呢，隱藏面剔除就是為了解決這個問題而提出一項技術，在下一節中我們將對這項技術進行詳細的闡述。
BSP技術詳解2
eXtreme3D
第二節 隱藏面剔除
對不可見物體進行剔除是游戲行業為了滿足提高畫面渲染速度的要求而產生的一項技術，就是在硬件加速技術飛躍發展的今天，雖然現在已經可以完成許多在過去被認為是不可能實現的工作，但是對于隱藏面進行剔除仍是加速圖形渲染的一項重要技術。通常當一個游戲運行的時候，它最少需要以每秒30幀的速度運行。在幾年前這意味著如果每一幀你渲染的帶紋理的多邊形數量超過5000個就被認為是不可接受的，而現在幾乎所有的商業顯卡每一秒都可以渲染幾千萬個多邊形。可是現在仍然需要使用隱藏面剔除這項技術，這是為什么呢？顯而易見，對不可見物體渲染以后將會被可見物體遮擋住，這樣做無謂的浪費了顯卡的帶寬，但是同時它也增加了場景的細節，使游戲畫面看起來更加吸引人。現在的問題是多大程度上來剔除隱藏的多邊形，象view frustum culling和portal渲染這樣的技術來剔除一個不可見多邊形是非常耗費時間的，用來去做這些計算的CPU時間可以用來完成其它諸如AI或碰撞檢測這樣的工作，因此開發一個隱藏面剔除算法必須注意到這一點。對于現在的游戲來說幾乎沒有一個是將每一個隱藏的多邊形都進行剔除，而是剔除一個多邊形的集合如一個節點或一個物體等等。對于一個單獨的多邊形它并不進行剔除，因此一個正確的隱藏面剔除方案是允許一定的重復渲染來適當的減少計算量。
當建立一個FPS游戲時進行隱藏面剔除最通常的方法是使用portal渲染。這項技術可以非常充分的利用BSP的優點，但是請注意portal技術并不僅僅只能用于BSP中。Portal技術還可以用來產生一些特效如鏡子和監視器等等。
Portal渲染
在這里我將介紹一下portal技術的原理，通常對于一個室內場景來說它可以被描述為由一個個“洞口”相互連接的“房間”組成，這里“洞口”被稱為portal而“房間”被稱為sector，通常sector被定義為一個“凸”的“閉合”的多邊形集合，定義中的“凸”閱讀過前面的內容你應當已經能很好的理解了，而“閉合”是什么意思呢？它意味著在sector內部任意連接兩個頂點做一條線段，這條線段不會和其它的多邊形相交。換句話說如果你想在sector內部任意畫一條線段通到sector的外部必定與組成sector的多邊形相交。這也意味著連接每一個sector的“洞口”必須被一個組成portal的多邊形所填充，而對于放置portal多邊形來說你既可以手工放置也可以由程序自動產生，在我講解這項技術之前我必須提醒一下，由于硬件加速Z緩沖的出現對sector必須為“凸”的限制已經消除，因此有許多游戲引擎已經不再遵守這個標準，但是在這里我還是要對過去的方法進行一下介紹。
一個portal引擎的基本方法是當你通過一個指定觀察位置的可視平截體（view frustum）進行渲染時，如果一個portal出現在可視范圍內，那么portal將對可視平截體進行剪切，這樣與其相連的sector將會通過一個觀察位置相同但已經改變過的可視平截體進行渲染。這是一個非常簡單而且非常適合進行遞歸調用的方法，由于可視平截體被portal進行了精確的限制，因此被隱藏的物體可以很簡單進行剔除。下面的例圖顯示了一個portal引擎中的可視平截體是如何被剪切的。
圖6.10
在圖6.10中觀察者的位置位于V，而初始的可視平截體為F1，當它通過一個portal多邊形P1后被P1剪切產生新的可視平截體F2，接著當它通過portal多邊形P2、P3后F2被剪切為F3、F4，而F3通過P4后被剪切為F5而F4被剪切為F6。觀察這個過程我們可以發現portal技術非常適合進行遞歸調用。
接著需要考慮的是如何對物體進行揀選剔除，通常對于所有的3D引擎來說都需要通過一系列步驟來加速這個處理過程，回憶一下前面講解的內容，這個過程首先要計算出物體的“最大包圍球”或是“最大包圍盒”，它是包含了物體所有頂點的最小包圍體，接著用包圍體來和“可視平截體”每一個剪切面進行碰撞檢測，如果包圍體位于每一個剪切面的“反面”那么物體將不會進行渲染，下圖顯示了這個過程：
圖6.11
圖中物體1位于右剪切面的“正面”但位于左剪切面的“反面”因此它將不會被渲染，而物體2不僅位于左剪切面的“正面”而且有一部分位于右剪切面的“正面”因此將會被渲染出來。
Portal技術最初的想法是通過剪切多邊形來保證只有物體可見的部分被渲染出來，也就是無效渲染的多邊形數量為0。但是現在這種想法被認為不是很理想，因為它無謂的浪費了處理時間。但是由于一個多邊形在遞歸循環過程中將被遍歷多次因此我們需要知道在渲染場景時它是否已經被渲染過，一個較好的方法是使用一個幀數來標識這個多邊形，這樣可以很容易的來描述這個多邊形在上一幀是否被渲染過。再看一下圖6.10中最右邊的墻，它同時通過F5和F6來進行渲染，通過對它進行標識我們可以知道它是否被渲染過，否則就會產生Z緩沖錯誤。
為了便于在portal引擎中進行渲染我們需要對“可視平截體”進行一下定義，一個“可視平截體”是一個保存了多個剪切面的結構，每一個剪切面的法線都將指向“可視平截體”的內部，因此在它內部將產生一個閉合的錐體。下面的算法顯示了如何計算一個多邊形是否包含在“可視平截體”的內部。在這個算法中我們使用了一個函數CLASSIFY-POINT，它使用一個剪切面和一個點作為輸入參數。
l 函數INSIDE-FRUSTUM
l 參數:
l Frustum – 用于檢測多邊形是否位于其中的“可視平截體”。
l Polygon – 用于檢測的多邊形。
l 返回值:
l 多邊形是否位于“可視平截體”的內部。
l 功能:
l 使用“可視平截體”的每一個剪切面來對多邊形的每一個頂點進行檢測，如果所有的頂點都位于所有剪切面的“正面”，那么多邊形處于“可視平截體”的內部。
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
在一個portal引擎中它的主渲染函數可以簡單的用下面的方法來實現。
函數RENDER-PORTAL-ENGINE
參數:
Sector – 觀察者所處的sector。
ViewFrustum – 當前的“可視平截體”。
返回值:
None
功能:
渲染portal引擎中的多邊形，場景被描述為由多個portal連接的sectors所組成。
RENDER-PORTAL-ENGINE (Sector, ViewFrustum)
1 for each polygon P1 in Sector
2 if (P1是一個portal and INSIDE-FRUSTUM (ViewFrustum, P1))
3 NewFrustum = CLIP-FRUSTUM (ViewFrustum, P1)
4 NewSector = 獲得由當前sector通過portal P1相連接的sector
5 RENDER-PORTAL-ENGINE (NewSector, NewFrustum)
6 else if (P1任然沒有被渲染)
7 draw P1
8 return
如何放置portal
正如我前面提到的在一個portal引擎中最大的問題就是如何放置portal，如果手工來放置它的話非常花費時間，同時要求地圖的設計者有熟練的技巧。因此一個良好的自動放置portal的算法非常有必要，在這里我將要介紹一下關于這方面的幾個解決方案，這些方案都使用了BSP。
我介紹的第一個解決方案是由瑞典DICE公司的Andreas Brinck提出的，它的原理非常簡單，觀察一下一個完整的BSP層次樹，可以發現這樣一個現象，對于每一個portal來說它必定與BSP層次樹中由分割多邊形定義的分割面位置相同，因此在相同的位置上我們可以在分割面之外建立一個portal多邊形，portal多邊形被初始化為一個矩形，這個矩形的大小將超過portal所處的BSP節點的“最大包圍盒”的大小，接著將portal多邊形放入包含它的節點所位于的子樹中，當節點不是葉節點時，那么portal將繼續被傳送到節點的子樹中，這樣子節點中的分割面將對它進行分割，而當包含它的節點為葉節點時，它也會被節點中的多邊形進行剪切，因為portal初始化的大小超過了節點的范圍。當portal被分割后，被分割的兩個部分會繼續傳送到最頂層的節點重復這個過程，而當portal不需要進行分割時，根據它所處于分割面的位置來放置到相應的子節點中，如果位于分割面的“正面”它將被放置在右子樹中，而當它位于分割面的“反面”將被放置于左子樹中。如果portal正好位于分割面之上它將同時放在左右子樹中。
為了方便方便將所有的portal放置到BSP中我們需要定義如何對一個多邊形進行分割，為了方便使用我們假設完成這個功能的函數為INTERSECTION-POINT，它將返回一個面與一個線段的交點。
l 函數CLIP-POLYGON
l 參數:
l Clipper – 去分割其它多邊形的多邊形或面。
l Polygon – 被分割的多邊形。
l 返回值:
l 被分割后的兩個部分。
l 功能:
l 由指定的分割面來分割多邊形。如果多邊形沒有被分割將會返回一個空的多邊形。
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)
現在我們可以定義如何在一個BSP層次樹中對portal進行分配了，在算法中portal被初始化為一個大于BSP根節點“最大包圍盒”的多邊形。
l 函數PLACE-PORTALS
l 參數:
l PortalPolygon – 放置到BSP中的多邊形。
l Node – 我們當前遍歷的節點。
l 返回值:
l None
l 功能:
l 放置一個portal多邊形到BSP層次樹中，如果需要的話對它進行剪切。這個函數將會產生一個節點將由portal連接而每一個節點將包含一個portal多邊形列表的BSP層次樹。
PLACE-PORTALS (PortalPolygon, Node)
1 if (IS-LEAF (Node))
l 將portal和節點中的每一個多邊形進行檢測。當portal所包含的多邊形和由一個多邊形定義的面相交時它將被這個面進行分割，分割后的兩個部分將被重新傳送到最頂層的節點中繼續進行檢測。
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 從當前節點中將portal的多邊形剔除，因為它的位置和節點中一個多邊形的位置相同。
l 參考下面的描述。
11 添加當前節點到portal多邊形所連接的節點集合中。
12 else
13 if (當前節點的分割多邊形沒有放置在樹中)
14 建立一個多邊形P，它的大小將超過包含當前節點所有多邊形的最大包圍盒的范圍，并且和分割多邊形的位置相同。
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行進行一下解釋，當剔除和當前節點中一個多邊形位置相同的portal多邊形部分將會產生什么樣的結果。參考一下圖6.12。
圖6.12
在圖6.12中一個portal已經到達了一個葉節點，圖中灰色的區域是是portal多邊形在遍歷BSP樹過程中被剔除的區域稱它為1。而圖中標注為2、3、4的亮灰色部分是和portal多邊形位置相重疊的多邊形，因此這一部分的portal多邊形也將會被剔除，而剩下的部分5將被用來做為一個portal。
在上面的算法第一次看的話會覺的非常復雜，但實際上它非常簡單和容易理解，最終的結果就是每一個portal將會在兩個節點上結束而對于任一個portal來說它必定可以和一個portal之間相互可見。在下面我將用一個實際的例子來解釋一下這個算法。
圖6.13
對于圖6.13中的結構，需要進行下面的幾步：
第一步，portal多邊形s1進入節點n1中。
在節點n1中portal多邊形s1將會被分割，因為它的一部分和節點中間的一個多邊形位置相同，因此portal多邊形s1將會被分割為兩部分分別為p1、p2，重疊的部分被剔除。
第二步，p1、p2進入節點s2中。
在節點s2中由于p1位于分割面s2的“正面”，因此將和分割面s2一起被送入到節點n2中，而p2由于位于分割面s2的“反面”，因此將和分割面s2一起被送入到節點s3中。由于p1、p2沒有和分割面相交因此這一步沒有出現分割操作。
第三步，p1、s2進入節點n2中。
在節點n2中n2被認可作為一個portal，因此在節點n1和n2中它不會再發生任何變化。而多邊形p3的一部分將會被剔除，因為它的一部分和節點中間的一個多邊形位置相同，在上一步中多邊形s2也被送入到節點s3中，而在這里它又被稱為p3。
第四步，p3和s3進入節點n3中。
在節點n3中多邊形p3被認可為一個portal，而多邊形s3的一部分因為和上面的原因一樣被剔除，同時在這里它又被稱為p4。
第五步，p2和p4進入節點s4中。
沒有任何多邊形要進行分割，因此多邊形p2和p4將與s4一起被送入節點n4中，而s4將被單獨送入節點n5中。
第六步，p2、p4和s4一起進入節點n4中。
無論是p2還是p4都不需要分割，但是由于s4和中間的一個多邊形完全重疊因此將會被剔除。
第七步，結束，沒有任何多邊形進入節點n5中。
這個節點將沒有portal，因為對于任何節點來說它都是不可見的，而從這個節點位置上將不會看見任何一個節點。
結果：
portal p1同時位于節點n1和n2中；
portal p2同時位于節點n1和n4中；
portal p1同時位于節點n2和n3中；
portal p1同時位于節點n3和n4中。
上面我所講解的內容是建立一個簡單的portal引擎所必備的功能，它能給我們提供一個較高的運行幀速。
PVS
一個portal引擎雖然能夠提供許多非常好的特性，但是它的結構太復雜。當你使用portal技術來構建一個游戲引擎時你會發現它存在許多問題，最大的一個問題是在渲染場景的每一幀都需要進行可視性檢測，這會產生大量的多邊形剪切操作，在場景非常復雜的情況下，運算的費用會非常的高，因此需要尋找一種技術來對場景中可視性檢測進行預計算而不是在運行期間進行計算。PVS（Potentially Visible Set）可視性集合，就是為了解決這個問題而出現的一項技術，可以通過對BSP中每一個葉節點設置一個PVS，這個PVS保存了從第一個葉節點開始看到的葉節點集合，它不僅可以用來幫助加速場景渲染，還可以用來加速場景中光照運算和進行網絡優化。
PVS是在場景進行預渲染時計算出來的，每一個BSP的葉節點都保存一個可視節點的集合，當對場景進行渲染時，攝象機所在的葉節點將被渲染，同時保持在PVS中的葉節點也將會被渲染出來，這里需要一些算法來避免場景重復渲染，由于今天硬件加速卡的發展，它所提供的硬件Z緩沖的大小已經可以方便的解決這個問題。
計算PVS
如果要求PVS必須在BSP的葉節點之間進行標準的光線跟蹤計算，來查找一下在一個葉節點中任一個點是否在其它葉節點中可見。為了加速光線跟蹤的計算，在每一個葉節點中必須指出一些典型的位置點來避免無謂的計算，現在的問題就是如何放置這些典型的點。
對于一個portal引擎的portal來說，典型點可以沿著樹的分割面放置，這是因為只有在兩個portal是相互開放的情況下才可以進行可視化檢測。如果位于一個葉節點中間的一個點被從另一個葉節點發射出來的光線認為是可見的話，那么這條光線必然通過連接兩個節點的portal，參考下圖：
圖6.14
在圖6.14中我們可以看見如果在一個節點中的一個點可以從其它節點看見，那么視線必然通過兩個節點相互連通的區域。這是非常明顯的，如果視線被物體阻斷的話那么兩點之間必定不可見。因此將典型點放置在兩個節點之間所開放的區域是非常合適的，下面描述的算法將在一個BSP樹上放置典型點。對于這個函數需要一組幫助函數來把點放置在一個節點上，它們是
l DISTRIBUTE-POINTS (Node) 這個函數將按照一定的間隔沿著給定節點的分割面來放置點，點的位置會處于節點包圍盒的內部。它將返回一個點的集合，復雜度為O(xy)，這里x為節點包圍盒內分割面的寬度，而y為高度。
l CLEANUP-POINTS (Node, PointSet) 從點的集合中剔除不合格的點，這些點可能和節點中的一個多邊形位置相同，也可能是位于節點包圍盒的外部。函數的復雜度為O(np)，這里n為節點中多邊形的數量而p為集合中點的數量。
l 函數 DISTRIBUTE-SAMPLE-POINTS
l 參數:
l Node – 當前我們遍歷的節點。
l PointSet – 放置到給定節點子樹中的點的集合。
l 返回值:
l None
l 功能：
l 沿著給定節點的分割面放置點。它將按照分割面的位置來對輸入的點進行檢測，如果這些點和節點中的一個多邊形位置相同，或者位于節點包圍盒的外部那么將會被剔除。新產生的點將會被添加到左、右兩個集合中，當一個點的集合遍歷到一個葉節點時那么它就是這個葉節點的典型點。
DISTRIBUTE-SAMPLE-POINTS (Node, PointSet)
1 CLEANUP-POINTS (Node, PointSet)
2 if (IS-LEAF (Node))
3 設置點的集合為當前節點的典型點。
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)
算法分析
每一次調用這個函數的復雜度為O(np + xy)（參考函數CLEANUP-POINTS和
DISTRIBUTE-POINTS），為了計算完整的復雜度我們可以用下面的公式來表示（我們假設典型點的集合同時分布在兩個集合之中）：
T(n) = 2T(n/2) + O(np + xy)
這個函數第一次調用時將會從BSP樹的根節點開始并會傳入一個空的集合。換句話說它是按照下面的方法進行的，它是從被BSP樹根節點所定義的分割面上的點開始的，由于一個面的大小沒有限制因此也會有無限個典型點，因此就需要對典型點進行限制，這個現在就是根節點的包圍盒。
在根節點上獲得合格的典型點后需要把所有的點發送到根節點的兩個子樹中，當一個典型點的集合進入一個節點后會被分割為兩個部分，一個部分包含了所有位于節點分割面的“正面”的點，而另一部分包含了所有位于節點分割面的“反面”的點。而位于分割面上的點將會同時放在兩個集合中。接著“正面”集合將會被傳入到右子樹中而“反面”集合將會被傳入到左子樹中。重復這個過程直到進行到葉節點時結束，在這些操作后每一個葉節點將包含一個典型點的集合，這些點都位于節點所連通的地方。
如果我們現在在這個階段對每一個節點進行光線跟蹤那么是非常耗費時間的，但是如果我們知道葉節點是與哪一個節點相連的，那么這個過程將會變的簡單，因為這樣可以減少一些不必要的光線跟蹤運算。查找相互連接的葉節點非常簡單，可以通過檢測每一個葉節點的典型點來查找，如果同時有兩個節點共享一個點那么這兩個節點必然是相互連通的，因為在遍歷BSP樹放置典型點的過程中，點不是沒有放置到節點上就是同時放置在兩個節點上。當我們知道哪些節點是相互連通的，就可以定義進行光線跟蹤的算法了，不過首先我們需要定義一些幫助函數。
為了方便進行光線跟蹤我們需要一些基本的光線跟蹤函數，BSP樹是非常適合進行光線跟蹤的結構，因為大部分不可見的區域通過BSP樹可以很簡單的剔除掉，不用進行遍歷，因此花費的時間也非常少。我們需要的函數如下：
POLYGON-IS-HIT (Polygon, Ray) 返回光線是否和多邊形相交。
RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray) 返回光線是否和節點中的子樹相交。
INTERSECTS-SPHERE (Sphere, Ray) 返回光線是否和球體相交。
CREATE-RAY (Point1, Point2) 通過兩個點來建立一條光線。
上面的函數RAY-INTERSECTS-SOMETHING-IN-TREE是一個非常有趣的函數，因為它顯示了一些BSP樹的優點，同時也顯示了如何使用BSP樹來加速光線跟蹤的處理。它是一個遞歸函數，首先在樹的根節點上使用，偽算法如下：
l 函數RAY-INTERSECTS-SOMETHING-IN-TREE
l 參數：
l Node – 用來進行跟蹤的節點。
l Ray – 用來進行求交的光線。
l 返回值：
l 光線是否和節點中的物體相交。
l 功能：
l 檢測光線是否與給定節點極其子樹中的物體相交。
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 如果光線和節點的分割面相交或和分割面的位置重疊，對節點的兩個子節點進行檢測。
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 如果光線只位于分割面的“正面”對節點的右子樹進行檢測。在if語句中使用or操作符是因為光線的一個端點可能與分割面的位置重疊。
10 if (startSide = INFRONT or endSide = INFRONT)
11 if(RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
12 return true
l 如果光線只位于分割面的“反面”對節點的左子樹進行檢測。在if語句中使用or操作符是因為光線的一個端點可能與分割面的位置重疊。
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樹中每一個節點，這樣光線將與節點中每一個單獨的多邊形進行檢測，這時函數的復雜度將為O(n)，這里n為BSP樹中所有多邊形的數量。一般情況下光線并不會檢測樹中的每一個節點，這樣將會大大減少進行檢測的多邊形數量。最佳的情況是光線被限制在一個節點中，這時函數的復雜度接近于Ｏ(lg n)．這取決于BSP樹的結構大小。
l 函數CHECK-VISIBILITY
l 參數：
l Node1 – 開始處的節點。
l Node2 – 結束處的節點。
l 返回值：
l Node2是否可以被node1看見。
l 功能：
l 在兩個葉節點的典型點之間進行跟蹤，檢測兩個節點之間是否可見。
CHECK-VISIBILITY (Node1, Node2)
1 Visible = false
2 for each 典型點P1 in Node1
3 for each 典型點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
算法分析
函數CHECK-VISIBILITY非常耗費時間，當我們在兩個葉節點之間進行光線跟蹤來檢測兩者之間是否可見時，我們不得不從Node1的每一個典型點開始對Node2的每一個典型點進行跟蹤，最壞的情況是每一次跟蹤都將對樹中所有的多邊形進行檢測，這時函數的復雜度O(s1 s2 p)，這里s1為Node1中典型點的數量，s2為Node2中典型點的數量，p為樹中多邊形的數量。通常它的性能是比較好的，接近于O(s1 s2 lg p)。
l 函數TRACE-VISIBILITY
l 參數：
l Tree – 去進行光線跟蹤的BSP-tree。
l 返回值：
l None
l 功能：
l 對于樹中每一個葉節點，它將進行光線跟蹤運算來檢測和它相連的節點的可見性。每一個被發現是可見的節點將會被添加到當前節點的PVS中。當一個葉節點發現是可見的，我們還要對和它相連的節點進行光線跟蹤運算來檢測可見性。
TRACE-VISIBILITY (Tree)
1 for (each 樹中的葉節點L)
2 for (each 和葉節點L相連的葉節點C)
3 添加節點C到節點L的PVS中
4 for (each 樹中的葉節點L1)
5 while (在葉節點L的PVS中存在一個葉節點L2，它所連接的節點沒有進行可見性檢測)
5 for (each 連接到節點L2中的葉節點C)
6 if (節點C沒有位于節點L1的PVS中 and
CHECK-VISIBILITY (L1, C))
7 添加節點C到節點L1的PVS中
7 添加節點L1到節點C的PVS中
算法分析
如果我們沒有使用根據葉節點的相連情況來進行處理的優化技術，那么必須對樹中的每一個葉節點進行檢測，這時函數的復雜度為O(n2)，這里n為樹中葉節點的數量。要對上面的算法估計一個對處理過程提高了多少性能的具體數值非常困難，因為它依賴于所處理的結構的大小。對于每一個葉節點與其它節點都是可見的結構，這個算法不會做任何優化。對于每一個葉節點只有一到二個可見的節點的結構，這個算法將會產生非常大優化，它的復雜度接近與O(n)。
現在在一個設計良好的地圖上所產生的結構在每一幀上將會避免檢測大量的多邊形。一個設計良好的地圖在建立時將會考慮物體的可見性，這意味著應盡可能的在地圖中放入一些能障礙視線的物體，如墻壁等。如果在地圖中包含一個有大量細節的大房間，那么在上面的算法中（或在一個portal引擎中）進行的隱藏面剔除工作對它不會產生任何效果。這時我們需要使用其它類似于LOD這樣的技術來進行多邊形剔除。
靜態物體
考慮一下這樣的場景，一個球體位于一個立方體的中心，如果用BSP對它進行渲染那么將會產生大量的節點，并會產生大量的分割多邊形，這是因為在球體上的每一個多邊形都會送入到葉節點中。如果球體有200個多邊形當渲染時就會產生200個葉節點的BSP樹。這樣做非常影響運行的速度，因此必須尋找一個方法來避免這種現象的發生。
為了解決這個問題地圖的設計者可以選擇組成地圖的幾何體，在上面的例子中也就是立方體，接著將剩余的物體做為靜態物體，它們將不會用來對BSP樹進行渲染或進可見性檢測，但是它們會參與到地圖的光照運算當中去。當進行可見性運算時每一個靜態物體會被添加到BSP樹中，每一個靜態物體的多邊形將會被添加到BSP樹中，這個過程如下：
l 函數PUSH-POLYGON
l 參數：
l Node – 多邊形當前所在的節點。
l Polygon – 將被添加的多邊形。
l 返回值：
l None
l 功能：
l 將多邊形添加到樹中。如果多邊形的一些點與節點的分割面相交將會被分割。分割后的部分將會被繼續向下傳送。當一個多邊形進入一個葉節點后它將被添加到葉節點的多邊形集合中。
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是一個遞歸函數，它將一個多邊形添加到BSP樹中，這個函數對每一個靜態物體的每一個多邊形都會調用一次，
在這個過程處理之后葉節點可能不再成為一個“凸”集合，這在進行碰撞檢測時可能會產生一些問題，后面的內容將會對這個問題進行闡述。
BSP技術詳解3
eXtreme3D
第三節 室內場景中光照運算
關于Radiosity的算法最早是由Goral、Cindy M、Torrance、Kenneth E、Greenberg、Donald P、Battaile和Bennett在論文《Modelling the interaction of light between diffuse surfaces》提出的。他們使用Radiosity來模擬能量在漫反射表面之間進行傳送，漫反射表面對照到表面上的光線在所有的方向上都進行相同的反射，和它相反的是鏡面反射表面，它只在反射方向上傳播反射光。由于漫反射表面的這個特性，這就意味著對于所有的觀察角度而言看起來表面都是相同的，這樣對于場景中的每一個表面只需要進行一次光照運算，而且可以在場景的預渲染時進行，因此這項技術被大量的3D游戲所采用。
下面我再簡短的講解一下Radiosity是如何工作的，而將主要的精力放在如何使用BSP樹來加速Radiosity的計算，對于Radiosity的詳細介紹請參考前面的章節。Radiosity技術是設計用來使場景中光照看起來更加真實和光滑，如果我們使用一個一直向前傳播而不考慮反射的光照模型，那么當場景中的燈光照亮場景中的物體時，并不會計算遠處經過反射過來的光線，這樣場景中的陰影看起來非常尖銳而物體表面也看起來非常不真實。為了使用radiosity技術我們需要把場景分割成一塊一塊很小的部分，每一部分我們稱它為patch，每一個patch都有一個初始化的能量級別，如果它不是一個燈光這樣的發光體的話通常為0，有許多方法來分配場景中的能量，這里我們將要使用的方法稱為交互式radiosity。這個方法的過程是我們從場景中未發送能量的級別最高的patch開始發送能量，能量經過傳遞后將不再發送能量的patch的等級設為0，重復這個過程直到場景中的每一個patch的能量等級都小于一個預定值為止。
當能量從一個patch（j）開始發送到另一個patch（i）時我們使用下面的公式：
Bi = Bi + Bj * Fij * Ai / Aj
這里Bi = patch（i）的能量級別 Bj = patch（j）的能量級別
Ai= patch（i）的作用區域 Aj = patch（j）的作用區域
Fij = patch（i）與patch（j）之間的系數
在公式中系數Fij是由以下公式來確定的：
Fij = (cos qi * cos qj) / d2 * Hij
這里Fij = patch（i）與patch（j）之間的系數
qi = patch（i）與patch（j）法線之間的夾角
qj = patch（i）與patch（j）法線之間的夾角
d = patch（i）與patch（j）之間的距離
Hij = patch（i）與patch（j）之間的可見性系數。如果在兩個patch之間只有一條光線可以跟蹤，這個值為1，如果沒有光線可以跟蹤為0。一般情況下由于每一個patch都不是一個點而是一個區域，因此光線有很多條。
從上面的公式中我們可以看到在場景中進行radiosity計算是非常耗費時間的。這個函數的復雜度為O(n3)，這里的n為場景中patch的數量。由于對于場景中每一個patch你需要發送最少一條光線到其它patch上，因此需要對場景中的幾乎所有的多邊形都進行光線跟蹤計算。在上面的公式中系數H的計算非常耗費時間，下面我們將看一下如何在BSP樹中對它的計算進行優化。
BSP樹中的radiosity計算
在進行場景中的光照計算之前需要把場景中的面分割為patch，一個方法是在開始的時候設定每一個patch為預定的大小，當計算每一個patch的能量時，如果在patch上的能量足夠大，對這個patch進行分割。不過這個方法是非常耗費時間的，因此必須尋找一個更好的方法來通過BSP樹對計算進行優化。
在radiosity的一般算法中場景中的每一個光源都被看作為一個或多個patch，這里我們可以改進一下，將每一個光源放在它所位于的葉節點中，接下來每一個光源都發送自己的能量到場景中所有的patch上，當這個過程完成后radiosity計算也就結束了。為了使最后的結果看起來更好可以使用一種稱為“漸進精選”（progressive refinement）的技術來對這個方法進行很小的修改。在每一次過程中，葉節點中具有高能量的patch將發送能量到其它低能量的patch上，這樣做的結果是高亮度的patch將發送能量到處于陰影中patch上。這是因為在實際生活中并沒有真正黑暗的地方，它多多少少要獲得一些其它物體反射過來的光亮。
由于計算非常耗費時間需要做一下優化，使用渲染BSP樹時獲得的PVS信息可以在選擇哪些patch將接受能量時剔除一些無用的計算。因為在計算PVS時使用了相同的方法來進行光線跟蹤。
通過場景來分配能量的算法如下：
l 函數RADIOSITY
l 參數：
l Tree – 進行radiosity計算的BSP樹。
l 返回值：
l None
l 功能：
l 在場景中的patch之間發送能量。
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是為了讓地圖編輯者在任何時候都可以檢查場景渲染的效果，如果他感到看起來已經足夠好了可以中斷能量的傳播。
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.
復雜度分析
這個函數的運算費用實在是太高昂了，可以稱為時間殺手，在最壞的情況下每一條光線將不得不檢測場景中的每一個多邊形，此時復雜度為O(n3)，這里n為樹中patch的數量。一般情況下由于進行了優化可以減少大量的計算，但是減少多少并不能計算出來，因為這依賴于樹結構的復雜度。
上面的函數給出了一個充分利用BSP樹的優點來加速場景光照運算的方法，尤其是可以顯著的減少光線跟蹤的計算量，而且地圖設計者可以來決定當場景渲染時如果渲染的效果可以接受中斷渲染循環。這對地圖的預渲染實在是太方便了，運行的時間可以根據渲染的效果來決定。
第四節 BSP樹的預渲染
現在我們需要完成一個完整BSP引擎的預處理過程，下面的算法顯示如何將場景渲染到BSP樹中。
l 函數RENDER-SCENE
l 參數：
l Scene – 被渲染的場景
l 返回值：
l 一個BSP樹。
l 功能
l 預渲染來獲得一個包含場景信息的BSP樹。
RENDER-SCENE (Scene)
l 使用描述場景中圖元的物體來渲染BSP樹。
1 GeometryPolygons = {}
2 for (每一個包含場景圖元的物體object O)
3 GeometryPolygons = GeometryPolygons U O.PolygonSet
4 GENERATE-BSP-TREE (Tree.RootNode, GeometryPolygons)
l 分配葉節點上的取樣點。
5 DISTRIBUTE-SAMPLE-POINTS (Tree.RootNode, {})
6 TRACE-VISIBILITY (Tree)
7 for 每一個場景中的靜態物體object O
8 for 物體O中每一個多邊形P
9 PUSH-POLYGON (Node, P)
l 函數CREATE-PATCHES是一個未定義的函數，由于我們的解決方案效率并不是太好，因此沒有對它進行詳細的介紹。
10 CREATE-PATCHES (Tree)
11 RADIOSITY (Tree)
復雜度分析
函數的復雜度如下：
函數 最壞情況 一般情況 描述
GENERATE-BSP-TREE O(n2 lg n) O(n2) n為場景中多邊形的數量
DISTRIBUTE-SAMPLE-POINTS Q (np + xy) Q (np + xy) n為樹中多邊形的數量，p為樹中典型點的數量，x和y為分割面的寬度和高度。
TRACE-VISIBILITY O(n2) O(n lg n), n為樹中多邊形的數量。
RADIOSITY O(n3) O(n2 lg n) n為樹中patch的數量
在一般情況這一列中顯示了算法通常所需運行的時間，對算法時間影響最大的是函數RADIOSITY，它使整個算法的復雜度趨向于O(n3)。