基于线性规划的碰撞检测算法研究

Research on Collision Detection Algorithm Based on Dual Model

介绍了虚拟环境中一种基于凸多面体面信息对偶线性规划模型(DualModel)的快速旋转和移动物体之间干涉碰撞实时检测方法。该文详细介绍了建模过程和求解步骤,物体由构成凸多面体的三角形面信息表示,而物体的运动由一组虚拟现实环境中的全局移动和旋转矩阵表示。这种数学编程方法具有数据结构简单、算法可靠和速度快等优点,同时能够很好地解决高速(运动帧)碰撞的问题。这一方法通过使用主-对偶(primal-dual)内点方法来解线性规划方程,具有很好的效果,能够检测多物体对之间的碰撞。实验结果表明,基于数学编程的方法相对两种著名的工具包I-COLLIDE和SOLID,具有速度快和稳定可靠的优点,而I-COLLIDE和SOLID工具包基于两种著名的算法:LinCanny(LC)最近特征算法和GJK算法(EnhancedGilbertJohnsonandKeethialgorithm)。

This paper presents a real-time collision detection methodology between a pair of convex polyhedral objects undergoing fast rotational and translational motion,which models the collision detection problem as a dual model linear program based on convex triangle information.The paper introduces the modeling process and solution method in detail.The objects are specified by a set of triangles,and movements specified by a set of global translation and rotation matrices generated through any virtual reality environment.The mathematical programming approach offers robustness,speed,simpler data structures,and it naturally addresses situations such as high speed(interframe )collisions.The strength of developed approach is demonstrated by solving the generated linear programs using a primal-dual interior point method.The method can detect collisions between multiple object pairs.Experimental results show that mathematical programming approaches offer substantial advantages in speed and robustness,when compared with two well known toolkits for this problem:I-COLLIDE and SOLID,which provide easy to use public domain access for two of the most popular algorithms -Lin Canny(LC)closest feature algorithm and Enhanced Gilbert Johnson and Keerthi (GJK)algorithm.