Parallel Collision Detection in Constant Time

Weller, Rene; Frese, Udo; Zachmann, Gabriel

Parallel Collision Detection in Constant Time

Files

061-070.pdf (2 MB)

Date

2013

Authors

Weller, Rene
Frese, Udo
Zachmann, Gabriel

Publisher

The Eurographics Association

Abstract

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.

        @inproceedings{:10.2312/PE.vriphys.vriphys13.061-070
,
booktitle = {Workshop on Virtual Reality Interaction and Physical Simulation
},
editor = {Jan Bender and Jeremie Dequidt and Christian Duriez and Gabriel Zachmann
},
title = {{Parallel Collision Detection in Constant Time
}},
author = {Weller, Rene and 
Frese, Udo and 
Zachmann, Gabriel
},
year = {2013
},
publisher = {The Eurographics Association
},
ISBN = {978-3-905674-57-6
},
DOI = {/10.2312/PE.vriphys.vriphys13.061-070
}
}