复杂物体连续碰撞检测动态投影分离剔除算法

Continuous collision detection of complex objects based on dynamic projection separation for eliminating algorithm

针对复杂物体间碰撞检测,为提高碰撞检测效率,减少计算量,解决普通算法不直接适用于非凸体等问题,提出了一种连续碰撞检测算法。首先,该算法在初检测阶段利用基于波前法的三角网格生成,对非凸体等复杂物体表面进行网格划分,获取高质量三角形,得到三角形点、线、面参数信息;然后,用动态投影分离剔除法对三角形单元对进行高层剔除,从而剔除掉不可能发生碰撞的三角形;最后,针对可能碰撞的三角形特征对进行精确相交测试,返回发生第一次碰撞时间,完成碰撞检测。经过复杂度分析和实验论证,该算法响应速度快,在结构复杂物体的连续碰撞检测中效率较高,对于非凸体也可适用。

A continuous collision detection algorithm for complex objects is presented, to improve the efficiency of collision detection, and reduce the amount of computation to address issues such as common algorithms not directly applied to non-convex body. Firstly, the algorithm utilizes the triangular mesh generation algorithm of the advancing front technique to the surface of objects such as non-convex body, by which one can obtain the high quality triangle and the parameters of points, lines and surfaces. Then, the dynamic projection separation for the eliminating algorithm is used to remove those triangular which cannot be collided. Finally, precise test is car- ried out to complete the test for those possible collision characteristics of triangular, returning the first collision time at the same time. The experimental results and analysis show that this algorithm has fast response time and more efficient continuous collision detection for complex obiects, which are also applicable to non-convex body.