CN104200031A - 一种基于距离优先和时空相关性的碰撞检测方法 - Google Patents

Abstract

本发明公开了一种基于距离优先和时空相关性的碰撞检测方法，其首先对待检测对象构造对应的方向包围盒，构建相应的层次包围盒树；遍历上述层次包围盒树，在对所述包围盒进行遍历的过程中：首先将所述包围盒各自对应的根节点作为初始节点进行第一次遍历，记录上述包围盒中的不相交的节点，并将所述节点记录到跟踪表中；当再次进行遍历时直接从跟踪表中记录的不相交的节点进行遍历，且在再次遍历的过程中需要对跟踪表进行基于距离优先和时空相关性的更新策略。本发明首先遍历距离比较近的包围盒，寻找最佳路径，减少遍历包围盒的数目，提高了碰撞检测的效率；并提出跟踪表采用堆来保存，加快了碰撞检测的效率。

Description

一种基于距离优先和时空相关性的碰撞检测方法

技术领域

本发明属于碰撞检测领域，尤其涉及基于方向包围盒的碰撞检测方法，并且引入距离优先思想和时空相关性方法。

背景技术

碰撞检测方法在计算几何,计算机动画，仿真机器人和虚拟现实等领域都有较好的应用前景。

近几十年来国内外研究人员对碰撞检测进行了广泛而深入的研究，已经成熟并且被广泛应用的方法有空间分解法和层次包围盒方法。空间分解法是将整个虚拟空间划分成相等体积小的单元，只对占据了同一单元和相邻单元格的几何对象进行相交测试，比较典型的例子有均匀网格，k-d树，八叉树，BSP树。空间分解法通常适用于稀疏环境中分布比较均匀的几何对象间的碰撞检测；层次包围盒法是碰撞检测算法中广泛使用的一种方法，基本思想是用体积略大的几何特征简单包围盒来近似地描述复杂几何对象，通过树状的层次结构逼近几何模型，直到几乎完全获得对象的几何特征，从而只需对包围盒重叠的部分进行进一步的相交测试，典型的方法有AABB,包围球，方向包围盒OBB，k-DOPs。

OBB包围盒因其具有紧密的包裹性，对包围盒进行更新时只需要进行简单的选择平移操作等优点被广泛使用。但是OBB包围盒也具有一定的缺陷，在遍历OBB包围盒树的过程中需要进行包围盒相交测试和三角形相交测试，如果OBB重叠，则需要进行15次测试，那么在进行OBB包围盒树的遍历过程中就需要进行大量的基于包围盒的相交测试，影响计算效率。

发明内容

鉴于已有技术存在的缺陷，本发明的目的是要提供一种新型的碰撞检测方法，本方法引入基于距离优先和时空相关性思想，可有效减小包围盒相交测试的数目，加快碰撞检测的效率，继而提高了算法的效率。

为了实现上述目的，本发明的技术方案：

一种基于距离优先和时空相关性的碰撞检测方法，其特征在于：

ⅰ、首先对待检测对象构造对应的方向包围盒，进而构建相应的层次包围盒树；

ⅱ、遍历上述层次包围盒树，检测待检测对象对应的当前的包围盒是否相交，在对所述包围盒进行遍历的过程中：首先将所述包围盒各自对应的根节点作为初始节点进行第一次遍历，在进行第一次遍历时，记录上述包围盒中的不相交的节点，并将所述节点记录到跟踪表中；当再次进行遍历时直接从跟踪表中记录的不相交的节点进行遍历，且在再次遍历的过程中需要对跟踪表进行基于距离优先和时空相关性的更新策略。

所述的跟踪表基于距离优先和时空相关性的更新策略包括：跟踪表初始化过程以及跟踪表优化过程：

所述的跟踪表初始化过程为：

设vT为跟踪表中第一个标记节点，vF为活动对象根节点

(8)若vT不空，则判断vT的包围盒和vF的包围盒是否相交，若相交进入(2)判断，若不相交，则进入(5)；

(9)如果上述两个包围盒相交，则判断vT是否为叶节点，如果是叶节点，则进入(3)判断，否则进入(4)；

(10)如果vT是叶节点，则遍历vT相应的包围盒树；

(11)如果vT不是叶节点，则删除这个节点，向下更新，即对于vT的每个子节点判断前一时刻与vF不相交的内部节点在当前时刻是否与vF相交，若相交，则从跟踪表中插入此节点，产生新的标记节点；

(12)提取跟踪表的下一节点vN，判断vN和vT是否为兄弟节点。如果vN和vT是兄弟节点，则判断vN的包围盒和vF的包围盒是否相交；

(13)如果vN的包围盒和vF的包围盒不相交，则从跟踪表中删除vT和vN，将vT和vN父节点加入当前相应的位置；

(14)vT指向下一节点，直到遍历完成整个跟踪表的更新初始化过程；

所述的跟踪表优化过程是指：初始化过程之后，基于距离优先的准则，按照距离的远近由近到远对上述跟踪表中的节点进行排序，其中所述的距离是指系统环境中待检测对象的空间位移，即待检测对象的时空相关性，在进行下次遍历时，根据跟踪表中按照距离进行排序的节点对对应的包围盒进行遍历，并实时更新跟踪表。

进一步的，所述跟踪表的存储方式是二叉堆存储方式。

进一步的，所述遍历采用基于距离优先和时空相关性的跟踪表优化的前提条件是系统环境中待检测对象的其各自对应的包围盒的距离小于一定阈值。

进一步的，所述方法还包括设定跟踪表的最大长度，当跟踪表的长度大于当前系统预设的超限值时，不使用本文提出的优化算法，直接采用二叉树遍历策略。

进一步的，基于上述方法在进行待测对象精确相交测试之前，即在遍历上述跟踪表之后，找到两个需要遍历的包围盒后，首先利用预处理方法对待检测对象对应的包围盒进行是否相交的初步检测，从而避免了复杂检测的方法，提高了效率；

所述利用预处理方法包括如下步骤：

首先通过层次遍历，找到需要检测对象对应的两个包围盒，分别以两个包围盒各自中心点作为球心，分别计算两个包围盒的最远顶点与对应的球心的距离得到两个包围盒各自的大球的半径，记为r1,r2；相应的分别以两个包围盒各自中心点作为球心，分别计算两个包围盒的最近顶点与对应的球心的距离得到两个包围盒各自的小球的半径，记为rmin1,rmin2；

其次判断两个包围盒之间的距离re与大球半径之和、小球半径之和的关系：当两个包围盒之间的距离re大于大球半径之和时，则上述包围盒不会相交，返回包围盒相交测试的结果；当上述包围盒之间的距离小于小球半径之和时则上述包围盒一定会相交，同理返回上述包围盒相交测试的结果，不再进行分离轴测试；当两个上述包围盒之间的距离re位于大球半径之和与小球半径之和之间时，利用分离轴的方法进行检测。

其中计算两个包围盒的距离re的公式如下，因为包围盒在不同的坐标系下，所以需要将两个包围盒转换到相同坐标系下才能进行计算，因为算法需要计算根号，为了保证算法的正确性，在计算re时加入一定的弥补因子，保证算法的强健性，

$\mathrm{re}=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2+{(z_1-z_2)}^2}+\mathrm{\ϵ}---\left(1\right)$

其中点(x₁,y₁,z₁)和点(x₂,y₂,z₂)分别表示将两个球转换至同一坐标系下的原点坐标，ε表示弥补因子；

将两个球坐标系原点转换至一个坐标系的公式如下：

P₍₂₎R_(2->1)+T_(2->1)＝P₍₁₎   (2)

其中P₍₂₎表示图中第二个包围盒的坐标原点，R_(2->1)和T_(2->1)分别表示由第二个坐标系到第一个坐标系的旋转矩阵和平移矩阵，P₍₁₎表示将第二个坐标系中的P₍₂₎点转换至第一个坐标系中的点。

与现有技术相比，本发明的有益效果：

本发明选用OBB包围盒作为物体的包围体具有简单快速和检测精确的特点并在OBB包围盒的优势的基础上，利用距离优先的方法根据距离远近有选择的对包围盒树进行遍历，首先遍历距离比较近的包围盒，寻找最佳路径，减少遍历包围盒的数目，提高了碰撞检测的效率；并提出跟踪表采用堆来保存，加快了碰撞检测的效率。

附图说明

图1是本发明OBB碰撞检测算法的流程图；

图2是两个OBB包围盒位置关系二维示意图；

图3是本发明实施例兔子模型的场景图；

图4是本发明实施例龙模型的场景图；

图5是采用本发明实施例提供的利用预测算法进行碰撞检测方法的包围盒数目对比图；

图6是本发明实施例提供的利用跟踪算法进行碰撞检测方法的包围盒数目的对比图；

图7是本发明实施例提供的利用本发明提供的算法进行碰撞检测的时间比较图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图，对本发明进行进一步详细说明。

如图1-图2所示，本发明提供了一种引入距离优先和时空相关性思想，采用基于OBB包围盒进行碰撞检测的新方法。

其中OBB包围盒的计算和创建层次包围盒树为碰撞检测的预处理阶段，检测出碰撞检测的过程为碰撞阶段。OBB计算的关键是寻找最佳方向，确定在该方向上包围对象的包围盒的最小尺寸。建立层次包围树的过程就建立了碰撞检测的层次结构。通常采用二叉树遍历方法生产有向包围盒树。

在预处理阶段，算法已经为将要进行碰撞检测的两个物体(A和B)构建了层次包围盒树，检测两个物体是否相交可以通过递归遍历它们的层次二叉树，遍历采用广度优先的策略进行，具体步骤如下：

(1)遍历过程首先从两物体的层次树的根节点开始，并将它们设置为当前遍历的节点。

(2)判断当前的节点的OBB包围盒是否相交，如果不相交，则递归返回。否则执行步骤(3)

(3)假如当前的包围盒相交，则进一步判断当前节点是否为叶子节点，如果是，则进行基本图形三角形相交测试，并根据三角形相交测试的结果判断A和B是否发生碰撞

(4)如果B物体到达叶子节点或者A物体没有到达叶子节点，则遍历A物体的左右孩子，进行递归遍历，否则进行(5)

(5)遍历B物体的左右孩子进行递归遍历。

OBB包围盒不同于其他包围盒，进行两个方向包围盒之间的相交测试比较复杂。OBB相交测试可以采用“分离轴测试”加以实现。

当判断两个长方体是否相交时，判断二者是否存在分离轴，需要将两个长方体的15个可能的矢量进行判断(每个长方体的各个面的法向量6个，长方体的各个边的方向矢量与另一个长方体的各个边的方向矢量叉积共9个矢量，共6+9＝15个矢量)。如果在某一个潜在分离轴上没有相交，那么存在分离轴，可以判断两个长方体并不相交，如果不能得出分离轴，那么需要判断其他的矢量。

图2示出了本发明涉及的利用预处理方法处理时，两个OBB包围盒位置关系二维示意图，采用预处理方法，可以减小包围盒分离轴检测的数目，从而避免了复杂检测的方法，提高了效率；

所述利用预处理方法对待检测包围盒进行是否相交的初步检测包括如下步骤：通过层次遍历，找到需要检测的两个包围盒，分别以包围盒中心点作为球心，通过计算最远顶点与球心的距离得到大球的半径(r1,r2)以及最近顶点与球心的距离得到小球的半径(rmin1,rmin2)。当两个包围盒之间的距离(re)大于大球半径之和的距离时，包围盒不会相交，返回包围盒相交测试的结果；当包围盒之间的距离小于小球半径之和的距离时包围盒一定会相交，同理返回包围盒相交测试的结果，不再进行分离轴测试；当包围盒之间的距离位于二者之间时利用分离轴的方法进行检测。

其中计算两个包围盒的距离re的公式如下，因为包围盒在不同的坐标系下，所以需要将两个包围盒转换到相同坐标系下才能进行计算。因为算法需要计算根号，为了保证算法的正确性，在计算re时加入一定的弥补因子，保证算法的强健性。

$\mathrm{re}=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2+{(z_1-z_2)}^2}+\mathrm{\ϵ}---\left(1\right)$

其中点(x₁,y₁,z₁)和点(x₂,y₂,z₂)分别表示将两个球转换至同一坐标系下的原点坐标。ε表示弥补因子，通常为10^-6。

将两个球坐标系原点转换至一个坐标系的公式如下：

P₍₂₎R_(2->1)+T_(2->1)＝P₍₁₎   (2)

其中P₍₂₎表示图中第二个包围盒的坐标原点，R_(2->1)和T_(2->1)分别表示由第二个坐标系到第一个坐标系的旋转和平移矩阵。P₍₁₎表示将第二个坐标系中的P₍₂₎点转换至第一个坐标系中的点。

上述预处理方法对应的伪代码如下：

if(re<rmin1+rmin2)//当包围盒之间的距离小于小球之间的距离时，返回包围盒相交

利用包围盒的思想构建好层次包围盒树在遍历包围盒的过程中，首先进入基于距离优先以及时空相关性的特性建立跟踪表的方法。结合碰撞检测的实验条件，通过优化跟踪方法的存储结构以及结合距离优先方法的思想，进一步优化遍历条件。

其中，结合时空相关性减小包围盒相交的数目即遍历的过程中需要对跟踪表进行基于距离优先和时空相关性的更新策略。

所述的跟踪表基于距离优先和时空相关性的更新策略包括：跟踪表初始化过程以及跟踪表优化过程：

所述的跟踪表初始化过程为：

设vT为跟踪表中第一个标记节点，vF为活动对象根节点

(15)若vT不空，则判断vT的包围盒和vF的包围和是否相交，若相交进入(2)判断，若不相交，则进入(5)

(16)如果包围盒相交，则判断vT是否为叶节点。如果是叶节点，则进入(3)判断。否则进入(4)

(17)如果是叶节点，则遍历相应的包围盒树

(18)如果不是叶节点，则删除这个节点，向下更新，即对于vT的每个子节点判断前一时刻与vF不相交的某个内部节点在当前时刻是否与vF相交，若相交，则从跟踪表中插入此节点，产生新的标记节点。

(19)取得跟踪表的下一节点vN，判断vN和vT是否为兄弟节点。如果是兄弟节点，则判断vN的包围盒是否和vF的包围盒是否相交。

(20)如果包围盒不相交，则从跟踪并删除vT和vN，将父节点加入当前位置。

(21)vT指向下一节点，直到遍历完成整个跟踪表。

其中，跟踪表中的元素都是标记节点，因为在第一次进行遍历时，记录了不相交的节点，并将它记录到跟踪表中，再次进行访问时从跟踪表进行访问，所以称作标记节点；那么在将碰撞检测的两个物体一个当作环境对象，我们记录环境对象中的相关节点作为标记节点，相对的，另一个则当作活动对象。

所述的跟踪表优化过程是指：初始化过程之后，基于距离优先的准则，按照距离由近到远对上述跟踪表中的节点进行排序，其中所述的距离是指系统环境中待检测对象的空间位移，即待检测对象的时空相关性，在进行下次遍历时，根据跟踪表中按照距离进行排序的节点对对应的包围盒进行遍历，并实时更新跟踪表。

具体的：

跟踪表的更新优化原则是，若跟踪表在前一时刻与物体根节点不相交的某个内部节点在当前时刻与根节点相交，则从跟踪表中删除这个节点，并加入对这个节点子树作为遍历时的标记节点。如果表中有两个互为兄弟的节点在当前情况下都与根节点不相交，便把兄弟节点从表中删除，用它们的父节点进行取代。构建层次包围盒树之后，利用距离(从数学绝对值的角度也可以理解为距离的大小)优先的方法，对跟踪表中的节点进行排序。利用距离优先的方法根据距离远近有选择的对包围盒树进行遍历，首先遍历距离比较近的包围盒，寻找最佳路径，减少遍历包围盒的数目，提高碰撞检测的效率；

其中，根据跟踪表中按照距离进行排序的节点，对包围盒进行遍历。对跟踪表中的节点按照距离先后由小到大排序即由近及远，先从最近的开始遍历，当判断不出未相交时，再向后遍历。其中，排在跟踪表前面的节点称为距离近的节点，排在跟踪表后面的节点称为距离远的节点。在遍历包围盒树的过程中，按照距离近的包围盒优先遍历。如果距离短的包围盒返回不相交，则没必要进行远距离的包围盒的遍历。如果距离短的包围盒相交，说明两个物体已经发生碰撞，提高了检测发生碰撞的时间，如果需要精确得出包围盒相交的三角形片的个数，则需要对距离远的包围盒进行遍历，在遍历过程中仍然按照距离优先的原则。

同时当两个物体在两个间隔的时间间隔内运行速度比较快，两个物体已经不相交，利用常规的方法，只需要从包围盒树的根节点遍历一次就可以判断包围盒是分离的，即当两物体相交度小时，但是采用时空相关性进行遍历需要遍历在上一个时间点不相交的节点，需要访问大量的节点，逐渐向上递归，才能够判断包围盒不相交，大大降低了效率，从而失去了优势。虽然减少了树的深度，但是需要内存额外的添加保存跟踪表的空间，相当于用空间换取时间，效果并不明显。所以本文提出基于最初包围盒的距离判断(本方法中提及距离判断是系统环境中，空间位移的判断，并不是是碰撞检测结果中的两个包围盒之间的最近距离，这个距离可以从系统数据中计算从来。例如已知两个物体的中心点在三维空间中平移和旋转，能够得到移动后的位移，通过跟前一刻的位移对比，即可判断距离是变大还是变小。当物体之间距离在一定范围内才使用跟踪策略。)是否使用跟踪表优化策略，当两个包围盒之间的距离小于一定阈值之后，即通过跟踪表中记录的节点小于一定数目时，才利用跟踪表优化策略进行遍历。当包围盒之间的距离大于一定值是，采用一般的遍历方法进行遍历。

当两个包围盒之间的距离增大时，包围盒不会向上更新，每次需要从跟踪表中遍历之前不相交的大量节点，而此时可能从根节点遍历少数节点就可以判断包围盒不相交。然而使用遍历策略却增加了内存的存储空间，降低了遍历的效率。所以可以在包围盒之间的距离减少时才使用遍历策略。从而避免了上述情况的发生。

同时对于距离优先优化算法，如果需要对整棵树按照距离的远近，生成新的树，会额外增加存储空间，而且在生成新树的过程已经完成遍历的操作。如果只是对于跟踪表中的节点进行距离排列，则相当于对树的节点增加了索引，只对索引进行距离排列。当距离近的索引返回不相交时，则无需对距离远的索引进行遍历。在解决对于索引表排序的问题上，放弃使用链表存储，而使用二叉堆存储。

因为当使用链表，对于n个标记节点进行排序时，时间复杂度为O(n2),读取时间为O(1)，总的时间复杂度为O(n2)+O(1)。对于n个标记节点构建堆，时间复杂度为O(n)，每次操作的平均时间复杂度和最坏情况下时间复杂度都为O(logn)，总的时间为O(nlogn)，故采用二叉堆后，总时间复杂度为O(nlogn)+O(n)＝O(nlogn)，时间上要比链表快。

当物体完全相交时，跟踪表记录了所有的叶子节点，会增大跟踪表的长度。通过测试当跟踪表长度到达2564时，内存分配不足，会造成死机。(仅限于本机的实验环境，数据仅做参考)所以需要设定跟踪表的最大长度，当跟踪表大于一定值(系统预设的超限值)时，直接使用遍历策略，不再向下更新跟踪表。

实施案例1

本案例在传统的方法上增加了预处理方法以及基于距离优先法和跟踪方法的改进方法。

本案例选用斯坦福大学提供的模型作为数据进行验证。实验使用VC++在CPUPentium(R)Dual-core内存2G的PC机上运行的。为了直观的现实碰撞的情景，采用OpenGL对数据进行展示。我们选用两个实验场景，三角形切片数依次增加。选用斯坦福提供的模型作为数据，进行分析。场景一为兔子模型，含有16301个三角形切片。场景二为龙模型，含有43765个三角形切片。实验场景如图3，图4所示。

采用本发明所提供的预处理算法进行包围盒的相交检测的预测，实验结果如图5所示。

其中横坐标代表两个包围盒的不同状态，纵坐标表示利用分离轴方法进行检测的包围盒数目。带有正方形的曲线表示之前的数目，带有菱形的曲线表示之后的数目。其中1至8状态分别表示两个物体由远及近的过程，在本实验中，状态1表示x轴平移距离为1，以后每个状态平移距离依次减少0.1。

采用本发明所提供的改进的跟踪算法和距离优先算法对进行检测的包围盒的数目进行统计，实验结果如图6所示。

同样的横坐标表示包围盒的不同状态，纵坐标表示碰撞检测中包围盒相交检测的数目。带有正方形的曲线表示没有加入跟踪策略的数据，带有菱形的曲线表示加入后的数据。为了更好的表现规律，选取了7个状态。1状态表示两个物体横坐标距离为1.2，之后每个状态横坐标减少0.1。由上图可知，当包围盒树达到一定的深度，采用跟踪优化策略效果比较明显。

采用本发明提供的算法，对碰撞检测的效果进行测试，结果如图7所示。

案例中的时间采用时钟计数除以时钟周期获得的值，仅作为衡量标准。同样的选取八个状态。其中1至8状态分别表示两个物体由远及近的过程，状态1表示x轴平移距离为1，以后每个状态平移距离依次减少0.1。带有正方形的曲线表示利用传统的碰撞检测方法碰撞检测的时间，带有菱形的曲线表示利用本发明所使用的方法进行碰撞检测所用的时间。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。

Claims (6)

1.一种基于距离优先和时空相关性的碰撞检测方法，其特征在于：

ⅰ、首先对待检测对象构造对应的方向包围盒，进而构建相应的层次包围盒树；

ⅱ、遍历上述层次包围盒树，检测待检测对象对应的当前的包围盒是否相交，在对所述包围盒进行遍历的过程中：首先将所述包围盒各自对应的根节点作为初始节点进行第一次遍历，在进行第一次遍历时，记录上述包围盒中的不相交的节点，并将所述节点记录到跟踪表中；当再次进行遍历时直接从跟踪表中记录的不相交的节点进行遍历，且在再次遍历的过程中需要对跟踪表进行基于距离优先和时空相关性的更新策略。

2.根据权利要求1所述的基于距离优先和时空相关性的碰撞检测方法，其特征在于：所述的跟踪表基于距离优先和时空相关性的更新策略包括：跟踪表初始化过程以及跟踪表优化过程：

所述的跟踪表初始化过程为：

设vT为跟踪表中第一个标记节点，vF为活动对象根节点

(1)若vT不空，则判断vT的包围盒和vF的包围盒是否相交，若相交进入(2)判断，若不相交，则进入(5)；

(2)如果上述两个包围盒相交，则判断vT是否为叶节点，如果是叶节点，则进入(3)判断，否则进入(4)；

(3)如果vT是叶节点，则遍历vT相应的包围盒；

(4)如果vT不是叶节点，则删除这个节点，向下更新，即对于vT的每个子节点判断前一时刻与vF不相交的内部节点在当前时刻是否与vF相交，若相交，则从跟踪表中插入此节点，产生新的标记节点；

(5)提取跟踪表的下一节点vN，判断vN和vT是否为兄弟节点。如果vN和vT是兄弟节点，则判断vN的包围盒和vF的包围盒是否相交；

(6)如果vN的包围盒和vF的包围盒不相交，则从跟踪表中删除vT和vN，将vT和vN父节点加入当前位置；

(7)vT指向下一节点，直到遍历完成整个跟踪表的更新初始化过程；

所述的跟踪表优化过程是指：初始化过程之后，基于距离优先的准则，按照距离由近到远对上述跟踪表中的节点进行排序，其中所述的距离是指系统环境中待检测对象的空间位移，即待检测对象的时空相关性，在进行下次遍历时，根据跟踪表中按照距离进行排序的节点对对应的包围盒进行遍历，并实时更新跟踪表。

3.根据权利要求2所述的基于距离优先和时空相关性的碰撞检测方法，其特征在于：所述跟踪表的存储方式是二叉堆存储方式。

4.根据权利要求2所述的基于距离优先和时空相关性的碰撞检测方法，其特征在于：所述遍历采用基于距离优先和时空相关性的跟踪表优化的前提条件是系统环境中待检测对象的其各自对应的包围盒的距离小于一定阈值。

5.根据权利要求2所述的基于距离优先和时空相关性的碰撞检测方法，其特征在于：所述方法还包括设定跟踪表的最大长度，当跟踪表的长度大于当前系统预设的超限值时，不使用本文提出的优化算法，直接采用二叉树遍历策略。

6.根据权利要求1所述的基于距离优先和时空相关性的碰撞检测方法，其特征在于：基于上述方法在进行待测对象精确相交测试之前，即在遍历上述跟踪表之后，找到两个需要遍历的包围盒后，首先利用预处理方法对待检测对象对应的包围盒进行是否相交的初步检测；

所述利用预处理方法包括如下步骤：

首先通过层次遍历，找到需要检测对象对应的两个包围盒，分别以两个包围盒各自中心点作为球心，分别计算两个包围盒的最远顶点与对应的球心的距离得到两个包围盒各自的大球的半径，记为r1,r2；相应的分别以两个包围盒各自中心点作为球心，分别计算两个包围盒的最近顶点与对应的球心的距离得到两个包围盒各自的小球的半径，记为rmin1,rmin2；

其次判断两个包围盒之间的距离re与大球半径之和、小球半径之和的关系：当两个包围盒之间的距离re大于大球半径之和时，则上述包围盒不会相交，返回包围盒相交测试的结果；当上述包围盒之间的距离小于小球半径之和时则上述包围盒一定会相交，同理返回上述包围盒相交测试的结果，不再进行分离轴测试；当两个上述包围盒之间的距离re位于大球半径之和与小球半径之和之间时，利用分离轴的方法进行检测；

其中计算两个包围盒的距离re的公式如下，因为包围盒在不同的坐标系下，所以需要将两个包围盒转换到相同坐标系下才能进行计算，因为算法需要计算根号，为了保证算法的正确性，在计算re时加入一定的弥补因子，保证算法的强健性，

$\mathrm{re}=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2+{(z_1-z_2)}^2}+\mathrm{\&epsiv;}---\left(1\right)$

其中点(x₁,y₁,z₁)和点(x₂,y₂,z₂)分别表示将两个球转换至同一坐标系下的原点坐标，ε表示弥补因子；

将两个球坐标系原点转换至一个坐标系的公式如下：

P₍₂₎R_(2->1)+T_(2->1)＝P₍₁₎   (2)

其中P₍₂₎表示图中第二个包围盒的坐标原点，R_(2->1)和T_(2->1)分别表示由第二个坐标系到第一个坐标系的旋转矩阵和平移矩阵，P₍₁₎表示将第二个坐标系中的P₍₂₎点转换至第一个坐标系中的点。