AABB层次包围盒优化方案

（1）包围盒思想

在虚拟环境中进行碰撞体之间的求交检测，其数学原理就是对碰撞体间的位置关系进行判断，即从碰撞体出发，构建表示该碰撞体表面的数学方程并构成联立方程组，通过求解方程组来判断碰撞体之间是否发生碰撞。

但由于在虚拟环境中，实际参与碰撞检测的碰撞体多种多样，因此构建不同碰撞体表面的数学方程十分不易，而且方程组的求解方法也很难实现。同时，为了满足虚拟模拟的实时性的需要，碰撞检测的效率必须达到一定的要求。因此，用于碰撞检测的数学模型必须简化，而采用与碰撞体相似的包围盒来代替碰撞体进行碰撞检测正是包围盒的基本思想。

（2）分离面定理

利用包围盒方法进行碰撞检测，要用到一个重要的定理即分离面定理。

①分离面定理

给定ℜn空间的凸面体P和Q，如果它们内部不相交，则一定存在超平面H，有H//a且H//b，其中：

a，b∈EP∪EQ，EP＝｛e|eisoneofedgeofP｝，EQ＝｛e|eisoneofedgeofQ｝

②分离轴定理

给定ℜn空间的凸面体P和Q，当且仅当存在直线l∈L使π（P，l）∩π（Q，l）＝Φ成立时，P∩Q＝Φ成立。其中：

π（P，l），π（Q，l）分别代表P、Q在l上的投影；(www.xing528.com)

L＝｛l|l//a×b，a，b∈EP∪EQ｝；

EP、EQ定义同上。

分离轴定理是进行相交测试的一个重要的定理，适用于AABB、OBB和k-DOP等凸多面体。它给出了一种判断两个物体相交的充分不必要条件，将相交检测的过程转化为寻找分离轴的过程，即在三维空间中找到一个向量，使得被检测的几何体在该向量上的投影是不相交的，那么就断定被检测的几何体不相交，此时这条向量就被称为分离轴。借助于分离轴可以大大降低相交检测计算的复杂度。

（3）AABB层次包围盒

在虚拟仿真技术领域，层次包围盒法是进行碰撞体间碰撞检测的主要方法之一。其基本思想是利用体积略大、几何特性简单的包围盒将被检测对象包围起来，首先进行包围盒之间相交测试，只有包围盒相交时，才对其所包围的对象做进一步求交计算。

层次包围盒法采用包围盒树来逐渐逼近碰撞体的几何特性。其中层次结构的根节点包围了整个碰撞体，每个父节点包围的几何对象是它的所有子节点包围的几何对象之和，节点从上到下逐渐逼近它包围的几何对象。其求交流程如图5-7所示。该方法只需对包围盒相交的部分进行进一步的相交测试，减少了碰撞检测的元素，有效提高了碰撞检测的效率。

1995年，Smith提出了一种基于AABB包围盒的碰撞检测方法，该方法在每个步长都重建碰撞体的包围盒，但该方法不能对复杂碰撞体进行实时检测。1997年，G.van.den.Bergen对原有基于AABB包围盒法的SOLID1.0库进行改进，用自下而上的更新方式加快包围盒树的更新速度，并发表了SOLID2.0库，但对于变形较大的碰撞体，其构建的包围盒树会出现较多的重叠区域。2007年，王晓荣又对SOLID2.0库提出了进一步改进，首先利用碰撞体的时空相关性对可能相交的对象进行快速排序，然后通过减少AABB树的存储空间来提高算法执行的效率。

图5-7　包围盒法原理

（4）构建AABB树的过程

首先，构建碰撞体碰撞体的包围盒树根节点，然后向下细分。在每一步细分中，首先计算出所有基元的最小AABB包围盒，选择AABB包围盒的最长轴方向作为分离平面的分离轴，选取一个适当的J作为分离平面与分离轴的交点坐标来确定分离平面。分离平面将该基元分成正负两个子集。重复执行直到每个子集只剩下一个元素。因此，一个包含n个基元的碰撞体对应的AABB包围盒树有n个叶节点和n－1个子节点。