VolCCD: Fast continuous collision culling between deforming volume meshes

Min Tang, Dinesh Manocha, Sung-Eui Yoon, Peng Du, Jae-Pil Heo, Ruofeng Tong

Abstract

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. In addition, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra, hexahedra, triangular prisms, etc.). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.
BibTeX
@article{tang2011volccd,
  author = {Min Tang and Dinesh Manocha and Sung-Eui Yoon and Peng Du and Jae-Pil Heo and Ruofeng Tong},
  title = {{VolCCD: Fast continuous collision culling between deforming volume meshes}},
  journal = {ACM Trans. Graphics},
  year = {2011},
  doi = {10.1145/2019627.2019630},
}

Loading related content...

Figure