性能优化概述

碰撞测试是CPU密集的工作。因为判断两个形状是否相交需要相当的计算量，并且随物体数量递增所需的相交测试会迅速增长。检测N个物体的相交，蛮力地测试逐对物体需要一个O(N^2)的算法。

实践上有更高效的算法，碰撞引擎通常会使用某种空间散列方法、空间细分或者层次式包围体积，以降低相交测试次数。

1.时间一致性

常见的优化技巧是利用时间一致性(temporal coherency)，也称为帧间一致性。当碰撞体以正常速度移动，在两时间step中其变换通常接近。通过跨越多帧把结果缓存，我们可以避免每帧计算一些类型的信息。

2.空间划分

空间划分(space partitioning)基本思路是通过把空间切割成较小的区域，以大幅降低需要做相交测试的碰撞体。属于不同区域的碰撞体不需要更进一步的相交测试。

有多种层阶式的方案可以为优化碰撞测试划分空间，例如八叉树、BSP树、kd树等，这些方案把空间以不同方式细分，它们都是层阶式的。

3.例子：Havok的不同阶段

Havok使用三阶段的方式，缩减每时间step中所需检测的碰撞体几何。

1. 粗略阶段：粗略的AABB测试判断哪些物体有机会碰撞。
2. 中间阶段：检测复合形状的逼近包围体。
3. 精确阶段：测试碰撞体中个别碰撞原型是否相交。

4.扫掠裁剪算法

所有主要的碰撞引擎的粗略阶段碰撞检测会使用一个名为扫掠裁剪算法。其基本思路是对每个碰撞体的AABB的最小最大坐标在三个主轴上排序，然后通过遍历该有序表检测AABB间是否重叠。

扫掠裁剪算法可以利用帧间一致性把O(nlogn)的排序操作缩减至O(n)的预期运行时间。帧间一致性也可以帮助旋转物体时更新其AABB。

（END）