by Peng Du, Min Tang, and Ruofeng Tong.

Zhejiang University, China

Deforming Non-collinear Filter: for VF pair, in the orthogonal plane perpendicular to n_t, if vertex P_t is always on one side of edge a_tb_t, and vertex c_t is always on the other side of a_tb_t, this pair should be culled out; for EE pair, in the orthogonal plane perpendicular to n_t, 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.

Abstract

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.

Contents

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)

NCF Source code

DNF Source code

Source code: Self-CCD

Related Links

VolCCD: Fast Continuous Collision Culling between Deforming Volume Meshes

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

Self-CCD: Continuous Collision Detection for 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

Acknowledgements

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, China (Y1100069,Y1100018).

College of Computer Science and Technology
Zhejiang University
tang_m@zju.edu.cn