碰撞 Collision

检测

• 第一阶段，broad phase 快速找出潜在的碰撞物体对列表，不在这列表里的是绝对没可能碰撞的。broad phase确定了一批需要进一步查的物体对。
  • broad phase其中有一个简单算法叫sweep and prune(SAP)，本质上是利用了排序算法。
  • 第一步是初始化排序列表，列表中的元素是包围盒，可以用任意排序算法完成，例如快排；之后的排序就不是用快排了，而是用冒泡排序。
    • 为什么用冒泡排序更好呢？
    • 是因为一个默认的前提：物体的运动有时间相关性（temporal coherence），即当前帧和下一帧的位置是相近的，所以在冒泡排序过程中，发生的位置交换预期都很靠近。
• 第二阶段，narrow phase 准确找出发生碰撞的物体对列表。因为一个阶段的部分物体对实际上是没有碰撞的，需要在这个阶段剔除。