BSP Trees

2.8. BINARY SPACE PARTITIONING TREES Exploration of BSP trees

Overview of binary space-partitioning trees

BSP Tree Hierarchies A binary space-partitioning (BSP) tree recursively partitions space into pairs of subspaces with respect to dividing planes of arbitrary position and orientation. The two partitions are referred to as the positive and negative halfspaces (respectively in front of and behind the dividing plane). A BSP tree is a versatile data structure, capable of performing the same tasks as a k-d tree or octree (but not vice versa). The BSP tree can also be used to provide boundary/solid representations of arbitrary polyhedral scenes.

BSP Tree Hierarchies BSP trees are very versatile in collision detection as they can provide both a spatial partitioning (a nonboundary representation) and a volume representation (a boundary representation, for a solid object). As a volume representation, BSP trees can be used to represent and distinguish the interiors of polygons and polyhedra from their exteriors.

BSP Tree Hierarchies The left figure provides an example of spatial partitioning (with a typical lookup cost of O(log n)). The right figure shows how a BSP tree can map out the exterior/internal of a polygonal object. When, as illustrated, the dividing planes are selected to match the faces of the input geometry it is termed autopartitioning (or polygon aligned). In contrast, dividing planes coplanar to the xy, xz, or yz planes are called axis aligned. Dividing planes that have no restrictions put on them (nor on the partitionings they form) are called arbitrary or general.

Types of BSP Tree: Leaf storing A leaf-storing (or leaf-based) BSP tree stores geometry in the leaves of the tree (rather than in the internal nodes). Each internal node only contains the dividing plane and references to the child subtrees. The dividing planes of leaf-storing trees can be either arbitrary or autopartitioning. An example leaf-storing tree is shown using arbitrary positioning.

Types of BSP Tree: Solid Leaf Solid-leaf BSP trees are built to represent the solid volume occupied by the input geometry, i.e. dividing planes are selected to separate the solid volume from the exterior of the object. No geometry is stored in the tree, with leaf nodes only indicating if the area in front and behind of the dividing plane is empty or solid.

Consider the example in which a solid-leaf BSP tree is constructed to represent the interior of a concave (dart-shaped) polygon. Solid-leaf BSP trees are useful for collision detection as there is no need to perform specific polygon tests (no polygons are explicitly stored).

Overview of how a BSP tree can be constructed

Building the BSP tree Building a BSP tree (either from scratch or recomputing parts of a tree) is computationally expensive, i.e. BSP trees are typically pre-computed and hold static background geometry (moving objects are handled using some other approach). Building a BSP tree involves three steps. 1. Selection of a partitioning plane.

2.Partitioning input geometry into the

positive and negative halfspaces of the dividing plane. Geometry that straddles the plane is split to the plane before partitioning. 3. Recursively repeat the above steps for each subtree until some termination condition is reached.

Building the BSP tree Recursively build a leaf storing BSP using the input list of polygons (depth initially equal to o) BSPNode BuildBSPTree(List polygons, int depth) { if (polygons.empty()) return NULL; If no more polygons are available, then return if (depth >= MAX_DEPTH || polygons.Count ... Testcase Straddling are split, list(s) each polygon against the dividing plane, adding them polygons to their forwarding STRADDLING_PLANE: } Polygon frontPart, backPart; with a part sent to each side } SplitPolygon(polygons[i], out node frontPart, out backPart); Recursively build child subtrees andsplitPlane, return the combined BSPNode frontTree =frontList.AddAtBack(frontPart); BuildBSPTree(frontList, depth + 1); BSPNode backTree = backList.AddAtBack(backPart); BuildBSPTree(backList, depth + 1); break; return new BSPNode(frontTree, backTree); }

Building the BSP tree The PickSplittingPlane() function is non-trivial if a good partitioning plane is to be selected. The condition under which tree construction halts depends on the type of tree. • For a solid-leaf tree construction proceeds until the set of remaining

input polygons becomes empty. • A leaf-storing BSP tree is typically stopped when:

oThe leaf contains less than some preset number of polygons. oA fixed cutoff depth has been reached.

oA good dividing plane cannot be found.

Selecting Dividing Planes The dividing planes selected during tree construction greatly effects the size and shape of the resulting tree (and hence performance and memory). Typically good results can be obtained by trying a number of candidate dividing planes at each level of the tree, picking the one that scores best according to an evaluation function If using autopartitioning then the search is restricted to the supporting planes of the faces in the input geometry. Whilst simple to implement, autopartitioning may produce more splitting than desired in leaf-storing trees – e.g. consider the autopartitioning of a polygon sphere (all convex faces will lie on the same side of the plane, with a resultant tree depth equal to the number of sphere faces!)

Selecting Dividing Planes A good approach of handling detailed objects within a scene, is to use bounding volume approximations of the objects and autopartition through the faces of the bounding volumes before performing any splitting involving the geometry within the bounding volumes. Alternative candidate dividing planes can include planes in a few predetermined directions (e.g. coordinate axes) or evenly distributed across the extents of the input geometry (i.e. forming a grid across the geometry). Arbitrary planes can also be selected through a hill-climbing approach whereby, repeatedly, a number of slightly different planes to a candidate plane are tested to determine the new candidate plane.

Evaluating Dividing Planes Evaluation criteria of use to collision detection includes picking planes so as to minimize splitting of geometry (least-crossed stragegy) or to attempt to balance the geometry equally on both sides of the splitting plane. The approaches tend not to be complementary, with a strong focus on one criteria likely to provide poor performance in the other criteria. A weighted linear combination of the two is often used in practice (with reduced splitting often weighted higher than balancing).

Line A minimises split polygons; Line B balances the number of polygons; Line C represents a compromise.

Classifying Polygons with Respect to a Plane When building a BSP tree, all polygons need to be partitioned with respect of a dividing plane into those that: • lie in front of the dividing plane.

• lie behind the dividing plane. • straddle the dividing plane. • lie coincident with the dividing plane

Whilst mathematically straightforward, inaccuracies in floating-point arithmetic entail that a split polygon may still be found to straddle the dividing plane. A practical solution to this problem is to use thick planes defined as n • (X − P) < ε (for some ε), i.e. all points within a small distance of the plane are considered lying on the plane.

Splitting Polygons Against a Plane During BSP tree construction, when a polygon is found straddling a dividing plane it must be split in two. Clipping a polygon against a plane is done using the Sutherland– Hodgman algorithm. The algorithm considers one polygon edge at a time and returns a set of points based on an intersection test between the edge and plane.

Splitting Polygons Against a Plane Whilst polygons are split during the construction of the tree, this need not mean that the polygon fragments ending up in the leaves must be the polygons output in the final tree. For collision detection, it is better to store a reference to the original polygon with each fragment generated during splitting. In the leaves, the reference is output, and not the fragment.

Overview of how a BSP tree can be used

Testing a Point Against a Solid-leaf BSP Tree Determining if a point lies in empty or solid space of a solid-leaf BSP tree can be done by evaluating the point with respect to a node’s dividing plane. The side on which the point falls determines which child node is next visited. Traversal continues until a leaf node is reached. The value of the leaf node answers the query. If the tested point lies on the boundary of a solid volume represented by the BSP tree then both subtrees should be explored. When both subtrees are traversed if different results are returned (e.g. solid and empty) then the point lies on the boundary (a matching return from both subtrees is simply returned).

Testing a Point Against a Solid-leaf BSP Tree HitType PointInSolidSpace(BSPNode node, Point p) { Determine the distance the point is from the plane while (!node.IsLeaf) { float dist = Dot(node.Plane.n, p) – node.Plane.d; if (dist > EPSILON) { If the point lies in front of the plane, then visit the node = node.Child[0]; first subtree, else if behind the plane, then visit } else if (dist < -EPSILON) { the second subtree node = node.Child[1]; } else { If the point lies on the dividing plane then visit both subtrees HitType front = PointInSolidSpace(node.Child[0], p); HitType back = PointInSolidSpace(node.Child[1], p); If the returned results differ, then return that the point is on the boundary return (front == back) ? front : HitType.OnBoundary; } } If a leaf node has been reached then return it’s recorded type return node.IsSolid ? HitType.Inside : HitType.Outside; }

Intersecting a Ray Against a Solid-leaf BSP Tree When testing for intersection of a ray or segment against the tree care must be exercised to ensure that the tested ray or segment is not repeatedly subdivided against the splitting plane (as repeated subdivision can introduce drift due to accumulated floating point inaccuracies). A better approach is to determine the intersection ‘time’ of the ray against the plane (R(t) = P + td, tmin ≤ t ≤ tmax). The time thit of the first intersection with a solid leaf is returned (should an intersection be found). Aside: If thick planes are used, then an epsilon term needs to be added to the plane intersection tests, with both sides explored given plane intersection.

Testing a Ray Against a Solid-leaf BSP Tree HitType RayIntersect(BSPNode node, Point p, Vector d, float tmin, float tmax, out float thit) { Stack nodeStack; Define two stacks to hold Stack timeStack; ‘recursive’ information

Determine if the ray (or segment) intersects with solid geometry. If available, also return the ‘time’ of intersection thit (where R(t) = p + t*d, tmin