湖南大学毕业论文 第24页
计算AABB的重点在于计算AABB的中心及盒子的长、宽、高，由此确定包围盒的尺寸。AABB内的任一点V(x，y，z)都需要满足：如图4-1.
其中Xmax、Xmin。分别指模型中各个点在x轴方向的最大、最小值，Ymax、Ymin分别指模型中各个点在Y轴方向的最大、最小值，Zmax、Zmin分别指模型中各个点在z轴
图4-1 AABB内的任一点V(x，y，z)满足条件
方向的最大、最小值。根据两个重要的点：Pmin=[ Xmin，Ymin，Zmin]，Pmax=[Xmax，Ymax，Zmax]，求出包围盒的中心点。
中心点m和长、宽、高a，b，c分别为，如图4-2
图4-2 中心点m和长、宽、高a，b，c
2. 包围球(sphere)算法
包围球是进行碰撞检测的三维几何体的最小外接球，当几何体旋转后不需要对包围球进行旋转。包围球同样具有计算较为简单，紧密性较差的缺点。计算包围球的重点在于计算包围球的球心和半径。其球
湖南大学毕业论文 第25页
心的计算与AABB的计算相同。半径则是长、宽、高的最大值。根据已介绍的AABB算法对包围球的球心及半径进行计算，如图4-3。
图4-3 球心m和半径R
3. 沿任意方向包围盒OBB(Onented Bounding Box)算法
OBB是最贴近三维几何体的平行六面体。一个物体的OBB被定义位包含该三维碰撞体并且相对于坐标轴方向任意的正六面体。与AABB包围盒相比，OBB包围盒的最大特点是其方向的任意性，这使得它可以根据被包裹对象的形状特点尽可能紧密地包裹对象。同时，当几何对象进行旋转后，不需要做复杂的运算，只需对OBB的基底进行同样的旋转即可。虽然这个算法实现起来有些复杂，但这并不会影响场景的运行速度。
构造OBB包围盒的关键是寻找最佳方向即确定一组正交的基底，并确定在该方向上包围对象的包围盒的最小尺寸。它的计算相对复杂，需要对包围盒的方向、中心位置、尺寸分别进行计算。其中，其中心位置和方向是利用一次矩(均值)和二次矩(协方差矩阵)统计量来计算的。尺寸则是通过位置和方向这两个量进行计算的。需要进行碰撞检测的物体是由多个三角形面片组成的，设三角形集的第i个三角形的顶点矢量为n，qi和ri组成包围盒包围对象的三角面片数为n。则包围盒的中心位置m为：如图4-4.
湖南大学毕业论文 第26页
图4-4 包围盒的中心位置m
协方差矩阵元素Cjk，如图4-5.
图4-5 协方差矩阵元素Cjk
其中，公式pi=pi—m，qi=q—m和ri=ri—m都是3*1向量。 利用数值的方法解出协方差矩阵的特征向量并单位化，由于C是一个实对称矩阵，所以矩阵C的特征向量相互垂直，可以作为包围盒的方向轴。把将要包围的几何体的顶点向方向轴上投影，找出各方向轴的投影区间，各投影区间的长度就是所求包围盒相应的尺寸。 4．固定方向包围盒FDH(Fixed Directions Hulls)算法
固定方向包围盒FDH法，其概念最早是由Kay和Kajiya提出的，他们在分析了以往采用的层次包围盒进行光线跟踪计算的缺点后，提出了一个高效的场景层次结构应满足的条件。综合起来就是个层次包围盒都应尽可能紧密地包裹其中所含的三维碰撞体。
在此算法中，其包围盒的所有面的方向量都来自一个固定的方向向量集合，因此它的简单性较好；但是当物体变形后，需要对变形的叶结点包围盒进行重新计算，然后严格按照自底向上的顺序，由子结点的FDH合成父结点的FDH。重新计算包围盒的计算量较大。
湖南大学毕业论文 第27页
包围盒的简单性与其包裹几何体的紧密性是一对矛盾,包围盒越简单它对几何体的包裹紧密性就越差。 4.1.2 游戏引擎使用的BSP碰撞检测简要解析
BSP Trees英文全称为Binary Space Partioning trees，二维空间分割树，简称为二叉树。它于1969年被Shumacker在文章《Study for Applying Computer-Generated Images to Visual Simulation》首次提出，并被ID公司第一次使用到FPS游戏Doom中，Doom的推出获得了空前的成功，不仅奠定了ID公司在FPS游戏开发的宗师地位，也使BSP技术成为室内渲染的工业标准，从BSP产生到现在已经有30多年了，其间虽然产生了大量的室内渲染的算法，但却无人能撼动它的地位，对于以摩尔定律发展的计算机业来说这不能不是一个奇迹。BSP技术作为室内引擎渲染的主流技术虽然已经存在多年，但是生命力仍然非常顽强，最新的DOOM3，HL2仍然将它作为渲染的主流技术。
该引擎实现的BSP树原理很简单：它将场景中所有的三角形面组织存储于一颗二叉树内，每个平面均将空间分为前后两个空间，这两个空间又被其它面分成更小的空间??直到最后，按照前面的算法，确定每个房间相对于摄像机的遮档顺序。这是一个非常标准的二分法，仅按照“前”和“后”两个逻辑上的概念来划分空间。如图 4-6所示：
湖南大学毕业论文 第28页
图 4-6 BSP原理简要解析图
空间ABC由A、B、C三个独立的空间组成，首先，分割平面1将空间分成了平面正向的A空间和平面负向的BC空间，BC空间被2紧接着分割为平面2正向的C空间和负向B空间。如果一个人处于C房间内，那么如何判断空间的遮挡顺序呢？从根结点开始，由于处于平面1的“后面”，所以，BC空间应该先于A空间，然后，由于人处于分割平面2的“前”面，所以，C空间应该先于B空间。这样，整个空间离人由近到远的顺序就可以确定了：C-B-A。仅需要通过两次平面的前后判断就可以确定空间的先后顺序，算法威力可见一斑。
该引擎使用二叉树主要用于碰撞检测。原理很简单，对场景中的碰撞网格进行了二叉树分割之后，网格存储进了一颗二叉树内。当需要判断一个面与一个物体是否发生碰撞时，只需要在二叉树内查找该面，然后计算是否碰撞即可。因为使用了二叉树存储，平均查找100