by Min Tang¹ , Ruofeng Tong¹ , Zhendong Wang¹ , and Dinesh Manocha².

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 Wang¹ , Min Tang¹ , Ruofeng Tong¹ , and Dinesh Manocha^2,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