游戏物理引擎(二) 碰撞检测之Broad-Phase

游戏物理引擎中的碰撞检测是一个复杂的过程，尤其在处理大量物体时， Broad-Phase算法起着关键作用。它将碰撞检测划分为两个阶段：粗粒度的Broad-Phase和细粒度的Narrow-Phase。 Broad-Phase通过使用Bounding Volume（如AABB、OBB和Circle/Sphere）来简化物体形状，通过空间划分减少碰撞检测的计算量。常见的空间分割策略如Sort and Sweep和Uniform Grid，前者通过轴向排序和区间扫除减少相交测试，后者则利用格子划分减少查找范围。其他高级技术如Hierarchical Grids、BVH（包括top-down、bottom-up、incremental tree-insertion和linear BVH）以及BSP和Octree/Quadtree，通过递归划分和优化分割方式进一步提高效率。这些技术广泛应用于游戏实时渲染、视锥裁剪和光线追踪等领域。

粗粒度的 Broad-Phase 首先定义Bounding Volume，如矩形（AABB）、定向矩形（OBB）或圆（Circle/Sphere），来简化物体形状。这些bounding volume的碰撞信息通过空间划分，如Sort and Sweep中的轴向排序和区间扫除，或者Uniform Grid的格子划分，可以在较短时间内筛选出可能碰撞的物体对，显著降低计算复杂度。而Narrow-Phase则负责对这些候选对进行精确的碰撞检测。

在实际应用中，空间组织如Grid、BVH和BSP树，如Octree/Quadtree，它们不仅用于碰撞检测，还广泛用于遮挡裁剪、视锥裁剪和光线追踪等图形处理任务。这些技术的选择和优化对于游戏性能至关重要。