Skip to Main content Skip to Navigation
New interface
Conference papers

Hierarchy Accelerated Stochastic Collision Detection

Stephan Kimmerle 1 Matthieu Nesme 2, 3 François Faure 3 
3 EVASION - Virtual environments for animation and image synthesis of natural objects
GRAVIR - IMAG - Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble, Inria Grenoble - Rhône-Alpes, CNRS - Centre National de la Recherche Scientifique : FR71
Abstract : In this paper we present a new framework for col- lision and self-collision detection for highly de- formable objects such as cloth. It permits to effi- ciently trade off accuracy for speed by combining two different collision detection approaches. We use a newly developed stochastic method, where close features of the objects are found by track- ing randomly selected pairs of geometric primi- tives, and a hierarchy of discrete oriented polytopes (DOPs). This bounding volume hierarchy (BVH) is used to narrow the regions where random pairs are generated, therefore fewer random samples are nec- essary. Additionally the cost in each time step for the BVH can be greatly reduced compared to pure BVH-approaches by using a lazy hierarchy update. For the example of a cloth simulation framework it is experimentally shown that it is not necessary to respond to all collisions to maintain a stable simu- lation. Hence, the tuning of the computation time devoted to collision detection is possible and yields faster simulations.
Document type :
Conference papers
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : François Faure Connect in order to contact the contributor
Submitted on : Monday, September 13, 2010 - 3:55:14 AM
Last modification on : Friday, February 4, 2022 - 3:16:44 AM
Long-term archiving on: : Tuesday, December 14, 2010 - 2:31:17 AM


Files produced by the author(s)


  • HAL Id : inria-00516887, version 1



Stephan Kimmerle, Matthieu Nesme, François Faure. Hierarchy Accelerated Stochastic Collision Detection. 9th International Workshop on Vision, Modeling, and Visualization, VMV 2004, Nov 2004, Stanford, California, United States. ⟨inria-00516887⟩



Record views


Files downloads