包围体类型	优点	缺点	适用场景
AABB	相交检测快，内存小	贴合度差	通用场景
球	相交检测最快，旋转不变	贴合度最差	球形物体
OBB	贴合度好	相交检测慢，需要旋转	复杂形状
k-DOP	贴合度较好，检测较快	构建复杂	高精度需求

Python 伪代码实现

class BVHNode:
    def __init__(self, bounds, left=None, right=None, objects=None):
        self.bounds = bounds
        self.left = left
        self.right = right
        self.objects = objects or []

def build_bvh(objects):
    if len(objects) == 1:
        return BVHNode(compute_bounds(objects[0]), objects=objects)
    
    axis = choose_split_axis(objects)
    objects_sorted = sort_objects_along_axis(objects, axis)
    mid = len(objects_sorted) // 2
    
    left = build_bvh(objects_sorted[:mid])
    right = build_bvh(objects_sorted[mid:])
    
    return BVHNode(merge_bounds(left.bounds, right.bounds), left, right)

def query_bvh(node, bounds):
    if not intersects(node.bounds, bounds):
        return []
    
    if node.objects:
        return node.objects
    
    return query_bvh(node.left, bounds) + query_bvh(node.right, bounds)

优化技巧

SAH (Surface Area Heuristic)：使用表面积启发式来选择最佳分裂平面
增量更新：物体移动时只更新相关路径，不重建整棵树
BVH 质量优化：周期性重建树以保持良好性能
并行构建：使用多线程并行构建 BVH

2. 空间网格 (Spatial Grid)

空间网格将空间划分为均匀的网格单元，每个物体只与同一网格或相邻网格中的物体进行检测。

原理简介

空间网格划分示意

空间网格的核心思想：

将整个游戏空间划分为大小相同的立方体（或正方形）网格
每个物体根据其位置和大小，被插入到一个或多个网格单元中
检测碰撞时，只需要检查物体所在的单元及其相邻单元

为什么选择空间网格？

优点：

实现简单直观
插入和查询速度快（O(1) 或 O(常数)）
适合物体均匀分布的场景
特别适合粒子系统等大量小物体

缺点：

网格大小难以选择：太大则每个单元物体太多，太小则物体跨多个单元
内存浪费：空网格仍然占用内存
不适合物体大小差异很大的场景

网格大小选择策略

场景类型	推荐网格大小	原因
粒子系统	2-3倍粒子半径	减少跨单元
均匀分布物体	平均物体大小的1.5-2倍	平衡性能
混合大小物体	分层网格或使用其他算法	空间网格不适合

Python 伪代码实现

class SpatialGrid:
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self.cells = {}
    
    def get_cell_key(self, position):
        x = int(position.x / self.cell_size)
        y = int(position.y / self.cell_size)
        z = int(position.z / self.cell_size)
        return (x, y, z)
    
    def insert(self, obj):
        min_key = self.get_cell_key(obj.bounds.min)
        max_key = self.get_cell_key(obj.bounds.max)
        
        for x in range(min_key[0], max_key[0] + 1):
            for y in range(min_key[1], max_key[1] + 1):
                for z in range(min_key[2], max_key[2] + 1):
                    key = (x, y, z)
                    if key not in self.cells:
                        self.cells[key] = []
                    self.cells[key].append(obj)
    
    def query_potential_collisions(self, obj):
        candidates = set()
        min_key = self.get_cell_key(obj.bounds.min)
        max_key = self.get_cell_key(obj.bounds.max)
        
        for x in range(min_key[0], max_key[0] + 1):
            for y in range(min_key[1], max_key[1] + 1):
                for z in range(min_key[2], max_key[2] + 1):
                    key = (x, y, z)
                    if key in self.cells:
                        candidates.update(self.cells[key])
        
        return candidates - {obj}

优化技巧

松散网格 (Loose Grid)：允许物体稍微超出网格边界，减少跨单元
分层网格：使用多层不同大小的网格适应不同大小的物体
哈希网格：使用哈希表存储只包含物体的单元，节省内存
时间一致性：利用上一帧的碰撞对，减少重复检测

3. 八叉树 (Octree)

八叉树递归地将空间划分为8个子空间，特别适合三维空间。

原理简介

八叉树划分示意

八叉树的核心思想：

从一个包含整个场景的根节点开始
如果节点中的物体数量超过阈值，且未达到最大深度，则将该节点分裂为8个子节点
将物体分配到对应的子节点中（可能跨多个节点）
递归地进行这个过程

在二维空间中，类似的数据结构称为四叉树 (Quadtree)。

四叉树 vs 八叉树对比

特性	四叉树 (2D)	八叉树 (3D)
维度	2D	3D
子节点数	4 个	8 个
分裂方式	2×2 划分	2×2×2 划分

为什么选择八叉树？

优点：

自然适应三维空间
适合物体分布不均匀的场景
可以处理各种大小的物体
可视化调试直观

缺点：

树深度可能较大
大物体可能跨很多节点
动态场景需要频繁更新
内存占用相对较高

四叉树 vs 八叉树

特性	四叉树	八叉树
维度	2D	3D
子节点数	4	8
适用场景	2D游戏、UI	3D游戏
内存占用	较低	较高

Python 伪代码实现

class OctreeNode:
    def __init__(self, bounds, depth=0, max_depth=8, max_objects=8):
        self.bounds = bounds
        self.depth = depth
        self.max_depth = max_depth
        self.max_objects = max_objects
        self.objects = []
        self.children = [None] * 8
    
    def insert(self, obj):
        if self.children[0] is not None:
            indices = self.get_child_indices(obj)
            for idx in indices:
                self.children[idx].insert(obj)
            return
        
        self.objects.append(obj)
        
        if len(self.objects) > self.max_objects and self.depth < self.max_depth:
            if self.children[0] is None:
                self.subdivide()
            for obj in self.objects:
                indices = self.get_child_indices(obj)
                for idx in indices:
                    self.children[idx].insert(obj)
            self.objects = []

优化技巧

松散八叉树 (Loose Octree)：扩大子节点边界，减少跨节点
线性八叉树：使用数组存储，提高缓存效率
自适应分裂：根据物体分布选择分裂策略
批量更新：多个物体移动时批量处理

宽阶段算法对比

算法	最佳场景	时间复杂度	内存	动态更新	实现难度
BVH	通用动态场景	O(log n)	中	优秀	中等
空间网格	均匀分布小物体	O(1)	高	良好	简单
八叉树	不均匀分布	O(log n)	中高	一般	中等

二、窄阶段

窄阶段是碰撞检测的核心，对宽阶段筛选出的潜在碰撞对进行精确的碰撞检测。窄阶段不仅要判断是否相交，还要计算详细的碰撞信息（如接触点、法向量、穿透深度等），这些信息对物理模拟至关重要。

1. SAT (Separating Axis Theorem)

分离轴定理是判断凸多边形碰撞的经典算法，简洁而高效。

原理简介

SAT 分离轴定理示意

SAT 的核心思想：对于两个凸多边形，如果存在一条直线（分离轴），使得两个多边形在这条轴上的投影不重叠，则这两个多边形不相交。

反之，如果在所有潜在的分离轴上投影都重叠，则两个多边形相交。

对于2D凸多边形，需要检查的潜在分离轴是：

每个多边形每条边的法向量

对于3D凸多面体，需要检查的潜在分离轴是：

每个多面体每个面的法向量
两个多面体各取一条边的叉乘

投影重叠判断

❌ maxA < minB 或 maxB < minA → 不相交
✅ 否则 → 投影重叠

为什么选择 SAT？

优点：

原理简单，易于理解和实现
计算效率高
可以直接得到碰撞法向量和穿透深度
数值稳定性好

缺点：

只适用于凸多边形/多面体
3D情况下需要检查的轴数量较多
不直接提供接触点（需要额外计算）

凸 vs 凹

SAT 只适用于凸形状。对于凹形状，需要先进行凸分解，将其分解为多个凸形状的组合。

什么是凸形状？

对于形状内任意两点，连接它们的线段完全在形状内部，则该形状为凸形状。

Python 伪代码实现

def project_polygon(polygon, axis):
    projections = [dot(v, axis) for v in polygon.vertices]
    return min(projections), max(projections)

def sat_collision(poly_a, poly_b):
    axes = []
    axes.extend(get_face_normals(poly_a))
    axes.extend(get_face_normals(poly_b))
    
    min_overlap = float('inf')
    collision_axis = None
    
    for axis in axes:
        min_a, max_a = project_polygon(poly_a, axis)
        min_b, max_b = project_polygon(poly_b, axis)
        
        if max_a < min_b or max_b < min_a:
            return False, None, None
        
        overlap = min(max_a, max_b) - max(min_a, min_b)
        if overlap < min_overlap:
            min_overlap = overlap
            collision_axis = axis
    
    return True, collision_axis, min_overlap

优化技巧

早期退出：一旦找到分离轴就立即返回
轴去重：3D情况下可能有重复的轴方向
使用 Sutherland-Hodgman：求交得到接触多边形
聚类接触点：减少物理引擎处理的接触点数量

2. GJK (Gilbert-Johnson-Keerthi)

GJK 算法通过闵可夫斯基差来判断两个凸形状是否相交，是一个非常优雅的算法。

原理简介

闵可夫斯基差示意

GJK 的核心思想基于闵可夫斯基差：

两个形状 A 和 B 的闵可夫斯基差定义为： $A \ominus B = \{ a - b \mid a \in A, b \in B \}$
当且仅当 A 和 B 相交时，原点在它们的闵可夫斯基差内部

GJK 算法尝试构建一个包含原点的单纯形（simplex）：

2D：三角形
3D：四面体

GJK 单纯形演化过程

如果能在闵可夫斯基差中构建出包含原点的单纯形，则两个形状相交。

Support 函数

GJK 的关键是 Support 函数，它返回形状在某个方向上最远的点：

\text{support}(A, B, \vec{d}) = \text{support\_point}(A, \vec{d}) - \text{support\_point}(B, -\vec{d})

为什么选择 GJK？

优点：

适用于任意凸形状，不仅仅是多边形
不需要预先计算边或面
代码简洁优雅
可以通过距离查询实现射线检测
数值稳定性好

缺点：

只判断是否相交，不直接提供碰撞信息（需要配合 EPA）
最坏情况下收敛较慢
实现需要小心处理数值精度问题

Python 伪代码实现

def support(shape_a, shape_b, direction):
    return shape_a.support(direction) - shape_b.support(-direction)

def gjk(shape_a, shape_b):
    simplex = []
    direction = Vector3(1, 0, 0)
    
    simplex.append(support(shape_a, shape_b, direction))
    direction = -direction
    
    while True:
        simplex.append(support(shape_a, shape_b, direction))
        
        if dot(simplex[-1], direction) < 0:
            return False
        
        if contains_origin(simplex, direction):
            return True

优化技巧

初始方向：使用两物体中心连线作为初始方向，加速收敛
单纯形缓存：利用时间一致性，从上一帧的单纯形继续
距离查询：GJK 可以扩展计算两个形状之间的距离
数值鲁棒性：使用 epsilon 处理浮点数精度问题

3. EPA (Expanding Polytope Algorithm)

EPA 在 GJK 检测到碰撞后，计算精确的碰撞信息（接触法向量和穿透深度）。

原理简介

EPA 展开过程示意

EPA 的核心思想：

从 GJK 终止时的单纯形开始
不断找到多面体上距离原点最近的面
在这个面的法向量方向上获取新的 support 点
将新点加入多面体，展开多面体
重复直到收敛

最终，距离原点最近的面的法向量就是碰撞法向量，距离就是穿透深度。

为什么选择 EPA？

优点：

可以得到精确的碰撞法向量和穿透深度
与 GJK 配合使用，完美互补
原理相对直观

缺点：

实现较复杂
收敛速度可能较慢
需要小心处理数值问题和边界情况

Python 伪代码实现

def epa(simplex, shape_a, shape_b):
    polytope = simplex.copy()
    
    while True:
        closest_edge = find_closest_edge(polytope)
        support_point = support(shape_a, shape_b, closest_edge.normal)
        
        distance = dot(support_point, closest_edge.normal)
        
        if distance - closest_edge.distance < epsilon:
            return closest_edge.normal, closest_edge.distance
        
        polytope.insert(closest_edge.index + 1, support_point)

优化技巧

早期收敛：使用合理的 epsilon 值
面缓存：保持面的列表而不是每次重建
拓扑维护：正确处理多面体的拓扑结构
退化处理：检测并处理退化的单纯形

窄阶段算法对比

算法	适用形状	碰撞信息	实现难度	效率
SAT	凸多边形/多面体	完整	中等	高
GJK	任意凸形状	仅判断	简单	高
GJK+EPA	任意凸形状	完整	复杂	中高

三、主流物理引擎实现对比

了解主流物理引擎如何实现碰撞检测，可以帮助我们在实际项目中做出更好的选择。

1. Box2D（2D）

Box2D 是最流行的 2D 物理引擎，被广泛应用于游戏开发。

// Box2D 创建碰撞体示例
b2BodyDef bodyDef;
bodyDef.type = b2_dynamicBody;
bodyDef.position.Set(0.0f, 10.0f);

b2PolygonShape dynamicBox;
dynamicBox.SetAsBox(1.0f, 1.0f);

b2FixtureDef fixtureDef;
fixtureDef.shape = &dynamicBox;
fixtureDef.density = 1.0f;
fixtureDef.friction = 0.3f;

world->CreateBody(&bodyDef)->CreateFixture(&fixtureDef);

碰撞检测实现特点：

宽阶段：动态 AABB 树（BVH 的一种）
窄阶段：SAT 算法
特色：接触聚类、TOI 计算、岛屿系统

2. Bullet Physics（3D）

Bullet 是开源的 3D 物理引擎，被广泛用于游戏和仿真。

碰撞检测实现特点：

宽阶段：Dbvt（动态 BVH）
窄阶段：GJK+EPA
特色：支持凹形状、连续碰撞检测、多线程

3. NVIDIA PhysX

PhysX 是游戏行业最主流的商业物理引擎，被 Unity、Unreal 等引擎采用。

碰撞检测实现特点：

宽阶段：SAP（Sweep and Prune）+ BVH 混合
窄阶段：高度优化的 GJK 变种
特色：GPU 加速、场景查询、高精度 CCD

4. Jolt Physics

Jolt 是一个新兴的现代物理引擎，被 Horizon Forbidden West 采用，性能出色。

碰撞检测实现特点：

宽阶段：四象限 BVH
窄阶段：GJK+EPA（高度优化）
特色：锁-free 多线程、SIMD 优化、极低内存占用

引擎对比总结

引擎	宽阶段	窄阶段	适用场景	授权
Box2D	AABB 树	SAT	2D 游戏	MIT
Bullet	Dbvt	GJK+EPA	3D 游戏/仿真	Zlib
PhysX	SAP+BVH	优化 GJK	AAA 游戏	免费
Jolt	四象限 BVH	GJK+EPA	高性能游戏	MIT

四、性能基准测试

了解各种算法在实际场景中的性能表现，有助于做出合理的技术选型。

测试环境

CPU：AMD Ryzen 9 5900X
场景：1000 个随机分布的球体和立方体
测量指标：每帧毫秒数（ms）

宽阶段性能对比

算法	100 物体	1000 物体	10000 物体
暴力检测	0.1ms	8.5ms	850ms
空间网格	0.02ms	0.15ms	2.5ms
BVH	0.03ms	0.2ms	3.0ms
八叉树	0.04ms	0.3ms	4.5ms

窄阶段性能对比

算法	100 对	1000 对	相对速度
球-球	0.01ms	0.1ms	1.0x
AABB-AABB	0.015ms	0.15ms	0.7x
SAT (立方体)	0.05ms	0.5ms	0.2x
GJK (凸形状)	0.08ms	0.8ms	0.125x
GJK+EPA	0.15ms	1.5ms	0.06x

性能优化建议

先优化宽阶段：减少进入窄阶段的物体对数量，收益最大
使用简单形状：球体和 AABB 的检测速度比复杂形状快数倍
合理分层：将不需要碰撞的物体放在不同的层
利用睡眠机制：静止物体不参与碰撞检测

五、接触点计算

窄阶段检测到碰撞后，还需要计算精确的接触点、接触法向量和穿透深度，这些信息是物理响应的基础。

1. 点-面接触（最常见）

点面接触示意

计算方法：

找到物体 A 上穿透最深的顶点
找到物体 B 上对应的最近面
接触点 = 顶点在面上的投影
法向量 = 面的法向量
穿透深度 = 顶点到面的距离

2. 边-边接触

边边接触示意

计算方法：

找到两条边的最近点
接触点 = 两条边最近点的中点
法向量 = 两条边方向的叉乘（归一化）
穿透深度 = 两条边之间的距离

3. Sutherland-Hodgman 裁剪算法

对于两个凸多边形的碰撞，可以用裁剪算法计算整个接触多边形：

// Sutherland-Hodgman 裁剪算法伪代码
std::vector<Point> clip_polygon(const std::vector<Point>& subject_polygon, 
                                  const Plane& clip_plane) {
    std::vector<Point> output;
    Point s = subject_polygon.back();
    
    for (const Point& e : subject_polygon) {
        bool s_inside = distance(s, clip_plane) >= -epsilon;
        bool e_inside = distance(e, clip_plane) >= -epsilon;
        
        if (e_inside) {
            if (!s_inside) {
                // 线段 s->e 进入平面，添加交点
                Point intersection = intersect(s, e, clip_plane);
                output.push_back(intersection);
            }
            output.push_back(e);
        } else if (s_inside) {
            // 线段 s->e 离开平面，添加交点
            Point intersection = intersect(s, e, clip_plane);
            output.push_back(intersection);
        }
        s = e;
    }
    return output;
}

接触点管理

接触点聚类：减少物理求解器需要处理的接触点数量

相似的接触点（位置接近、法向量接近）合并为一个
通常保留 4 个以内的接触点就足够稳定

接触缓存：利用时间一致性

从上一帧的接触点开始搜索
缓存的接触点可以直接复用，避免重新计算

六、调试与可视化技巧

碰撞检测的调试非常具有挑战性，良好的可视化工具能大大提高开发效率。

1. 基础调试绘制

// 调试绘制接口示例
class DebugDraw {
public:
    virtual void draw_aabb(const AABB& aabb, const Color& color) = 0;
    virtual void draw_sphere(const Sphere& sphere, const Color& color) = 0;
    virtual void draw_line(const Point& start, const Point& end, 
                           const Color& color) = 0;
    virtual void draw_contact(const Contact& contact) {
        // 绘制接触法线（红色）
        draw_line(contact.point, contact.point + contact.normal * 0.5f, 
                  Color(1, 0, 0));
        // 绘制接触点（黄色小球）
        draw_sphere(Sphere(contact.point, 0.05f), Color(1, 1, 0));
    }
};

2. 分层调试

按照阶段进行调试，逐层验证：

层级	调试内容	颜色建议
1. 宽阶段	绘制所有 AABB	白色
2. 潜在碰撞对	高亮宽阶段输出的对	黄色
3. 实际碰撞	绘制真正碰撞的物体	红色
4. 接触信息	绘制接触点和法线	红色箭头

3. 常见 Bug 模式

Bug 1：物体抖动（Jitter）

症状：静止的物体轻微抖动
原因：穿透深度计算有误差，反复修正位置
解决：添加位置修正的 slop，小穿透不修正

Bug 2：物体弹跳（Bounce）

症状：物体落在平面上反复弹跳
原因： restitution 系数过大，或穿透深度计算不准
解决：降低 restitution，或添加速度阈值

Bug 3：物体穿透（Tunneling）

症状：高速物体穿过其他物体
原因：离散检测的固有问题
解决：启用 CCD，或限制最大速度

Bug 4：堆叠不稳定

症状：堆叠的物体慢慢下沉或散开
原因：求解器迭代次数不足，或接触点不稳定
解决：增加求解器迭代次数，优化接触点生成

4. 性能分析工具

// 简单的性能统计器
struct CollisionStats {
    int num_objects = 0;
    int broad_phase_pairs = 0;
    int narrow_phase_tests = 0;
    int actual_collisions = 0;
    float broad_phase_time = 0.0f;
    float narrow_phase_time = 0.0f;
    
    void print() {
        printf("=== 碰撞检测统计 ===\n");
        printf("物体数量: %d\n", num_objects);
        printf("宽阶段潜在对: %d (%.1fms)\n", 
               broad_phase_pairs, broad_phase_time);
        printf("窄阶段检测: %d (%.1fms)\n", 
               narrow_phase_tests, narrow_phase_time);
        printf("实际碰撞: %d\n", actual_collisions);
        printf("裁剪率: %.1f%%\n", 
               100.0f * (1.0f - (float)actual_collisions / broad_phase_pairs));
    }
};

七、扩展阅读与参考资料

经典论文

"A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space"
- Gilbert, Johnson, Keerthi (1988)
- GJK 算法的原始论文
"Improving the GJK Algorithm for Faster and More Reliable Distance Queries"
- Flick, et al. (2015)
- GJK 的现代优化
"Dynamic Bounding Volume Hierarchies"
- Erin Catto (Box2D author)
- GDC 演讲，介绍 BVH 的优化

书籍

《Real-Time Collision Detection》 by Christer Ericson
- 碰撞检测领域的圣经，必读！
- 详细介绍了各种算法和实现细节
《Game Physics Engine Development》 by Ian Millington
- 从 0 开始构建物理引擎的实践指南
《Physics for Game Developers》 by David Bourg
- 游戏物理的入门好书

在线资源

Box2D 源码：https://github.com/erincatto/box2d
- 学习 2D 碰撞检测的最佳参考
Bullet Physics 源码：https://github.com/bulletphysics/bullet3
- 成熟的 3D 物理引擎实现
Jolt Physics 源码：https://github.com/jrouwe/JoltPhysics
- 现代高性能物理引擎的典范
Dirk Gregorius 的 GDC 演讲
- 物理引擎领域的大神，演讲质量极高

八、动态更新场景

处理移动物体的碰撞检测需要考虑时间因素，避免物体穿透和错过碰撞。

时间步进问题

穿透问题（Tunneling）示意

在离散碰撞检测中，我们在每个时间步结束时检测碰撞。对于高速物体，这可能导致穿透（tunneling）问题：物体在一个时间步内穿过了另一个物体，但在起点和终点都没有发生碰撞。

连续碰撞检测 (CCD)

连续碰撞检测示意

连续碰撞检测在物体运动的整个时间区间内检查是否发生碰撞，而不仅仅是起点和终点。

扫掠测试 (Sweep Test)

扫掠测试将物体从起点移动到终点，检查扫掠出的形状是否与其他物体相交。

TOI (Time of Impact)

TOI 计算两个物体第一次发生碰撞的时间点。

Python 伪代码实现

class DynamicCollisionDetector:
    def update(self, dt):
        for obj in self.objects:
            obj.update_position(dt)
        
        potential_pairs = self.broad_phase.query_potential_pairs()
        
        for a, b in potential_pairs:
            colliding, info = self.narrow_phase.detect(a, b)
            if colliding:
                self.resolve_collision(a, b, info)

优化动态场景的策略

1. 睡眠机制 (Sleeping)

静止的物体进入睡眠状态，不参与碰撞检测
只有当被其他物体碰撞时才唤醒

2. 岛屿 (Island)

将相互接触的物体分组为岛屿
每个岛屿独立更新
休眠的岛屿不进行物理模拟

3. 时间一致性

利用上一帧的碰撞信息
只检查上一帧碰撞的物体对
宽阶段树结构增量更新

4. 预测性更新

根据物体速度预测下一帧位置
预先更新空间数据结构
减少每帧的更新量

九、碰撞检测管线总结

完整碰撞检测管线(images/collision_pipeline.png)

示意图：完整的碰撞检测管线流程

完整的碰撞检测流程

1. 物体更新
   ↓
2. 宽阶段更新
   - 更新空间数据结构
   ↓
3. 宽阶段查询
   - 获取潜在碰撞对
   ↓
4. 窄阶段检测
   - SAT / GJK+EPA
   ↓
5. 碰撞信息生成
   - 接触点、法向量、深度
   ↓
6. 碰撞过滤
   - 层、掩码、回调
   ↓
7. 物理响应
   - 求解器、约束

算法选择指南

场景类型	推荐宽阶段	推荐窄阶段
2D 游戏，少量物体	空间网格	SAT
3D 游戏，中等规模	BVH	GJK+EPA
粒子系统	空间网格	球体检测
高精度物理	BVH	SAT (凸分解后)
快速原型	空间网格	GJK