Fast GPU-based Collision Detection for Deformable Models (original) (raw)
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. |
Abstract
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.
Contents
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.
@inproceedings{CStreams11,
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
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
Acknowledgements
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
919.962.1749
geom@cs.unc.edu