Self-customized BSP trees for collision detection

The ability to perform efficient collision detection is essential in Virtua l reality environments and their applications, such as walkthroughs. In thi s paper we re-explore a classical structure used for collision detection th e binary space partitioning tree. Unlike the common approach, which attribu tes equal likelihood to each possible query, we assume events that happened in the past are more likely to happen again in the future. This leads us t o the definition of self-customized data structures. We report encouraging results obtained while experimenting with this concept in the context of se lf-customized BSP trees. (C) 2000 Elsevier Science B.V. All rights reserved .