title: Fast and Exact Continuous Collision Detection with Bernstein Sign Classification.
abstract: We present fast algorithms to perform accurate CCD queries between triangulated models. Our formulation uses properties of the Bernstein basis and Bézier 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. Our 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.
authors.affiliation: State Key Lab of CAD&CG, Zhejiang University.
authors.forename: Min
authors.initials: M
authors.lastname: Tang
authors.affiliation: State Key Lab of CAD&CG, Zhejiang University.
authors.forename: Ruofeng
authors.initials: R
authors.lastname: Tong
authors.affiliation: State Key Lab of CAD&CG, Zhejiang University.
authors.forename: Zhendong
authors.initials: Z
authors.lastname: Wang
authors.affiliation: University of North Carolina at Chapel Hill.
authors.forename: Dinesh
authors.initials: D
authors.lastname: Manocha
keywords: Bernstein sign classification; Continuous collision detection; Exact geometric computation; Physically based simulation