Continuous collision detection with medial axis transform for rigid body simulation

Continuous Collision Detection (CCD) is a fundamental problem for physically based simulation, such as rigid motion, elastic deformation, cloth animation, etc. CCD has been widely studied in the past decades, and most proposed algorithms are performed on the level of triangle mesh by using some culling methods to reduce the number of tested triangle pairs. However, the efficiency of these algorithms is very sensitive to the resolution of the triangular mesh. In this paper, we present an effective and efficient CCD method based on Medial Axis Transform (MAT) for simulating rigid motion. The simplified MAT, represented as a medial mesh composed of medial primitives like cones and slabs can provide a high-quality tight enclosure of the original 3D shape, while its number of primitives is smaller than that of the original triangle mesh by several orders of magnitude. With this key observation, our colliding elementary tests are only performed on the medial mesh, and the first time-of-impact in CCD can be computed by solving a quadratic optimization problem. The experiments show our algorithm can accurately and efficiently handle CCD of multi-bodies with thin features, without any penetration or tunnelling artifacts. Compare to the standard Bounding Volume Hierarchy (BVH) methods, our method achieves great improvement in efficiency.

Full Text (PDF format)

Received 23 July 2020

Published 7 February 2022