3d碰撞检测技术

核心提示10.3 碰撞检测技术 到目前为止，构造的各种对象都是相互独立的，在场景中漫游各 种物体，墙壁、树木对玩家（视点）好像是虚设，可以任意从其中穿越。为了使场景人物更加完 善，还需要使用碰撞检测技术。 10.3.1 碰撞检测技术简介 无论是 PC 游戏，还是移动应用， 10.310.3碰撞检测技术碰撞检测技术 到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体， 墙壁、树木对玩家（视点）好像是虚设，可以任意从其中穿越。为了使 场景人物更加完善，还需要使用碰撞检测技术。 10.3.110.3.1碰撞检测技术简介碰撞检测技术简介 无论是 PC 游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至 可以用碰撞检测作为衡量游戏引擎是否完善的标准。 好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可 以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上 去，斜率过大则会把人物挡住，在各种前进方向被挡住的情况下都要尽 可能地让人物沿合理的方向滑动而不是被迫停下。 在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。 做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中 的常识。如果出现 Bug，很容易被人发现，例如人物无缘无故被卡住不能 前进或者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法， 算法复杂，容易出错。 对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶 点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游 戏上使用的碰撞检测不可能使用太精确的检测，而且对于 3D 碰撞检测问 题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和 精确性。 目前成功商业 3D 游戏普遍采用的碰撞检测是 BSP 树及 AABB（axially aligned bounding box）包装盒（球）方式。简单地讲，AABB 检测法就 是采用一个描述用的立方体或者球形体包裹住 3D 物体对象的整体（或者 是主要部分），之后根据包装盒的距离、位置等信息来计算是否发生碰 撞，如图 10-24 所示。 除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和 方便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一 些特殊场合使用。BSP 树是用来控制检测顺序和方向的数据描述。 在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者 相对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可 以节省重要的时间。 如果使用单步碰撞检测，需要注意当时间步长较大时会发生两个物体完 全穿透而算法却未检测出来的问题，如图 10-25 所示。其解决方案是产 生一个 4D 空间，在物体运动的开始和结束时间之间产生一个 4D 超多面 体，用于穿透测试。 图 10-24 AABB 包装盒图 10-25碰撞检测的单步失控和 4D 测试 读者在程序开发初期有必要对碰撞检测有一个初步的估计，以免最后把 大量精力消耗在碰撞检测问题上，从而降低了在基础的图形编程之上的 注意力。 10.3.210.3.2球体碰撞检测球体碰撞检测 真实的物理模拟系统需要非常精确的碰撞检测算法，但是游戏中常常只 需要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而 不用知道模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影 成较规则的物体进行碰撞检测。 球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知 道两个球体的球心和半径就能进行检测。 那么球体碰撞是如何工作的主要过程如下。 n计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较。 n如果距离大于半径和，则没有发生碰撞。 n否则，如果距离小于半径和，则发生了物体碰撞。 考虑由球心c 1、c2 和半径r 1、r2 定义的两个球，如图 10-26 所示。设d 为球心间的距离。很明显，当d＜r 1r2 时相交，在实践中通过比较d 2＜ r 1r2 2，可以避免包括计算d在内的平方根运算。 对两个运动的球进行碰撞检测要麻烦一些，假设两个球的运动 向量为d 1 和d 2，球与位移向量是一一对应的，它们描述了所讨 论时间段中的运动方式。 事实上，物体的运动是相对的，例如两列在两条平行轨道上相 向行驶的火车，在其中一列中观察，对方的速度是两车速度之和。同样， 也可以从第一个球的角度来简化问题，假设第一个球是“静止”的，另 一个是“运动”的， 那么该运动向量等于原向量d 1 和d 2 之差， 如图 10-27 所示。 图 10-27动态球的检测过程 球体碰撞的优点是非常适用于需要快速检测的游戏，因为它不需要精确 的碰撞检测算法。执行速度相对较快，不会给CPU 带来过大的计算负担。 球体碰撞的另一个劣势是只适用于近似球形物体，如果物体非常窄或者 非常宽，该碰撞检测算法将会失效，因为会在物体实际发生碰撞之前， 碰撞检测系统就发出碰撞信号，如图 10-28 所示是球体碰撞检测中可能 出现的坏情况，其解决方法是缩小检测半径，或者使用其他检测模型， 如图 10-29 所示。 图10-28球体碰撞的坏情 况图 10-29缩小检测半径 为了解决包容球精确度不高的问题，人们又提出了球体树的方法。 球体树实际上是一种表达 3D 物体的层次结构。对一个形状复杂的 3D 物 体，先用一个大球体包容整个物体，然后对物体的各个主要部分用小一 点的球体来表示，然后对更小的细节用更小的包容球体，这些球体和它 们之间的层次关系就形成了一个球体树。 举例来说，对一个游戏中的人物角色，可以用一个大球来表示整个人， 然后用中等大小的球体来表示四肢和躯干，然后用更小的球体来表示手 脚等。这样在对两个物体进行碰撞检测时，先比较两个最大的球体。 如果有重叠， 则沿树结构向下遍历， 对小一点的球体进行比较， 直到没有任何球体重叠，或者到了最小的球体，这个最小的球 体所包含的部分就是碰撞的部分，如图 10-30 所示。 10.3.310.3.3 AABB AABB 立方体边界框检测立方体边界框检测 用球体去近似地代表物体运算量很小，但在游戏中的大多数物体是方的 或者长条形的，应该用方盒来代表物体。另一种常见的检测模型是立方 体边界框，如图 10-31 展示了一个 AABB 检测盒和它里面的物体。 坐标轴平行（Axially-aligned）不仅指盒体与世界坐标轴平行，同时也 指盒体的每个面都和一条坐标轴垂直，这样一个基本信息就能减少转换 盒体时操作的次数。AABB 技术在当今的许多游戏中都得到了应用，开发 者经常用它们作为模型的检测模型，再次指出，提高精度的同时也会降 低速度。 因为 AABB 总是与坐标轴平行， 不能在旋转物体时简单地旋转 AABB， 而是 应该在每一帧都重新计算。如果知道每个对象的内容，这个计算就不算 困难，也不会降低游戏的速度。然而，还面临着精度的问题。 假如有一个 3D 的细长刚性直棒，并且要在每一帧动画中都重建它的 AABB。可以看到每一帧中的包装盒都不一样而且精度也会随之改变，如 图 10-32 所示。 图 10-313D 模型与 AABB 检测盒图 10-3