3.1.2 扫描与修剪算法

文档摘要

3.1.2 扫描与修剪算法在物理引擎、游戏开发、机器人运动规划乃至大规模粒子仿真中，宽相检测（Broadphase）从来不是“配角”——它是一场无声的守门战。当数以万计的刚体在场景中并行运动，若每帧都对所有物体对执行精确的几何交叠判定（即窄相检测），计算量将爆炸式增长至 $O(n^2)$ 级别：一万物体意味着单帧需执行一亿次碰撞测试。这不仅毫无必要，更是对算力的残酷浪费。宽相检测的核心使命，从来不是“判断是否相撞”，而是以极低成本筛出“可能相撞”的候选对集合，将后续高开销的精确检测压缩到 $O(k)$ 量级（其中 $k \ll n^2$）。