FASTCD: Fracturing-Aware Stable Collision Detection

by Jae-Pil Heo, Joon-Kyung Seong, DukSu Kim, Miguel A. Otaduy, Jeong-Mo Hong, Min Tang, and Sung-eui Yoon.

ACM SIGGRAPH/Eurographics Symp. on Computer Animation (SCA), 2010

Video(MOV, 18MB)

These figures show two complex and large-scale fracturing benchmarks that have topological changes. (Left) Three frames of a breaking dragon benchmark that consists of 252K triangles throughout the simulation. (Right) Three frames of a breaking-wall benchmark that starts with 42K triangles and ends with 140K triangles. Our method spends 252ms and 97ms for discrete collision detection including self-collision detections of these dragon and wall benchmarks respectively by using a single CPU-thread. Moreover, we show a more stable performance by achieving up to two orders of magnitude performance improvement at fracturing events where deforming meshes change their topologies.

We release our fracturing benchmarks (Click figure)


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.


Paper: FASTCD (PDF, 3MB) , Supplementary Report(PDF, 0.3MB)

Slides: FASTCD_Slides(ppt, 3.7MB)

author = {Jae-Pil Heo, Joon-Kyung Seong, DukSu Kim, Miguel A. Otaduy, Jeong-Mo Hong, Min Tang, Sung-Eui Yoon},
title = {{FASTCD}: Fracturing-Aware Stable Collision Detection},
booktitle = {SCA '10: Proceedings of the 2010 ACM SIGGRAPH / Eurographics Symposium on Computer Animation},
year = {2010}

Fracturing Benchmarks

We release our two fracturing benchmarks that we used in the paper.

Related Links

Fracturing Benchmarks

HPCCD: Hybrid Parallel Continuous Collision Detection

Interactive Continuous Collision Detection between Deformable Models using Connectivity-Based Culling


UNC Dynamic Scene Benchmarks

Dept. of Computer Science
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com