1 background
The BSP tree invented in 1969, used in the game after the 1990s.
The BSP tree is a structure that can be divided into a subset. The BSP algorithm handles polygons during pre-processing, not in Run-Time.
The structure of the BSP tree is as follows:
Class Bsptree
{
BSPTREENODE ROOTNODE
}
Class Bsptreenode
{
BSPTree Tree
BSPTreePolygon Divider
BSPTREENODE * RIGHTCHILD
BSPTREENODE * LEFTCHILD
BSPTreePolygon PolygonSet []
}
Class BsptreePolygon
{
3DVector Point1
3DVector Point2
3DVector Point3
}
You can divide some or all of the Scene in the scene into a small collection (Convex Set), where each polygon is in front of any other polygon. When all points in Polygon1 are in front of Polygon2, we say Polygon1 in front of Polygon2.
Front surfaces point in the algorithm is as follows: CLASSIFY-POINT (Polygon, Point) SideValue = Polygon.Normal × Pointif (SideValue = Polygon.Distance) then return COINCIDINGelse if (SideValue The algorithm in front of the face is as follows: Polygon-Infront (Polygon1, Polygon2) for Each Point P in Polygon2 IF (Classify-Point (POLYGON1, P) <> infront) THEN RETURN FALSERTURN TRUE Decision is a CONVEX SET algorithm as follows: Is-convex-set (polygonset) for i = 0 to polygonset.length () for j = 0 to polygonset.Length () ing (i <> j& not polygon-infront) PolygonSet [I], POLYGONSET [J]) THEN RETURN FALSERETURN TRUE Determined before and after the polygon algorithm follows: CALCULATE-SIDE (Polygon1, Polygon2) NumPositive = 0, NumNegative = 0for each point p in Polygon2 if (CLASSIFY-POINT (Polygon1, p) = INFRONT) then NumPositive = NumPositive 1 if (CLASSIFY- POINT (Polygon1, p) = BEHIND) then NumNegative = NumNegative 1if (NumPositive> 0 && NumNegative = 0) then return INFRONTelse if (NumPositive = 0 && NumNegative> 0) then return BEHINDelse if (NumPositive = 0 && NumNegative = 0) Then Return Coincidingelse Return SPANNING In the above algorithm, when returning spanning, the Polygon2 explains the Polygon1, at this time, a typical algorithm is to separate the Polygon1 into two polygons. There are several ways to divide the polygons in the scene into the required BSP tree, and the usual method is to define a polygon set (ConveX SET) and then divide others. The algorithm is as follows: Choose-Dividing-Polygon (POLYGONSET) IF (! Is-convex-set (polygonset)) Then Return NopolyGonMinRelation = MINIMUMRELATIONBESTPOLYGON = NopolygonLeastSplits = infinityBestRelation = 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
