1 - Zhejiang University, China
2 - University of North Carolina at Chapel Hill, USA
Figure 1: Benchmarks: We use five different benchmarks arising from cloth and FEM simualtions to verify our algorithm.
Abstract
We present fast algorithms to perform accurate CCD queries between triangulated models. Our formulation uses properties of the Bernstein basis and Bezier curves and reduces the problem to evaluating signs of polynomials. We present a geometrically exact CCD algorithm based on the exact geometric computation paradigm to perform reliable Boolean collision queries. This algorithm is more than an order of magnitude faster than prior exact algorithms. We evaluate its performance for cloth and FEM simulations on CPUs and GPUs, and highlight the benefits.
Paper (PDF 744 KB)
Min Tang, Ruofeng Tong, Zhendong Wang, and Dinesh Manocha, Fast and Exact Continuous Collision Detection with Bernstein Sign Classification, ACM Transactions on Graphics, 33(6), Article 186 (November 2014), 8 pages (Proc. of ACM SIGGRAPH Asia), 2014.
@ARTICLE {BSC,
author = {Tang, Min and Tong, Ruofeng and Wang, Zhendong and Manocha, Dinesh},
title = {Fast and Exact Continuous Collision Detection with Bernstein Sign Classification},
journal = {ACM Trans. Graph.},
volume = {33},
issue = {6},
month = {November},
year = {2014},
pages = {186:1--186:8},
}
Video (24.3 MB)
This research is supported in part by NSFC (61170140), the National Basic Research Program of China (2011CB302205), the National Key Technology R\&D Program of China (2012BAD35B01), the Doctoral Fund of Ministry of Education of China (20130101110133). Dinesh Manocha is supported in part by ARO Contract W911NF-10-1-0506, Intel and the Office Of The Director, National Institutes Of Health under Award Number R44OD018334, and the National Thousand Talents Program of China. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health. Ruofeng Tong is partly supported by NSFC (61170141), the National High-Tech Research and Development Program (No.2013AA013903) of China. We gratefully acknowledge the support of NVIDIA Corporation with the donation of the Tesla K40c GPU used for this research.
1 - Zhejiang University, China
2 - University of North Carolina at Chapel Hill, USA
Figure 1: Funnel. We use our CCD algorithm, TightCCD, for collision detection and response for cloth simulation. We highlight its performance on complex benchmarks with multiple layers. As compared to prior CCD algorithms, TightCCD improves the performance and reliability of the cloth simulation system.
Abstract
We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite-precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90-95% of the false positives. We integrated our algorithm (TightCCD) with physically-based simulation system and observe speedups in collision queries of 5-15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.
Paper (PDF 6.55MB)
Zhendong Wang, Min Tang, Ruofeng Tong, and Dinesh Manocha, TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds, Computer Graphics Forum, 34(7): 289-298, (Proc. of Pacific Graphics), 2015.
@ARTICLE {TightCCD,
author = { Wang, Zhendong and Tang, Min and Tong, Ruofeng and Manocha, Dinesh},
title = {TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds},
journal = {Computer Graphics Forum},
volume = {34},
issue = {7},
month = {September},
year = {2015},
pages = {289--298},
}
Video (17.5 MB)
This research is supported in part by NSFC (61170140), the National High-Tech Research and Development Program of China (No.2013AA013903), the National Key Technology R&D Program of China (2012BAD35B01), the Doctoral Fund of Ministry of Education of China (20130101110133). Dinesh Manocha is supported in part by ARO Contract W911NF-10-1-0506, Intel and the Office Of The Director, National Institutes Of Health under Award Number R44OD018334, and the National Thousand Talents Program of China. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health. Ruofeng Tong is partly supported by NSFC (61170141).
UNC dynamic model benchmark repository
A GPU-based Streaming Algorithm for High-Resolution Cloth Simulation
VolCCD: Fast Continuous Collision Culling between Deforming Volume Meshes
Collision-Streams: Fast GPU-based Collision Detection for Deformable Models
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
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
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
919.962.1749
geom@cs.unc.edu