Fast Continuous Collision Culling with Deforming
Deforming Non-collinear Filter: for VF pair, in the orthogonal plane perpendicular to nt, if vertex Pt is always on one side of edge atbt, and vertex ct is always on the other side of atbt, this pair should be culled out; for EE pair, in the orthogonal plane perpendicular to nt, if the two vertices of one edge are always on the same side of the other edge during the time interval [0, 1], this pair should be culled out.
Benchmarks: In the benchmark airbag, where the deforming airbag has intra-object collisions as well as inter-object collisions with the steering wheel, our algorithm based on a deforming filter improves the performance of the CCD algorithm by 1.16-1.41x over previous algorithms. In the benchmark cloth-ball, where a piece of cloth drops on top of a ball and curls around, our algorithm improves the performance of the CCD algorithm by 1.24-1.53x over previous algorithms. In the benchmark funnel, where a cloth falls into a funnel and pass through it under the pressure of a ball, our algorithm improves the performance of the CCD algorithm by 1.09-2.16x over previous algorithms. In the benchmark bunny, where a poor bunny is smashed onto the ground by a steel plate, our algorithm improves the performance of the CCD algorithm by 1.54-2.36x over previous algorithms.
We present a novel culling algorithm that uses deforming non-collinear filters to improve the performance of continuous collision detection (CCD) algorithms. The underlying idea is to use simple and effective filters, deforming non-collinear filters (NCFs), that reduce the number of false positives between the primitives. These filters are derived from the collinear conditions and can be easily combined with other culling methods. We have tested its performance on several benchmarks. Compared with previous methods, we can reduce the number of false positives significantly and improve the overall performance of CCD algorithms, especially for simulations with large time steps.
Paper (PDF 0.5 MB)
Peng Du, Min Tang, Ruofeng Tong, Fast Continuous Collision Culling with Deforming Non-collinear Filters, Accepted by CASA 2012.
Video (12 MB)
The project is
supported in part by National Basic Research Program (2011CB302205), National
Key Technology R&D Program (2012BAD35B01), Natural Science Foundation of
China (61170140), Natural Science Foundation of Zhejiang,
College of Computer Science and