毕业设计（论文）-增强现实系统中碰撞检测算法研究

第1章绪论1.1背景和意义计算机辅助设计与制造（CAD/CAM）、计算几何、机器人和自动化、工程分析、计算机图形学、虚拟现实等领域都遇到了有关碰撞检测的问题，甚至成为其中的关键问题。例如对于机器人的控制和规划，碰撞检测可以帮助机器人避开周围环境中的障碍物，是一个非常关键的部分。相应地，在不同的领域中也出现了很多碰撞检测算法，有的算法已经应用到实际中。总体上讲，进行碰撞检测的目的主要有三个：检测模型之间是否发生碰撞，报告发生或即将发生碰撞的部位，动态的查询模型之间的距离等。碰撞检测是计算机动画、物理仿真、计算几何、CAD/CAM等研究领域的重要课题。碰撞检测的任务是确定两个或两个以上模型之间是否发生了接触或穿透。精确的碰撞检测不仅对提高虚拟环境的真实性、而且还对增强虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性又对碰撞检测提出了更高的要求。所以，增强现实系统中碰撞检测算法研究是很有必要的，在大部分的应用中要求实时碰撞检测，例如虚拟现实要求系统能够实现与用户的交互，这不仅要求实现实时绘制，而且实时进行碰撞检测，表现碰撞后的变化；而对于触觉反馈系统，每秒钟需要进行1000次检测。因此研究的主要目的就是降低算法的复杂度。影响碰撞检测的因素主要包括两个方面：静态检测方法和采样方式。那么碰撞检测算法的计算代价主要取决于这两个方面的复杂度。静态检测是最基本的问题，关键是解决不同类型的模型的相交检测问题，如凸多面体、凹多面体、不封闭的多面体以及可变形的模型等等。同样尽量减少静态检测算法的调用次数也是提高算法效率的重要方面，应该尽量在碰撞即将发生时调用，通常采用的策略有：寻找距离第一次碰撞发生最近的时间区间；减少将要发生碰撞的物体中需要检测的元素对数；减少需要检测的物体对数等。这些策略的应用依赖于距离跟踪算法、模型层次表示方法、方向性裁剪标准以及空间分割模式等等。增强现实是一种人与通过计算机生成的虚拟环境之间可自然交互的人机界面，其应用开发前景非常广阔，市场潜力不可估量。目前，它在航空航天、机械设计、科学计算、影视娱乐、化学医药和军事训练等诸多领域得到了初步应用，而且很多应用是其他技术无法代替的。但总的来说，现在的增强现实技术并不成熟，当前发展状况距离各行各业的实际需求相差甚远。增强现实要得到充分的应用研究还有许多工作需要完成。1.2主要方法和研究进展研究人员根据的研究对象，采用了不同的研究方法，也由此提出多种多样的碰撞检测算法。从总体上看将这些算法归为两类：A)静态干涉检测算法。主要用于检测静止状态中各物体之间是否发生干涉的算法，如机械零件装配过程中的干涉检查。这类算法对实时性要求不高，但对精度要求较高。B)动态碰撞检测算法。针对的是场景中的物体的相对位置不断随时间变化的情况，如机械零件的加工过程以及机械系统的运动仿真等。动态碰撞检测算法又分为离散碰撞检测算法和连续碰撞检测算法。从本质上说，离散碰撞检测算法在每一时间离散点上可以通过类似静态干涉检测算法的方法来实现，但它更注重算法效率。虽然这类算法自身还存在一些问题，如检测中的刺穿现象和遗漏情况等，但由于其检测过程的实时性能较好地迎合多数应用的需求，目前仍是碰撞检测算法研究的重点和热点。此外，通过采用自适应步长技术等可以在一定程度上减少离散碰撞检测算法的不足。连续碰撞检测算法的研究一般涉及到四维时空问题或结构空间精确的建模。这类算法能较好地解决离散碰撞检测算法存在的问题，但通常计算速度较慢，需要作进一步的研究才能适用于大规模场景中的实时碰撞检测。研究人员在实时碰撞检测方面展开了一系列研究，取得了一些成果。目前，大部分实时性好的碰撞检测算法都属于离散碰撞检测算法。纵观这些算法，大致可分为基于图形和基于图像的碰撞检测算法。这两类算法的主要区别在于是利用物体三维几何特性进行求交计算，还是利用物体二维投影的图像及深度信息来进行相交分析。其中在基于图形的碰撞检测上，研究人员已经做了大量的工作，形成了层次包围盒法和空间分割法等成熟算法。基于图像的碰撞检测算法能有效利用图形硬件的绘制加速功能来提高碰撞检测算法的效率，特别是近几年图形硬件技术的飞速发张，图形硬件在性能不断提高的同时还具备了可编程的功能，使得基于图像的碰撞检测算法进入了一个新的发展阶段。1.3主要内容本文对目前碰撞检测算法进行分析总结，简要介绍了几种典型的算法以及碰撞检测算法设计需要注意的问题。详细介绍了利用射线法进行碰撞检测的原理以及实现。

第2章碰撞检测算法分析2.1基于图形的实时碰撞检测算法基于图形的实时碰撞检测算法主要分为层次包围盒法(hierarchyboundingbox)和空间分割法(spacesegmentationmethod)两类。这两类算法都使用了层次结构模型。其目标都是尽可能的减少需进行相交测试的几何对象的数目以提高算法的实时性。空间分割法由于存储量大、灵活性差，通常适用于稀疏环境中分布比较均匀的几何对象间的碰撞检测；层次包围盒法则应用得更为广泛，适用于复杂环境中的碰撞检测。2.1.1层次包围盒法层次包围盒方法的核心思想是用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，从而只需对包围盒重叠的对象进行进一步的相交测试。此外构造树状层次结构可以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特性。典型的层次结构树主要包括AABB(alignedaxisboundingbox)层次树、包围球(shperes)层次树、OBB(orientedboudingbox)层次树和K-DOP(discreteorientationpolytope)层次树等。其他还包括混合层次包围体树等。1.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次比较运算即完成一个节点的更新，效率较高。2.包围球层次树。一个给定对象的包围球被定义为包含该对象的最小球体。相对于AABB而言,在大多数情况下，包围球无论是紧密性和简单性都有所不如。因此它是用的较少的一种包围盒。(1)构造难度低。先分别计算物体中各个元素顶点的x、y和z坐标均值，以确定包围盒的球心c，再由球心与三个最大值坐标所确定的点间的距离计算半径r。构造是计算时间略多与AABB。(2)存储量较小。存数一个包围球只需两个浮点数。(3)相交测试复杂度低。对于两个包围球(c1,r1)和(c2,r2)，如果球心距离不小于两球半径之和，即|c1-c2|<r1+r2，则两包围球相交，可进一步简化为判断c1-c2*(c1-c2)(4)紧密性较差。除了在三个坐标轴上分布的比较均匀的几何体外，几乎都会留下很大的空隙。因此通常需要花费大量的预处理时间以构造一个好的层次结构逼近对象。(5)物体旋转时包围盒更新计算量无。这是包围球比较显著地一个特性。对于进行频繁旋转运动的刚体，采用包围球可以得到较好地结果。(6)变形体碰撞适用度中等。当对象发生变形时，很难从子节点大的包围球合成父节点的包围球，只能重新计算。3.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不适用于软体对象环境中的碰撞检测。4.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对平行面包围体图2-1几种典型包围盒的构造方式2.1.2空间分割法空间分割法是将整个虚拟空间划分成等体积的规则单元格，以此将场景中的物体分割成更小的群组，并只对占据了同一单元格或相邻单元格的几何对象进行测试。一般来说，空间分割法在每次碰撞检测时都需要确定每个模型占有的空间单元。如果场景不可动的模型很多，可以预先划分好空间单元格并确定每个模型占有的空间单元。当有模型运动时，只需要重新计算运动模型所占有的空间就可以了。所以该类方法通常适用于机床的加工仿真、飞行器避障飞行模拟等虚拟场合。空间分割法也采用层次树的方法进一步提高算法的速度。比较典型的有八叉树、BSP树等。传统的八叉树有空间非均匀网格剖分算法和层级边界盒算法。传统算法适用于静态场景；对于动态场景，采用较多的是基于面向对象的动态八叉树结构，它是对原算法的改进。动态八叉树的构造和碰撞检测策略是将场景表示为等体积的规则单元格的组合。以立方体单元格为例，将单位立方体有动态八叉树动态表示。当单位立方体检测到碰撞，它将被分解成八个子立方体；否则不解。以此循环递归，再通过预先设定阈值，控制分解的终止。BSP树包含的是平面的层级，其每一个平面都将一个区域的空间分割成两个子空间。可将实体表面的一部分作为叶节点的平面。该平面的一个子空间代表实体的内部；另一个子空间代表实体的外部。BSP的碰撞检测策略为：在两个对象间找出分割平面以确定两个对象是否相交；若存在分割平面，则无碰撞发生。为了提高效率，可先遍历整个场景树检测分割平面是否与包围盒相交；当有相交时再与包围盒中对象的多边形进行精确检测。具有n个节点的二叉树可在O（log（n））次内完成搜索。2.2基于图像的碰撞检测算法基于图像的碰撞检测算法一般利用图形硬件对物体的二维图像采样和相应的深度信息来判别两物体之间的相交情况。图形硬件有时也称为图形处理单元。这类算法主要有四点优势：(1)能有效利用图形硬件加速技术来减轻CPU的计算负荷，从而达到提高算法效率的目的；(2)算法本身对于场景的复杂性不敏感，适合于复杂体间的碰撞检测；(3)对同一复杂度的场景而言，碰撞检测时间变化不大，具有较高的平稳性，有利于预测碰撞检测过程；(4)图形硬件技术发展快速，算法有良好的发展前景。基于图像的碰撞检测算法由于其检测结果的不精确性和依赖硬件支持而一直发展较慢，而且对其在大规模场景中的应用有待进一步研究。近年来，随着图形硬件计算性能的迅速提高，基于图像的碰撞检测算法进入了一个新的快速发展阶段。2.3总结基于图形的碰撞检测算法相对成熟，形成了一系列典型的算法，如包围盒法和空间分解法等，但算法本身受场景复杂度的影响较大。在保证算法精确度的前提下，进一步提高算法的实时性一直是研究者追求的目标。所以算法的研究一方面要优化其本身的构造；另一方面要充分利用如图形硬件GPU加速处理技术和并行计算方法的优势。目前基于图形硬件加速计算正在开创一个新的时代。国外有一批研究者正在进行该方面的研究，包含了碰撞检测领域；国内在这方面的研究尚属起步阶段，成果较少。基于图像的算法属于一类较新的算法。虽起步较早，但由于受到图形硬件发展的限制，曾在很长的一段时间被边缘化。20世纪90年代随着图形硬件的发展才得以重新进入研究者的视野，但研究进展相对比较缓慢，检测精度一直是限制其发展的重要原因之一。提高分辨率可在一定程度上解决这个问题，但会影响绘制速度；算法对于非凸体及大规模场景的适用性研究有待进一步开展；CPU与GPU间的负载平衡问题有待进一步研究，以提高算法效率。该类算法由于其本身的优势，特别是随着图形硬件的飞速发展，具有广阔的研究前景和研究价值。

第3章碰撞检测系统中的设计问题3.1碰撞算法的设计因素在设计碰撞检测系统时，多种因素将会影响设计者的选择，包括以下几类：(1)应用程序中对象的表达式。场景以及物体的几何表达方式将直接影响到相关算法的选择，表达方式的约束条件越少，则碰撞检测的解决方案也就越通用，同时也能够满足既定的运行性能。(2)查询类型的多样化。通常，查询及其相应的结果越详细，需要的计算量就越大。另外也许还需要额外的数据结构对某一类特定的查询加以支持。最后，某些对象的几何表达方式还可能不存在相应的查询类型与之对应。(3)环境模拟参数。模拟环境自身也包含了某些参数，并对碰撞检测系统产生直接的影响。例如，对象的数量、尺寸和位置、是否移动预计如何移动、物体间是否允许相互穿透、物体是刚体还是可变形物体。(4)系统的性能。实时碰撞检测系统对时间要求苛刻，并受到物体尺寸的约束。由于时间和空间的可交换性，为了满足既定的性能需求，某些特性通常应均衡加以考虑。(5)系统的健壮性。应用程序的物理仿真级别还是存在差距的。例如，考察一个堆砌的砖垛，与一个球场上跳动的篮球相比，其碰撞检测系统要复杂的多。篮球弹射初期或以较大角度弹射时，其状态可以忽略不计。但是，在计算砖垛之间的接触点时，即使是很小的误差，都将导致砖块逐渐地彼此嵌入或脱离。(6)系统实现与应用的简易性。多数项目设计都存在其自身的开发周期，若系统不能按时交付使用，那么项目的时间规划将是一句空谈。因此，在考查采用何种方案时，“系统实现的简洁性”这一决策将扮演重要的角色。3.2应用程序中对象的表达方式在选择合适的碰撞检测算法时，要考虑到场景和物体的几何表达方式，这一点是十分重要的。3.2.1对象的表达方式当前多数图形学硬件均使用三角形作为基本的渲染图元。因此，多边形这一表达方式对于场景和场景中的物体，以及相应的碰撞几何体，将是一个自然的选择。而作为最通用的对想表达方式则是“多边形汤”：一组无序的多边形构成的集合，并且不包含确定多边形相互关系的连接信息。由于没有过多的表达限制，对于美术师和关卡设计者来讲，多边形汤往往是一种较具吸引力的对象表达方式。多边形汤的相关算法虽然可以适用于任意多边形集合，但是与那些具备额外信息的多边形集合相比较而言，其执行效率低下并且算法的健壮性也较差。多边形通过公共边可以连接成一个大型的多边形平面，称作多边形网格。当构造集合模型时，采用多边形网格集合是最常用的方法。多边形物体按照顶点、边和面加以定义。依据该方法构造的物体对象常被称为“具备显示的表达方式”。而“隐式表达方式”的物体对象一般是球体、圆锥体、椭圆、圆环以及其他非显示定义的、但可以间接地通过数学表达式表示的几何图元。球体、包围盒和圆柱体也可称为结构几何实体（CSG）对象的构造块。CSG物体对象可以在基础的几何形状或其它CSG物体上，利用集合理论实现递归构造，这将构造出任意形状的复杂几何对象。因此CSG对象可以表达为一棵树，内部节点表达为集合操作；叶结点为几何图元，CSG物体属于隐式对象，其中顶点、边和面均无法直接获取。3.2.2碰撞与几何渲染虽然几何渲染可以直接置入碰撞检测系统，但最好将渲染系统与其分离开来，理由如下：(1)当前，图形平台之上的几何渲染过程十分复杂，并且不适用于碰撞检测和物理运算。另外对于碰撞检测的精度也存在着某种限制。因此，不建议采用供渲染的几何对象执行碰撞检测，而是采用同一位置的替代对象。(2)对于当前的硬件环境来讲，几何图元趋于一种特定的格式并加以表达。(3)在数据组织方面，渲染几何体与碰撞检测几何体二者之间存在着显著的区别：静态渲染数据可以按照材质的特征加以分类排序，而碰撞数据一般按照空间特征加以组织。渲染几何体需要内嵌诸如材质信息、顶点颜色和纹理坐标等数据信息，而碰撞几何体则关联其面属性。分离两者的数据格式并只保持碰撞相关信息，将有利于碰撞信息的最小化。反之，这种较好的数据缓存一致性也将有助于执行效率的改善。(4)有时，通过一些设计手法，也可以对碰撞几何体和渲染几何体加以区别。(5)为了实现正确的模拟，即使渲染数据透明不可见，其碰撞数据也需要加以保留。只有当碰撞区域小于对应的渲染几何体时，其碰撞标志才可以适度减少。(6)原始的几何体可以通过多边形汤或网格形式给定，而模拟过程通常需要以实体方式加以显示。在这种情况下计算实体的代替几何将会更加简便，而非实体化原始的几何显示数据。然而，采用分离的碰撞几何体仍然存在着如下潜在的缺点：(1)数据冗余（主要是顶点数据的重复）将导致额外的内存占用。这一问题可以通过从实时渲染的几何体中创建部分或全部碰撞几何体这一方式加以加以缓解。(2)生成并维护这两类相似几何体集合还需要一些额外的步骤。手工构造替代几何体将会减缓设计者的开发进度。若该替代几何体是通过某种工具加以构造的，那么在碰撞系统的构造过程中该工具应该是数据可写入的；另外，如果用户手工修改该工具的数据输出值，那么改变化状态也应该能狗通知该工具和原始数据集合。(3)如果构造过程和维护过程分开加以实现，那么渲染几何体和碰撞几何体之间可以不实现完全匹配。因此，当碰撞几何体不完全填充其对应的渲染几何体空间时，渲染几何体之间(4)对象状态和其他也可能产生于上述两种几何体之中。采用与真实尺寸接近的替代几何体在游戏中亦运行良好。从直观角度来讲，用户并不擅长判断真实的碰撞是否刚好发生，模拟过程中，所涉及的物体越多，其移动速度越快，玩家也就越难以把握；同时，用户也难以预测碰撞的最终结果，从而采取相应的反馈措施。在游戏中，碰撞检测和相应的反馈总是遵循“如果看上去是正确的，它就是正确的”这一法则。而其他一些应用程序，则需要比较严格的精确度。3.2.3特定的碰撞检测算法不建议设计并采用那种“全功能”的碰撞检测系统，为特定方案提供某种专用的碰撞检测系统往往是更加明智的选择。一个特定算法相关的例子是粒子系统。通常，例子往往以粒子云的方式发射，从而使得碰撞系统能够较好地接受并处理他们，而不是采用逐个粒子发射的方式。其中，粒子云可以依据当前环境加以构造并实现重组。而在某些碰撞可以忽略的情况下，粒子甚至可以不参与碰撞检测。另一个例子是：为物体-物体间的碰撞与物体-场景间的碰撞分别使用不同的算法。物体-物体之间的碰撞甚至可以采用更加特殊的算法，从而使玩家和快速移动的发射物区别于其他对象的处理。3.3查询类型最直接的碰撞检测查询称为“冲突检测或相交测试”，即回答两个（静态）物体在其给定的位置和方向上是否产生重叠这一布尔问题。布尔相交测试查询快速并易于实现，因此被广泛的采用。然而，有时仅知道碰撞的布尔结果值是远远不够的，还需要获取相交处的具体数据信息。相交数据的计算过程一般是比较困难的步骤，涉及计算一个或多个碰撞点。对于某些应用程序，计算物体之间的一个碰撞点已经足够；然而，在某些应用程序中，例如刚体的模拟，则需要计算碰撞点的集合。健壮的碰撞点集的计算通常是比较困难的。综上所述，与精确计算查询相比，近似计算查询往往更加易于处理。当然，后者的精确度取决于相应的误差范围。游戏中一般采用近似计算查询。另外在游戏中，碰撞计算通常需要给出某些特定的属性值，该值一般为某物体或其表面的、已定义好的属性值。例如，道路表面的防滑系数，或者墙壁表面的坡度。如果物体之间彼此穿越，某些程序还需要计算穿越深度。这里所说的“穿越深度”通常定义为最小位移距离：分离两物体的最短位移向量的长度值。但是计算该位移向量往往比较困难。两个不相交物体之间的“间隔距离”则定义为：物体A上的点与物体B上的点之间的最小距离值。当距离值为0时，则两物体相交。两物体间的距离计算对于预测下一次碰撞的发生时刻是非常有用的。一个比较常见的问题是计算两物体间的最近碰撞点：即两物体间的间隔距离。注意，最近碰撞点不一定是唯一的，也可能是无限多个。对于动态物体，计算下一次碰撞的发生时刻常称为“预计到达时刻（ETA）计算”，或称为“碰撞时刻（TOI）计算”。在刚体模拟中，ETA的值往往用于控制时间步（timestep）。另外，运动的类型也是模拟参数之一。3.4环境模拟参数模拟过程中的某些参数将直接影响碰撞检测系统的相应算法的选择。3.4.1物体对象的数量由于任何一个物体都有可能与其他物体发生碰撞，则包含n个物体的碰撞检测过程在最坏情况下需要O(n2)次相互测试。对于这中平方级别的时间复杂度，物体间的碰撞检测的代价将会变得十分昂贵；同时，减少这种相互测试所产生的消耗，将会线性的影响测试的运行时间。为了提高测试速度，上述物体间相互测试的数量必须适度的降低。这种降低的方式可以描述为粗略测试将确定可能发生碰撞的较小的一组物体对象，并快速排除那些一定不会发生碰撞的物体对象。精确测试则继续在上述子划分组中执行物体对象间的相互测试。3.4.2顺序移动和同步移动在显示生活中，当多个物体在给定的时间间隔内同步移动时，需要处理期间可能法生的碰撞。对于真实时间的模拟，要求确定某两个运动物体的先期碰撞时刻，当模拟系统准时到达这一时刻点时，将移动所有所有物体至首次发生碰撞的位置。从而，碰撞问题得以解决，同时，相关的操作过程将会继续计算下一次碰撞，重复上述步骤，直至全部的位移时间步用尽。这种“重复地推进至下一个最早碰撞时刻”的模拟执行方式将会十分耗时。例如，当一个或多个物体逐渐停止向某一表面运动时，模拟过程仍然会即刻计算当前碰撞时刻后的下一次碰撞时刻。虽然模拟过程只是因此向后退役了一个很小的时间片，但是实际上却“永久地”独占了全部时间步。该问题的一种解决方案是，在时间步内，利用粗略测试确定可能与当前划分组碰撞的其他对象划分组而非组对象。而每一个子划分将一部不同的代价加以执行，通常这将在一定程度上解决上述问题。一种替代的方法是，仍然同步移动的物体，但设定一个固定的位移时间步。同步移动物体可能导致物体之间的相互贯穿，一般可以通过将模拟备份至早期状态加以解决。在上述两种情况下，同步更新仍然是十分耗时的，因此只用于精确的刚体模拟中。然而，多数游戏和其他类型的应用程序并非刚体模拟，因此，试图模拟高精度的运动方式将得不偿失。对此，一种可替代的方案是：以顺序的方式处理运动问题，即一次只移动一个物体，若检测到碰撞，则进行处理，随后再继续处理下一个物体。显然，这种顺序移动并非物理意义上的精确运动模型。当对象间进行同步移动时，对于尚未移至当前帧中的对象而言，则有可能产生碰撞；而对于已移出碰撞路径之外的对象，则不会产生碰撞。另外，对于顺序移动的对象，也将会出现碰撞现象。在某些情况下，同步移动的对象间可能产生碰撞，而顺序移动的对象反而不会出现碰撞。针对游戏=程序设计而言，由于较高的帧速率仅呈现很小的位移量，进而使得相交区域难以实现量化操作，因而通常可忽略顺序移动模型所产生的问题。顺序移动模型的优点之一便是避免了单一物体的穿透现象。例如，如果一个物体在运动期间发生了碰撞，则可以简单的撤销该运动位移。仅当需要撤销单一物体的运动位移时，才与采用固定时间步的同步移动模型具有可比性—后者将撤销所有同步运动物体的位移。3.4.3不连续移动与连续移动某些因素将在很大程度上影响碰撞检测结果的计算量，以及碰撞检测结果自身的准确度。例如，“对组合”测试中的两个物体在执行测试时是否处于运动状态。静态碰撞检测负责处理：物体在运动过程中以及每一个离散点处是否发生碰撞。在每一个离散点处，物体在其当前位置视为静止并且速度为0。相比较而言，动态碰撞测试则视为：在给定的时间间隔内，物体的连续位移。动态碰撞测试通常能够告知首次碰撞时的精确碰撞时刻和碰撞点。与动态碰撞测试相比较，静态碰撞测试无需付出太多的代价即可实现，但是，测试之间的时间步必需足够小，从而使物体的位移小于其占据的空间的范围。否则，物体只是在相邻的两个时间步内彼此简单地经过对方，并且无法检测收到相应的碰撞。这种现象称作“隧道效应”。在给定的时间间隔内，物体连续移动所覆盖的空间体积称作扫掠体。如果两个运动物体对应的扫掠体没有相交，则两个物体也不存在相交。另外，即使两个扫掠体出现相交的情况，对应的两个物体也未必在其运动过程中相交。因此，扫掠体的相交是物体相交的必要不充分条件。对于复杂的运动过程，扫掠体难以计算与使用。幸好，在计算过程中，较高的精确度并不是必需的。对于那些复杂的、呈现翻转运动的动态碰撞测试，其往往可以设定为分段线性运动，从而得到相应的简化：即运动范围内的直线平移和中点处的旋转，而二者之间的某一位置则可以看做是自由的螺旋运动。当处理运动的物体时，考虑他们的相对运动通常是一种更可取的方式，即从一个物体的运动中“减去”另一个物体的运动，从而使得前者静止。因此，物体间的直线平移使得上述操作构成一个向量减法。考查相对运动方式的一个优点是：当前行为变为一个运动的物体朝向一个静止的物体执行碰撞测试从而使得对应的扫掠体测试成为一种准确的相交测试。3.5性能3.5.1优化概览优化的首要原则是：无需执行额外的任务。因此，较好的加速优化方案是将工作量削减至最低。同样，碰撞检测系统重要的优化方案之一便是粗略测试操作，即物体对象的空间定位计算。因为物体只是有可能碰撞其附近的对象，而对于远端的对象可以通过空间划分加以排除，及忽略那些距离较远的、不可能相交的物体。对空间划分和“视锥体剔除并限制渲染物体的数量”，他们之间存在着诸多类似之处。可以采用平面结构执行空间划分，将空间分割为统一尺寸的单元格。这一过程也可以按照层次结构方式加以实现，其中空间被递归的划分为半空间，直至满足某种终止条件。物体对象将被置入上述网格或结构层次中。网格和层次结构的划分方式对于精确测试中的对组合测试也是十分有效的，特别是对象比较复杂时。通常不采用物体之间的一一测试方式，空间划分将碰撞测试限定在彼此接近的两个物体的范围之内。在执行高昂的几何体测试之前，预先计算耗费较少的体空间测试是一个较好的方法，这将减少碰撞过程中的计算量。例如，当封闭的包围球应用于所有物体上时计算过程将呈现为简单的球体间的碰撞测试：如果球体间没有产生交叉重叠，则无需进一步执行几何体之间的复杂测试。假设物体处于运动中，则每一帧之间物体会产生一个较小的位移量，针对于此，引入了时间一致性。例如，只是自上一帧开始处的运动物体需要执行测试，而对于其他物体，其碰撞信息需要保持一致。时间一致性还应允许缓存并复用当前帧的数据和计算结果，从而提高测试速度。针对特定平台的结构的优化也是非常重要的。多种平台都支持某些类型的代码和数据的并行计算，充分利用这一特性将极大地提高运行速度。由于，CPU操作与主存向其提供数据之间存在着显著的速度差异，主存中碰撞几何体和其他数据的存储方式，也将对碰撞检测系统产生较为明显的速度影响。3.6健壮性碰撞检测是空间应用几何程序的一种，健壮性问题是十分重要的。健壮性是指程序处理数字计算和复杂几何结构的相应能力。当出现复杂的数据输入时，健壮的计算程序可以提供相应的期望值，否则，可能会出现系统崩溃或产生死循环。相关问题可以划分为两类：数字精度的丢失和错误的几何形状。数字精度问题源于计算过程中变量的有限精度。例如，当中间计算结果值大于浮点变量或整型变量所能表达的范围，其值将无效。如果该问题未被检测到，计算的最终结果很可能是错误的。健壮的计算实现方式必须防止这种问题发生，或者即使发生了上述错误，系统也能狗进行相应的调整并返回正确的结果。几何健壮性应确保拓扑关系的完整性以及几何完整性。这类问题常常来源于错误的几何图形或退化的几何图形，从而导致错误的数字计算结果。在某种程度上，大多数算法期望具有良好格式的输入值。当发生错误的几何输入时，如果这种情况不加以捕捉并及时处理，其计算结果将是未知的。数字健壮性和几何健壮性的差别有时难以确定，甚至相互作用。为了避免这种隐藏的、难以修复的错误，健壮性问题应在碰撞检测系统的整个设计与开发过程中加以考虑。3.7实现与使用的简洁性碰撞检测系统容易受到各种错误的影响，当然，发现这种错误往往比较困难并且十分耗时。在开发阶段可以采取相应的步骤来减轻调试过程中带来的痛苦，下面是一些有用的建议：(1)对于最近的n次碰撞查询，保持一个循环缓冲区，对应于若干秒的数据值。当运行过程中出现某种错误时，可以暂停程序并输出上述错误，以供进一步分析。(2)提供碰撞几何体的可视化方案。(3)实现一个简单的参考算法，并对应于其搞计算法加以运行。(4)维护一个测试查询组，当代码改变时，可以对照测试查询组运行碰撞测试代码。具有几何性质的代码一般都存在多种性的特例，因此全面的测试将有助于早起捕捉问题，无论何时发现bug都需要添加测试用例以检测其是否被重引入。

第4章射线法检测碰撞的实现4.1平面碰撞检测下面先介绍两种基本图形的碰撞检测算法的原理。4.1.1矩形和矩形的碰撞检测一般规则的物体碰撞都可以处理成矩形碰撞，实现的原理就是检测两个矩形是否重叠。假设矩形1的参数是：左上角的坐标是(x1,y1)，宽度是w1，高度是h1;矩形2的参数是：左上角的坐标是(x2,y2)，宽度是w2，高度是h2。在检测时，数学上可以处理成比较中心点的坐标在x和y方向上的距离和宽度的关系。即两个矩形中心点在x方向的距离的绝对值小于等于矩形宽度和的二分之一，同时y方向的距离的绝对值小于等于矩形高度和的二分之一。下面是数学表达式：x方向：x14-1y方向：y1+4-2在程序中，只需要将上面的条件转换成代码就可以实现了。但是矩形碰撞只是一种比较粗糙的碰撞检测方法，因为很多实际的物体可能不是一个规则的矩形。4.1.2圆形和圆形的碰撞检测圆形和圆形的碰撞应该说是一种最简单的碰撞，因为在数学上对于两个圆形是否发生重叠，有计算两个圆心之间的距离的公式。那么条件就变为：计算两个圆心之间的距离是否小于两个圆的半径和。假设圆形1的左上角坐标是(x1,y1)，半径是r1，圆形2的左上角的坐标是(x2,y2)，半径是r2。因为浮点数的运算比较慢，所以将条件做一个简单的变换：对于条件的两边都进行平方，这样就去掉了开方的运算步骤。下面是数学表达式：x1-x24-3在程序中，只需要将上面的条件转换成代码就可以了。4.2三维物体碰撞检测4.2.1射线的定义在几何光学中，射线是描述光线或其他电磁辐射传播的方向的一条曲线。射线的定义为：PointOnRay4-4式中Raystart：射线上的原点PointOnRay：射线上的点ta：用来描述射线上的点距离原点的位置，t∈[0，无限远)aRaydirection：射线的方向4.2.2射线与平面的碰撞检测在空间中，到两点距离相同的点的轨迹为平面。平面的定义为：XndotX4-5式中Xn：平面的法线X：平面上的一个点da：平面到原点的距离这种矢量表示法与通常的参数表达式方法是等价的，参数表达式描述一个平面公式如下：Ax+By+Cz+D=0只需要简单的将法线的矢量（x,y,z）代替A，B，C，将D=-d即可。如图4-1所示，现在得到射线和平面的两个方程:PointOnRay4-4XndotX4-5如果他们相交，则上诉方程组有解，如下所示：XndotPointOnRay4-6XndotRaystart4-7解得t:t4-8t4-9XnXnPointOnRayRaystartRaydirection图4-1射线与平面相交测试t是从该射线的起点沿着射线的方向到该平面的距离。因此将t代入射线公式即可算出撞击点。如果XndotRaydirection=0，表明射线和平面是平行的，将不会有撞击点。如果t是负数，那么表明撞击点是在射线的起始点的后面，也就是沿着射线后退的方向才能撞到平面，这只能说明射线和平面没有交点。其检测代码如下：//测试直线是否与平面相交函数intCMyCollision1View::TestIntersionPlane(constPlane&plane,constCVector&position,constCVector&direction,double&rt,CVector&pNormal){doubleDotProduct=direction.dot(plane._Normal); doublel2;//检查直线是否与平面平行，如果dotproduct=0则平行if(DotProduct==0) return0;l2=(plane._Normal.dot(plane._Position-position))/DotProduct; //交点在射线的相反方向，此时不会发生碰撞if(l2<0) return0;pNormal=plane._Normal;//平面的法线 rt=l2;return1;}上面这段代码计算并返回射线和平面的撞击点。如果有撞击点函数返回1否则返回0。函数的参数依次是平面，射线的起点，射线的方向，一个浮点数记录了撞击点的距离，最后一个参数记录了平面的法线。4.2.3射线与圆柱体的碰撞检测光线与圆柱体相交碰撞检测方法与平面相似，联立射线方程和圆柱体方程即可求解。主要思想就是：检测光线方向是否与圆柱体轴线平行，如果不平行，则求两个矢量之间的距离，若此距离大于圆柱体的半径则不发生碰撞，否则发生碰撞。一个圆柱体的描述类似于射线，有一个起点和方向，该方向描述了圆柱体的轴，还有一个半径。设X为圆柱体表面上的一点，Position是圆柱体轴线上的一点，Direction是轴线的方向，圆柱体半径为Radius。则圆柱体的方程为：v-w4-10式中v=X–PositionW如果射线与圆柱体相交则4-10与4-4联立有解：t4-11式中abc=RaystartRaystartRaydirectionDirectionPositionRadius图4-2射线与圆柱体相交测试当a=0时，表示射线与圆柱体平行不相交；当b2当b2-4ac>当b2其检测代码如下：//检测与圆柱体是否碰撞，是则返回1，否则返回0intCMyCollision1View::TestIntersionCylinder(constCylinder&cylinder,constCVector&position,constCVector&direction,double&rt,CVector&pNormal,CVector&newposition){ CVectorRC; doubled; doublet,s; CVectorn,D,O; doubleln; doublein,out; CVector::subtract(position,cylinder._Position,RC);//向量之差 CVector::cross(direction,cylinder._Axis,n);//光线与轴线向量叉积ln=n.mag();//取模 if((ln<ZERO)&&(ln>-ZERO))return0;//ln=0则平行不相交 n.unit();//单位化向量 d=fabs(RC.dot(n));//计算光线与轴线之间的距离if(d<=(cylinder._Radius+20)) { CVector::cross(RC,cylinder._Axis,O); t=-O.dot(n)/ln; CVector::cross(n,cylinder._Axis,O); O.unit(); s=fabs(sqrt(cylinder._Radius*cylinder._Radius-d*d)/direction.dot(O)); in=t-s; out=t+s; if(in<-ZERO){ if(out<-ZERO)return0; elsert=out; } elseif(out<-ZERO){ rt=in; } else if(in<out)rt=in; elsert=out;//记录撞击点的距离 newposition=position+direction*rt;//记录撞击点的位置 CVectorHB=newposition-cylinder._Position; pNormal=HB-cylinder._Axis*(HB.dot(cylinder._Axis));//记录撞击点法线 pNormal.unit(); return1; }//距离大于圆柱体半径则不会发生碰撞 return0;}4.2.4球体与球体的碰撞检测一个球体通过圆心和半径来描述。判断两个球体是否相撞十分简单，只要算一下这两个球体的圆心的距离，如果小于这两个球体半径的和，即表明该两个球体已经相撞。问题是该如何判断两个运动球体的碰撞。两个球体的运动轨迹相交并不能表明它们会相撞，因为它们可能是在不同的时间经过相交点的。球2球2球2球1球1图4-3球体相交测试以上的检测碰撞的方法解决的是简单物体的碰撞问题。当使用复杂形状的物体或方程式不可用或不能解决时，要使用一种不同的方法。球体的起始点，终止点，时间片，速度（运动方向+速率）都是已知的，如何计算静态物体的相交方法也是已知的。为了计算交叉点，时间片必须被切分成更小的片断。然后按照物体的速度运动一个片段，检测一下碰撞，如果有任何点的碰撞被发现（那意味着物体已经互相穿透了），那么就将前一个位置作为相撞点。时间片分的越小，片段切分的越多，得到的结果就越精确。举例来说，如果让时间片为1，而将一个时间片切分成3个片段，那么就会在0，0.33，0.66，1这几个时间点上检测2个球的碰撞。下面的代码实现了以上所说的：球被表示为中心和它的半径，决定两个球是否相交就是求出它们之间的距离是否小于它们的直径。当找到了碰撞位置后,下一步需要知道它是否发生在当前这一步中.如果距离碰撞点的位置小于这一步球体运动的间隔,则碰撞发生.使用如下的方程计算运动到碰撞时所需的时间:Tc4-10接着知道碰撞点位置,如下面公式所示:Collisionpoint4-11//返回两个球的索引号，碰撞点以及碰撞所发生的时间片intCMyCollision1View::FindBallCol(CVector&point,double&TimePoint,doubleTime2,int&BallNr1,int&BallNr2){ CVectorRelativeV; CTrayrays; doubleMyTime=0.0,Add=Time2/300.0,Timedummy=10000;//time2是时间的步长，add将一个时间片分成了150个小片 CVectorposi;//判断球和球是否相交，将所有的球都和其他的球检测一遍，BrOfBalls是球的总个数 for(inti=0;i<NrOfBalls-1;i++) { for(intj=i+1;j<NrOfBalls;j++) { RelativeV=ArrayVel[i]-ArrayVel[j]; rays=CTray(OldPos[i],CVector::unit(RelativeV));//计算射线公式 MyTime=0.0; if((rays.dist(OldPos[j]))>40)//如果两个球心的距离大于两个球的半径（20+20=40），表明没有碰撞，直接返回，//如果有碰撞的话，计算出精确地撞击点 continue; while(MyTime<Time2)//循环检测以找到精确地撞击点 { MyTime+=Add;//将一个时间片分成150份 posi=OldPos[i]+RelativeV*MyTime;//计算每个时间片段的位置 if(posi.dist(OldPos[j])<=40)//如果球心距离小于40，表明在该时间片发生了碰撞 { point=posi;//将球的位置更新为撞击点的位置 if(Timedummy>(MyTime-Add)) Timedummy=MyTime-Add; BallNr1=i;//记录哪两个球发生了碰撞 BallNr2=j; break; } } } } if(Timedummy!=10000)//如果发生了碰撞，记下碰撞发生时间 { TimePoint=Timedummy; return1; } return0;}

4.2.5时间片的选取时间片越小算法精度越高，但是计算量提高降低了算法的效率。下面以球体碰撞为例来说明时间片的计算。第一种情况：球1与球2正向碰撞，假设球1和球2的半径为R，球1速度为V。如图所示，t1时刻正好相碰，t3时刻正好离开。球2球1VR球2球1VR球1球2球1球2(a)时刻t0(b)时刻t1球2球1球2球1球2球1球2球1(c)时刻t2(d)时刻t3图4-4球1与球2正向碰撞时间片第二种情况：球1与球2侧向碰撞，假设球1和球2的半径为R，球1的速度为V，运动方向为Raydirection，球1的球心为Raystart，球心的运动轨迹上的点为PointOnRay，球2的球心为position，S为球1的位移。如图4-5所示，联立方程组求得时间片∆t4-12

RV球2球1RV球2球1RV球2RV球2时刻t0时刻t1VR球2VR球2RV球2RV球2时刻t2(d)时刻t3球2球2SD2R2RSD2R2R时刻t3求位移S图4-5球1与球2侧向碰撞由此得到的时间片恰好是临界值，可以很大程度上减少计算量，提高算法的效率。

第5章碰撞模拟5.1球体间的碰撞模拟为了计算对于一个静止物体的碰撞,需要知道以下信息:碰撞点,碰撞法线,碰撞时间.它是基于以下物理规律的，碰撞的入射角等于反射角。如下图所示:IINRR为反射方向I为入射方向N为法线方向图5-1碰撞模拟反射方向有以下公式计算：R5-1注意的是I和N都必须是单位化向量:其代码如下：rt2=ArrayVel[BallNr].mag();a//求出球的速率ArrayVel[BallNr].unit();//归一化a//计算反弹ArrayVel[BallNr]=TVector::unit((normal*(2*normal.dot(-ArrayVel[BallNr])))+ArrayVel[BallNr]);ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;//乘上速率以求得反弹后的速度U1UU1U2U2yU2xU1xU1y图5-2碰撞后的速度如上图所示，U1和U2为速度向量，X_Axis表示两个球中心连线的轴，U1x和U2x为U1和U2在这个轴上的分量。U1y和U2y为垂直于X_Axis轴的分量。M1和M2为两个球体的分量。V1和V2为碰撞后的速度，V1x,V1y,V2x,V2y为他们的分量。假设所有球的质量都相等，解得方程为，在垂直轴上的速度不变，在X_Axis轴上互相交换速度。代码如下：求出X_AxisX_Axis5-2b）求出两个球体的速度在X_Axis上的分量U1x=X_Axis5-3U1y=U1-U1x5-4U2x=-X_Axis*(-X_AxisdotU2)5-5U2y=U2-U2x5-6求出新的速度V5-7V5-8令M1=M2=1d）求出最终的速度V1y=U1yV2y=U2yV1=V1x+V1yV2=V2x+V2y其代码如下：Vector3pb1,pb2,xaxis,U1x,U1y,U2x,U2y,V1x,V1y,V2x,V2y;doublea,b;pb1=OldPos[BallColNr1]+ArrayVel[BallColNr1]*BallTime;//找到球1的位置pb2=OldPos[BallColNr2]+ArrayVel[BallColNr2]*BallTime;//找到球2的位置xaxis=(pb2-pb1).unit();//计算出X_Axis的矢量a=xaxis.dot(ArrayVel[BallColNr1]);//计算球1的速度在X_Axis上的分量U1x=xaxis*a;U1y=ArrayVel[BallColNr1]-U1x;xaxis=(pb1-pb2).unit();//和上面的代码一样，计算球2的速度在X_Axis上的分量b=xaxis.dot(ArrayVel[BallColNr2]);U2x=xaxis*b;U2y=ArrayVel[BallColNr2]-U2x;V1x=(U1x+U2x-(U1x-U2x))*0.5;V2x=(U1x+U2x-(U2x-U1x))*0.5;V1y=U1y;V2y=U2y;for(j=0;j<NrOfBalls;j++)ArrayPos[j]=OldPos[j]+ArrayVel[j]*BallTime;ArrayVel[BallColNr1]=V1x+V1y;//设置新的速度给那两个发生了碰撞的球ArrayVel[BallColNr2]=V2x+V2y;

5.2程序截图采用射线法进行碰撞检测，程序中有6个平面，3个圆柱体和10个圆球。基于OPENGL的演示程序截图如下：图5-3球和圆柱体碰撞图5-4球和平面碰撞图5-5球和球碰撞

结论随着大型3D游戏的普及，以及虚拟现实领域的深入发展，很多专家学者投入到碰撞检测算法的研究中。目前有各种各样的算法，但是都有一定的局限性。寻找更快、更准、更小的算法成为众多学者的目标。层次包围盒法受到很多人欢迎，但是在大量数据下容易变成程序的瓶颈，影响效果。而基于射线法的碰撞检测算法具有快速，准确的特点。本文实现了球体与平面、球体与圆柱体、球体与球体之间的碰撞检测，通过优化数学计算，使得算法更快，效率更高。但是现在基于射线主要对规则的物体，针对不规则物体的碰撞检测算法还有待研究。未来关于快速碰撞检测算法的研究将永不止步。

参考文献[1]魏迎梅,王涌,吴泉源,等.碰撞检测中的固定方向凸包包围盒的研究[J].软件学报,2001,12(7):105621063.[2]潘振宽,李建波.基于压缩的AABB树的碰撞检测算法[J].计算机科学,2005,33(2):2132215.[3]ChristerEricson.实时碰撞检测算法技术.刘天慧.清华大学出版社,2010:5~272[4]邹益胜.实时碰撞检测算法技术综述.计算机应用研究.2008,25(1):1~10[5]赵伟.复杂虚拟环境下的实时碰撞检测算法.系统仿真学报.2010,22(1):125~129[6]马登武.基于包围盒的碰撞检测算法综述.系统仿真学报.2006,18(4):1058~1064[7]梁鹏帅.碰撞检测算法的探讨.科技信息.2008,25(1):1~10[8]王志强.碰撞检测问题研究综述.软件学报.1999,10(5):545~551[9]何伟.碰撞检测中的包围盒方法.重庆工学院学报.2007,21(12):148~152[10]魏迎梅.碰撞检测中的固定方向凸包包围盒的研究.软件学报.2002,23(7):1056~1063[11]钟帅.谈虚拟现实中的碰撞检测问题.河南机电高等专科学校学报.2009,17(6):107~109[12]梁小红.虚拟环境中的软体碰撞检测技术综述.计算机与数字工程.2007,35(3):25~28[13]侯伟伟.虚拟装配中基于精确模型的碰撞检测算法.2010,22(5):797~802[14]周俊玮.一种基于八叉树的OBB包围盒碰撞检测方法.计算机应用于软件.2009,26(4):75~77[15]黄通浪.一种快速精确地连续碰撞检测算法.浙江大学学报.2006,40(6):1051~1055[15]刘小平.运用改进的八叉树算法实现精确碰撞检测.计算机辅助设计与图形学学报.2005,17(12):2631~2635[16]陶阳.自定义的AABB碰撞检测算法.电脑编程技巧与维护.2010,21(6):71~74

附录1几何模型中的碰撞检测几何模型中的碰撞检测调查北卡罗来纳大学的MingC.Lin教授和StefanGottschalk教授摘要我们调查了几何模型中的碰撞检测的艺术。其中的几何模型包括多边形对象，样条曲面或代数曲面，CSG模型和可变形体。我们提出了若干能用于接触检测的技术和系统。我们也描述了一些体算法来减少成对的相交测试的数量。1. 简介碰撞检测（干扰探测或接触检测）的目的是当几何接触将要发生或已经发生时自动产生报告。其中几何模型包括多边形对象，曲线或代数曲线。这个问题经常出现在计算机辅助设计和加工(CAD/CAM)，机器人学，自动化，制造业，计算机图形学，动画制作和计算机模拟环境。碰撞检测使模拟为基础的设计，工程分析，装配和拆卸，运动规划，动画图清晰，预排等等成为可能。所有这些任务包括接触分析和静态和动态对象的空间推理。在许多这样的应用领域中，碰撞检测被认为是主要的计算瓶颈。碰撞检测是机器人移动和控制的主要组成部分，它可以帮助机器人远离周围的障碍物。在虚拟的原型设计中，在开始的设计阶段它常常被用来改善设计。碰撞检测还是工程分析中的重要的手段。现实中不易进行的实验可以模拟仿真，例如对隧道设计的支持。另一个事例就是可以有组织的完成从而减少开支的车祸实验和工程分析，而且这些实验更易于控制，通过计算机可以模拟不同的环境。在本论文中，我们通过一系列多边形的曲面调查了几何模型中的碰撞检测的艺术。论文中的其余部分按如下股则划分。在第2部分，我们提出了问题域的分类。在第3部分，我们简要调查了多边型模型的算法。在第4部分，我们描述了几何模型中的碰撞检测的艺术，并且讨论了每种方法的优缺点。在第5部分，主要介绍了可以减少成对的交互实验的技术。在第6部分，我们列出了一些公共领域软件。2. 问题域分类包括分层的展示，代数公式，空间分割，分析方法和最优方法在内的许多不同技术都已经被提出来。算法设计依赖于模型展示和模拟环境。2.1 模型展示在CAD/CAM和3D图形学中有很多类型的模型展示，我们采取的分类方法在第一部分有说明。2.1.1 多边形模型多边形对象是计算机图形学中最常用的模型，他们不仅很容易展示，而且是通用的，最常用的多边形模型类是多边形类，他们既没有几何上的联系又没有拓扑信息。一些几何算法依赖于这个结构。2.1.2 立体几何立体几何包括球体，圆柱体，锥形体，圆环面，以及他们之间的交叉和连接。CSG展示的增强之处在于他可以通过剪切和连接简单的形状来形成更复杂的模型。他还使碰撞检测的观察变得更加容易。2.2 模拟环境为碰撞检测设计和选择最适合的算法经常要考虑每一次模拟的特点，这里我们测试几个常见的实例。2.2.1 一对过程与N体过程如果一个问题只含有一对模型，那么我们称他为一对过程；如果有很多不同的部分我们称它为N体过程。2.2.2 移动：静态与动态对于相同的环境中的相同的模型经常进行重复的查询，因为对象会在连续的阶段进行旋转和转化。在动态的环境中，如果这两个阶段相对较小的话，几何关系可能与前一阶段只有很少的改变。可以利用上述特性的算法具有暂时的一致性。为了暂时一致，一些算法要求限定对象的移动边界。其他算法,例如基于区间运算的算法,需要根据时间解析移动。还有一些算法仅需要对象在连续的阶段的位置，而不需要移动的信息。有时候，一个问题只包含静态的对象。例如，对于一个整体的发电站模型，工厂设计师可能对检查整个工厂中的部分静电干扰感兴趣。2.2.3 刚体与变体当组件的时间被引进，模型的变形就有可能超时。假设各个