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

 

 

 

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

 

 

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