Scalable and Conservative Continuous Collision Detection for GPU

We introduce an algorithm for continuous collision detection (CCD) for linearized trajectories designed to be scalable on modern parallel architectures and provably correct when implemented using floating point arithmetic. Our approach to broad-phase CCD is based on new simple, yet efficient and scalable, broad-phase algorithm based on the surprising experimental observation that sorting and linearly checking for intersections has a performance comparable to state of the art approaches when executed on a modern GPU. For narrow-phase CCD, we extend the recently proposed interval-based algorithm of Wang et al. [2021] to work on massively parallel hardware. To evaluate the correctness, scalability, and overall performance of our approach, we introduce a large scale benchmark for broad- and narrow-phase CCD with symbolically computed time of impacts, and compare our approach with 11 state-of-the-art (SOTA) methods for broad-phase and 1 SOTA methods for narrow-phase. We integrate our algorithm with the IPC contact solver and evaluate its impact on challenging simulation scenarios. We release the dataset with analytic ground truth, which required over 5 CPU years to be generated, the implementation of all the algorithms tested, our testing framework, and a reference CPU and GPU implementation of our algorithm as an open-source project to foster adoption and development of linear CCD algorithms.