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
|