GMRV Publications

FASTCD: Fracturing-Aware Stable Collision Detection

Jae-Pil Heo, Joon-Kyung Seong, DukSu Kim, Miguel A. Otaduy, Jeong-Mo Hong, Min Tang, Sung-eui Yoon
Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation - 2010
We present a collision detection (CD) method for complex and large-scale fracturing models that have geometric and topological changes. We first propose a novel dual-cone culling method to improve the performance of CD, especially self-collision detection among fracturing models. Our dual-cone culling method has a small computational overhead and a conservative algorithm. Combined with bounding volume hierarchies (BVHs), our dual-cone culling method becomes approximate. However, we found that our method does not miss any collisions in the tested benchmarks. We also propose a novel, selective restructuring method that improves the overall performance of CD and reduces performance degradations at fracturing events. Our restructuring method is based on a culling efficiency metric that measures the expected number of overlap tests of a BVH. To further reduce the performance degradations at fracturing events, we also propose a novel, fast BVH construction method that builds multiple levels of the hierarchy in one iteration using a grid and hashing. We test our method with four different large-scale deforming benchmarks. Compared to the state-of-the-art methods, our method shows a more stable performance for CD by improving the performance by a factor of up to two orders of magnitude at frames when deforming models change their mesh topologies.

Project page with paper and video available at KAIST

Images and movies

a.PNG [363Ko]
b.PNG [670Ko]

BibTex references

  author       = "Heo, Jae-Pil and Seong, Joon-Kyung and Kim, DukSu and Otaduy, Miguel A. and Hong, Jeong-Mo and Tang, Min and Yoon, Sung-eui",
  title        = "FASTCD: Fracturing-Aware Stable Collision Detection ",
  booktitle    = "Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation",
  year         = "2010",
  url          = ""

Other publications in the database

» Miguel A. Otaduy
» Min Tang