孙劲光　吴素红　周积林

1(辽宁工程技术大学电子与信息工程学院　辽宁 葫芦岛 125105)

2(辽宁工程技术大学研究生学院　辽宁 葫芦岛 125105)



基于形状分类的包围盒碰撞检测优化算法

孙劲光1吴素红2周积林2

1(辽宁工程技术大学电子与信息工程学院辽宁 葫芦岛 125105)

2(辽宁工程技术大学研究生学院辽宁 葫芦岛 125105)

摘要由于现有的包围盒不能足够紧密地包围所有待检测的物体，剔除不相交物体的效果差导致了碰撞检测效率低。针对这个问题，提出一种基于形状分类的包围盒碰撞检测优化算法。算法根据每个物体的偏球率将它们进行分类，形状接近球体的，采用球包围盒；形状与球体偏离大的，采用OBB包围盒，这能够更加逼近真实的物体。同时，加入时空相关性和区域划分策略来优化遍历过程。实验结果表明，该算法缩短了相交测试的时间，提高了碰撞检测的效率。

关键词碰撞检测层次包围盒形状分类区域划分时空相关性

OPTIMISATION ALGORITHM FOR BOUNDING BOX COLLISION DETECTION BASED ON SHAPE CLASSIFICATION

Sun Jinguang1Wu Suhong2Zhou Jilin2

1(School of Electronics and Information Engineering,Liaoning Technical University,Huludao 125105,Liaoning, China)2(Institute of Graduate,Liaoning Technical University,Huludao 125105,Liaoning, China)

AbstractSince current bounding boxes cannot sufficiently close to surround all the objects to be detected,the poor effect of weeding out disjoint objects leads to low efficiency in collision detection. In view of this,we propose a shape classification-based optimisation algorithm for bounding box collision detection. This algorithm classifies objects according to the similar-to-sphere rate of each object. For those similar to sphere in shape,it uses the sphere bounding box,and those deviating a lot from sphere in shape,the oriented bounding box will be used,in this way it can better approach real objects. At the same time,the spatiotemporal correlation and space division strategy are added to optimise the process of traversal. Experimental results show that the algorithm shortens the time of intersection test and improves the efficiency of collision detection.

KeywordsCollision detectionHierarchical bounding boxShape classificationSpace divisionSpatiotemporal correlation

0引言

碰撞检测是一项用来检测虚拟环境中的物体在某一时间点上是否占据了同一空间的技术，它可以应用在计算机动画、计算机辅助设计、虚拟现实等各个领域。

由于碰撞检测的应用极其广泛，国内外的专家们已经对其研究多年，并已形成了比较经典的两类算法：空间分割法[1]和层次包围盒法。其中层次包围盒算法由于构造简单且检测更精确，所以更常用。它的核心思想是用体积略大而几何特性简单的包围盒来代替复杂的几何对象，通过构造层次树并对其进行遍历来确定物体的相交状态。

在层次包围盒算法中，需要用紧密性比较好的包围盒来逼近真实的物体，通过检测包围盒间的相交情况来剔除那些没有碰撞上的物体。包围盒的选取是碰撞检测算法的重点，紧密性的好坏将直接影响检测的效率。在早期，算法大多采用单一且结构简单的包围盒，如包围球(sphere)[2]、轴向包围盒(AABB)[3]、任意方向包围盒(OBB)[4,5]、离散方向包围盒(K-Dop)[6]。近几年，专家们纷纷对包围盒的结构进行了改进。在2010年，出现了双层树[1]结构，它是将层次包围盒树的每个节点分成内外两层，分别采用不同的包围盒。在2014年，出现了分层树结构[7]，这是将每个物体的层次包围盒树分成几个层次，分别采用不同的包围盒。这些算法在一定程度上都提高了算法的效率，但是分成层结构造成了不同层内节点的相交，一定程度上会增加复杂性，而多层结构的存储难免会造成数据的冗余。

现有的算法都是对每一个物体采用统一的包围盒结构，而现实中的物体大多都形状各异，同一种包围盒结构很难适应所有的物体。所以本文考虑每个物体形状上的差异，提出一种基于形状分类的包围盒碰撞检测算法。考虑到包围盒的紧密性，将形状近似球体的一类，采用球包围盒，而形状与球体相差大的一类，采用OBB包围盒。此外，加入区域划分策略和时间相关性理论，对碰撞检测过程进行优化，从而整体提高了碰撞检测的效率。

1算法的基本思想

算法分三个阶段：区域划分阶段、物体分类阶段和遍历优化阶段。

在物体分类阶段，所有物体将在形状上进行分类，分类的依据为本文定义的偏球率的大小。物体将被分为两类，第一类的物体形状逼近球体，在各坐标轴上的分布均匀，在包围盒构造时，采用球包围盒;第二类的物体形状与球体相差较大，往往比较细长，在包围盒构造时，采用OBB包围盒。这一分类的操作是本文的一个重点，它能够增加包围盒对物体的拟合程度，从而更加精确地将不相交的物体剔除掉，减少基本三角形间的测试次数

在区域划分阶段，要将虚拟空间划分成一个个小的长方体区域，只对同处于一个小区域的物体两两组合进行碰撞检测。这一步可以减少大量的待检测的物体对。

最后，在包围盒遍历优化阶段，加入时间相关性理论，利用上一时刻存储的关键节点信息来为这一时候判断它们的碰撞情况提供线索，减少冗余的遍历路径，从而达到优化效果。

2基于形状分类的包围盒碰撞检测优化算法

2.1物体在形状上的分类

虚拟空间中的几何物体都是有一个个三角面片构成，构成三角面片的点集完全能够显示出物体的特性，分析点集的分布可以确定物体的大致形状。

定义1偏球率：物体与其所构成的包围球之间的差异率。公式如下：

(1)

其中，n表示点集中点的个数，(xi,yi,zi)表示点集中第i个点的坐标，(ox,oy,oz)表示包围球的中心坐标，r表示包围球的半径。

偏球率的大小反映出物体偏离其包围球体的程度。数值越小越接近球，数值越大越偏离球体。

根据物体的形状将物体分类的过程如下：

(1) 根据每个物体的点集计算出最小包围球。

包围球的球心坐标为各点的x、y和z坐标的均值，包围球的半径为球心与三个最大值坐标所确定的点间的距离。

(2) 根据式(1)计算每个物体的偏球率。

(3) 根据偏球率将物体分类。在这里需要设定一个偏球阈值，如果物体的偏球率超过该值说明这个物体偏离球的程度很大，那么就对其采用OBB包围盒；如果物体的偏球率小于该值说明它十分逼近球体，那么就采用球对其包围。

2.2包围盒间的相交测试

层次包围盒算法在实时检测时，需要进行三类包围盒间的相交测试，即Sphere-sphere、OBB-OBB、OBB-Sphere。

2.2.1Sphere-Sphere

判断是否相交的依据为两球心的距离是否大于两球半径之和，为减少计算的复杂度，采用平方形式：

|o1o2|2>(r1+r2)2

(2)

其中，o1、o2为两个包围球的球心，r1、r2为两个包围球的半径，|o1o2|为两球心的距离。

式(2)成立，这两个包围球是相离的，否则，这两个包围球被判定为相交。

2.2.2OBB-OBB

1) 接触情况的预判断

在检测两个OBB包围盒是否相交之前，先对它们的接触情况进行预测[8]，这样可以避免一些不必要的相交测试过程。

有2个待检测的OBB包围盒Bi和Bj，oi(xi,yi,zi)，oj(xj,yj,zj)分别表示两个包围盒的中心。oi.max和oi.min分别是包围盒Oi到其中心的最大距离和最小距离，oj.max和oj.min分别是包围盒Oj到其中心的最大距离和最小距离，D表示Oi到Oj的距离。通过下面不等式预测两个OBB间的相交情况。

(3)

D

(4)

D>Oi.max+Oj.max

(5)

若式(4)成立，两个OBB必相交，返回碰撞检测结果为未碰撞；若式(5)成立，这两个OBB必定不相交，返回碰撞检测结果为碰撞；否则，需要继续继续执行OBB间的基本相交测试。

2) 相交测试

采用分离轴理论[9]来实现OBB的相交测试。如图1所示，对于某一轴L，若两个包围体投影半径之和小于中心点之间的投影距离，即|T·L|>r1+r2，那么它们就是相离的。

图1　分离轴理论

最多需要测试15个潜在分离轴来确定OBB的相交状态。这些轴包括B1的三个坐标轴，B2的三个坐标轴以及垂直于每一轴的9个轴。若在上述轴上的任一轴上没有产生重叠，那么这两个OBB是分离的，若检测完所有轴，每个轴上都产生重叠，那么这两个OBB就是相交的。

2.2.3Sphere-OBB

类似于OBB-OBB间的相交测试，判断Sphere-OBB是否相交的依据同样是不等式|T·L|>r1+r2。假设有包围球O和OBB包围盒B，r为O的半径，bi为B的长宽高长度的一半(i=1,2,3)，Bi是平行于B的轴单位向量(i=1,2,3)，T为两包围盒中心的距离，L为平行于OBB分离轴的单位向量。r1为r在L上的投影，r2为bi在L上的投影之和。那么得到公式如下：

r1=r

(6)

(7)

(8)

若式(8)成立，则两个包围盒不相交，否则继续计算它们在其他2个分离轴上的投影是否重叠，若三个轴上的投影都不满足该不等式，那么判断这两个包围盒相交。

2.3算法的优化

2.3.1区域划分策略

虚拟环境中的物体众多，如果将所有物体两两组合进行检测，那么系统每秒钟的测试量将是巨大的。很可能会造成“刺穿”[10]甚至“遗漏”现象，这严重影响了碰撞检测的实时性。

为了及时检测出物体对间的碰撞，本文在构造层次包围盒之前加入区域划分策略[14]。该策略是将整个虚拟空间划分为一个个小的长方体区域，只对同处于一个小区域内的物体们执行包围盒碰撞检测算法。在这里，将每个物体的相邻物体(同处于一个小区域的)存起来，针对每个物体实现碰撞检测的并行化。

现空间中有n个物体，它们的标识依次为O1，O2，…，On，为每一个物体的数据结构中都添加一个相邻链表AdList，用来存储该物体的相邻物体。算法的具体过程如下：

(1) 将整个空间分割成小的长方体单元。在这里将所有物体长宽高的均值作为长方体单元的大小。

(2) 创建一个数组Array，用于存放空间中的所有物体。

(3) 遍历数组Array并对其中的每一个物体构造AdList链表，链表中存放与该物体占据同一个单元的比自身标识序号大的其他物体的标识。

(4) 为每个AdList链表不为空的物体分配一个线程[11]，并行地执行与其相邻的物体间的碰撞检测，实现检测的并行化。

2.3.2时间相关性

在虚拟环境中物体虽然都在随机运动，但是它们的运动却是连续的，而不是每一个时刻都在瞬移。那么在相邻时间采样点上，物体的位置和状态往往变化很小。也就是说，当前时间点两物体的相交状态与上一时间采样点是关联的。如果两个物体碰撞了，那么在下个时间采样点物体也很有可能是碰撞的，并且碰撞的位置是相近的；如果两个物体没碰撞，那么在下个时间采样点也很可能不发生碰撞[12]，这就是时间相关性理论。

引入时空相关性，可以通过记录上一时间采样点两物体的相交测试状态，为下一时间采样点判断它们的相交状态提供方便，从而来优化遍历过程。在这里，记录一些关键节点[13](未发生碰撞的内部节点和遍历到的叶节点)，在下一个时间采样点就可以不必从树根开始向下遍历，而是从这些关键节点开始向下遍历，减少重复的遍历路径。由于这些关键节点所包含的子树的交集是空集，并集是全集，所以整个遍历过程是正确完整的。

下面是一个用二叉树表示的对象，它在两个相邻时间采样点(t，t+1时刻)与其他对象发生碰撞的情况如图2和图3所示。其中灰色节点表示与其他对象发生了碰撞，白色节点表示与其他对象未发生碰撞，右侧list表存储当前采样点的关键节点。

图2　t时刻物体的碰撞情况以及对应的关键点表

图3　t+1时刻物体的碰撞情况以及对应的关键点表

根据图2和图3可知，在t时刻，需要存储的关键节点为：(a2,a7,a10,a11)，在t+1时刻，需要存储的关键节点为：(a4,a5,a10,a11,a12,a13)。在t+1时刻进行层次树遍历时，如果按传统的遍历过程(a1,a2,a4,a5,a3,a6,a10,a11,a7,a12,a13),将执行11次相交测试。如果有了t时刻的list表，就可以从关键节点开始向下遍历(a2,a4,a5,a10,a11,a7,a12,a13)，将简化执行8次相交测试。层次包围盒树的高度越高，时间相关性对遍历过程的优化效果越好。

2.4算法的伪程序

CollisionDetection(Array)

描述：该函数依次执行物体分类，区域划分，包围盒遍历优化函数操作，得到每个物体对的碰撞结果。其中Array为存储所有物体的数组，Array.length表示数组的大小，Oi表示Array数组中第i个物体，Oi.Adlist.length表示第i个物体的相邻链表的大小。

输入：Array

输出：Result

//对物体进行分类

For i=0 To Array.length

{

If(Oi的偏球率<=0.143)

//1/7约等于0.143

{//物体Oi划分到第一类，对其构造球包围盒

CreateSphere(Oi);

}

Else

{//物体Oi划分到第二类，对其构造OBB包围盒

CreateOBB(Oi);

}

}

//区域划分并执行包围盒碰撞检测算法

For i=0 To Array.length

{ For j=0 To Array.length

{//构造每个物体的相邻链表AdList

CreateAdList(Oj)

}

If(Oi.AdList不为空)

{//创建线程

CreateThread()

For k=0 To Oi.Adlist.length

{ //并行执行包围盒遍历优化算法

Traverse(Oi,Ok,result)

//更新两物体的关键点表List

UpdateList(Oi,Ok)

}

}

}

3实验

本文算法在Win 7系统下，在具有CPU 2.2 GHz，四核处理器的PC机上应用VS2010和OpenGL实现。实验场景中，有40个形状各异的物体进行随机运动，三角面片的个数多达9000个，如图4所示。

图4　碰撞场景

为了证实本文算法的优越性，我们做了两个实验。

实验一偏球阈值对本算法的影响

通过逐步变化偏球阈值的大小来统计本文算法运行1000步的平均碰撞检测时间(ms)。实验结果如图5所示。

图5　偏球阈值的设定对本文算法的影响

由图可以看出，偏球阈值的大小在一定程度上会影响本文算法的效果。我们发现，当偏球阈值大约等于1/7时，运行1000步的平均碰撞检测时间达到最小。

实验二各算法与本文算法的比较

实验分别采用包围球，OBB和本文采用的分类包围盒进行物体间的碰撞检测，在这里，偏球阈值设为1/7。统计运行1000步的平均碰撞检测时间(ms)和帧频(frame/s)如表1所示。

表1　各算法在碰撞检测时间和帧频上的对比

从表1可以看出，采用形状分类的包围盒方法的碰撞检测算法的平均碰撞检测时间比采用统一包围盒的碰撞检测时间要小，并且帧频也稍有提高。在加入时间相关性和区域划分策略后，算法得到了进一步的优化，平均碰撞检测时间缩小到37.206 ms，场景绘制速度达到了38.42 frame/s。

4结语

本文提出了一种基于物体形状分类的包围盒碰撞检测优化算法。算法根据每个物体的偏球率将物体分成了两类，对不同类别的物体采用不同的包围盒，从而增加了包围盒的紧密性，达到了很好的碰撞剔除效果。除此之外，使用时空相关性来简化遍历过程，利用区域划分策略来减少待检测的物体对，这使碰撞检测过程得到了优化。最后，通过对比实验，证明了相对于其他基于统一包围盒的碰撞检测算法，本文算法所需的碰撞时间更少，碰撞检测的效率在一定程度上得到了提高。

参考文献

[1] 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.

[2] Jiménez P,Thomas F,Torras C.3D collision detection: a survey[J].Computers & Graphics,2001,25(2): 269-285.

[3] Zhang L.The research and realization of collision detection in virtual reality[J].Journal of Communication and Computer,2011,8(8): 693-696.

[4] Stüvel S A,Magnenat Thalmann N,Thalmann D,et al.Hierarchical structures for collision checking between virtual characters[J].Computer Animation and Virtual Worlds,2014,25(3-4): 333-342.

[5] Seiler C,Pennec X,Reyes M.Geometry-aware multiscale image registration via OBBTree-based polyaffine log-demons[M]//Medical Image Computing and Computer-Assisted Intervention-MICCAI 2011.Springer Berlin Heidelberg,2011: 631-638.

[6] Klosowski J T,Held M,Mitchell J S B,et al.Efficient collision detection using bounding volume hierarchies of k-DOPs[J].Visualization and Computer Graphics,IEEE Transactions on,1998,4(1):21-36.

[7] Ding X J.Research on Collision Detection Algorithm Based on Combined Bounding Box[J].Advanced Materials Research,2014,912(2):1353-1356.

[8] 郭凌云,郑延斌,刘晶晶.基于时空相关性的快速碰撞检测算法[J].计算机应用与软件,2013,30(5):174-176.

[9] 张应中,范超,罗晓芳.凸多面体连续碰撞检测的运动轨迹分离轴算法[J].计算机辅助设计与图形学学报,2013,25(1):7-14.

[10] 方彬,王竹林,郭希维.基于完AABB的四维时空层次包围盒碰撞检测方法[J].计算机测量与控制,2014,22(12),397-420.

[11] 赵建斌,李灵巧,杨辉华.线程级并行计算在图形渲染引擎中的研究[J].计算机工程与设计,2011,32(12):4143-4146.

[12] 裴嵩.面向虚拟维修的实时碰撞技术研究[D].南京:南京航空航天大学,2012.

[13] 蒋健勋,方志刚,徐洁,等.基于 Sphere-OBB 的改进碰撞检测算法及其应用[J].计算机工程与应用,2011,47(17):172-174.

[14] 水泳.虚拟现在中连续碰撞检测算法研究[D].合肥:中国科技大学,2013.

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.056

收稿日期：2014-08-12。国家科技支撑计划项目(013bah120 f00)。孙劲光，教授，主研领域：图形图像处理与人脸识别。吴素红，硕士生。周积林，硕士生。