Hierarchy Accelerated Stochastic Collision Detection

International audienceIn 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