A fast algebraic non-penetration filter for continuous collision detection

作者：Zhang, Xinyu^*; Liu, Yao

来源：Graphical Models, 2015, 80: 31-40.

DOI：10.1016/j.gmod.2015.06.001

• Continuous collision detection
• Non-penetration filter
• Cubic equation
• Deformable objects

Continuous collision detection is a key technique to meet non-penetration requirements in many applications. Even though it is possible to perform efficient culling operations in the broad stage of a continuous collision detection algorithm, such as bounding volume hierarchies, a huge number of potentially colliding triangles still survive and go to the succeeding narrow stage. This heavily burdens the elementary collision tests in a collision detection algorithm and affects the performance of the entire pipeline, especially for fast moving or deforming objects. This paper presents a low-cost filtering algorithm using algebraic analysis techniques. It can significantly reduce the number of elementary collision tests that occur in the narrow stage. We analyze the root existence during the time interval [0, 1] for a standard cubic equation defining an elementary collision test. We demonstrate the efficiency of the algebraic filter in our experiments. Cubic-solvers augmented by our filtering algorithm are able to achieve up to 99% filtering ratios and more than 10 x performance improvement against the standard cubic-solver without any filters.

• 出版日期2015-7
• 单位华东师范大学