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
