vriphys13

Permanent URI for this collection

Now showing 1 - 1 of 1

Parallel Collision Detection in Constant Time
(The Eurographics Association, 2013) Weller, Rene; Frese, Udo; Zachmann, Gabriel; Jan Bender and Jeremie Dequidt and Christian Duriez and Gabriel Zachmann
We prove that the maximum number of intersecting pairs spheres between two sets of polydisperse sphere packings is linear in the worst case. This observation is the basis for a new collision detection algorithm. Our new approach guarantees a linear worst case running time for arbitrary 3D objects. Additionally, we present a parallelization of our new algorithm that runs in constant time, even in the worst case. Consequently, it is perfectly suited for all time-critical environments that allow only a fixed time budget for finding collision. Our implementation using CUDA shows collision detection at haptic rates for complex objects.