Tight Normal Cone Merging for Efficient Collision Detection of Thin Deformable Objects

Abstract

When simulating thin deformable objects such as clothes, collision detection alone takes a lot of computation. One way of reducing the computation is culling false-positives as much as possible. In the context of bounding volume hierarchy, Provot proposed a culling method that is based on hierarchical merging of normal enclosing cones. In this work, we investigate Provot's merging algorithm and show that there is some room for improvement. We propose a new merging algorithm, in the context of discrete collision detection, which always produces an equal or tighter mergence than Provot's merging. We extend the above algorithm so that it can be used in the context of continuous collision detection. Experiments show that the proposed method makes about 25% reduction in the number of triangle pairs for which vertex-triangle or edge-edge collision test has to be performed, and 18% reduction in time for collision detection.