Deferred, self-organizing BSP trees
BSP trees and KD trees are fundamental data structures for collision detection in walkthrough environments. A basic issue in the construction of these hierarchical data structures is the choice of cutting planes. Rather than base these choices solely on the properties of the scene, we propose using information about how the tree is used in order to determine its structure. We demonstrate how this leads to the creation of BSP trees that are small, do not require much preprocessing time, and respond very efficiently to sequences of collision queries.
collision detection walkthrough binary space partitioning ray-shooting self-organizing data structares deferred data structures