游戏引擎中的碰撞检测

碰撞检测是物理引擎的第一个环节，负责回答"谁和谁碰上了"。核心挑战在于：逐对检测 O(n²) 的复杂度不可接受，必须通过**宽阶段（快速排除）+ 窄阶段（精确检测）**两阶段，配合空间加速结构，将复杂度降至近似 O(n log n)。

---

一、宽阶段（Broad Phase）

宽阶段用包围体 + 空间加速结构快速筛出"可能相碰"的候选对，是性能的第一道关卡。

1.1 BVH（Bounding Volume Hierarchy）

边界体积层次结构，将物体用包围体包裹后递归分组为树。每个节点存包围盒，查询时从根下潜，不相交的整枝剪掉：

                [根 AABB]
               /         \
        [子树 AABB]     [子树 AABB]
         /     \          /     \
     [叶:物体A][叶:物体B][叶:物体C][叶:物体D]

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)

BVH 的构建通常在物体移动后采用增量 refit（自底向上更新包围盒），而非每帧从头重建。对于包含大量动静态物体的混合场景，双 BVH 方案（动态物体与静态场景各一棵树）是常见的优化手段。

1.2 Sweep and Prune（SAP）

沿轴排序所有包围盒端点，利用帧间连续性增量更新，摊销 O(n)。对轴向分布敏感——物体沿某轴分布较广时效率更高。

1.3 空间网格 / 空间哈希

将世界划分为均匀网格，物体落入若干格子，仅在相同格子内检测。格子尺寸通常取物体平均大小的 2~3 倍。粒子系统、均匀分布场景尤其适合：

class SpatialGrid:
    def __init__(self, cell_size):
        self.cell_size = cell_size
        self.cells = {}

    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()
        # 查询 obj 所在的所有格子
        # ...
        return candidates - {obj}

1.4 八叉树（Octree）

递归将空间划分为 8 个子空间，特别适合物体分布不均匀的三维场景。在二维空间中，类似的数据结构称为四叉树（Quadtree）。

class OctreeNode:
    def __init__(self, bounds, depth=0, max_depth=8, max_objects=8):
        self.bounds = bounds
        self.objects = []
        self.children = [None] * 8

    def insert(self, obj):
        if self.children[0] is not None:
            for idx in self.get_child_indices(obj):
                self.children[idx].insert(obj)
            return
        self.objects.append(obj)
        if len(self.objects) > self.max_objects and self.depth < self.max_depth:
            self.subdivide()
            # 重新分配已有物体到子节点...

宽阶段算法对比

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

---

二、窄阶段（Narrow Phase）

对候选对做精确几何相交，生成接触流形（接触点、法线、穿透深度）。

2.1 GJK（Gilbert-Johnson-Keerthi）

判断两凸形是否相交。核心思路：对两形状计算闵可夫斯基差（Minkowski Difference），若差集包含原点则相交。通过支撑函数迭代构造单纯形逐步逼近原点，效率极高：

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 适用于任意凸形状，不需要预先计算边或面，代码简洁。但只判断是否相交，不直接提供碰撞信息，需配合 EPA。

2.2 EPA（Expanding Polytope Algorithm）

GJK 判定相交后，EPA 在闵可夫斯基差边界上扩展多面体，外推得到穿透深度与分离法线：

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)

2.3 SAT（Separating Axis Theorem，分离轴定理）

判断凸多边形碰撞的经典算法。核心思想：若存在一条轴使两形状的投影不重叠，则它们不相交。对于 2D 凸多边形需检查每条边的法向量，对于 3D 凸多面体还需检查边与边的叉乘：

def sat_collision(poly_a, poly_b):
    axes = get_face_normals(poly_a) + get_face_normals(poly_b)
    min_overlap = float('inf')
    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
    return True, collision_axis, min_overlap

SAT 可直接得到碰撞法向量和穿透深度，但只适用于凸多边形/多面体（凹形需先做凸分解）。

窄阶段算法对比

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

简单形状（球、盒、胶囊、三角形）有解析的快速专用检测，通常作为 GJK 的前置快速路径（early out）。

---

三、接触点计算

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

点-面接触（最常见）

1. 找到物体 A 上穿透最深的顶点
2. 找到物体 B 上对应的最近面
3. 接触点 = 顶点在面上的投影

边-边接触

找到两条边的最近点，接触点取中点，法向量为两边方向的叉乘。

Sutherland-Hodgman 裁剪

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

std::vector<Point> clip_polygon(const std::vector<Point>& subject,
                                  const Plane& clip_plane) {
    std::vector<Point> output;
    Point s = subject.back();
    for (const Point& e : subject) {
        bool s_inside = distance(s, clip_plane) >= -epsilon;
        bool e_inside = distance(e, clip_plane) >= -epsilon;
        if (e_inside) {
            if (!s_inside) output.push_back(intersect(s, e, clip_plane));
            output.push_back(e);
        } else if (s_inside) {
            output.push_back(intersect(s, e, clip_plane));
        }
        s = e;
    }
    return output;
}

接触点管理

• 聚类（Contact Reduction）：相似接触点合并，通常保留 ≤4 个足够稳定
• 缓存：利用时间一致性从上一帧接触点开始搜索

---

四、连续碰撞检测（CCD）

高速物体在一步内可能穿过薄物体（隧穿 Tunneling）。CCD 通过扫掠（swept）检测运动路径上的碰撞：

• 扫掠测试（Sweep Test）：将物体从起点扫到终点，检测扫掠体是否相交
• TOI（Time of Impact）：计算两物体第一次碰撞的时间点
• Speculative CCD：预测当前步内最早 TOI，提前响应

CCD 开销高，通常只对高速关键物体（子弹、碎片）开启。

---

五、性能基准测试

测试环境：AMD Ryzen 9 5900X，1000 个随机分布的球体和立方体

宽阶段

算法	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

优化建议

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

---

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

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

// 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	白色
潜在碰撞对	高亮宽阶段输出	黄色
实际碰撞	碰撞中的物体	红色
接触信息	接触点和法线	红箭头

常见 Bug

Bug	症状	解决
物体抖动	静止物体轻微抖动	添加位置修正 slop，小穿透不修正
物体弹跳	落下反复弹跳	降低 restitution / 添加速度阈值
物体穿透	高速穿过其他物体	启用 CCD / 限制最大速度
堆叠不稳	堆叠体下沉或散开	增加求解器迭代 / 优化接触点

---

八、性能与实践

• 宽相是关键：好的空间结构能将 O(n²) 降到近似 O(n log n)
• 休眠（Sleeping）：静止物体进入睡眠后不再参与宽相，直到被扰动
• 碰撞体简化：动态物体尽量用简单凸形（盒、球、胶囊），静态物体可用 triangle mesh collider
• 分层过滤（Collision Matrix）：用层和掩码排除不需要的碰撞对
• CCD 按需开启：只对高速小物体开启
• Pair Cache 管理：宽相候选对缓存，下一帧增量更新
• 数值精度：始终使用 epsilon 做浮点比较，避免接近零的向量归一化

---

总结

碰撞检测通过宽相与窄相两阶段将 O(n²) 降为近似 O(n log n)。宽相利用 BVH、SAP、空间网格、八叉树等加速结构排除大量不可能碰撞的对；窄相通过 GJK/EPA/SAT 完成精确相交判定与接触流形生成。CCD 解决高速物体隧穿问题，休眠、碰撞体简化、分层过滤、pair cache 等工程实践进一步平衡精度与性能。理解主流引擎（Box2D/Bullet/PhysX/Jolt）的实现选型有助于实际项目中的技术决策。

---

附：核心概念速查

概念	说明
宽相 / 窄相	快速排除候选 / 精确检测生成接触
AABB / BVH / SAP / 八叉树	宽相的包围体与加速结构
空间网格 / 空间哈希	均匀网格分桶加速宽相
GJK	凸形相交判断（闵可夫斯基差 + 支撑函数）
EPA	GJK 后求穿透深度与分离法线
SAT	分离轴定理，凸多边形碰撞经典算法
接触流形	接触点、法线、穿透深度
Contact Reduction	聚类去重接触点（≤4 个足够）
CCD / TOI	连续碰撞检测 / 碰撞时间，防高速隧穿
Sleeping	静止物体休眠省开销
碰撞矩阵	层 / 掩码过滤碰撞对

---

参考资源

书籍

• 《Real-Time Collision Detection》 by Christer Ericson — 碰撞检测领域经典
• 《Game Physics Engine Development》 by Ian Millington — 从零构建物理引擎实践

论文

• Gilbert, Johnson, Keerthi (1988) — GJK 原始论文
• Erin Catto — "Dynamic Bounding Volume Hierarchies" (GDC)

开源引擎

• Box2D：https://github.com/erincatto/box2d
• Bullet Physics：https://github.com/bulletphysics/bullet3
• Jolt Physics：https://github.com/jrouwe/JoltPhysics