Efficient and accurate interference detection for polynomial deformation

Abstract

We present efficient and accurate algorithms for interference detection among objects undergoing polynomial deformation. The scope of our algorithms include physically-based models undergoing dynamic simulation subject to non-penetration constraints, variational models, deformable models used in soft object animation, geometric models including polygonal meshes, parametric surfaces such as Bezier patches and B-splines, and solid models defined by such surfaces. Our algorithms use axis aligned bounding boxes and convex hulls of the objects to identify the object pairs in close vicinity. They use subdivision, convex hull properties and linear programming to perform surface intersection tests and loop intersection tests. Frame-to-frame coherence is utilized to achieve incremental computations. The resulting algorithms have been implemented and work well in practice. In particular we are able to compute all contacts accurately and at interactive speeds for flexible bodies undergoing second-order polynomial deformations.