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)
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)
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