C++ 碰撞检测是物理引擎的核心模块。通过引入空间分割与层次化包围体技术可显著降低无效检测次数。文章对比了 AABB、OBB 及 GJK 算法的精度与开销，阐述了分离轴定理与连续碰撞检测避免隧道效应的方法。讨论了多线程任务队列与 SIMD 指令集并行化处理策略，并结合工业案例说明刚体动力学与内存布局优化对性能的影响。
在高性能物理引擎开发中，碰撞检测是决定整体效率的核心模块。传统暴力检测算法的时间复杂度高达 O(n²)，面对大规模动态物体场景时极易成为性能瓶颈。通过引入空间分割与层次化包围体技术，可显著降低无效检测次数，实现接近 O(n log n) 的运行效率。
四叉树将空间递归划分为四个象限，仅对同一节点内的物体进行碰撞判断，大幅减少比较次数。以下是一个简化的四叉树插入逻辑示例：
// 插入物体到四叉树节点
{
(!->boundary.(collider->())) {
;
}
(children.() < MAX_CAPACITY && ->()) {
nodes.(collider);
;
}
(->()) {
();
}
(& child : children) {
child->(collider);
}
;
}
不同包围体在精度与计算开销之间存在权衡，常见类型对比如下：
| 包围体类型 | 计算开销 | 包裹精度 | 适用场景 |
|---|---|---|---|
| AABB | 低 | 中 | 静态或轴对齐物体 |
| OBB | 高 | 高 | 旋转频繁的复杂模型 |
| 圆形/球体 | 极低 | 低 | 快速粗筛阶段 |
在游戏物理和计算机图形学中，碰撞检测依赖于精确的数学模型。核心在于利用向量运算与几何体的数学表达式进行相交判断。
向量用于表示位置、速度和方向。两个物体是否相交，常通过计算其边界体（如 AABB、球体）的向量距离来判定。
以轴对齐包围盒（AABB）为例，其相交判定可通过比较各维度区间重叠实现：
bool aabbIntersect(const AABB& a, const AABB& b) {
return (a.min.x <= b.max.x && a.max.x >= b.min.x) &&
(a.min.y <= b.max.y && a.max.y >= b.min.y) &&
(a.min.z <= b.max.z && a.max.z >= b.min.z);
}
该函数通过逐维比较最小最大值，判断两个 AABB 是否存在空间重叠。逻辑简洁高效，适用于大规模场景的粗检测阶段。参数 min 和 max 表示包围盒在世界坐标系下的顶点边界。
在实时物理模拟与游戏开发中，碰撞检测是保障交互真实性的核心环节。不同场景对精度与性能的要求各异，促使多种算法并存发展。
AABB 通过最小/最大顶点定义立方体，检测逻辑简洁高效：
bool intersectAABB(const AABB& a, const AABB& b) {
return (a.min.x <= b.max.x && a.max.x >= b.min.x) &&
(a.min.y <= b.max.y && a.max.y >= b.min.y) &&
(a.min.z <= b.max.z && a.max.z >= b.min.z);
}
该方法仅需 6 次比较，适合大规模粗筛，但无法适应旋转物体。
OBB 支持任意方向包围盒，虽提升精度，但相交判断需分离轴定理（SAT），计算成本显著增加。GJK 算法则通过迭代生成闵可夫斯基差集，适用于凸体间精确距离与穿透深度计算，广泛用于高保真物理引擎。
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| AABB | O(1) | 粗检测、静态场景 |
| OBB | O(n) | 动态旋转物体 |
| GJK | O(log n) | 高精度物理模拟 |
在实现分离轴定理（SAT）时，关键在于减少冗余投影计算。通过预计算多边形的边法线并缓存结果，可显著提升性能。仅需遍历两凸多边形的所有边，生成潜在分离轴。
struct Vec2 {
float x, y;
Vec2 operator-() const { return {-x, -y}; }
float dot(const Vec2& b) const { return x * b.x + y * b.y; }
};
bool projectAndCheckSeparation(
const std::vector<Vec2>& poly,
const Vec2& axis,
float& min,
float& max)
{
min = max = poly[0].dot(axis);
for (const auto& v : poly) {
float proj = v.dot(axis);
min = std::fmin(min, proj);
max = std::fmax(max, proj);
}
return false; // 仅投影，不判断
}
上述代码实现了沿指定轴的投影计算。参数 poly 为顶点数组，axis 为归一化后的分离候选轴，输出该多边形在此轴上的投影区间 [min, max]。
在高速运动物体的物理模拟中，离散时间步长可能导致'隧道效应'，即物体在帧间穿越障碍物而未被检测到碰撞。连续碰撞检测（Continuous Collision Detection, CCD）通过插值运动轨迹，在时间维度上进行扫描，有效解决该问题。
CCD 通过计算物体在两帧之间的运动胶囊（Swept Volume）来预测潜在碰撞点。相较于离散检测仅检查起始与结束位置，CCD 沿运动路径进行连续性求交。
bool SweepSphere(const Vector3& start, const Vector3& end, float radius, const Plane& wall, float& outTime) {
float distStart = Dot(start, wall.normal) - wall.distance;
float distEnd = Dot(end, wall.normal) - wall.distance;
if (distStart < radius && distEnd < radius) return false; // 始终在内部
if (distStart >= radius && distEnd >= radius) return false; // 未穿透
float sweepDist = Dot(end - start, wall.normal);
outTime = (radius - distStart) / sweepDist;
return outTime >= 0 && outTime <= 1;
}
上述代码判断球体沿线段移动时是否与平面发生碰撞。通过比较起始和结束距离与半径的关系，并利用点积计算穿透时间（outTime），实现精确的碰撞时机预测。
在分离轴定理（SAT）检测到碰撞后，需计算最小位移向量（MTV），用于将两物体沿最短路径分离。MTV 包含方向和大小，直接影响物理响应的真实感。
通过缓存投影轴和提前终止机制减少冗余计算：
// 计算最小穿透深度与对应法向
Vector2 ComputeMTV(const std::vector<float>& axes, const Shape& a, const Shape& b) {
float minOverlap = FLT_MAX;
Vector2 mtvAxis;
for (const auto& axis : axes) {
float overlap = CalculateProjectionOverlap(axis, a, b);
if (overlap < minOverlap) {
minOverlap = overlap;
mtvAxis = axis;
}
}
return mtvAxis * minOverlap; // 返回 MTV 向量
}
上述代码中，axes 为候选分离轴集合，CalculateProjectionOverlap 计算沿某轴的投影重叠量。选择最小正值重叠作为 MTV 大小，对应轴为方向。
| 方法 | 平均耗时 (μs) | 精度 |
|---|---|---|
| 朴素 SAT | 12.4 | 高 |
| 带缓存 MTV | 7.1 | 高 |
在动态三维场景重建中，网格哈希技术通过将空间划分为固定大小的体素网格，并利用哈希函数映射存储稀疏有效数据，显著提升内存效率与访问速度。
每个哈希桶管理一个体素块，仅存储被占用的块，避免全分辨率网格的内存浪费。典型实现如下：
struct VoxelBlock {
float sdf[8][8][8]; // 符号距离值
float weight[8][8][8];
};
该结构以局部 8³ 体素块为单位组织数据，配合全局哈希表实现动态加载与剔除，适应相机实时移动产生的新区域。
| 方法 | 内存占用 | 查询延迟 |
|---|---|---|
| 稠密网格 | 高 | 低 |
| 八叉树 | 中 | 可变 |
| 网格哈希 | 低 | 稳定 |
得益于固定尺寸块与哈希映射，网格哈希在动态更新场景中表现出更优的时空平衡性。
在空间索引结构中，四叉树（Quadtree）和八叉树（Octree）的性能高度依赖于内存布局与节点插入策略。合理的内存分配方式可显著减少缓存未命中。
采用数组式存储替代指针链表，将子节点连续存放，提升空间局部性：
struct OctreeNode {
bool is_leaf;
float bounds[6]; // xmin, xmax, ymin, ymax, zmin, zmax
union {
Object* objects;
OctreeNode* children; // 指向 8 个子节点起始地址
};
};
该布局使子节点在内存中连续排列，配合预取机制可加速遍历。
为避免频繁树重构，引入批量插入缓冲区，当节点对象数超过阈值时才触发分裂，降低动态更新开销。
在实时渲染与物理仿真中，动态 BVH 用于高效管理移动物体的碰撞检测。相较于静态 BVH，其核心挑战在于如何在对象持续运动时维持树结构的紧凑性与查询效率。
采用惰性更新机制，仅当物体位移超过预设阈值时标记对应节点需重构。该策略显著降低频繁重建开销。
// BVH 节点更新伪代码
void updateNode(BVHNode* node, const Transform& newTransform) {
if (node->isLeaf()) {
BoundingBox newBox = computeTransformedBounds(node->object, newTransform);
if (!node->aabb.contains(newBox)) {
markForRebuild(node);
}
}
}
上述逻辑通过比较变换后的包围盒与原 AABB 的空间包含关系，决定是否触发局部重建，确保边界一致性。
| 策略 | 更新延迟 | 查询效率 |
|---|---|---|
| 全局重建 | 高 | 低 |
| 增量更新 | 低 | 高 |
在高并发场景下，窄相检测（Narrow Phase Collision Detection）需高效处理大量物体间的精确碰撞判断。为提升性能，采用基于任务队列的多线程架构，将检测任务解耦并分发至线程池。
主线索引潜在碰撞对后，将其封装为任务提交至无锁队列。工作线程循环从队列中取出任务并执行计算：
struct CollisionTask {
Object* a, * b;
bool operator()() const { return detect(a, b); }
};
ConcurrentQueue<CollisionTask> taskQueue;
该设计避免了线程频繁创建销毁的开销，同时通过任务队列实现负载均衡。
在物理仿真系统中，碰撞检测是计算密集型任务。利用 SIMD（单指令多数据）指令集可显著提升批量处理效率，通过一条指令同时对多个物体的包围盒进行距离计算。
为充分发挥 SIMD 性能，需将物体位置与包围盒参数按 AOSOA（Array of Structure of Arrays）方式存储，使同类数据连续排列，便于向量化加载。
// 使用 Intel SSE 指令计算 4 组 AABB 间距
__m128 minA = _mm_load_ps(&aabb_min_x[i]);
__m128 maxA = _mm_load_ps(&aabb_max_x[i]);
__m128 minB = _mm_load_ps(&other_min_x[i]);
__m128 maxB = _mm_load_ps(&other_max_x[i]);
// 并行判断是否无重叠：maxA < minB || maxB < minA
__m128 no_overlap1 = _mm_cmplt_ps(maxA, minB);
__m128 no_overlap2 = _mm_cmplt_ps(maxB, minA);
__m128 disjoint = _mm_or_ps(no_overlap1, no_overlap2);
上述代码利用 SSE 一次性处理 4 对 X 轴边界，_mm_cmplt_ps 执行并行浮点比较，最终 disjoint 寄存器包含每对对象是否分离的掩码结果，极大减少了循环开销。
现代 CPU 访问内存以缓存行为单位（通常为 64 字节）。若结构体成员未合理排列，可能导致跨缓存行访问，增加内存延迟。编译器默认按字段类型对齐，但可能引入填充字节，影响空间利用率。
struct BadStruct {
bool a; // 1 字节
int64_t b; // 8 字节 —— 此处有 7 字节填充
int32_t c; // 4 字节
// 总大小：24 字节（含填充）
};
struct GoodStruct {
int64_t b; // 8 字节
int32_t c; // 4 字节
bool a; // 1 字节
// 填充 3 字节，总大小 16 字节
};
通过将大字段前置并按大小降序排列，GoodStruct 减少 8 字节内存占用，提升缓存命中率。
| 场景 | 缓存效率 | 说明 |
|---|---|---|
| 多核并发修改同缓存行变量 | 低 | 引发频繁缓存同步 |
| 变量隔离至独立缓存行 | 高 | 使用 align 或填充避免干扰 |
在并行计算中，多核或异构处理器频繁访问共享内存，极易引发内存带宽瓶颈。当计算单元的处理速度远超数据供给能力时，系统陷入'算力闲置、等待数据'的状态。
不合理的数据布局会加剧带宽压力。例如，频繁的随机访问导致缓存命中率下降，增加主存请求次数。
采用数据分块（tiling）技术可提升局部性。以下为矩阵乘法中的分块代码片段：
for (int ii = 0; ii < N; ii += BLOCK) {
for (int jj = 0; jj < N; jj += BLOCK) {
for (int kk = 0; kk < N; kk += BLOCK) {
// 在缓存友好的小块内计算
for (int i = ii; i < ii + BLOCK && i < N; i++) {
for (int j = jj; j < jj + BLOCK && j < N; j++) {
for (int k = kk; k < kk + BLOCK && k < N; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
}
}
该代码通过限制每次操作的数据集大小，使中间结果尽可能驻留在高速缓存中，显著降低对主存带宽的依赖。BLOCK 大小需根据缓存容量调整，通常为 16~64。
在构建工业级物理引擎时，刚体动力学是核心模块之一。以下是一个简化的速度更新代码片段，展示了如何在时间步进中应用外力与角动量：
void RigidBody::integrate(float dt) {
// 应用重力（假设为全局力）
force += mass * gravity;
// 线速度更新
velocity += (force / mass) * dt;
// 角加速度计算
angularVelocity += inverseInertiaTensor * torque * dt;
// 位置与朝向积分（使用欧拉法）
position += velocity * dt;
orientation = orientation + (angularVelocity * orientation) * (dt * 0.5f);
// 清除累积力和力矩
force = Vector3(0, 0, 0);
torque = Vector3(0, 0, 0);
}
大规模场景中，暴力检测所有物体对效率极低。常用空间划分结构提升性能：
某自动驾驶公司在其仿真系统中集成定制化物理引擎，用于高保真车辆动力学模拟。通过引入轮胎摩擦模型（如 Pacejka 模型）与悬挂系统微分方程，实现了±2cm 的轨迹预测精度。
| 参数 | 值 | 单位 |
|---|---|---|
| 时间步长 | 0.001 | s |
| 平均碰撞响应延迟 | 8.7 | μs |
| 最大同步物体数 | 10,000 | entities |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online