Chapter 8
BSP Tree Hierarchies
Of the many spatial partitioning methods available, the BSP tree is the most versatile. It can perform the same tasks as the k-d tree, the quadtree, or the octree, but not vice versa. In addition to spatial partitioning, the BSP tree can be used as a boundary or solid representation of arbitrary polyhedral scenes. BSP trees are also powerful structures for collision detection, which this chapter explores.
8.1 BSP Trees
A binary space-partitioning tree (or BSP tree for short) is a binary tree structure that recursively partitions space into pairs of subspaces with respect to dividing planes of arbitrary position and orientation. If the space being partitioned is n-dimensional, the dividing planes are ( ...
Get Real-Time Collision Detection now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
