Quick collision detection of polytopes in virtual environments
Kelvin Chung, Wenping Wang · 1996
The problem of collision detection is fundamental to inter-active applications such as computer animation and virtual environments. In these fields, prompt recognition of possible impacts is important for computing real-time response. We present a simple exact collision detection algorithm for convex polytopes. The algorithm finds quickly a separating plane between two polytopes if they are non-colliding, or else reports collision if it cannot possibly find a separating plane. In the case of non-collision, the separating plane found for one time frame is cached as a witness for the next time frame, an idea borrowed from [10]; this use of time coherence further speeds up the algorithm in dynamic applications. Both temporal and geometric coherences are exploited to make this algorithm run in expected constant time empirically.