基于空间分解与混合包围盒的碰撞检测算法*

宋涛，舒涛，梅朝，张卫东

（空军工程大学防空反导学院，西安710051）

基于空间分解与混合包围盒的碰撞检测算法*

宋涛，舒涛，梅朝，张卫东

（空军工程大学防空反导学院，西安710051）

针对如何提高碰撞检测效率的问题，提出一种基于空间分解法和混合包围盒的碰撞检测算法。首先利用均匀剖分法确定相邻对象，然后只对相邻对象构建混合层次包围盒树，最后引入任务树的概念加速包围盒树的遍历过程。在包围盒碰撞检测中，提出了一种顶层采用AABB，其他层采用OBB的混合层次包围盒结构。实验结果表明，该算法有效提高了碰撞检测的效率和实时性。

碰撞检测，空间分解，包围盒，任务树

0 引言

碰撞检测（Collision Detection，CD）也称为干涉检测或者接触检测，是系统仿真、虚拟现实技术等领域中的关键性问题。顾名思义，其任务就是根据现实中一对或多对对象不能在同一时刻占有相同区域的事实来检测虚拟场景中的对象是否发生碰撞或穿透现象，这对于虚拟场景的真实感和实时性有着重大作用。空间分解法和层次包围盒法是两类经典的碰撞检测算法［1］。空间分解法是将空间划分为不同的区域，找到占据同一区域的相邻对象，只对相邻对象进行检测，常用的空间分解方法有树、均匀网格和空间排序等；层次包围盒的思想是用体积略大而几何特征简单的包围盒来代替复杂的几何对象进行碰撞检测，只需对包围盒重叠的对象进行进一步碰撞检测，常用的包围盒有Spheres，AABB，OBB和k-DOPs等［2］。

随着人们的认知水平对计算机虚拟世界复杂度、真实感要求的提高和虚拟场景中模型的数量和复杂度急剧增大，单纯基于空间分解或层次包围盒的碰撞检测法的精确性和实时性已经难以满足需求，本文提出了一种将空间分解和层次包围盒相结合的算法，首先利用空间均匀剖分法确定相邻对象，然后利用层次包围盒法对相邻对象进行精确碰撞检测，在层次包围盒的构造上选取上层为AABB，下层为OBB的混合包围盒结构，在保证算法精度的前提下，有效减少了构造层次包围盒树的数量和深度以及包围盒相交测试的次数，提高了检测效率。

1 相关理论

1.1空间分解

空间分解法是将空间剖分为邻接区域并将场景对象与其交叠的全部区域关联，仅对位于同一区域的对象执行组合测试，可以尽快排除明显不相交的对象，大大降低了组合测试的数量。均匀网格是一种常用的空间分割方法，将整个空间划分为大小均匀的网格，每个对象对应一个或多个网格单元，只有处于同一网格单元中的对象才可能相交，因而只需对这些空间单元进行进一步的精确碰撞检测，本文采用这种空间分解方法。

1.2AABB

轴向包围盒（Axis-Aligned Bounding Box，AABB）被定义为包含对象且边平行于坐标轴的最小正六面体［3］。对于给定的对象，仅需得到对象基本几何元素各顶点的x坐标、y坐标以及z坐标的最大值和最小值就可构造AABB。包含的区域为：

AABB最大的特点是相交测试简单快速：能够直接将三维求交降为一维求交问题，只需做6次比较运算。只有当两个AABB在3个坐标轴上的投影区间均相交时AABB才相交。

1.3OBB

方向包围盒（Oriented Bounding Box，OBB）定义为包含该对象且相对于坐标轴方向任意的最小长方体［4］。其最大的特点是包围盒方向的任意性，可以根据对象的形状特点尽可能紧密地包围对象，但这也同时增加了其相交测试的复杂性。

采用“分离轴测试”的方法检测两个OBB之间是否相交，只需得出两个OBB是否存在一条分离轴即可。其相交测试需要存储两个OBB的6个轴向和3个轴向与另3个轴向叉乘得到的9个向量总共15个轴。依次在这些轴上，检查两个OBB的投影区间是否相交。判断两个OBB相交即判断它们在15个方向上的投影区间是否均相交，最多只要做15次比较运算。构造OBB的关键问题是找到最佳方向并确定该方向上包围对象的包围盒的最小尺寸。

1.4任务树

碰撞检测的核心就是遍历两个对象的层次包围盒树，本文引入任务树的概念改进传统的遍历方法，加速遍历过程。

这里把遍历两棵层次包围盒树定义为一棵任务树，任务为两对象包围盒树节点间的碰撞检测，从而只需对该任务树进行单重遍历即可完成对两棵包围盒树同步深度优先遍历［5］。子任务树之间是或的关系，只要其中一个子任务树检测出相交，则两对象一定发生碰撞，遍历完整棵任务树都没有相交，则两对象没有碰撞。因为各子任务是相互独立的，所以各层次上的子任务可以并行处理，从而加快了处理速度。假设对对象A、B进行碰撞检测，其任务树如图1所示，a和b是两棵待检测的包围盒二叉树的根节点，a→left与a→right分别表示节点a的左右两个子节点。

图1 A，B两个对象的碰撞检测任务树

2 算法实现

2.1算法概述

算法主要包括空间分解和混合层次包围盒碰撞检测两个阶段。首先，通过均匀剖分法将空间划分为均匀网格，找到占据同一网格的相邻对象。然后，对相邻对象构造AABB-OBB混合层次包围盒树，利用任务树的方法遍历这些包围盒树，得到可能相交的基本几何元素对。最后，对这些基本几何元素对进行几何间的相交测试，最终获得详细的碰撞信息，算法流程如图2所示。

图2 算法流程图

2.2空间分解阶段

利用均匀剖分法将空间划分为大小为a的正方体空间单元，并进行编号。假设场景空间中有n个对象，分别标记为O1，O2，…，On，求出每个对象所在的空间单元，然后在对象的数据结构中增加一个list链表，用于存储与该对象相邻的对象标识，在list中仅记录对象标识比自身标识大的相邻对象，从而防止重复检测。

空间分解的目的是为了快速排除距离较远的对象，确定相邻对象，从而大大减少层次包围盒检测阶段需要构造包围盒树的数量，在复杂多对象的虚拟场景中效果显著。如果直接将对象的基本几何元素映射到空间单元中，计算较为复杂，本文先求出整个对象的AABB，近似表示对象所在的空间单元。取3个整数（i，j，k）依次代表x，y，z轴上的标识来唯一的标识一个空间单元。

假设对象的AABB包围盒的主对角线上两个顶点分别是p1（x1，y1，z1），p2（x2，y2，z2）。p1所在的空间单元（i1，j1，k1）可由式（2）得到：

同理可得p2所在的空间单元（i2，j2，k2）。那么该对象所占的空间单元可以近似表示为（i1，j1，k1）和（i2，j2，k2）之间所有的连续空间单元。占据同一单元的称为相邻对象。

2.3碰撞检测阶段

采用自顶向下的方法对相邻对象构造AABB-OBB混合层次包围盒二叉树，包围盒树设计为两层结构，上层根节点采用AABB，下层采用OBB。因为包围盒树的遍历每次都是从顶层开始，所以上层采用结构简单的AABB可以大大减少计算量，并能迅速排除相邻单元明显不相交的对象。下层采用紧密性好的OBB可以及时进入精确的碰撞检测阶段，避免过多的冗余计算，并能保证检测精度。由于AABB可以看作特殊方向的OBB，则此设计结构实际上只需进行顶层之间的AABB-AABB相交测试和其他层的OBB-OBB两种相交测试，解决了混合层次包围树相交测试复杂的问题。AABB-OBB混合层次包围盒二叉树结构如图3所示。

图3 AABB-OBB结构图

遍历对象的list链表，检测各对象与其list表中的相邻对象是否发生碰撞，采用任务树的方法遍历对象包围盒树之间的相交情况，具体步骤如下：

步骤1：对两个对象的根节点a和b进行碰撞检测。检测两个根节点的AABB是否相交，若不相交，则直接判定两对象之间未发生碰撞，否则进入步骤2。

步骤2：若a和b均为非叶子节点，同时并行进行a→left与b→left，a→left与b→right，a→right与b→left，a→right与b→right相交测试的4个子任务，如果都不相交，则判定两对象之间未发生碰撞，否则进入步骤3；

若a为叶子节点，b为非叶子节点，并行进行a与b→left和a与b→right相交测试两个子任务，如果都不相交，则判定两对象之间未发生碰撞，否则进入步骤3；

若b为叶子节点，a为非叶子节点，并行进行a→left与b和a→right与b相交测试两个子任务，如果都不相交，则判定两对象之间未发生碰撞，否则进入步骤3；

若a和b均为叶子节点，则进行基本几何元素之间的精确碰撞检测，如果相交，则判定两对象之间发生碰撞，返回碰撞详细信息，否则可最终判定两对象不相交。

步骤3：把相交的节点重新记为a和b，返回步骤2。

3 实验结果与分析

实验在CPU I5-4590 3.3 GHz、内存4 G、独立显卡1G的PC机上应用VC 6.0平台实现。每组实验在相同的场景，相同的运动轨迹下，分别利用基于OBB的碰撞检测算法RAPID［6］，基于k-DOPs的Quick CD［7］算法，Sphere-OBB［8］混合包围盒算法以及本文算法进行碰撞检测，对比不同算法在得到相同正确的检测结果（三角形重叠数目相同）下的碰撞检测时间。提高场景的复杂度和包含对象的个数，重复上述实验，实验结果如表1所示，三角形重叠数随着场景复杂度的增加而增加，总共10组实验，算法效率对比如图4所示。

图4 算法碰撞检测时间对比图

由图4可以直观地看出，在三角形重叠数目相同时，本文提出的算法相比RAPID、Quick CD、Sphere-OBB算法，缩短了碰撞检测的时间，提高了碰撞检测的实时性，并且随着空间复杂程度的增加优势更加明显。这是由于本文提出的算法在复杂多对象的场景中结合空间分解法尽早排除了相距较远的对象，大大减少了需要构造的混合层次包围盒树的数量，从而减少算法的计算量。

表1 碰撞检测时间对比

4 结论

本文提出一种基于空间分解与混合层次包围盒相结合的碰撞检测算法。首先利用均匀剖分法排除了场景中相距较远的对象，找到相邻对象，然后对相邻对象进行混合层次包围盒碰撞检测。在混合层次包围盒树的构造中采用一种上层AABB，下层OBB的结构，充分利用了AABB和OBB的优点。在包围盒树的遍历中引入任务树的概念，提高了遍历的速度。实验结果表明，该算法相比其他传统算法提高了碰撞检测的速度和实时性。但是任一碰撞检测算法都不可能适用于所有场景，在包含对象较少的场景中，本文算法的优势并不明显，更适用于包含对象较多、较为复杂的虚拟场景。

［1］LIN M，GOTTSCHALK S.Collision detection between geometric models：a survey［M］.Birmingham：Euro Graphics Association，1998.

［2］邓乾旺，高礼坤，起重机吊装仿真中事实碰撞检测的研究与应用［J］.计算机仿真，2013，30（12）：214-218.

［3］李煜一，李梦怡，王俊彦.碰撞检测中各种包围盒比较研究［J］.信息通信，2014，134（2）：20-21.

［4］史旭升，乔立红，朱作为.基于改进OBB包围盒的碰撞检测算法［J］.湖南大学学报，2014，41（5）：26-31

［5］范昭炜，万华根，高曙明.基于并行的快速碰撞检测算法［J］.系统仿真学报，2000，12（5）：548-552.

［6］GOTTSCHALK S，LIN M C，MANOCHA D.OBB Tree：A hierarchical structure for rapid interference detection［C］//Proc of SIGGRAPH’96，1996：171-180.

［7］KLOSOWSKI J，HELA M，MITCHELL J，et al.Efficient collisiondetectionusingboundingvolumehierarchiesof k-DOPs［J］.IEEE Transactions on Visualization and Computer Graphics，1998，4（1）：21-37.

［8］王立文，刘壁瑶.基于OBB的混合包围盒碰撞检测算法研究［C］∥第六届全国仿真器学术会议论文集.北京：中国系统仿真学会，2007.

A Collision Detection Algorithm Based on Spatial Partitioning and Hybrid Bounding Box

SONG Tao，SHU Tao，MEI Zhao，ZHANG Wei-dong
（Air Defense and Antimissile Institute，Air Force Engineering University，Xi’an 710051，China）

Aiming at the problem of how to improve the efficiency of collision detection，the paper comes up with a collision detection algorithm based on spatial partitioning and hybrid bounding box. Firstly，the adjacent objects with the method of uniform subdivision is determined.Then，hybrid bounding box trees is only built on them.At last，the task tree is introduced to accelerate the process of traveling bounding boxes.In the bounding box collision detection，this paper puts forward a kind of top using AABB，other layer using OBB hybrid bounding box structure.The experimental results show that the proposed algorithm effectively improves the efficiency and real-time performance of collision detection.

collision detection，spatial partitioning，bounding boxes，task trees

TP391

A

1002-0640（2016）11-0094-04

2015-09-25

2015-11-07

国家自然科学基金资助项目（61273156）

宋涛（1990-），男，山东枣庄人，在读硕士。研究方向：武器装备虚拟训练。