搜索
《虚拟现实》课程报告2014年5月1.概述碰撞检测是计算机动画、物理仿真、计算几何、CAD/CAM等研究领域的重要课题。碰撞检测的任务是确定两个或两个以上模型之间是否发生了接触或穿透。精确的碰撞检测不仅对提高虚拟环境的真实性、而且还对增强虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性又对碰撞检测提出了更高的要求。基于图形的实时碰撞检测算法主要分为层次包围盒法(hierarchyboundingbox)和空间分割法(spacesegmentationmethod)两类。这两类算法都使用了层次结构模型。其目标都是尽可能的减少需进行相交测试的几何对象的数目以提高算法的实时性。空间分割法由于存储量大、灵活性差，通常适用于稀疏环境中分布比较均匀的几何对象间的碰撞检测；层次包围盒法则应用得更为广泛，适用于复杂环境中的碰撞检测。层次包围盒方法的核心思想是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，从而只需对包围盒重叠的对象进行进一步的相交测试。此外构造树状层次结构可以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特性。包围盒算法主要有这样几类：包围球算法、轴向包围盒（AABB）算法、沿任意方向包围盒（OBB）算法、离散多面体（K-DOP）算法。2.轴向包围盒（AABB）算法AABB碰撞检测的研究历史中使用的最广最久。一个给定对象的AABB被定义为包含该对象且边平行于坐标轴的最小长方体。(1)构造难度低。只需要分别计算物体中各个元素顶点的x、y和z坐标的最大值和最小值即可。计算一个物体的AABB只需要6m次比较运算。其中m为顶点数。(2)存储量较小。存数一物体的AABB只需要6个浮点数。(3)相交测试复杂度低。两个AABB相交定义为当且仅当他们在三个坐标轴上的投影区间均重叠。AABB间的相交测试最多只需要6次比较运算。(4)紧密性较差。尤其对于沿斜对角方向放置的瘦长形对象，用AABB将留下很大的边角空隙，从而导致大量冗余的包围盒相交测试。(5)物体旋转时包围盒更新计算量中等。当对象发生旋转后，根据定义AABB六个最大最小值的组合，可以得到AABB的八个顶点；对这八个顶点进行相应的旋转，并根据旋转后的顶点计算新的AABB。(6)变形体碰撞适用度大。当物体变形时，更新包围盒有一定的计算量，可通过自底向上由子节点的AABB合成父节点的AABB以减少计算量，只需6次比较运算即完成一个节点的更新，效率较高。3.包围球算法一个给定对象的包围球被定义为包含该对象的最小球体。相对于AABB而言,在大多数情况下，包围球无论是紧密性和简单性都有所不如。因此它是用的较少的一种包围盒。(1)构造难度低。先分别计算物体中各个元素顶点的x、y和z坐标均值，以确定包围盒的球心c，再由球心与三个最大值坐标所确定的点间的距离计算半径r。构造是计算时间略多与AABB。(2)存储量较小。存数一个包围球只需两个浮点数。(3)相交测试复杂度低。对于两个包围球(c1,r1)和(c2,r2)，如果球心距离不小于两球半径之和，即|c1-c2|r1+r2，则两包围球相交，可进一步简化为判断,故包围球相交测试只需要4次加减算法、4次乘法运算和1次比较运算。(4)紧密性较差。除了在三个坐标轴上分布的比较均匀的几何体外，几乎都会留下很大的空隙。因此通常需要花费大量的预处理时间以构造一个好的层次结构逼近对象。(5)物体旋转时包围盒更新计算量无。这是包围球比较显著地一个特性。对于进行频繁旋转运动的刚体，采用包围球可以得到较好地结果。(6)变形体碰撞适用度中等。当对象发生变形时，很难从子节点大的包围球合成父节点的包围球，只能重新计算。4.沿任意方向包围盒（OBB）算法一个给定对象的OBB被定义为包含该对象且相对于坐标轴方向任意的最小长方体。OBB间相交测试的代价较大，但其紧密性好，参与相交测试的包围盒数目和基本几何元素的数目可以成倍地减少。在大多数情况下其总体性能要优于AABB和包围球。(1)构造难度较大。构造给定物体的OBB的计算相对复杂。其关键是找出最佳方向，并确定该方向上包围对象的包围盒的最小尺寸。假设给定物体中的基本几何元素为三角形，第i个三角形的顶点用xi、yi和zi表示，则可计算出物体的均值L和协方差矩阵C。协方差矩阵C的三个特征向量是正交的，规范化后可作为一个基底，用于确定OBB的方向。分别计算物体所包含的各个元素的顶点在基底的三个轴上投影的最大值和最小值，以确定该OBB的大小。(2)存储量较中。存储一个OBB需要15个浮点数。包括表示方向的3个基底向量共9个浮点数和表示范围的6个浮点数。(3)相交测试复杂度较大。OBB间的相交测试基于分离轴理论。若两个OBB在一条轴线（不一定是坐标轴）上的投影不重叠，则这条轴称为分离轴；若一对OBB间存在一条分离轴，则可以判断这两个OBB不相交。对任何两个不相交的凸三维多面体，其分离轴要么与任一多面体的某一个面垂直，要么同时垂直于每个多面体的某一条边。因此，对于一对OBB需测试15条可能是分离的轴（每个OBB的3个方面方向再加上每个OBB的3个边方向的两两组合），只要找到一条这样的分离轴，就可以判定这两个OBB是不相交的。两个OBB的相交测试最多需15次比较运算、60次加法运算、81次乘法运算和24次绝对值运算。(4)紧密性好。因为其方向的任意性特点，可根据被包围对象的形状尽可能紧密地包围对象。(5)物体旋转时包围盒更新计算量小。当几何对象发生旋转运动后，只要对OBB的基底进行同样地旋转即可。因此，较适用于刚体间的碰撞检测。(6)变形体碰撞适用度小。迄今为止，还没有一种有效解决对象变形后OBB树更新问题的方法，而重新计算每个节点的OBB的代价又太大，故OBB不适用于软体对象环境中的碰撞检测。5.离散多面体（K-DOP）算法一个给定对象的K-DOP被定义为包含该对象，且它的所有面的法向量均来自一个固定的方向（k个向量）集合的凸包。其中的方向向量为共线且方向相反的向量对，术语上称为FDH(fixeddirectionhull)。其最简单的特例是固定集中包含坐标轴方向，这时便成为AABB。因此他也可以看做是AABB的扩展。另外，当k值取无限大时，它即成为对象的凸包。因此它不但继承了凸包紧密性好的优点，同时也继承了AABB简单性好的优点。(1)构造难度中等。一个几何对象的FDH可以由它在固定方向集D中的各个方向向量上的最大延伸所确定，即通过计算对象的顶点与固定方向集中的各个方向的最大点积得到。这样计算有n个顶点得对象FDH可以在O(kn)时间内完成（k为固定方向集中地向量的个数）。(2)存储量随k值变化而变。存一个K-DOP需要k个值，每个面一个。(3)相交测试复杂度较低。FDH间的相交测试与AABB相似，可以依次对它们在固定方向集D中的k/2个方向轴上的范围区间进行重叠测试。如果找到了一对不重叠的区间，则可判断这两个FDH包围盒不相交。尽管这一判断方法不是很精确，但它不会影响检测结果。从检测速度方面考虑，这种方法还是可行的。因此，两个FDH的相交测试最多只需要k次比较运算，尽管它比AABB间的相交测试（6次比较）略为复杂，但与OBB相比较，其复杂度已经大大降低了。(4)紧密性好。他继承了凸包紧密性好的特点，通过调整固定方向集合的大小和取值，可以在紧密性与简单性之间取得平衡。k的取值越大，紧密性越好，但计算复杂度与越大。因此如何取得合适的k值还有待进一步的研究。(5)物体旋转时包围盒更新计算量较大。当对象发生旋转时，如果仅简单地对FDH进行同样地旋转，得到的将是基于另一个固定方向集的FDH，这就违背了用FDH做包围盒的初衷。两个来自不同方向集合的FDH间的相交测试不能使用区间重叠测试方法，其代价要比来自同一个方向集的FDH的相交测试代价大得多。与AABB一样，它需要计算旋转后的FDH，但计算一个FDH的顶点坐标系的代价仍然是很大的。可以通过引用线性规划的一些基本原理进行优化，这样无需计算FDH顶点而得到旋转后的FDH在方向集D中各个方向向量上的最大延伸，其中大部分计算可以提前完成。更新一个节点上的FDH只需要3k次乘法运算。(6)变形体碰撞适用度较大。当对象发生变形时，可以重新计算FDH树中发生变形的叶节点上的FDH，然后严格按自底向上的顺序，由子节点的FDH合成父节点的FDH。更新一个节点的FDH只需要k次比较运算。所以基于FDH的碰撞检测不但可以应用于刚体对象间的碰撞检测，还可以应用于刚体与软体间的碰撞检测，适用于包含软体对象的复杂环境模型中。但软体对象的FDH更新有待进一步优化。表2-1几种典型包围盒的比较（1为最优）方法构造难度存储量相交测试复杂度紧密性物体旋转时包围盒更新计算量变形体碰撞适用度AABB122331Spheres211413OBB434224K-DOP343142（a）包围球（b）AABB包围盒（c）OBB包围盒（d）平行六面包围体（e）k对平行面包围体