什么是碰撞检测

碰撞检测指计算机在发送数据的同时检测信道上的信号电压大小。

通信信道

当一个站检测到的信号电压摆动值超过了一定的门限值时，就会认为总线上至少有两个站同时在发送数据，表示产生了碰撞。在发生碰撞时，总线上传输信号产生了严重的失真，无法从中恢复有效信息。每一个正在发送数据的站，一旦发现总线上产生了碰撞，则会立即停止发送，以免继续浪费资源，通常在等待一段时间后再次发送。

发送数据的站一旦发现发生碰撞时，除了立即停止发送数据外，还要继续发送若干比特的人为干扰信号，以便让所有用户都知道已经发生了碰撞。

3D游戏

碰撞检测在3D游戏中至关重要。好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度内的台阶可以自动上去；而过高的台阶则把人挡住，遇到斜率较小的斜坡可以上去，斜率过大则把人挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够详细和稳定，防止人物在特殊情况下穿墙而掉出场景。

早期3D游戏的碰撞检测多数基于格子或者BSP树，基于格子的系统实现简单但精度不够，不属于严格意义的3D碰撞检测。基于BSP树的碰撞检测一度十分流行，算法基本已经成熟定型，但它的固有缺点却使它不太适合游戏。BSP树需要很长的预处理时间不适合加载时计算，BSP划分经常会产生原多边形数三到四倍的多边形，考虑到不用保存法线、颜色、uv等信息也要增加将近一倍的资源容量，在一个大的游戏中将模型资源的容量从200M增加到400M相信是大部分人都不愿接受的。对于任意复杂三角形集合（mesh）的碰撞检测多数基于BVTree（bounding volume tree），具体可以是aabb tree，obb tree或者K-dop tree，这也是当今各种物理引擎和碰撞检测引擎流行的做法。

上面是碰撞检测按数据结构不同的分类，按检测方式又可以分为离散点的碰撞检测和连续碰撞检测（CCD continuous collision detection）。离散点的碰撞检测是指定某一时刻T的两个静态碰撞体，看它们之间是否交迭，如果没有交迭则返回它们最近点的距离，如果交迭则返回交迭深度，交迭方向等。连续碰撞检测则是分别指定在T1、T2两个时刻两个碰撞体的位置，看它们在由T1运动到T2时刻的过程中是否发生碰撞，如果碰撞则返回碰撞点的位置和法线。连续碰撞检测是最为自然的碰撞检测，可以大大方便碰撞响应逻辑的编写，可以很容易避免物体发生交迭或者穿越。离散点的碰撞检测则没有那么友好，当检测到碰撞时两个物体已经发生了交迭，如果其中有三角形网格对象那么已经有许多三角形发生了交迭，如何将两个交迭的对象分开并按合理的方式运动是一个挑战。虽然连续碰撞检测是最自然的方式，但它的实现非常复杂，运算开销也很大，所以大部分成熟的物理引擎和碰撞检测引擎还是采用了基于离散点的碰撞检测，为了避免物体交迭过深或者彼此穿越，大多都要采用比较小的模拟步长。

目前成功商业3D游戏普遍采用的碰撞检测是采用BSP树及包装盒方式。简单讲就是采用一个描述用的正方体或者球型体包裹住3D物体对象整体（或者是主要部分），之后根据“描述用”包装盒的距离、位置等信息来计算是否发生碰撞。