基于空间剖分和分类遍历的碰撞检测算法

刘 昭，李 伟，赵鲁阳，单联海

（中国科学院上海微系统与信息技术研究所 上海200050）

基于空间剖分和分类遍历的碰撞检测算法

刘 昭，李 伟，赵鲁阳，单联海

（中国科学院上海微系统与信息技术研究所 上海200050）

针对碰撞检测实时性与精确性不高的问题，提出一种基于空间剖分和分类遍历的碰撞检测算法。首先在空间剖分阶段利用八叉树空间剖分剔除不相交的物体对，在剖分子空间内构建混合层次包围盒，利用分类遍历的方法对层次包围盒进行遍历，有效减少了相交测试的次数。实验表明，该算法有效缩短了碰撞检测所需时间，在复杂环境下算法优势明显。

碰撞检测；空间剖分；混合层次包围盒；分类遍历

随着计算机仿真技术的发展，以三维场景为基础的虚拟现实技术和对自然环境的渲染技术已成为重要研究方向，可广泛应用于城市规划、军事模拟、突发事件模拟等领域[1-2]。随着三维模型复杂性的增加和人们对于场景真实感要求的提高，碰撞检测的实时性与高效性成为当前研究热点。

从空间角度对碰撞检测算法进行分类，可以分为基于图像空间的碰撞检测算法和基于物体空间的碰撞检测算法[4]。

基于图像空间的碰撞检测算法是利用三维模型在二维平面上的投影图像和相关的深度信息判断是否存在碰撞，这类算法主要是利用硬件辅助和模板缓存来加速碰撞检测的过程，对计算机性能的要求比较高[3]。

基于物体空间的碰撞检测算法是利用三维模型的几何特性来判断是否存在碰撞。这类算法又可分为空间剖分法和层次包围盒法。空间剖分法是按照某种划分规则将空间剖分成若干个子空间，对同一子空间内的物体进行相交测试。常用的空间剖分算法分为3种：网格、树以及空间排序算法[5]。层次包围盒法是利用一个简单的体空间实现对一个具有复杂形状的物体的包围，通过体空间的碰撞检测代替物体的碰撞检测。常用的层次包围盒算法有包围球（Sphere）、轴向包围盒（Axis-Aligned Bounding Box AABB）、方向包围盒（oriented bounding box，OBB）和固定方向凸包（Discrete Orientation Polytopes，k-Dops）等[6]。

国内外学者已经对碰撞检测进行了较为深入的研究。Gottschalk等人提出了基于OBB包围盒的碰撞检测算法，称为RAPID算法[7]，有效提高了刚体间碰撞检测速度。Govindaraju等人提出了一种基于图形硬件加速的碰撞检测算法[8]，通过计算潜在碰撞集，实现了可形变物体间的快速碰撞检测。S Katz等人将模糊聚类分割思想应用到空间剖分中，很好的避免了过分割和分割不完全的情况[9]。JW Chang等提出一种基于Sphere-OBB的混合包围盒碰撞检测算法[10]，充分利用了Sphere包围盒构造简单和OBB包围盒检测精确的特性。

随着碰撞检测精确性和实时性要求的提高，单一的空间剖分法或者层次包围盒法难以满足要求，文中提出了二者结合的快速碰撞检测算法，算法优势如下：

1）使用八叉树空间划分来快速排除不相交的物体，使碰撞检测集中到每一个子空间中；

2）对占用同一子空间的物体进行碰撞检测时，构造Sphere-OBB混合层次包围盒；

3）对混合层次包围盒采用基于分类的深度优先遍历算法，提高遍历速度。

1 算法描述

1.1 空间剖分

空间剖分法提供了粗略的碰撞检测方案：将检测空间划分为多个区域，并在同一空间内测试物体是否相交，降低了相交测试的次数。文中选用八叉树作为空间剖分树。

八叉树空间剖分[11]是基于树型结构的空间划分方法，在三维空间的层次结构划分中效果良好。树的每一个父节点包括8个子节点，而且每一个子节点代表一个子空间，其根节点是包含全部物体的最小立方体，将这一立方体沿3个坐标轴均匀分割得到8个子空间节点。

如果剖分后的子空间内物体数量仍然较多，则再次对子空间进行八叉树划分，直到子空间内的物体数量满足要求为止。

1.2 混合层次包围盒

混合层次包围盒选取的依据是平衡碰撞检测的实时性和精确性。对于包围盒优劣的评价一般从相交测试复杂度、紧密性以及更新计算量3个方面入手[12]，几种经典的包围盒的比较结果如表1所示。

表1 几种包围盒特性比较

Gottschalk提出了层次包围盒性能的计算公式[7]，如下所示：

在上述公式中，可以通过构造更紧凑的包围盒来降低NV和NP的值，通过实现快速检测降低CV和CP的值。但是这两组值之间存在一个矛盾关系，当包围盒更加紧凑时，相交测试代价会越大，但是会降低相交测试的数量，所以需要在两者之间实现一个平衡。

因此选取Sphere和OBB包围盒来构建混合层次包围盒，利用Sphere包围盒更新简单以及相交测试复杂度低的优势进行初步碰撞检测，利用OBB包围盒紧密性好的优势进行精确的碰撞检测[13]，整体按照自顶向下[14]的方式构造混合层次包围盒。

1.3 层次包围盒的遍历

传统的碰撞检测包围盒树遍历方法有单一下降深度优先遍历法和同步下降深度优先遍历法。单一下降深度优先遍历法是先将一棵树遍历到叶子节点，再对另一棵树进行遍历；同步下降深度优先遍历法是同时对两棵树进行遍历，直至下降到叶子节点。研究表明，对两棵包含n个叶子节点的层次包围盒树A和B进行碰撞检测，如果采用单一下降深度优先遍历法，最多需要执行22n-1-1次相交测试；如果采用同步下降深度优先遍历法，最多需要执行（22n-1）3次相交测试[15]。单一下降深度优先遍历的劣势在于它不能发挥二叉树结构的优势；同步下降深度优先遍历的劣势在于当待遍历物体对的结构差异较大时，不能有效缩减搜索空间。

基于以上分析，文中提出一种基于分类的层次包围盒遍历方法：对于结构相似的待检测物体对，采用同步下降深度优先遍历法；对于结构不相似的待检测物体对，提出一种改进单一下降深度优先遍历法。我们通常用二叉树节点的左右子树的深度差表示该节点的平衡因子。通过定义两个层次包围盒树对应节点的平衡因子差值的绝对值来判断结构相似性，定义分类公式:

其中BAi表示树A中节点i的平衡因子；BBi表示树B中与A中节点i相同位置节点的平衡因子；Di表示节点i的平衡因子差值。当Di都不大于1时表示两个树结构相似，否则就不相似。

图1 a、b、c三棵树结构

图2 平衡因子差树

如图1表示3个树结构a、b、c各个结点的平衡因子，图2表示树结构a、b、c两两之间的平衡因子差树，从图2中可以看出a树和b树结构不相似，a树和c树结构不相似，b树和c树结构相似。树a的平衡性和树b、树c都不相同，说明树a存在细节较为精细的部分需要额外处理。

对于改进单一下降深度优先遍历过程，首先选择额外细节较多的树a进行遍历，当下降到树a的结点的平衡因子差值大于1时，转而对树b进行遍历，如果树b中出现平衡因子差值大于1时，再转回对树a进行遍历，如此循环，直到完成碰撞检测。

2 实验结果及分析

本实验程序运行的硬件环境是Windows 7系统，CPU 2.4 GHz的PC机，软件环境是Visual Studio 2010和OpenGL开发。实验场景分为两种，一种是模拟场景，另一个是软件应用场景。

实验场景1在Visual Studio2010中利用OpenGL搭建模拟场景，场景中有多个大小形状各不相同的物体在随机移动，为了验证算法性能，将本文算法和经典的I-COLLIDE算法进行对比，比较不同物体密度的情况下碰撞检测时间的变化情况，结果如图3所示。

图3 物体数量与碰撞检测时间关系

从图3看出，空间中物体数量越多，本算法的优势越明显，这说明本文算法的空间剖分直接减少了不相交物体的检测次数，再通过Sphere包围盒初步筛选，在OBB包围盒的碰撞检测阶段通过分类遍历的方法进一步加快了检测速度，从而有效改善了碰撞检测效率。

实验场景2在Visual Studio 2010中，基于虚幻引擎搭建一个消防演练场景，将本文提出的碰撞检测算法应用到水流和火焰的碰撞检测中，测试场景运行的流畅性。在实时系统中画面最低的流畅度要求是30帧/秒的刷新频率。文中分别在单个消防员单个着火点、多个消防员多个着火点以及多个消防员单个着火点的情况下测试帧数变化，场景环境如图4所示。

图4 消防灭火场景

在上述3种消防救援场景中，分别对3个场景下的帧数变化进行统计，以10秒为一个时间间隔，统计10秒帧数的平均值作为当前帧数，统计结果如图5所示。

图5 复杂场景下帧数随时间变化情况

从图5中可以看出帧数随着运行时间的增加和碰撞检测复杂度的增加并没有显著的降低，都能满足实时性的要求。

3 结 论

针对碰撞检测的实时性和精确性不足的问题，文中提出一种基于空间剖分和分类遍历的混合层次包围盒碰撞检测算法。文中首先对物体空间进行八叉树剖分，在子空间内构建Sphere-OBB混合层次包围盒进行碰撞检测，减少了不相交物体的检测，在碰撞检测的初级阶段，利用Sphere包围盒进一步筛选不相交物体对，再进行OBB包围盒的精确碰撞检测，在OBB包围盒的碰撞检测中采用分类遍历法进行快速碰撞检测，这种方法在保证精确性的情况下提高了碰撞检测的实时性。

碰撞检测算法在虚拟装配系统仿真中发挥着重要作用，为了实现用户和系统的友好交互，需要快速给出碰撞物体的位置信息，对碰撞检测提出了更高的要求，而本算法有效提高了碰撞检测的实时性和精确性，为虚拟装配系统的应用研究提供了一个行之有效的解决方案。

[1]赵沁平.虚拟现实综述[J].中国科学，2009（39）:2-46.

[2]Burdea G，Coiffet P.Virtual Reality Technology[J].Presence Teleoperators&Virtual Environments，2003，12（6）:663-664.

[3]卞锋，江漫清，桑永英.虚拟现实及其应用进展[J].计算机仿真，2007，24（6）:1-4.

[4]陈承收.基于云模型与GPU缓存技术的快速碰撞检测算法研究[D].长春工业大学，2011.

[5]Ericson C.实时碰撞检测算法技术[M].刘天慧译.北京:清华大学出版社，2010.

[6]姜晓路，刘渊.一种新的基于混合层次包围盒的碰撞检测算法[J].计算机工程与应用，2012，48（6）:143-145.

[7]Gottschalk S，Lin M C，Manocha D.OBB-Tree:a Hierarchical structure for rapid interference detection[C]// Proceedings of Computer Graphics Conference.New York：ACM，1996：171-180.

[8]Govindaraju N K，Redon S，Lin M C，et al.Cullide: Interactive Collision Detection Between Complex Models In Large Environments Using Graphics Hardware [J]. Proceedingsofthe Siggraph/eurographicsWorkshop on Graphics Hardware，2003:25-32.

[9]Katz S，Tal A.Hierarchical mesh decomposition using fuzzy clustering and cuts[M]//ACM Transactions on Graphics（TOG）.ACM，2003:954-961.

[10]Chang J W，Wang W，Kim M S.Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J].Computer-Aided Design，2010，42（1）:50-57.

[11]王文玺，肖世德，孟文，等.一种基于八叉树空间剖分技术的光线跟踪算法[J].计算机应用，2008，28（3）:656-658.

[12]邹益胜，丁国富，许明恒，等.实时碰撞检测算法综述[J].计算机应用研究，2008（1）:8-12.

[13]王鹏，刘旭敏，关永.基于OBB层次包围盒的碰撞检测算法改进[J].计算机工程与设计，2009，30（13）:3196-3198.

[14]谭同德，吴强，赵红领，等.OBB层次包围盒构造方法的改进[J].计算机工程与应用，2008，44（5）:79-81.

[15]孙劲光，吴素红.基于分类遍历的碰撞检测优化算法[J].计算机应用，2015，35（1）:194-197.

Collision detection algorithm based on space subdivision and classified traversal

LIU Zhao，LI Wei，ZHAO Lu-yang，SHAN Lian-hai
（Chinese Academy of Science Shanghai Institute of Microsystem and Information Technology，Shanghai 200050，China）

In order to solve the shortcoming of real-time and accuracy in collision detection，a novel collision detection algorithm based on space subdivision and classified traversal was proposed.In the space subdivision stage，the octree division was used to get rid of object pairs without intersecting.Then Create hybrid bounding box in the subspace and use classified traversal method to traverse them，aim to reduce the times of intersect tests efficiently.Experimental analyses show that this algorithm can reduce the time cost of collision detection，especially in complex situation.

collision detection；space subdivision；hybrid bounding box；classified traversal

TN919.82

A

1674－6236（2016）24-0151-03

2015-12-09 稿件编号：201512100

上海市青年科技启明星计划（14QB1404400）

刘 昭（1990—），男，河北廊坊人，硕士研究生。研究方向：计算机仿真、数字信号处理。