Efficient Culling Criteria for Continues Collision Detection Using a Fast Statistical Analysis Method

ABSTRACT

Continuous Collision Detection (CCD) between deforming triangle mesh elements in 3D is significant in many computer and graphics applications, such as virtual surgery, simulation and animation. Although CCD is more accurate than discrete methods, its application is limited mainly due to its time-consuming nature. To accelerate computation, we present an efficient CCD method to perform both inter-object and intra-object collision queries of triangle mesh models. Given a model set of different poses as training data, our method uses Statistic Analysis (SA) to make regression on a deformation subspace and also on collision detection conditions in a pre-processing stage, under a uniform framework. A data-driven training process selects a set of “key points” and produces a credible subspace representation, from which a plug-in type of collision culling certificate can be then obtained by regression process. At runtime, our certificate can be easily added to the classic BVH traversal procedure, as a sufficient condition of collision free cases, providing efficient culling in overlapping test and reducing hierarchy updates frequency. In the end, we describe performance and quality of our method using different experiments.

Keywords:

CCD, Deformation body, Regression, Statistical analysis, Canonical correlation analysis, Linear discriminant analysis.