碰撞响应中方向穿透深度算法的研究

Research on Directional Penetration Depth Algorithm in Collision Response

方向穿透深度是碰撞响应的基础,在增强虚拟环境的逼真性和真实感方面起到了重要的作用.现有的方向穿透深度算法,很难同时兼顾计算速度和计算精度,实用性受到很大限制.提出一种新的方向穿透深度计算方法,无须对凹多面体进行凸分解,就能精确地计算任意多面体间的方向穿透深度.在此基础上,提出一种基于体分解的包围体层次——ISBVH,极大地提高了算法的效率.

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.