broad-phase collision detection using semi-adjusting bsp-trees
The broad-phase step of collision detection in scenes composed of n moving objects is a challenging problem because enumerating collision pairs has an inherent O(n 2 ) complexity. Spatial data structures are designed to accelerate this process, but often their static nature makes it difficult to handle dynamic scenes. In this work we propose a new structure called Semi-Adjusting BSP-tree for representing scenes composed of thousands of moving objects. An scheduling algorithm evaluates locations where the BSP-tree becomes unbalanced, uses several strategies to alter cutting planes, and defer updates based on their re-structuring cost. We show that the tree does not require a complete re-structuring even in highly dynamic scenes, but adjusts itself while maintaining desirable balancing and height properties.
collision detection bsp-trees dynamic scenes