基于单形体的碰撞检测算法的研究与改进

Research and Improvement in Simplex-based Collision Detection

碰撞检测是计算机游戏、物理仿真(如计算机动画)、机器人技术、虚拟样机仿真技术以及工程仿真等领域中一个非常关键的问题,其基本任务是确定两个(或多个)物体是否、何时以及在何处形成碰撞。该文重点研究了基于单形体的Gil bert-Johnson-Keerth(简称GJK)碰撞检测算法.虽然GJK数学模型比较复杂,且难以理解,但是基于GJK碰撞检测算法有快速,易实施且适应于多种凸体的优点.传统的GJK算法主要是用来计算物体间的距离,该文对GJK算法作了改进,使它不仅能够查询物体间的距离,还能返回相互穿刺物体间的穿刺深度,使其在性能上得到优化。

Collision detection is a key problem of computer games,physical simulation(such as animation),robotics,virtual proto type simulation and engineering system simulation.Its basic task is to determine when and where do two(or more) objects inter act with each other.This article focused on simplex-based Gilbert-Johnson-Keerth(GJK) collision detection algorithm.Al though mathematical model of GJK is complicated and incomprehensible,but GJK has virtue of running rapidly,being imple mented easily and accommodate multiple convex objects.Conventional GJK is used to compute distance between objects merely,by means of making an improvement of GJK,the new GJK can inquire distance between objects,as well as return penetration depth.Furthermore impose a performance optimization on the improved GJK.