碰撞检测是物理仿真引擎的核心组件之一，直接影响仿真的准确性和效率。在具身智能应用中，高效而精确的碰撞检测不仅决定了机器人与环境交互的真实性，更是强化学习训练速度的关键瓶颈。本章将深入探讨从宽相筛选到窄相精确检测的完整流程，重点介绍GJK、EPA等经典算法的数学原理，以及连续碰撞检测在高速运动场景中的应用。我们还将讨论空间数据结构的选择如何影响大规模并行仿真的性能，为读者在实际工程中的算法选择提供理论指导。
完成本章学习后，您将能够：
碰撞检测的计算复杂度在最坏情况下为$O(n^2)$，其中$n$为场景中的物体数量。为了提高效率，现代物理引擎普遍采用两阶段策略：宽相（Broad Phase）快速筛选可能碰撞的物体对，窄相（Narrow Phase）精确计算实际接触信息。
| 宽相检测的核心思想是使用简化的几何表示（通常是轴对齐包围盒AABB）快速排除不可能发生碰撞的物体对。给定$n$个物体，宽相检测输出一个候选碰撞对集合$\mathcal{P} \subseteq {(i,j) | 1 \leq i < j \leq n}$，满足： |
AABB重叠测试是最基本的宽相检测方法。对于两个AABB $B_1 = [x_1^{\min}, x_1^{\max}] \times [y_1^{\min}, y_1^{\max}] \times [z_1^{\min}, z_1^{\max}]$和$B_2$，重叠条件为：
\[\forall k \in \{x,y,z\}: \max(k_1^{\min}, k_2^{\min}) \leq \min(k_1^{\max}, k_2^{\max})\]扫描线算法通过维护物体在各坐标轴上的有序投影区间，将重叠检测的平均复杂度降至$O(n\log n)$。算法维护三个有序列表，每个列表存储物体在对应轴上的区间端点：
轴向投影结构:
X轴: [(x_min, id, BEGIN), (x_max, id, END), ...]
Y轴: [(y_min, id, BEGIN), (y_max, id, END), ...]
Z轴: [(z_min, id, BEGIN), (z_max, id, END), ...]
当物体$i$移动时，只需更新其6个端点在有序列表中的位置。通过增量式更新，对于运动连贯的场景，每帧的更新复杂度接近$O(n)$。
对于包含大量小物体的场景，空间哈希提供了更好的局部性。将空间划分为大小为$h$的网格单元，物体$i$根据其AABB覆盖的单元被插入哈希表：
\[\text{hash}(x,y,z) = (p_1 \cdot x \oplus p_2 \cdot y \oplus p_3 \cdot z) \bmod M\]其中$p_1, p_2, p_3$为大质数，$M$为哈希表大小。单元大小$h$的选择需要平衡：过小导致物体跨越多个单元，过大则降低筛选效率。经验上，$h \approx 2\bar{r}$，其中$\bar{r}$为物体平均半径。
宽相检测为每个候选对$(i,j) \in \mathcal{P}$触发窄相检测。窄相检测需要计算：
这些信息构成接触流形（Contact Manifold），是后续接触力计算的输入。
Gilbert-Johnson-Keerthi（GJK）算法是凸体间距离计算的经典方法，其优雅之处在于将碰撞检测问题转化为闵可夫斯基差中的原点包含测试。Expanding Polytope Algorithm（EPA）则在GJK检测到碰撞后，计算穿透深度和接触法向。
给定两个凸体$A$和$B$，其闵可夫斯基差定义为：
\[A \ominus B = \{a - b | a \in A, b \in B\}\]关键观察：两凸体相交当且仅当其闵可夫斯基差包含原点。
直接构造闵可夫斯基差是不现实的，GJK通过支撑映射（Support Mapping）隐式地在闵可夫斯基差上操作：
\[s_{A \ominus B}(\mathbf{d}) = s_A(\mathbf{d}) - s_B(-\mathbf{d})\]其中支撑函数$s_A(\mathbf{d})$返回凸体$A$在方向$\mathbf{d}$上的最远点：
\[s_A(\mathbf{d}) = \arg\max_{\mathbf{p} \in A} \mathbf{d} \cdot \mathbf{p}\]GJK维护一个单纯形（Simplex）$W \subseteq A \ominus B$，迭代地逼近原点。算法框架：
初始化：选择任意方向$\mathbf{d}$，计算$w_1 = s_{A \ominus B}(\mathbf{d})$，初始化$W = {w_1}$
GJK的效率关键在于高效的单纯形更新。在3D中，单纯形可能是：
Voronoi区域分析决定如何更新单纯形。例如，对于线段$[A,B]$：
Voronoi(A) | Voronoi(AB) | Voronoi(B)
A------+-------AB-------+------B
| |
原点在哪个区域决定了最近点位置和下一步搜索方向。
当GJK检测到碰撞（原点在闵可夫斯基差内）时，EPA计算穿透信息。EPA维护一个包含原点的凸多面体，通过迭代扩展找到距原点最近的边界点。
算法步骤：
初始化：使用GJK的最终四面体作为初始多面体
EPA的计算代价高于GJK，但提供了精确的穿透信息，对于精确接触响应至关重要。
离散碰撞检测在每个时间步检查静态配置下的碰撞，可能错过高速运动物体间的碰撞（隧穿问题）。连续碰撞检测通过考虑物体在时间区间$[t, t+\Delta t]$内的完整运动轨迹来解决这一问题。
对于在时间区间$[0,1]$内运动的物体，其配置由插值函数描述：
线性运动（最常用）： \(\mathbf{x}(s) = (1-s)\mathbf{x}_0 + s\mathbf{x}_1, \quad s \in [0,1]\)
螺旋运动（刚体）： \(\mathbf{T}(s) = \exp(s\log(\mathbf{T}_1\mathbf{T}_0^{-1}))\mathbf{T}_0\)
其中$\mathbf{T} \in SE(3)$为刚体变换矩阵。
对于凸多面体，分离轴定理（SAT）可扩展到CCD。两个运动凸体在$[0,1]$内不碰撞，当且仅当存在分离轴$\mathbf{n}$使得：
\[\forall s \in [0,1]: \max_{\mathbf{p} \in A(s)} \mathbf{n} \cdot \mathbf{p} < \min_{\mathbf{q} \in B(s)} \mathbf{n} \cdot \mathbf{q}\]潜在分离轴包括：
每个潜在分离轴对应一个时间区间多项式，需要求解其根。
保守推进（Conservative Advancement）通过迭代缩小安全时间步长来逼近首次碰撞时刻：
初始化：$t_{safe} = 0$，$t_{max} = 1$
迭代：
速度界$v_{max}$的紧致估计对算法效率至关重要。
对于某些几何形状，CCD可转化为射线投射问题。考虑点$\mathbf{p}$与三角形$\triangle ABC$的CCD：
点的轨迹：$\mathbf{p}(t) = \mathbf{p}_0 + t\mathbf{v}_p$
三角形平面方程：$\mathbf{n}(t) \cdot (\mathbf{x} - \mathbf{a}(t)) = 0$
碰撞条件转化为求解： \(\mathbf{n}(t) \cdot (\mathbf{p}(t) - \mathbf{a}(t)) = 0\)
这是一个关于$t$的三次方程（线性运动情况下），可用Cardano公式求解。
高效的空间数据结构是宽相检测性能的关键。不同的数据结构适用于不同的场景特征，包括物体分布、运动模式和查询类型。本节介绍四种主要的空间划分策略及其在物理仿真中的应用。
BVH通过树状结构组织包围体，支持高效的射线投射和最近邻查询。每个节点存储其子树所有物体的包围体。
构建策略：
自底向上（Bottom-up）：迭代合并最近节点对
动态更新：
对于运动物体，BVH需要增量更新：
双重遍历（Dual Traversal）用于BVH间的碰撞检测：
function DualTraverse(nodeA, nodeB):
if not Overlap(nodeA.bbox, nodeB.bbox):
return
if IsLeaf(nodeA) and IsLeaf(nodeB):
NarrowPhase(nodeA.object, nodeB.object)
else if DescendA(nodeA, nodeB):
DualTraverse(nodeA.left, nodeB)
DualTraverse(nodeA.right, nodeB)
else:
DualTraverse(nodeA, nodeB.left)
DualTraverse(nodeA, nodeB.right)
八叉树通过递归八分空间来组织物体，特别适合均匀分布的场景。
自适应细分：
节点细分条件：
松散八叉树（Loose Octree）：
每个节点的实际包围体大于其理论边界： \(\text{LooseBound} = \text{Bound} \times (1 + k)\)
其中$k \in [0.5, 1.0]$为松散因子。这允许略大于节点的物体无需跨越多个节点。
查询加速：
k-d树通过轴对齐平面递归划分空间，每层循环使用不同的划分轴。
SAH构建：
选择最优划分位置$p$和轴$a$： \(\arg\min_{a,p} \left[ n_L(p) \cdot V_L(p) + n_R(p) \cdot V_R(p) \right]\)
其中$n_L, n_R$为左右子空间的物体数，$V_L, V_R$为体积。
平衡性维护：
均匀网格是最简单但往往最有效的空间划分，特别适合GPU并行化。
哈希网格：
使用空间哈希避免存储空单元： \(h(i,j,k) = (i \cdot p_1 \oplus j \cdot p_2 \oplus k \cdot p_3) \bmod M\)
分层网格：
多分辨率网格处理不同尺度的物体：
GPU优化：
| 数据结构 | 构建复杂度 | 查询复杂度 | 内存占用 | 适用场景 |
|---|---|---|---|---|
| BVH | $O(n\log n)$ | $O(\log n)$ | $O(n)$ | 不均匀分布、复杂几何 |
| 八叉树 | $O(n\log n)$ | $O(\log n)$ | $O(n)$ | 均匀分布、体素数据 |
| k-d树 | $O(n\log n)$ | $O(\log n)$ | $O(n)$ | 点云、最近邻查询 |
| 均匀网格 | $O(n)$ | $O(1)$ | $O(n+m^3)$ | 粒子系统、GPU并行 |
选择建议：
在强化学习的物理仿真环境中，碰撞检测往往占据30-50%的计算时间。优化碰撞检测不仅提升单个环境的仿真速度，更重要的是支持大规模并行训练。本节探讨碰撞检测在RL训练中的特殊考虑。
强化学习训练环境具有独特的碰撞检测需求：
环境级并行：
每个环境维护独立的碰撞检测状态：
class ParallelCollisionWorld:
def __init__(self, num_envs):
self.broad_phases = [BroadPhase() for _ in range(num_envs)]
self.contact_caches = [ContactCache() for _ in range(num_envs)]
def step(self, env_id):
# 独立处理每个环境，无需同步
pairs = self.broad_phases[env_id].find_pairs()
contacts = narrow_phase(pairs)
self.contact_caches[env_id].update(contacts)
GPU批处理：
将多个环境的碰撞检测合并为单个GPU kernel：
__global__ void batch_gjk_kernel(
ConvexShape* shapes, // [num_envs, max_objects, ...]
Transform* transforms, // [num_envs, max_objects, ...]
Contact* contacts // [num_envs, max_contacts, ...]
) {
int env_id = blockIdx.x;
int pair_id = threadIdx.x;
// 每个线程处理一个碰撞对
gjk_test(shapes[env_id], transforms[env_id],
pair_id, contacts[env_id]);
}
连续帧之间的接触通常具有时间相关性。接触缓存可显著加速窄相检测：
接触缓存策略：
RL特殊考虑：
训练时使用简化碰撞体，部署时使用精确几何：
简化策略：
Sim-to-Real考虑：
class CollisionGeometry:
def __init__(self):
self.training_shape = SimplifiedConvexHull()
self.deployment_shape = DetailedMesh()
self.shape_noise = Normal(0, 0.02) # 域随机化
def get_shape(self, mode='train'):
if mode == 'train':
# 训练时添加随机扰动补偿简化误差
return self.training_shape.perturb(self.shape_noise)
else:
return self.deployment_shape
关键性能指标：
性能剖析示例（1000个并行环境，每环境20个物体）：
| 组件 | CPU时间(ms) | GPU时间(ms) | 占比 |
|---|---|---|---|
| 宽相检测 | 2.3 | 0.8 | 15% |
| 窄相检测 | 5.1 | 1.2 | 35% |
| 接触求解 | 4.8 | 1.5 | 32% |
| 数据传输 | - | 0.6 | 8% |
| 其他 | 1.2 | 0.4 | 10% |
可微分仿真需要碰撞检测的梯度：
光滑接触模型：
将硬接触替换为光滑势能： \(\phi(d) = \begin{cases} \frac{k}{2}d^2 & d < 0 \text{（穿透）} \\ 0 & d \geq 0 \text{（分离）} \end{cases}\)
梯度： \(\nabla_{\mathbf{x}} \phi = k \cdot d \cdot \nabla_{\mathbf{x}} d\)
其中$\nabla_{\mathbf{x}} d$是距离函数的梯度，可从GJK的最近点计算。
梯度截断：
防止梯度爆炸： \(\tilde{\nabla} = \text{clip}(\nabla, -g_{max}, g_{max})\)
Elmer G. Gilbert，密歇根大学航空航天工程系教授，与他的同事Daniel W. Johnson和S. Sathiya Keerthi在1988年发表了划时代的论文”A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space”，提出了后来被称为GJK的算法。这个算法的诞生不仅是计算几何的里程碑，更体现了跨学科研究的力量。
1980年代，机器人路径规划和计算机图形学的快速发展对碰撞检测提出了迫切需求。当时的方法要么只适用于特定形状（如球体），要么计算复杂度过高。Gilbert的团队原本在研究控制系统的可达集计算，意外发现其中的凸优化技术可以应用于距离计算。
GJK算法的革命性在于三个关键洞察：
Gilbert回忆道：”最困难的部分不是算法本身，而是证明它在所有退化情况下都能正确工作。我们花了近一年时间处理各种特殊情况。”
原始GJK算法主要用于计算凸体间的最小距离。后续研究者的贡献包括：
GJK算法被广泛应用于：
Gilbert强调理论与实践的结合：”一个好的算法必须在数学上优雅，在工程上实用。GJK的成功在于它同时满足了这两个标准。”他的研究方法论影响了一代计算几何研究者：
符号距离场（Signed Distance Field, SDF）提供了一种统一处理凸体和非凸体碰撞的优雅方法。通过将几何体表示为空间中每点到表面最近距离的标量场，SDF不仅简化了碰撞检测，还自然支持形状混合、变形和可微分计算。
给定闭合表面$\mathcal{S}$，其符号距离函数定义为：
\[\phi(\mathbf{x}) = \begin{cases} -\min_{\mathbf{y} \in \mathcal{S}} \|\mathbf{x} - \mathbf{y}\| & \mathbf{x} \text{ 在内部} \\ 0 & \mathbf{x} \in \mathcal{S} \\ \min_{\mathbf{y} \in \mathcal{S}} \|\mathbf{x} - \mathbf{y}\| & \mathbf{x} \text{ 在外部} \end{cases}\]SDF的关键性质：
解析SDF：
基本形状的解析表达式：
| 盒：$\phi(\mathbf{x}) = |\max(\mathbf{0}, | \mathbf{x} | - \mathbf{b})|$ |
离散SDF：
复杂形状通过体素网格存储：
class SDFGrid:
def __init__(self, resolution, bounds):
self.grid = np.zeros((resolution,)*3)
self.voxel_size = (bounds[1] - bounds[0]) / resolution
def sample(self, pos):
# 三线性插值
idx = (pos - self.bounds[0]) / self.voxel_size
return trilinear_interpolate(self.grid, idx)
神经SDF：
使用神经网络隐式表示： \(\phi(\mathbf{x}) = f_\theta(\gamma(\mathbf{x}))\)
其中$\gamma$是位置编码，$f_\theta$是MLP网络。
点与SDF碰撞：
直接评估：碰撞当且仅当$\phi(\mathbf{p}) \leq 0$
球与SDF碰撞：
球心$\mathbf{c}$，半径$r$的球与SDF碰撞： \(\phi(\mathbf{c}) \leq r\)
穿透深度：$d = r - \phi(\mathbf{c})$
SDF间碰撞：
两个SDF $\phi_A$和$\phi_B$的碰撞检测通过梯度下降寻找： \(\min_{\mathbf{x}} [\phi_A(\mathbf{x}) + \phi_B(\mathbf{x})]\)
若最小值小于0，则发生碰撞。
SDF自然支持CSG（Constructive Solid Geometry）运算：
光滑版本（避免导数不连续）： \(\phi_{smooth} = -\frac{1}{k}\log(e^{-k\phi_A} + e^{-k\phi_B})\)
SDF特别适合处理变形体的碰撞：
动态SDF更新：
变形时的SDF更新策略：
接触力计算：
基于SDF的罚函数： \(\mathbf{f} = \begin{cases} -k_n \phi \nabla\phi - k_d \mathbf{v}_n & \phi < 0 \\ \mathbf{0} & \phi \geq 0 \end{cases}\)
解析梯度：
对于解析SDF，梯度可直接计算。对于离散SDF： \(\nabla\phi \approx \frac{1}{2h}[\phi(x+h) - \phi(x-h), ...]\)
自动微分：
现代框架（JAX、PyTorch）支持SDF操作的自动微分：
def sdf_loss(params, points, targets):
pred = neural_sdf(params, points)
return jnp.mean((pred - targets)**2)
grad_fn = jax.grad(sdf_loss)
优化应用：
本章深入探讨了碰撞检测的核心算法和实现技术。我们从两阶段检测策略开始，理解了宽相筛选和窄相精确检测的分工。GJK算法展示了如何通过闵可夫斯基差的几何洞察优雅地解决凸体碰撞问题，而EPA算法则提供了精确的穿透信息。连续碰撞检测解决了高速运动的隧穿问题，空间数据结构的选择直接影响了大规模场景的性能。
宽相检测：使用AABB、扫描线或空间哈希快速筛选候选碰撞对，将$O(n^2)$复杂度降至$O(n\log n)$或更低
| 概念 | 公式 | 说明 |
|---|---|---|
| AABB重叠 | $\max(a_{min}, b_{min}) \leq \min(a_{max}, b_{max})$ | 各轴独立检测 |
| 闵可夫斯基差 | $A \ominus B = {a - b | a \in A, b \in B}$ | 碰撞检测的几何基础 |
| 支撑函数 | $s_A(\mathbf{d}) = \arg\max_{\mathbf{p} \in A} \mathbf{d} \cdot \mathbf{p}$ | GJK的核心操作 |
| SDF定义 | $\phi(\mathbf{x}) = \pm \min_{\mathbf{y} \in \mathcal{S}} |\mathbf{x} - \mathbf{y}|$ | 隐式几何表示 |
| CCD条件 | $\exists t \in [0,1]: A(t) \cap B(t) \neq \emptyset$ | 连续碰撞的数学表述 |
在实际应用中，碰撞检测的性能优化需要考虑：
实现一个2D版本的GJK算法，用于检测两个凸多边形是否相交。要求处理退化情况（如共线点）。
提示：先实现支撑函数，然后实现单纯形更新逻辑。注意处理数值精度问题。
给定1000个运动的AABB，设计一个增量更新的扫描线算法。分析最坏情况和平均情况的时间复杂度。
提示：考虑如何维护有序性，以及如何处理跨越多个其他物体的大幅移动。
推导线性运动物体的CCD中，数值误差对碰撞时间计算的影响。给出保证数值稳定的实现建议。
提示：分析浮点运算中的舍入误差传播，特别是在接近平行运动的情况。
证明Surface Area Heuristic（SAH）在某些假设下是最优的划分策略。设计一个快速近似SAH的方法。
提示：考虑射线遍历的期望代价模型。
推导胶囊体（Capsule）的SDF及其梯度的解析表达式。讨论梯度在不同区域的连续性。
提示：胶囊体可视为线段沿法向膨胀得到。
设计一个GPU上的并行碰撞检测算法，处理不均匀的碰撞对分布。分析负载均衡策略。
提示：考虑工作窃取和动态任务分配。
分析接触缓存的命中率与物体运动速度、时间步长的关系。推导最优缓存大小。
提示：建立接触持续时间的概率模型。
设计一个自适应选择不同碰撞检测算法的系统。考虑几何复杂度、运动模式和精度需求。
提示：定义选择准则和切换条件。
陷阱：当两个物体几乎接触时，GJK可能因数值误差而无法收敛。
症状：
解决方案：
// 使用相对容差而非绝对容差
float tolerance = max(EPSILON_ABS, EPSILON_REL * object_scale);
// 检测振荡
if(simplex == previous_simplex) {
// 强制终止，返回近似结果
return approximate_distance;
}
// 限制最大迭代次数
if(iteration > MAX_ITER) {
// 回退到更稳定但较慢的算法
return fallback_algorithm();
}
陷阱：使用固定的时间步进行CCD可能错过碰撞。
症状：
正确做法：
// 错误：固定步长
for(float t = 0; t < 1; t += 0.1) {
check_collision(t);
}
// 正确：自适应步长
float t = 0;
while(t < 1) {
float dt = compute_safe_step(velocity, separation);
t = min(t + dt, 1.0);
if(check_collision(t)) {
// 二分查找精确时刻
binary_search_collision_time(t - dt, t);
}
}
陷阱：延迟更新空间数据结构导致错误的碰撞检测结果。
症状：
最佳实践：
陷阱：直接比较浮点数导致的逻辑错误。
错误示例：
// 错误
if(distance == 0) { // 几乎永远不会为真
handle_contact();
}
// 正确
if(abs(distance) < EPSILON) {
handle_contact();
}
陷阱：在局部坐标系和世界坐标系之间转换时出错。
常见错误：
调试技巧：
// 添加断言检查坐标系一致性
assert(is_normalized(normal_world));
assert(is_in_world_space(contact_point));
// 可视化调试
debug_draw_arrow(contact_point, normal_world, Color::RED);
陷阱：多线程碰撞检测中的数据竞争。
症状：
解决方案：
陷阱：接触缓存在特定情况下提供错误信息。
触发条件：
缓解措施：
class ContactCache {
void validate() {
// 检查缓存有效性
if(teleported || parameters_changed) {
clear();
return;
}
// 验证接触点仍然有效
for(auto& contact : cached_contacts) {
if(separation(contact) > CACHE_TOLERANCE) {
remove(contact);
}
}
}
};
陷阱：离散SDF的分辨率不足导致碰撞检测错误。
症状：
解决方案：