碰撞侦测

碰撞侦测（Collision detection）或称为碰撞检测通常是指一种判断两个或多个对象是否产生交集的的方法。往往应用于电子游戏和其他计算物理学当中，也应用于人工智能当中。除了确定两个对象是否已经碰撞，碰撞侦测也可以用于计算冲击的时间（TOI），以及回报对象交叉的位置。[1] 碰撞响应（英语：collision response）一旦侦测到碰撞则处理模拟（物理引擎，布娃娃系统）。解决碰撞侦测问题需要使用广泛的概念，如线性代数和计算几何。

概述

 
台球碰撞的模拟是碰撞侦测的经典例子。

在物理模拟当中，如果验证台球产生的位置，则需要模拟刚体运动和弹性碰撞。并且在初始化的时候赋予与台球桌和球一些非常精确的物理描述，以及所有的球的初始位置。设置施于母球的力（可能是从一个玩家以球杆击中球的得到数值），之后计算球的运动轨迹，并计算所有球的最终位置。

电子游戏也应用碰撞侦测，但与模拟真实世界的物理通常需要较多的计算，与模拟真实世界的物理不一样的地方是，通常电子游戏当中都是采用可以实时且近似的计算来模拟物理来满足玩家。

物理模拟

改善

电子游戏

算法

GJK

GJK（Gilbert–Johnson–Keerthi distance algorithm）是确定两个凸集之间的最小距离的一个方法。与其它的距离的算法不同的是，它不需要对特定的形状编写代码即可通用，仅依赖于一个支撑集功能[2]，以迭代地生成单形以对两个凸集求闵可夫斯基和。

分离轴定理

分离轴定理（Separating Axis Theorem，简称SAT），是判断两个凸集状是否相交的方法。SAT是一个快速通用的算法不必为每个形状去编写代码由此减少和以便维护碰撞侦测的代码。[3]

参见

  • 四叉树
  • 八叉树
  • 包围体
  • 物理引擎

参考

  1. ^ Ericson, Christer. Real-time Collision Detection. Elsevier, 2005, p. 13.
  2. ^ GJK (Gilbert–Johnson–Keerthi). 2010-04-13 [2016-02-18]. （原始内容存档于2016-03-01） （英语）. 
  3. ^ SAT (Separating Axis Theorem). 2010-01-01 [2016-02-18]. （原始内容存档于2016-03-02） （英语）.