Fast Penetration Volume for Rigid Bodies
Handling collisions among a large number of bodies can be a performance bottleneck in video games and many other real-time applications. We present a new framework for detecting and resolving collisions using the penetration volume as an interpenetration measure. Given two non-convex polyhedral bodies, a new sampling paradigm locates their near-contact configurations in advance, and stores associated contact information in a compact database. At runtime, we retrieve a given configuration's nearest neighbors. By taking advantage of the penetration volume's continuity, cheap geometric methods can use the neighbors to estimate contact information as well as a translational gradient. This results in an extremely fast, geometry-independent, and trivially parallelizable computation, which constitutes the first global volume-based collision resolution. When processing multiple collisions simultaneously on a 4-core processor, the average running cost is as low as 5 microseconds. Furthermore, no additional proximity or contact-regions queries are required. These results are orders of magnitude faster than previous penetration volume approaches.
The work was supervised by Prof. Dani Lischinski of the Hebrew University.
This page was created for the benefit of curious minds, for researchers who could take the presented ideas to new places, and for any parties interested in applying a similar scheme in their creations. Do you fall in any of these categories? Do let me know! Otherwise, let me know what category you do fall into!