碰撞检测算法的研究现状

1.3国内外研究现状

1.3.1碰撞检测算法的国外研究现状【王海玲. 三维游戏技术的研究与实现[D]. 哈尔滨工程大学, 2009】【范昭炜.实时碰撞检测技术研究[D] .浙江大学, 2003】

起源于20世纪70年代的碰撞检测问题，研究至今已有40年的历史，现如今有一些比较成熟的碰撞检测技术。

Dobkin（1985）、Agarwal（1991）、Chaxelle（1989）等在静态碰撞检测技术上做了早期研究。静态碰撞检测算法是指当场景中物体在整个时间轴t上都不发生变化时，用来检测在这个静止状态中各物体之间是否发生碰撞的算法。这类算法要求较高的精度，由于是静止状态，因此没有实时性的要求，它广泛应用于计算几何中。

Lin（1998）、Jimenez（2001）对离散碰撞检测算法进行了研究，离散碰撞检测算法在每一时间离散点上通过类似于静态碰撞检测算法的方法来实现，可以迎合多数应用对实时性的需求。

Hubbard（1995）、Dingliana（2000，2001）、O’Sullivan（1999）为了改善离散碰撞检测算法中存在的刺穿现象和遗漏碰撞的现象，提出了自适应步长和可中断的碰撞检测技术。

Cameron（1990）、 Canny（1986）和Redon（2001，2002）为了解决在离散碰撞检测算法中存在的刺穿现象和遗漏发生碰撞的现象，对连续碰撞检测算法进行了研究。连续碰撞检测算法精确，但涉及到四维结构空间和时空问题，算法计算速度慢，在大规模场景中不能满足实时性。

Lin-Canny（1991，1993）提出了“最邻近特征算法”，基于特征的碰撞检测算法基本上都源自于该算法。

Hubbard（1995）、Gottschalk（1996）、Klosowski（1998）、Zachmann（1998）在面向多边形表示模型的多边形集合中做了广泛研究。

Gilbert（1988，1990）、Johnson和Keerthi提出了基于单纯形的碰撞检测算法，即GJK算法。该类算法通常将两物体看作一个单纯形，通过单纯形的几何特性来计算它们间的分离或穿透距离。

Hoff（2001）和Kim（2002）等将图像空间碰撞检测和物体空间碰撞检测算法结合起来，利用二者优点增强算法的功能，同时通过一定的负载平衡策略在CPU与图形硬件单元GPU之间进行调配来保证算法的整体效率。

Smitheral提出了一种基于AABB包围盒的角色变形体对象的算法，该算法在每一时间

步都重新计算对象的包围盒，缺点是模型复杂时包围盒的计算实时性差，效率低。

Bergen(1999)等提出一种基于SOLID（Software Library for Interference Detection）算法，该算法时刻由叶子节点开始完成由底向上的更新，其思想基于GJK的碰撞检测算法结合基于AABB的掠扫和裁剪的增量剔除技术，提高了算法效率，缺点是发生变形时，AABB包围盒的紧密性差并且包围盒之间存在很大的重叠区域。

大阪大学的Yashifumi Kitamura等人提出了一种用于解决复杂场景下的变形体的碰撞检测算法，算法的核心是包围盒方法与空间分解法的结合，该方法的缺点是空间分解法中采用八叉树的数据结果复杂，算法效率低。

Rossignac（1992）、Shinya（1991）、Myszkowski（1995）、Baciu （1997，1999）、Hoff

（2001）、Kim（2002）、Govindar （2003）、Heidelberger（2003）等人在基于图象空间的碰撞检测算法上做了大量研究，基于图象空间的算法有效利用了图形硬件（GPU）的高性能计算能力，减轻CPU的负担，随着GPU的发展，算法有一定的发展前景。

美国北卡罗来纳大学(UNC)的GAMMA Group（Geometric Algorithms for Modeling, Motion, and Animation ）做了大量的碰撞检测工作，开发了多个碰撞检测库，如I-COLLIDE，PQP，RAPID，SWIFT，还包括用GPU的Occlusion Query来做精细检测。 1.3.2碰撞检测算法的国内研究现状

王兆其、王志强等一直致力于基于物体空间的碰撞检测算法研究，该算法是把层次表示法、几何推理、代数范式、空间划分、解析方法和最优化方法等多种技术应用于碰撞检测。

国防科学技术大学的魏迎梅【魏迎梅,王涌,吴泉源,石教英. 碰撞检测中的固定方向凸包包围盒的研究[J]. 软件学报, 2001,(07) .】等人论述了固定方向凸包(fixed directions hulls,简称FDH)作为包围盒进行碰撞检测的方法,证明了其适用于复杂环境中的精确碰撞检测,尤其适用于软体对象环境中的碰撞检测，该方法可用于虚拟手术仿真。

范昭炜等人[邹益胜,丁国富,许明恒,何邕. 实时碰撞检测算法综述[J]. 计算机应用研究, 2008,(01)]采用Baciu等人提出的基于图像的碰撞检测算法,对物体表面进行自动凸分解,后将凸分解结果合理组织成层次二叉树结构,以及采用基于三角形带的绘制加速技术,有效提高了算法的效率,并且可以处理任意形状物体间碰撞检测。

宋永军等人利用凸包计算先对刚体进行凸分解，再利用深度缓存和模板缓存的组合功能对刚体的碰撞检测进行了研究。

本文来源：https://www.bwwdw.com/article/hdb2.html