Fast Continuous Collision Culling with
Deforming

Non-collinear Filters

*Zhejiang
University**,
China*

** Deforming
Non-collinear Filter:** for VF pair, in the orthogonal plane perpendicular to n

** 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.

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)

VolCCD: Fast Continuous Collision Culling
between Deforming Volume Meshes

Fast Continuous Collision Detection using
Deforming Non-Penetration Filters

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

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
Technology

Zhejiang University

tang_m@zju.edu.cn