碰撞检测是物理引擎的第一个环节，负责回答"谁和谁碰上了"。核心挑战在于：逐对检测 O(n²) 的复杂度不可接受，必须通过**宽相（快速排除）+ 窄相（精确检测）**两阶段，配合空间加速结构，将复杂度降至近似 O(n log n)。
逐对检测所有物体是 O(n²)，不可接受。所以分两阶段：
用包围体 + 空间加速结构快速筛出"可能相碰"的候选对：
| 结构 | 说明 |
|---|---|
| AABB | 轴对齐包围盒，相交测试极快 |
| BVH（层级包围体） | 树形组织包围盒，O(log n) 查询 |
| Sweep and Prune | 沿轴排序端点，增量更新，适合帧间连续 |
| 空间哈希 / 网格 | 均匀网格分桶，适合均匀分布 |
碰撞检测是物理引擎和游戏开发中的核心模块
示意图说明
本文中的部分示意图使用 Mermaid 绘制，确保在任何环境下都能正常显示。 :::，负责判断游戏世界中的物体是否发生相交。在现代游戏中，一个场景可能包含数千甚至数万个物体，因此高效的碰撞检测算法至关重要。
碰撞检测通常分为宽阶段（Broad Phase）和窄阶段（Narrow Phase）两个主要步骤：
宽阶段是碰撞检测的第一道关卡，其核心目标是快速。由于不需要精确结果，宽阶段可以使用各种空间划分和层次结构技术来加速。
边界体积层次结构是一种基于树的空间划分技术，通过构建树状结构来组织场景中的物体。
BVH 树结构示意
BVH 的核心思想是：
优点：
缺点：
四种常见包围体对比
| 包围体类型 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| AABB | 相交检测快，内存小 | 贴合度差 | 通用场景 |
| 球 | 相交检测最快，旋转不变 | 贴合度最差 | 球形物体 |
| OBB | 贴合度好 | 相交检测慢，需要旋转 | 复杂形状 |
| k-DOP | 贴合度较好，检测较快 | 构建复杂 | 高精度需求 |
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)空间网格将空间划分为均匀的网格单元，每个物体只与同一网格或相邻网格中的物体进行检测。
空间网格划分示意
空间网格的核心思想：
优点：
缺点：
| 场景类型 | 推荐网格大小 | 原因 |
|---|---|---|
| 粒子系统 | 2-3倍粒子半径 | 减少跨单元 |
| 均匀分布物体 | 平均物体大小的1.5-2倍 | 平衡性能 |
| 混合大小物体 | 分层网格或使用其他算法 | 空间网格不适合 |
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}八叉树递归地将空间划分为8个子空间，特别适合三维空间。
八叉树划分示意
八叉树的核心思想：
在二维空间中，类似的数据结构称为四叉树 (Quadtree)。
四叉树 vs 八叉树对比
| 特性 | 四叉树 (2D) | 八叉树 (3D) |
|---|---|---|
| 维度 | 2D | 3D |
| 子节点数 | 4 个 | 8 个 |
| 分裂方式 | 2×2 划分 | 2×2×2 划分 |
优点：
缺点：
| 特性 | 四叉树 | 八叉树 |
|---|---|---|
| 维度 | 2D | 3D |
| 子节点数 | 4 | 8 |
| 适用场景 | 2D游戏、UI | 3D游戏 |
| 内存占用 | 较低 | 较高 |
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 = []| 算法 | 最佳场景 | 时间复杂度 | 内存 | 动态更新 | 实现难度 |
|---|---|---|---|---|---|
| BVH | 通用动态场景 | O(log n) | 中 | 优秀 | 中等 |
| 空间网格 | 均匀分布小物体 | O(1) | 高 | 良好 | 简单 |
| 八叉树 | 不均匀分布 | O(log n) | 中高 | 一般 | 中等 |
窄阶段是碰撞检测的核心，对宽阶段筛选出的潜在碰撞对进行精确的碰撞检测。窄阶段不仅要判断是否相交，还要计算详细的碰撞信息（如接触点、法向量、穿透深度等），这些信息对物理模拟至关重要。
分离轴定理是判断凸多边形碰撞的经典算法，简洁而高效。
SAT 分离轴定理示意
SAT 的核心思想：对于两个凸多边形，如果存在一条直线（分离轴），使得两个多边形在这条轴上的投影不重叠，则这两个多边形不相交。
反之，如果在所有潜在的分离轴上投影都重叠，则两个多边形相交。
对于2D凸多边形，需要检查的潜在分离轴是：
对于3D凸多面体，需要检查的潜在分离轴是：
投影重叠判断
maxA < minB 或 maxB < minA → 不相交优点：
缺点：
SAT 只适用于凸形状。对于凹形状，需要先进行凸分解，将其分解为多个凸形状的组合。
什么是凸形状？
对于形状内任意两点，连接它们的线段完全在形状内部，则该形状为凸形状。