Fast and Exact Continuous Collision Detection with Bernstein Sign Classification

by Min Tang1 , Ruofeng Tong1 , Zhendong Wang1 , and Dinesh Manocha2.

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.

 

Contents

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)

BSC Source code

 

Acknowledgements

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.

 

 

by Zhendong Wang1 , Min Tang1 , Ruofeng Tong1 , and Dinesh Manocha2,1.

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.

 

Contents

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)

TightCCD Source code

 

Acknowledgements

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

 

 

Related Links

UNC dynamic model benchmark repository

A GPU-based Streaming Algorithm for High-Resolution Cloth Simulation

Continuous Penalty Forces

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

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

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

UNC GAMMA Group

 

 

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
919.962.1749
geom@cs.unc.edu