BSP TREE(occlusion culling)

BSP樹(1)

文檔提供者：newebug () 於 2005-3-15

1 背景
BSP樹1969年發明，90年代後用到遊戲中。
BSP樹是一個結構，可以分割為子集。BSP算法在pre-processing的時候處理多邊形，而不是在run-time。
BSP樹的結構定義如下：
class BSPTree
{
 BSPTreeNode RootNode
}
class BSPTreeNode
{
 BSPTree Tree
 BSPTreePolygon Divider
 BSPTreeNode *RightChild
 BSPTreeNode *LeftChild
 BSPTreePolygon PolygonSet[]
}
class BSPTreePolygon
{
 3DVector Point1
 3DVector Point2
 3DVector Point3
}

你可以將場景(scene)中的部分或全部的多邊形(polygon)劃分成一個個小集合(convex set)，在這些集合中每個多邊形都在其他任何多邊形的前麵。當polygon1中的所有點都在polygon2的前麵的時候，我們說polygon1在polygon2的前麵。

點在麵前麵的算法如下：
CLASSIFY-POINT (Polygon, Point)
SideValue = Polygon.Normal × Point
if (SideValue = Polygon.Distance)
 then return COINCIDING
else if (SideValue < Polygon.Distance)
 then return BEHIND
else return INFRONT

判斷麵在麵前麵的算法如下：
POLYGON-INFRONT (Polygon1, Polygon2)
for each point p in Polygon2
 if (CLASSIFY-POINT (Polygon1, p) <> INFRONT) then return false
return true

判斷是否是一個convex set的算法如下：
IS-CONVEX-SET (PolygonSet)
for i = 0 to PolygonSet.Length ()
 for j = 0 to PolygonSet.Length ()
  if(i <> j && not POLYGON-INFRONT(PolygonSet[i], PolygonSet[j])) then return false
return true

判斷多邊形前後的算法如下：
CALCULATE-SIDE (Polygon1, Polygon2)
NumPositive = 0, NumNegative = 0
for each point p in Polygon2
 if (CLASSIFY-POINT (Polygon1, p) = INFRONT)
  then NumPositive = NumPositive + 1
 if (CLASSIFY-POINT (Polygon1, p) = BEHIND)
  then NumNegative = NumNegative + 1
if (NumPositive > 0 && NumNegative = 0)
 then return INFRONT
else if(NumPositive = 0 && NumNegative > 0)
 then return BEHIND
else if(NumPositive = 0 && NumNegative = 0)
 then return COINCIDING
else return SPANNING

上麵的算法中，當返回SPANNING時，說明Polygon2跨越Polygon1，這時，一個通常的算法是將Polygon1分開成兩個多邊形。

有幾個方法可以將場景中的多邊形劃分成所需要的BSP樹，通常的辦法是先定義一個多邊形集合(convex set)，然後在劃分其他的。算法如下：
CHOOSE-DIVIDING-POLYGON (PolygonSet)
if( !IS-CONVEX-SET (PolygonSet) ) then return NOPOLYGON
MinRelation = MINIMUMRELATION
BestPolygon = NOPOLYGON
LeastSplits = INFINITY
BestRelation = 0

while(BestPolygon = NOPOLYGON)
 for each polygon P1 in PolygonSet
  if (Polygon P1 has not been used as divider previously during the creation of the tree)
   NumPositive = 0, NumNegative = 0, NumSpanning 0 0
   for each polygon P2 in PolygonSet except P1
    Value = CALCULATE-SIDE(P1, P2)
    if(Value = INFRONT)
     NumPositive = NumPositive + 1
    else if(Value = BEHIND)
     NumNegative = NumNegative + 1
    else if(Value = SPANNING)
     NumSpanning = NumSpanning + 1
   if (NumPositive < NumNegative)
    Relation = NumPositive / NumNegative
   else
    Relation = NumNegative / NumPositive
  if( (Relation > MinRelation) && (NumSpanning < LeastSplits) || (NumSpanning = LeastSplits) && (Relation > BestRelation) )
   BestPolygon = P1
   LeastSplits = NumSpanning
   BestRelation = Relation
  MinRelation = MinRelation / MINRELATIONSCALE
return BestPolygon