Mochi: Fast & Exact Collision Detection

Abstract

Efficient Discrete Collision Detection (DCD) uses indexing structures for acceleration, and developing these structures demands meticulous programmer efforts to achieve performance. The ray-tracing (RT) architecture of GPUs builds and traverses an indexing structure called Bounding Volume Hierarchy (BVH) and performs geometric intersection tests, which are all the essential components of a DCD kernel. However, BVHs built by the RT architecture are neither accessible nor programmable; the only way to use this architecture is to launch rays and map DCD queries to ray traversal. Despite these challenges, we developed an RT-accelerated DCD framework, Mochi, for handling spherical objects. Mochi optimizes collision detection by utilizing hardware-accelerated BVH traversal in the broad phase and introducing a novel object-object intersection test in the narrow phase. When performing an end-to-end particle simulation, Mochi achieved a speedup of up to $5.2$x for DCD and $2.8$x for the entire simulation, over a CUDA-based baseline implemented with Taichi, a high-performance framework targeting graphics applications.