BSP树(1)

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航