| Targeted on the current conflict between the accuracy and real-time which exists in collision detection universally, an algorithm of collision detection based on feature points is proposed, which using the feature points as the judgment basis of collision detection. The AABB bounding box is also used as an assistant tool to improve the speed and the efficiency of collision detection. This algorithm can ensure the accuracy, reduce the computing complexity, and improve the speed and the efficiency of collision detection.On the basis of the feature points extraction algorithm used in skeleton extraction which is proposed by Julien Tierny, using local extremum as the judgment basis, a novel algorithm of feature points extraction called feature point extraction based on local extremum (F-LE) is proposed to increase the number of significant feature points. Because of the high computing complexity of F-LE, two novel feature point extraction algorithms are proposed: feature point extraction based on neighbor faces angle algorithm (F-NFA) and feature point extraction based on neighbor point vectors angle algorithm (F-NPVA). F-NFA algorithm and F-NPVA algorithm are proposed on the basis of the triangular mesh model. Both of them can extract the model feature points fast and efficiently, also the number of the model's feature points and the accuracy can meet the requirement of collision detection well, but F-NFA algorithm uses two neighbor faces'angle whereas F-NPVA uses two neighbor point vectors'angle as the judgment basis of the model edge.In the view of the problem of determining the feature points extraction value in F-NFA algorithm and F-NPVA algorithm for different models, feature points extraction self-accommodated value (F-SAV) is proposed. It can easily get the suitable feature point extraction value according to the feature of models. F-NPVA algorithm involves computing the point vector. To solve the problem of the contribution to public point vector of long and narrow triangle face, a new method is proposed which called: point vector based on circle area (PV-CA). It is used to separate the contribution between long and narrow triangle faces to the public point vector logically.Experiment results show that the method could improve the efficiency and meet the requirement of real-time collision detection, which can ensure the accuracy, reduce the computing complexity and improve the speed of collision detection. |
