内容发布更新时间 : 2024/5/19 13:41:28星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

基于分类遍历的碰撞检测优化算法

作者：孙劲光 吴素红

来源：《计算机应用》2015年第01期

摘要：针对现有层次树遍历方法的低效率问题，提出了一种基于分类遍历的碰撞检测算法。首先根据两个物体树中节点的平衡因子差值来将所有的物体对进行分类：结构相似的，采用同步下降遍历方法；结构不相似的，采用交换下降遍历方法，这减少了相交测试的次数。然后加入时空相关性和优先级策略优化遍历过程。最后通过实验结果表明，相比基于统一遍历的碰撞检测算法，该算法缩短了相交测试的时间，物体数目越多，快速性优势越显著，大约可以缩减所需时间的1/5。

关键词：碰撞检测；层次包围盒；分类遍历；深度优先；物体结构；时空相关性 中图分类号： TP391.9； TP301.6 文献标志码：A 0 引言

在虚拟环境中，会有多个物体发生运动，它们不可能相互穿越。碰撞检测就是用来检测各物体在某一时刻是否占据了同一空间从而避免它们相互穿越的。这项技术多年来一直备受国内外专家学者的关注，现已形成了两类经典的算法：空间分割法和层次包围盒法。空间分割法[1]是将虚拟空间划分成一个个小区域，只对同处于一个区域的物体进行碰撞检测；而层次包围盒法实现起来更简单，并且检测更精准，所以更常用。它的核心思想是用体积略大而几何特性简单的包围盒来代替复杂的几何对象，通过构造层次树并对其进行遍历来确定物体的相交状态。现已经形成了包围球（sphere）层次树[2]、轴对齐包围盒（Axis Aligned Bounding Box， AABB）层次树[3]、任意方向包围盒（Oriented Bounding Box， OBB）层次树[4-5]、离散有向多面体（K-Discrete Orientation Polytopes， K-DOP）层次树[6]等经典的层次包围盒树。

在层次包围盒算法中，需要按某一下降规则遍历来确定两个包围盒层次树的相交状态。下降规则是相交测试的核心部分，它的好坏直接影响了相交测试的效率。早期，算法大多采用单一下降的规则[7]，虽然实现简单，但是相交测试的次数却很多；后期，出现了同时下降规则[8-9]

，它一定程度上减少了节点间的相交测试次数，但有时却不能有效地缩减搜索空间。这两种

遍历方法都没有考虑到物体对间结构的不同，而统一采用一种下降规则，这可能会降低相交测试的效率。

本文考虑待检测的物体对间结构的差异，提出了一种基于分类的深度优先遍历方法。算法将物体对分为两类：第一类为结构相似的，采用同步下降深度优先遍历方法；第二类为结构相

龙源期刊网 http://www.qikan.com.cn

差大的，采用交换下降深度优先遍历方法。此外，引入时间相关性的思想，使用优先级策略，对遍历过程进行优化，从而整体提高遍历的效率。 1 基于统一遍历的包围盒碰撞检测算法

基于统一遍历的包围盒碰撞检测算法，就是对所有待检测的物体对采用同一种遍历方法。常用的遍历方法有单一下降深度优先遍历和同步下降深度优先遍历方法。前者是先下降其中一棵树至叶节点，然后再下降另外一棵树；后者是同时下降两棵树。

现假设有两棵包含n个叶节点的层次树a和b，它们的叶节点相交了，但是2个物体却未真正地碰撞。那么采用单一下降深度优先遍历方法将会执行2n-1-1次内部节点与节点间的相交测试和（2n-1）2n-1次叶子节点与节点、节点与叶节点、叶节点与叶节点间的相交测试，累计共22n-1-1次相交测试；而同步下降深度优先遍历将会执行（22（n-1）-1）/3次内部节点间的相交测试和22（n-1）次叶节点与节点、节点与叶节点、叶节点与叶节点间的相交测试，累计共（22n-1）/3次相交测试。当n趋近于无穷大，后者的测试量仅为前者的2/3；并且单一下降规则并不太好，若先下降a（或b）的叶子节点几乎都与b（或a）相交，将导致b（或a）的递归次数为a（或b）的叶子节点数，那么结构a（或b）的设计就没有太大意义了。同步下降规则也有其局限性，它虽然能够快速地下降到叶节点；但是对于尺寸和结构相差大的a和b而言，同步下降遍历却不能有效地缩减搜索空间。

综上所述，物体的结构对遍历方法的有效性是有一定影响的。所以本文根据物体对间结构的差别，采用不同的深度优先遍历方法，避免上述下降规则所产生的问题，使得遍历更高效，碰撞检测的实时性更高。

2 基于分类遍历的包围盒碰撞检测算法 2.1 树的度数

在包围盒碰撞检测算法中，为了确定物体间的相交状态就会构造物体的层次树结构，这就会涉及树度数的选择问题。树的深度和度数是成反比的。较高度数的树的深度一般较小，从树根遍历到叶节点的步数会少，而深度大的树的度数一般较高，当前访问节点的子节点数就会增多。考虑两者之间的关系，本文选择二叉树层次结构。因为二叉树优于d叉树[10-11]。当给定n个叶子节点的平衡d叉树，采用单一下降与同步下降遍历方法的消耗分别与f1（d）=d logd（n）和f2（d）=d2 logd（n）成正比，当d=2.71时，前者有最小值；当d=2时，后者有最小值，优先选择d=2。除此之外，二叉树也易于构造和遍历。 2.2 物体对在结构上的分类

碰撞检测时需要将两两为一组的物体对进行碰撞检测。因为每对物体都有各自的特点，所以若将待检测的所有物体对在结构上进行分类，然后分别对其采用不同的遍历方法，将会减少遍历的时间，提高检测效率。

龙源期刊网 http://www.qikan.com.cn

二叉树节点上的平衡因子定义为该节点的左子树的深度减去它的右子树的深度[12]。因为在构造包围盒树的时候，会把具有对齐性质的轴作为分裂轴，物体会相对等体积地被分为左右两份，若左右平衡程度相差大，这就表示某一侧的三角面片数偏多，这一侧的细节程度更大。这样，可以通过两棵树相对应节点的平衡因子的差的绝对值来衡量这两棵树在结构上的差别。若所有对应上的节点的平衡因子差值的绝对值都不大于1，就认为两物体的细节程度相似，在结构上相差不大；否则两物体的细节程度相差大，在结构上不相似。 待检测物体对的分类结论如下：

1）结构上相似的，采用同步下降深度优先遍历方法。 2）结构上不相似，采用交换下降深度优先遍历方法。 交换下降深度优先遍历方法的具体说明如下：

首先下降尺寸较大的树结构a，这是因为树a可能仅有一小部分与尺寸小的树b接触，测试过程中能尽快对大树a进行剪枝。在这里，以树根的包围盒的体积作为物体的尺寸。 然后下降到树a的细节部分时，交换下降对象，对尺寸较小的树b执行下降操作。同样地，下降到树b的细节部分大于树a的细节部分时，再次交换下降对象，对树a进行下降，如此反复，直到遍历过程结束。也就是说，当下降到平衡因子差值大于1的节点时，转而下降另一棵树。

针对结构上相似的物体对，同步下降深度优先遍历方法能够更快地遍历到叶节点，节省遍历的时间，而结构上不相似的物体对，采用一种改进的单一下降（交换下降）深度优先遍历方法。它能够避免单一下降深度优先遍历中递归次数多的问题。 3 算法的优化 3.1 时空相关性

在虚拟环境中进行碰撞检测过程中，时间采样点往往很密集，这就导致相邻采样点的物体状态和位置变化很小。也就是说在上一时间采样点，如果两个物体碰撞了，那么在下个时间采样点物体也很有可能是碰撞的，并且碰撞的位置是相近的；如果两个物体没碰撞，那么在下个时间采样点也很可能不发生碰撞[13]，这就是时空相关性在碰撞过程上的体现。

引入时空相关性的思想，可以优化遍历过程。根据上一时间采样点的遍历情况，记录一些关键节点，在下一个时间采样点就可以不必从树根开始向下遍历，而是从这些关键节点开始向下遍历，减少重复的遍历路径。关键节点[14]包括未发生碰撞的内部节点和遍历到的叶节点。关键节点所包含的子树的交集是空集，并且并集是全集，这就保证了整个过程是完整、正确的，并且没有冗余的遍历路径。