A Fast and Generalized Broad-Phase Collision Detection Method Based on KD-Tree Spatial Subdivision and Sweep-and-Prune

Abstract

Various graphics applications use multibody collision detection, a critical technology in computer graphics, system simulations, and virtual reality. In these simulation environments, broad-phase collision detection, as part of collision detection, plays a critical role in ensuring that rejecting disjoint objects and collision detection is accelerated. Few existing methods implement collision detection of millions of objects in a general-purpose environment on the CPU. This paper proposes a broad-phase collision detection algorithm based on KD-Tree spatial subdivision and sweep-and-prune, which optimizes and accelerates broad-phase collision detection using a pre-sorting and temporal inference solution. Our method enables broad-phase collision detection for coherent and non-coherent settings for uniformly and non-uniformly sized objects respectively. Based on our proposed solution is tested in the context of complex scenarios and compared with other solutions available in the literature and in the industry. The experimental results show that our approach has a 1X to 2X performance improvement in virtual environments with up to $1024 \times 10^{3}$ objects, reaching the fastest collision detection speed of 119.45 milliseconds per frame in the test environment.

Keywords

• Collision detection
• KD-tree
• spatial subdivision
• sweep and prune