Fast continuous collision detection using deforming non-penetration filters

Figure 1: Benchmark Lion: In this simulation, a spherical ball falls on top of a Chinese statue of a lion and the lion gradually breaks into a high number of colliding pieces. This model has 805K vertices and 1.6M triangles. In this scene with changing topologies, our novel collision detection algorithm based on a deforming filter increases the culling efficiency and reduces the number of elementary tests by 10x when compared to prior methods and improves the performance of the CCD algorithm by 4.1x. We present a novel culling algorithm that uses deforming non-penetration filters to improve the performance of continuous col-lision detection (CCD) algorithms. The underlying idea is to use a simple and effective filter that reduces both the number of false pos-itives and the elementary tests between the primitives. This filter is derived from the coplanarity condition and can be easily combined with other methods used to accelerate CCD. We have implemented the algorithm and tested its performance on many non-rigid simula-tions. In practice, we can reduce the number of false positives sig-nificantly and improve the overall performance of CCD algorithms by 1.5 − 8.2x.