Collision-Streams: Fast GPU-based Collision Detection for Deformable Models

by Min Tang, Dinesh Manocha, Jiang Lin, and Ruofeng Tong.

Zhejiang University, China

University of North Carolina at Chapel Hill, USA


Benchmark Funnel: In this simulation, a cloth falls into a funnel and pass through it under the pressure of a ball. This model has 47K vertices, 92K triangles, and a lot of self-collisions. Our novel GPU-based CCD algorithm takes 4.4ms and 10ms per frame to compute all the collisions on a NVIDIA GeForce GTX 480 and a NVIDIA GeForce GTX 285, respectively.

The stream data: All the geometric data, such as vertex coordinates, BVs, BVH, BVTT front, Orphan set, triangle pairs, feature pairs, and colliding information are represented as GPU streams. Different kernels operate on these streams. Computation kernels: The modules, such as updating BVs, updating BVH, regenerate BVTT front, non-penetration filter, and elementary tests, etc., are represented as computation kernels.



We present a fast GPU-based streaming algorithm to perform collision queries between deformable models. Our approach is based on hierarchical culling and reduces the computation to generating different streams. We present a novel stream registration method to compact the streams and efficiently compute the potentially colliding pairs of primitives. We also use a deferred front tracking method to lower the memory overhead. The overall algorithm has been implemented on different GPUs and we have evaluated its performance on non-rigid and deformable simulations. We highlight our speedups over prior GPU-based and GPU-based algorithms. In practice, our algorithm can perform inter-object and intra-object computations on models composed of hundreds of thousands of triangles in tens of milliseconds.


Paper  (PDF 1 MB)

Min Tang, Dinesh Manocha, Jiang Lin, Ruofeng Tong, Collision-Streams: Fast GPU-based Collision Detection for Deformable Models, in Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (i3D 2011), San Fransisco, CA, Feb. 18-20, 2011, 63-70.

      author = {Tang, Min and Manocha, Dinesh and Lin, Jiang and Tong, Ruofeng},
      title = {Collision-Streams: Fast {GPU}-based collision detection for deformable models},
      booktitle = {I3D '11: Proceedings of the 2011 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games},
      year = {2011},
      location = {San Fransisco, CA},
      pages = {63--70},

Video (30 MB)


Related Links

UNC dynamic model benchmark repository

Fast Continuous Collision Detection using Deforming Non-Penetration Filters

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

MCCD: Multi-Core Collision Detection between Deformable Models using Front-Based Decomposition

Fast Collision Detection for Deformable Models using Representative-Triangles

DeformCD: Collision Detection between Deforming Objects

Self-CCD: Continuous Collision Detection for Deforming Objects

Interactive Collision Detection between Deformable Models using Chromatic Decomposition

Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams

CULLIDE: Interactive Collision Detection between Complex Models using Graphics Hardware

RCULLIDE: Fast and Reliable Collision Culling using Graphics Processors

Quick-CULLIDE: Efficient Inter- and Intra-Object Collision Culling using Graphics Hardware

Collision Detection



We would like to thank Simon Pabst for providing the funnel benchmark, Weiwei Xia and John Owens for useful discussions, and the anonymous reviewers for their thoughtful and constructive comments. The cloth models were provided by Rasmus Tamstorf at Disney Animation.

This research is supported in part by National Basic Research Program of China (No. 2011CB302205), MOE-Intel special research fund on information technology (No. MOE-INTEL-09-05), ARO Contract W911NF-04-1-0088, NSF awards 0636208, 0917040 and 0904990, DARPA/RDECOM Contract WR91CRB-08-C-0137, and Intel. Tang is supported in part by Natural Science Foundation of China (No. 60803054), Natural Science Foundation of Zhejiang, China (No. Y1100069), Important Science and Technology Specific Project of Zhejiang, China (2008C01059-4), and AMD China.

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175