Research on Directional Penetration Depth Algorithm in Collision Response

Directional penetration depth (DPD) is defined as minimum distance by which one polyhedron translates along the given direction and makes the interiors of the two overlapped polyhedrons disjoint. Since the penetration depth computation will influence over the research of collision response, thus it possesses great theory research significance and application value in promoting the naturalness of virtue reality. However the current existing methods can not handle the computing speed, computing accuracy and algorithm generality at the same time. These shortcomings limit severely the practicability of the methods. Facing this problem, a fast directional penetration depth algorithm is presented. First, based on the penetration point sets, a method is developed to calculate the DPD between any two polyhedrons using the technique of intersection test. Then presented are a series of optimization strategies, including the method to construct bounding volume hierarchy and the method to reduce the amount of points and triangle meshes need to be detected in the processing. Under the conditions for computational accuracy, these strategies can strongly improve the performance of the algorithm. Experimental results show that this algorithm can fast and accurately calculate the DPD between the two general complex polyhedrons, even in the environment of the two complex polyhedrons contain tens of thousand triangle meshes, and have multiple contacts. Moreover, compared with other algorithms, this algorithms can handle some special penetration problems, and thus it has more generality.