尧图网页设计 
1. 项目概述为什么我们要亲手造轮子如果你正在用C开发游戏、物理模拟器或者任何需要处理物体交互的图形应用那么“碰撞检测”这个词对你来说一定不陌生。市面上有成熟的物理引擎比如Bullet、Box2DUnity和Unreal Engine也内置了强大的碰撞系统。既然如此我们为什么还要“从零开始”实现一个C碰撞检测系统这听起来像是一个费力不讨好的“造轮子”行为。但恰恰是这个过程能让你真正掌握那些被封装在引擎黑盒里的底层原理。当你调用Physics.Raycast或者AddForce时你知道引擎背后是如何判断两个复杂模型是否相交的吗你知道为了优化性能成千上万的物体是如何被高效组织起来避免进行O(n²)次两两检测的吗亲手实现一遍你得到的将不仅仅是“会用”一个API而是深刻理解其设计哲学、性能瓶颈和优化边界。这对于解决那些引擎无法直接处理的怪异Bug、进行深度的性能调优甚至是设计全新的交互逻辑都是至关重要的底层能力。这篇文章就是带你走过这段“知其然更知其所以然”的旅程从最基础的数学概念开始一步步构建一个具备实用价值的碰撞检测框架。2. 碰撞检测系统的核心架构设计一个完整的碰撞检测系统远不止一个bool CheckCollision(A, B)函数。它需要一套清晰的架构来管理场景中所有的碰撞体Collider并高效地处理它们之间的交互。一个典型的自研系统可以分为以下几个核心层次。2.1 数据层碰撞体的抽象与表示首先我们需要定义什么是“可碰撞的物体”。在底层一个碰撞体通常由两部分组成几何形状Shape和变换信息Transform。几何形状定义了物体的“固有形态”。我们从一个最简单的AABB轴对齐包围盒开始。它本质上是一个长方体但其边与坐标轴平行这使得它的相交检测极其高效——只需比较最大最小坐标。我们用一个结构体来表示struct AABB { glm::vec3 min; // 最小顶点坐标 (x_min, y_min, z_min) glm::vec3 max; // 最大顶点坐标 (x_max, y_max, z_max) // 根据一个点集比如模型的顶点计算AABB void Fit(const std::vectorglm::vec3 points) { min max points[0]; for (const auto point : points) { min glm::min(min, point); max glm::max(max, point); } } // 判断两个AABB是否相交 bool Intersects(const AABB other) const { return (max.x other.min.x min.x other.max.x) (max.y other.min.y min.y other.max.y) (max.z other.min.z min.z other.max.z); } };注意glm::vec3来自GLM数学库它是一个在图形学中广泛使用的头文件库。如果你不想引入外部依赖也可以自己实现一个简单的三维向量类包含x, y, z和基本的加减、比较操作。然而AABB是轴对齐的一旦物体旋转它的AABB就会变得非常“臃肿”包含大量空白区域导致检测精度下降。这时我们就需要引入OBB有向包围盒。OBB也是一个长方体但它的方向是任意的需要用一个变换矩阵包含旋转、缩放来定义。它的相交检测涉及分离轴定理SAT比AABB复杂得多但精度更高。更复杂的形状还有球体Sphere、胶囊体Capsule、凸包Convex Hull甚至三角形网格Triangle Mesh。一个健壮的系统需要设计一个基类CollisionShape然后派生出各种具体形状。这里就涉及到一个关键设计选择是用继承还是用组件如std::variant继承方案设计一个Shape基类包含虚函数如GetType()、GetAABB(const Transform)、TestIntersection(const Shape, ...)。优点是扩展性强符合传统OOP思想。缺点是虚函数调用有开销且需要处理复杂的双分派Double Dispatch问题来判断两个未知具体类型的形状是否相交。组件/标签方案使用std::variantAABB, Sphere, OBB, ...来存储形状。通过std::visit来访问具体类型。优点是内存布局紧凑能利用现代C的编译期多态性能可能更好。缺点是类型列表需要预先确定扩展稍显繁琐。对于学习目的我建议从继承开始因为它概念更清晰。我们可以这样设计enum class ShapeType { AABB, Sphere, OBB /*, ...*/ }; class CollisionShape { public: virtual ~CollisionShape() default; virtual ShapeType GetType() const 0; // 获取该形状在当前变换下的AABB用于空间划分的粗略检测 virtual AABB GetAABB(const Transform transform) const 0; }; class SphereShape : public CollisionShape { public: float radius; // ... 实现虚函数 }; class BoxShape : public CollisionShape { // 可以是AABB或OBB public: glm::vec3 halfExtents; // 从中心到各面的距离 // 对于OBB还需要一个旋转矩阵 // ... 实现虚函数 };2.2 逻辑层碰撞对生成与粗检测Broad Phase当场景中有N个物体时进行两两精细检测Narrow Phase的复杂度是O(N²)这在N很大时比如超过1000是完全不可接受的。粗检测Broad Phase的目标就是快速剔除那些明显不可能相交的物体对将需要精细检测的候选对数量减少到O(N)或O(N log N)级别。最经典的粗检测算法是基于空间划分Spatial Partitioning。我们这里重点实现一个简单高效的动态AABB树Dynamic Bounding Volume Hierarchy, Dynamic BVH。它的思想是为每个碰撞体计算一个包围盒通常是AABB因为它计算快然后将这些包围盒组织成一棵二叉树。树的每个节点都存储一个能包围其所有子节点AABB的更大的AABB。当需要检测碰撞时我们从根节点开始递归如果当前节点是叶子节点存储了一个碰撞体则将其加入待检测列表。如果当前节点是内部节点则检查查询的AABB是否与该节点的AABB相交。不相交该节点下的所有物体都不可能相交整棵子树被剔除。相交递归检查它的两个子节点。这样我们只需要检查与查询AABB相交的那些叶子节点。对于两两检测我们可以通过遍历树来生成所有可能相交的叶子节点对。动态BVH的难点在于更新。物体移动后其AABB发生变化需要更新它在树中的位置。一个简单策略是先删除该叶子节点然后用新的AABB重新插入。为了保持树的平衡避免退化成链表在插入和删除时需要一些旋转或重构策略。实操心得在项目初期不必追求完美的动态BVH。可以先实现一个简单的基于网格Grid的划分将世界空间划分为均匀的单元格每个物体根据其AABB所在的单元格注册进去。检测时只检查与物体所在单元格相邻的单元格内的物体。这种方法实现简单对于物体均匀分布的场景效果不错是快速验证想法的好工具。2.3 逻辑层精细检测Narrow Phase与碰撞信息粗检测给我们提供了一个“可能碰撞”的物体对列表。接下来精细检测Narrow Phase就要对这些候选对进行精确的几何相交测试并计算出详细的碰撞信息。碰撞信息ContactManifold通常包括碰撞点Contact Point一个或多个物体表面的接触点。碰撞法线Contact Normal垂直于接触面的方向通常从物体A指向物体B用于计算反弹。穿透深度Penetration Depth物体相互嵌入的深度用于将物体推开解决穿透。不同的形状组合需要不同的检测算法球体 vs 球体最简单。计算圆心距离与半径和比较。碰撞点位于圆心连线上法线即连线方向。AABB vs AABB如前所述比较坐标即可。但计算碰撞信息特别是多个接触点稍复杂通常简化为找到最小穿透深度的面。OBB vs OBB或凸包 vs 凸包使用分离轴定理SAT。核心思想是如果能找到一条轴使得两个物体在该轴上的投影不重叠则它们不相交如果所有候选轴上的投影都重叠则它们相交。对于OBB候选轴就是两个盒子各自的三个面法向量以及它们边向量的叉积共15条轴。这是碰撞检测中的核心算法务必理解透彻。球体 vs AABB/OBB计算球心到盒子的最近点然后判断该点与球心的距离。胶囊体 vs 三角形网格更复杂通常用于角色控制器。需要用到射线与三角形的相交检测Möller–Trumbore算法以及点到线段、点到三角形的距离计算。实现时我们可以使用一个双分派Double Dispatch模式。定义一个CollisionDetector类里面包含一系列静态函数如DetectSphereSphere,DetectSphereBox,DetectBoxBox等。然后通过形状类型的组合来调用相应的函数。struct ContactPoint { glm::vec3 point; glm::vec3 normal; float depth; }; using ContactManifold std::vectorContactPoint; class CollisionDetector { public: static bool Detect(const SphereShape a, const Transform ta, const SphereShape b, const Transform tb, ContactManifold outManifold); static bool Detect(const SphereShape a, const Transform ta, const BoxShape b, const Transform tb, ContactManifold outManifold); static bool Detect(const BoxShape a, const Transform ta, const BoxShape b, const Transform tb, ContactManifold outManifold); // ... 更多组合 };3. 核心算法深度剖析与实现细节理解了架构我们来深入几个最核心算法的实现细节这是整个系统的灵魂所在。3.1 分离轴定理SAT在OBB碰撞中的实战SAT是处理凸体相交检测的利器。对于两个OBB的检测步骤如下准备数据每个OBB由中心c、三个互相垂直的单位方向向量u[0],u[1],u[2]即旋转矩阵的基向量以及在这三个方向上的半长e[0],e[1],e[2]定义。计算候选分离轴总共15条轴。A的3个面法线Au0, Au1, Au2。B的3个面法线Bu0, Bu1, Bu2。A的每个边方向与B的每个边方向的叉积3x39条即Au_i x Bu_j。注意叉积可能得到零向量需要忽略。对每条轴L进行投影测试计算两个OBB中心在该轴上的投影距离d | (cB - cA) · L |。计算两个OBB在该轴上的“投影半径”对于OBB A:rA eA0*|Au0·L| eA1*|Au1·L| eA2*|Au2·L|对于OBB B:rB eB0*|Bu0·L| eB1*|Bu1·L| eB2*|Bu2·L|如果d rA rB则在此轴上投影不重叠找到了分离轴立即返回“不相交”。如果所有15条轴都未能分离则两个OBB相交。实现时最大的性能优化点是提前退出。一旦找到一条分离轴检测立即结束。此外计算投影半径时点积的绝对值运算|Au_i·L|可以预先计算好一个3x3的旋转矩阵R其中R[i][j] Au_i · Bu_j这样在计算叉积轴上的投影时会方便一些。注意事项SAT只能告诉你是否相交。要获取碰撞信息法线、深度需要额外计算。通常我们选择穿透深度最小的那条轴作为碰撞法线方向。这条轴就是使(rA rB - d)值最大的那条轴且d不为0。深度就是该值。碰撞点的计算则更为复杂通常涉及寻找两个多面体的接触特征面-面、边-边、点-面等可以使用GJKGilbert–Johnson–Keerthi算法或EPAExpanding Polytope Algorithm来求取。对于刚入门可以先只实现相交检测碰撞信息用近似值如中心连线方向。3.2 动态AABB树的实现与优化实现一个可用的动态BVH我们需要定义树节点struct BVHNode { AABB aabb; // 该节点包围的AABB BVHNode* left nullptr; BVHNode* right nullptr; BVHNode* parent nullptr; Collider* collider nullptr; // 如果是叶子节点指向对应的碰撞体 int height 0; // 节点高度用于平衡 bool IsLeaf() const { return collider ! nullptr; } };核心操作包括插入Insert递归地将新节点的AABB与当前节点比较选择能使合并后AABB面积增量最小的子节点方向向下直到找到叶子节点将其替换为一个新的内部节点该内部节点有两个子节点原来的叶子节点和新插入的节点。然后需要向上更新父节点的AABB和高度。删除Remove将目标叶子节点从其父节点中移除。如果父节点现在只有一个子节点的父节点存在用这个子节点替代父节点。然后向上更新AABB和高度。更新Update如果物体的AABB移动后仍然被当前节点的AABB所包含则可以不用调整树结构只需更新叶子节点的AABB并向上更新父节点AABB。如果移动后超出了当前节点的AABB则执行一次Remove后接Insert。查询Query如前所述递归地进行AABB相交测试。平衡优化不平衡的树会严重降低查询效率。在插入或删除后我们可以像AVL树或红黑树那样进行旋转操作但基于AABB的旋转平衡条件不同。一个更简单实用的启发式方法是定期比如每帧或每N次更新后对整棵树进行完全重构。我们可以将所有叶子节点收集起来然后使用一种高效的方法如表面面积启发式SAH重新构建一棵平衡的树。虽然单次开销大但分摊到多帧后往往能获得更好的整体性能。3.3 碰撞响应与穿透解决浅析检测到碰撞后系统通常需要给出响应。这属于“物理引擎”的范畴但我们的碰撞检测系统需要为其提供准确的数据。最基本的响应是解决穿透Penetration Resolution也叫“推离”。假设我们得到了碰撞法线n和穿透深度d。最简单的解决方法是直接沿着法线方向将两个物体分开// 假设物体A是动态的物体B是静态的 transformA.position n * d;但这会产生抖动特别是当多个碰撞同时发生时。更稳定的方法是使用迭代求解或脉冲/约束求解器。例如可以存储一个“位置修正”向量在一帧内对所有碰撞进行多次迭代修正逐步消除穿透。更复杂的响应包括计算碰撞冲量Impulse改变物体的速度线性速度和角速度模拟摩擦和弹性。这需要物体的质量、惯性张量等物理属性。虽然超出了纯碰撞检测的范围但一个设计良好的碰撞检测系统应该能方便地与物理层对接输出足够的信息碰撞点、法线、相对速度等供物理层计算。4. 系统集成与性能优化实战有了核心组件我们需要将它们集成到一个可用的CollisionWorld或PhysicsScene中。4.1 主循环与对象管理class CollisionWorld { public: void AddCollider(Collider* collider); void RemoveCollider(Collider* collider); void Update(float deltaTime); // 更新所有动态碰撞体的变换并更新BVH // 执行一帧的碰撞检测返回所有碰撞对及其信息 std::vectorCollisionPair DetectCollisions(); private: std::vectorCollider* m_Colliders; BVHTree m_BVHTree; // 或 Grid 等空间划分结构 // ... 其他状态 }; void CollisionWorld::Update(float deltaTime) { for (auto collider : m_DynamicColliders) { collider-UpdateTransform(deltaTime); // 例如根据速度更新位置 m_BVHTree.Update(collider-GetNode()); // 更新BVH中该碰撞体的节点 } // 可选定期重构BVH以保持平衡 if (m_FrameCount % 60 0) { // 每60帧重构一次 m_BVHTree.Rebuild(); } } std::vectorCollisionPair CollisionWorld::DetectCollisions() { std::vectorCollisionPair results; // 1. Broad Phase: 使用BVH生成候选对 auto candidatePairs m_BVHTree.GeneratePairs(); // 2. Narrow Phase: 对每个候选对进行精细检测 for (auto pair : candidatePairs) { ContactManifold manifold; if (CollisionDetector::Detect( *pair.first-shape, pair.first-GetTransform(), *pair.second-shape, pair.second-GetTransform(), manifold)) { if (!manifold.empty()) { results.push_back({pair.first, pair.second, std::move(manifold)}); } } } return results; }4.2 性能剖析与关键优化点实现基本功能后必须进行性能剖析Profiling。在Debug模式下你的系统可能很慢这很正常。在Release模式下进行测试并关注以下几点内存布局与缓存友好Collider对象应尽量紧凑避免过多指针跳转。将频繁访问的数据如位置、AABB连续存储例如用std::vectorColliderData可以提高CPU缓存命中率。避免动态内存分配在DetectCollisions这样的每帧调用函数中避免使用new或std::vector::push_back导致频繁分配。使用对象池Object Pool或预分配内存的容器如std::vector::reserve。简化精细检测不是所有碰撞对都需要计算完整的ContactManifold。在游戏逻辑中有时只需要知道“是否碰撞”。可以提供一个快速的TestIntersection函数它可能在找到一条分离轴后就提前返回省去计算碰撞点的开销。分层检测Layer Masking为碰撞体设置层级Layer和遮罩Mask。只有层级与遮罩匹配的物体才会进行检测。这可以大量减少不必要的检测对。例如子弹不需要检测其他子弹背景装饰物不需要相互检测。时间相干性Temporal Coherence利用上一帧的检测结果。如果两个物体上一帧没有碰撞且它们在本帧移动不大那么它们在本帧碰撞的可能性也很低。可以在BVH更新或粗检测阶段利用这个信息进行优化。并行化碰撞检测是“令人尴尬的并行”问题。候选对之间的检测是相互独立的。可以使用多线程如C11的std::async或std::thread或SIMD指令来加速精细检测。例如使用SSE/AVX指令集同时进行多个标量点积运算。4.3 调试与可视化一个看不见的碰撞系统是难以调试的。必须实现可视化工具绘制包围盒在Debug渲染中用线框绘制每个碰撞体的AABB或OBB。用不同颜色表示静态/动态或者是否处于碰撞状态。绘制碰撞法线在碰撞点处绘制一条短线方向为碰撞法线长度与穿透深度相关。打印统计信息在屏幕上显示每帧处理的碰撞体总数、生成的候选对数量、实际发生的碰撞数量、检测耗时毫秒等。这是性能调优的黄金指标。单步调试与选择能够暂停游戏选择特定的碰撞体高亮显示它并打印其详细信息位置、大小、当前碰撞列表等。5. 常见陷阱、问题排查与进阶思考即使按照指南实现你也一定会遇到各种奇怪的问题。这里记录一些我踩过的坑和解决方案。5.1 浮点数精度误差与容差处理这是碰撞检测中最隐蔽的Bug来源。两个理论上刚好接触的物体由于浮点数计算误差可能被判定为“轻微穿透”或“微小分离”。症状物体在应该停下的地方轻微抖动或缓慢穿透。解决引入一个小的容差值Epsilon比如1e-6。在比较距离、深度时使用if (distance radiusSum EPSILON)而不是if (distance radiusSum)。在SAT算法中当投影距离d非常接近投影半径和rArB时可以认为它们刚好接触。注意容差值不能太大否则会错误地将明显分离的物体判定为碰撞。通常需要根据你的世界尺度来调整。5.2 高速物体穿透Tunneling当物体移动速度非常快时比如子弹它可能在一帧内从A点移动到B点完全穿过了另一个薄物体导致两帧的AABB都没有发生相交从而检测不到碰撞。症状高速运动的物体子弹、炮弹穿过了墙壁或敌人。解决连续碰撞检测CCD不检测物体在离散时间点的状态而是检测它们在一段时间内的运动轨迹是否相交。对于AABB可以计算其在本帧的“扫掠体”从上一帧AABB到本帧AABB的凸包然后与目标进行检测。计算量较大。子步长Sub-stepping将物理更新的时间步长deltaTime分成多个更小的子步长。在每个子步长内物体的位移变小穿透就不容易发生。这是最常用且相对简单的方法。扩大包围盒根据物体的最大速度适当扩大其包围盒比如在速度方向上加一个“厚度”但这会增加误报。5.3 复杂形状与凸分解我们的系统目前只处理了基本凸形状球、盒、胶囊。对于复杂的凹网格比如一个茶杯直接进行SAT或GJK检测是不行的因为算法只适用于凸体。解决将凹网格分解为多个凸体Convex Decomposition。有很多算法和工具可以做这件事如V-HACD库。然后一个复杂的碰撞体就由多个凸子碰撞体组成。检测时分别检测这些子碰撞体与目标的碰撞。只要有一个子碰撞体发生碰撞就认为整个物体发生了碰撞。代价碰撞体数量增加性能下降。需要权衡精度和性能。5.4 与渲染系统的同步碰撞体的变换位置、旋转需要与渲染模型的世界变换保持一致但更新时机可能不同。物理更新通常在固定时间步长进行而渲染是每帧一次。症状视觉上看到的模型和实际发生碰撞的边界对不上。最佳实践维护一个“渲染变换”和一个“物理变换”。物理系统在固定时间步长更新“物理变换”并检测碰撞。渲染时使用当前帧插值后的“渲染变换”介于上一物理状态和当前物理状态之间这样既能保证物理模拟的确定性又能实现平滑的视觉渲染。从零实现一个碰撞检测系统是一次深刻的修炼。它强迫你思考空间、几何、数据结构和性能的方方面面。当你看到自己编写的系统能让物体在屏幕上正确碰撞、反弹时那种成就感是使用现成引擎无法比拟的。更重要的是这份对底层的理解会让你在未来使用任何高级引擎时都具备一眼看穿问题本质的能力。 从零实现C++碰撞检测系统：架构、算法与性能优化
1. 项目概述为什么我们要亲手造轮子如果你正在用C开发游戏、物理模拟器或者任何需要处理物体交互的图形应用那么“碰撞检测”这个词对你来说一定不陌生。市面上有成熟的物理引擎比如Bullet、Box2DUnity和Unreal Engine也内置了强大的碰撞系统。既然如此我们为什么还要“从零开始”实现一个C碰撞检测系统这听起来像是一个费力不讨好的“造轮子”行为。但恰恰是这个过程能让你真正掌握那些被封装在引擎黑盒里的底层原理。当你调用Physics.Raycast或者AddForce时你知道引擎背后是如何判断两个复杂模型是否相交的吗你知道为了优化性能成千上万的物体是如何被高效组织起来避免进行O(n²)次两两检测的吗亲手实现一遍你得到的将不仅仅是“会用”一个API而是深刻理解其设计哲学、性能瓶颈和优化边界。这对于解决那些引擎无法直接处理的怪异Bug、进行深度的性能调优甚至是设计全新的交互逻辑都是至关重要的底层能力。这篇文章就是带你走过这段“知其然更知其所以然”的旅程从最基础的数学概念开始一步步构建一个具备实用价值的碰撞检测框架。2. 碰撞检测系统的核心架构设计一个完整的碰撞检测系统远不止一个bool CheckCollision(A, B)函数。它需要一套清晰的架构来管理场景中所有的碰撞体Collider并高效地处理它们之间的交互。一个典型的自研系统可以分为以下几个核心层次。2.1 数据层碰撞体的抽象与表示首先我们需要定义什么是“可碰撞的物体”。在底层一个碰撞体通常由两部分组成几何形状Shape和变换信息Transform。几何形状定义了物体的“固有形态”。我们从一个最简单的AABB轴对齐包围盒开始。它本质上是一个长方体但其边与坐标轴平行这使得它的相交检测极其高效——只需比较最大最小坐标。我们用一个结构体来表示struct AABB { glm::vec3 min; // 最小顶点坐标 (x_min, y_min, z_min) glm::vec3 max; // 最大顶点坐标 (x_max, y_max, z_max) // 根据一个点集比如模型的顶点计算AABB void Fit(const std::vectorglm::vec3 points) { min max points[0]; for (const auto point : points) { min glm::min(min, point); max glm::max(max, point); } } // 判断两个AABB是否相交 bool Intersects(const AABB other) const { return (max.x other.min.x min.x other.max.x) (max.y other.min.y min.y other.max.y) (max.z other.min.z min.z other.max.z); } };注意glm::vec3来自GLM数学库它是一个在图形学中广泛使用的头文件库。如果你不想引入外部依赖也可以自己实现一个简单的三维向量类包含x, y, z和基本的加减、比较操作。然而AABB是轴对齐的一旦物体旋转它的AABB就会变得非常“臃肿”包含大量空白区域导致检测精度下降。这时我们就需要引入OBB有向包围盒。OBB也是一个长方体但它的方向是任意的需要用一个变换矩阵包含旋转、缩放来定义。它的相交检测涉及分离轴定理SAT比AABB复杂得多但精度更高。更复杂的形状还有球体Sphere、胶囊体Capsule、凸包Convex Hull甚至三角形网格Triangle Mesh。一个健壮的系统需要设计一个基类CollisionShape然后派生出各种具体形状。这里就涉及到一个关键设计选择是用继承还是用组件如std::variant继承方案设计一个Shape基类包含虚函数如GetType()、GetAABB(const Transform)、TestIntersection(const Shape, ...)。优点是扩展性强符合传统OOP思想。缺点是虚函数调用有开销且需要处理复杂的双分派Double Dispatch问题来判断两个未知具体类型的形状是否相交。组件/标签方案使用std::variantAABB, Sphere, OBB, ...来存储形状。通过std::visit来访问具体类型。优点是内存布局紧凑能利用现代C的编译期多态性能可能更好。缺点是类型列表需要预先确定扩展稍显繁琐。对于学习目的我建议从继承开始因为它概念更清晰。我们可以这样设计enum class ShapeType { AABB, Sphere, OBB /*, ...*/ }; class CollisionShape { public: virtual ~CollisionShape() default; virtual ShapeType GetType() const 0; // 获取该形状在当前变换下的AABB用于空间划分的粗略检测 virtual AABB GetAABB(const Transform transform) const 0; }; class SphereShape : public CollisionShape { public: float radius; // ... 实现虚函数 }; class BoxShape : public CollisionShape { // 可以是AABB或OBB public: glm::vec3 halfExtents; // 从中心到各面的距离 // 对于OBB还需要一个旋转矩阵 // ... 实现虚函数 };2.2 逻辑层碰撞对生成与粗检测Broad Phase当场景中有N个物体时进行两两精细检测Narrow Phase的复杂度是O(N²)这在N很大时比如超过1000是完全不可接受的。粗检测Broad Phase的目标就是快速剔除那些明显不可能相交的物体对将需要精细检测的候选对数量减少到O(N)或O(N log N)级别。最经典的粗检测算法是基于空间划分Spatial Partitioning。我们这里重点实现一个简单高效的动态AABB树Dynamic Bounding Volume Hierarchy, Dynamic BVH。它的思想是为每个碰撞体计算一个包围盒通常是AABB因为它计算快然后将这些包围盒组织成一棵二叉树。树的每个节点都存储一个能包围其所有子节点AABB的更大的AABB。当需要检测碰撞时我们从根节点开始递归如果当前节点是叶子节点存储了一个碰撞体则将其加入待检测列表。如果当前节点是内部节点则检查查询的AABB是否与该节点的AABB相交。不相交该节点下的所有物体都不可能相交整棵子树被剔除。相交递归检查它的两个子节点。这样我们只需要检查与查询AABB相交的那些叶子节点。对于两两检测我们可以通过遍历树来生成所有可能相交的叶子节点对。动态BVH的难点在于更新。物体移动后其AABB发生变化需要更新它在树中的位置。一个简单策略是先删除该叶子节点然后用新的AABB重新插入。为了保持树的平衡避免退化成链表在插入和删除时需要一些旋转或重构策略。实操心得在项目初期不必追求完美的动态BVH。可以先实现一个简单的基于网格Grid的划分将世界空间划分为均匀的单元格每个物体根据其AABB所在的单元格注册进去。检测时只检查与物体所在单元格相邻的单元格内的物体。这种方法实现简单对于物体均匀分布的场景效果不错是快速验证想法的好工具。2.3 逻辑层精细检测Narrow Phase与碰撞信息粗检测给我们提供了一个“可能碰撞”的物体对列表。接下来精细检测Narrow Phase就要对这些候选对进行精确的几何相交测试并计算出详细的碰撞信息。碰撞信息ContactManifold通常包括碰撞点Contact Point一个或多个物体表面的接触点。碰撞法线Contact Normal垂直于接触面的方向通常从物体A指向物体B用于计算反弹。穿透深度Penetration Depth物体相互嵌入的深度用于将物体推开解决穿透。不同的形状组合需要不同的检测算法球体 vs 球体最简单。计算圆心距离与半径和比较。碰撞点位于圆心连线上法线即连线方向。AABB vs AABB如前所述比较坐标即可。但计算碰撞信息特别是多个接触点稍复杂通常简化为找到最小穿透深度的面。OBB vs OBB或凸包 vs 凸包使用分离轴定理SAT。核心思想是如果能找到一条轴使得两个物体在该轴上的投影不重叠则它们不相交如果所有候选轴上的投影都重叠则它们相交。对于OBB候选轴就是两个盒子各自的三个面法向量以及它们边向量的叉积共15条轴。这是碰撞检测中的核心算法务必理解透彻。球体 vs AABB/OBB计算球心到盒子的最近点然后判断该点与球心的距离。胶囊体 vs 三角形网格更复杂通常用于角色控制器。需要用到射线与三角形的相交检测Möller–Trumbore算法以及点到线段、点到三角形的距离计算。实现时我们可以使用一个双分派Double Dispatch模式。定义一个CollisionDetector类里面包含一系列静态函数如DetectSphereSphere,DetectSphereBox,DetectBoxBox等。然后通过形状类型的组合来调用相应的函数。struct ContactPoint { glm::vec3 point; glm::vec3 normal; float depth; }; using ContactManifold std::vectorContactPoint; class CollisionDetector { public: static bool Detect(const SphereShape a, const Transform ta, const SphereShape b, const Transform tb, ContactManifold outManifold); static bool Detect(const SphereShape a, const Transform ta, const BoxShape b, const Transform tb, ContactManifold outManifold); static bool Detect(const BoxShape a, const Transform ta, const BoxShape b, const Transform tb, ContactManifold outManifold); // ... 更多组合 };3. 核心算法深度剖析与实现细节理解了架构我们来深入几个最核心算法的实现细节这是整个系统的灵魂所在。3.1 分离轴定理SAT在OBB碰撞中的实战SAT是处理凸体相交检测的利器。对于两个OBB的检测步骤如下准备数据每个OBB由中心c、三个互相垂直的单位方向向量u[0],u[1],u[2]即旋转矩阵的基向量以及在这三个方向上的半长e[0],e[1],e[2]定义。计算候选分离轴总共15条轴。A的3个面法线Au0, Au1, Au2。B的3个面法线Bu0, Bu1, Bu2。A的每个边方向与B的每个边方向的叉积3x39条即Au_i x Bu_j。注意叉积可能得到零向量需要忽略。对每条轴L进行投影测试计算两个OBB中心在该轴上的投影距离d | (cB - cA) · L |。计算两个OBB在该轴上的“投影半径”对于OBB A:rA eA0*|Au0·L| eA1*|Au1·L| eA2*|Au2·L|对于OBB B:rB eB0*|Bu0·L| eB1*|Bu1·L| eB2*|Bu2·L|如果d rA rB则在此轴上投影不重叠找到了分离轴立即返回“不相交”。如果所有15条轴都未能分离则两个OBB相交。实现时最大的性能优化点是提前退出。一旦找到一条分离轴检测立即结束。此外计算投影半径时点积的绝对值运算|Au_i·L|可以预先计算好一个3x3的旋转矩阵R其中R[i][j] Au_i · Bu_j这样在计算叉积轴上的投影时会方便一些。注意事项SAT只能告诉你是否相交。要获取碰撞信息法线、深度需要额外计算。通常我们选择穿透深度最小的那条轴作为碰撞法线方向。这条轴就是使(rA rB - d)值最大的那条轴且d不为0。深度就是该值。碰撞点的计算则更为复杂通常涉及寻找两个多面体的接触特征面-面、边-边、点-面等可以使用GJKGilbert–Johnson–Keerthi算法或EPAExpanding Polytope Algorithm来求取。对于刚入门可以先只实现相交检测碰撞信息用近似值如中心连线方向。3.2 动态AABB树的实现与优化实现一个可用的动态BVH我们需要定义树节点struct BVHNode { AABB aabb; // 该节点包围的AABB BVHNode* left nullptr; BVHNode* right nullptr; BVHNode* parent nullptr; Collider* collider nullptr; // 如果是叶子节点指向对应的碰撞体 int height 0; // 节点高度用于平衡 bool IsLeaf() const { return collider ! nullptr; } };核心操作包括插入Insert递归地将新节点的AABB与当前节点比较选择能使合并后AABB面积增量最小的子节点方向向下直到找到叶子节点将其替换为一个新的内部节点该内部节点有两个子节点原来的叶子节点和新插入的节点。然后需要向上更新父节点的AABB和高度。删除Remove将目标叶子节点从其父节点中移除。如果父节点现在只有一个子节点的父节点存在用这个子节点替代父节点。然后向上更新AABB和高度。更新Update如果物体的AABB移动后仍然被当前节点的AABB所包含则可以不用调整树结构只需更新叶子节点的AABB并向上更新父节点AABB。如果移动后超出了当前节点的AABB则执行一次Remove后接Insert。查询Query如前所述递归地进行AABB相交测试。平衡优化不平衡的树会严重降低查询效率。在插入或删除后我们可以像AVL树或红黑树那样进行旋转操作但基于AABB的旋转平衡条件不同。一个更简单实用的启发式方法是定期比如每帧或每N次更新后对整棵树进行完全重构。我们可以将所有叶子节点收集起来然后使用一种高效的方法如表面面积启发式SAH重新构建一棵平衡的树。虽然单次开销大但分摊到多帧后往往能获得更好的整体性能。3.3 碰撞响应与穿透解决浅析检测到碰撞后系统通常需要给出响应。这属于“物理引擎”的范畴但我们的碰撞检测系统需要为其提供准确的数据。最基本的响应是解决穿透Penetration Resolution也叫“推离”。假设我们得到了碰撞法线n和穿透深度d。最简单的解决方法是直接沿着法线方向将两个物体分开// 假设物体A是动态的物体B是静态的 transformA.position n * d;但这会产生抖动特别是当多个碰撞同时发生时。更稳定的方法是使用迭代求解或脉冲/约束求解器。例如可以存储一个“位置修正”向量在一帧内对所有碰撞进行多次迭代修正逐步消除穿透。更复杂的响应包括计算碰撞冲量Impulse改变物体的速度线性速度和角速度模拟摩擦和弹性。这需要物体的质量、惯性张量等物理属性。虽然超出了纯碰撞检测的范围但一个设计良好的碰撞检测系统应该能方便地与物理层对接输出足够的信息碰撞点、法线、相对速度等供物理层计算。4. 系统集成与性能优化实战有了核心组件我们需要将它们集成到一个可用的CollisionWorld或PhysicsScene中。4.1 主循环与对象管理class CollisionWorld { public: void AddCollider(Collider* collider); void RemoveCollider(Collider* collider); void Update(float deltaTime); // 更新所有动态碰撞体的变换并更新BVH // 执行一帧的碰撞检测返回所有碰撞对及其信息 std::vectorCollisionPair DetectCollisions(); private: std::vectorCollider* m_Colliders; BVHTree m_BVHTree; // 或 Grid 等空间划分结构 // ... 其他状态 }; void CollisionWorld::Update(float deltaTime) { for (auto collider : m_DynamicColliders) { collider-UpdateTransform(deltaTime); // 例如根据速度更新位置 m_BVHTree.Update(collider-GetNode()); // 更新BVH中该碰撞体的节点 } // 可选定期重构BVH以保持平衡 if (m_FrameCount % 60 0) { // 每60帧重构一次 m_BVHTree.Rebuild(); } } std::vectorCollisionPair CollisionWorld::DetectCollisions() { std::vectorCollisionPair results; // 1. Broad Phase: 使用BVH生成候选对 auto candidatePairs m_BVHTree.GeneratePairs(); // 2. Narrow Phase: 对每个候选对进行精细检测 for (auto pair : candidatePairs) { ContactManifold manifold; if (CollisionDetector::Detect( *pair.first-shape, pair.first-GetTransform(), *pair.second-shape, pair.second-GetTransform(), manifold)) { if (!manifold.empty()) { results.push_back({pair.first, pair.second, std::move(manifold)}); } } } return results; }4.2 性能剖析与关键优化点实现基本功能后必须进行性能剖析Profiling。在Debug模式下你的系统可能很慢这很正常。在Release模式下进行测试并关注以下几点内存布局与缓存友好Collider对象应尽量紧凑避免过多指针跳转。将频繁访问的数据如位置、AABB连续存储例如用std::vectorColliderData可以提高CPU缓存命中率。避免动态内存分配在DetectCollisions这样的每帧调用函数中避免使用new或std::vector::push_back导致频繁分配。使用对象池Object Pool或预分配内存的容器如std::vector::reserve。简化精细检测不是所有碰撞对都需要计算完整的ContactManifold。在游戏逻辑中有时只需要知道“是否碰撞”。可以提供一个快速的TestIntersection函数它可能在找到一条分离轴后就提前返回省去计算碰撞点的开销。分层检测Layer Masking为碰撞体设置层级Layer和遮罩Mask。只有层级与遮罩匹配的物体才会进行检测。这可以大量减少不必要的检测对。例如子弹不需要检测其他子弹背景装饰物不需要相互检测。时间相干性Temporal Coherence利用上一帧的检测结果。如果两个物体上一帧没有碰撞且它们在本帧移动不大那么它们在本帧碰撞的可能性也很低。可以在BVH更新或粗检测阶段利用这个信息进行优化。并行化碰撞检测是“令人尴尬的并行”问题。候选对之间的检测是相互独立的。可以使用多线程如C11的std::async或std::thread或SIMD指令来加速精细检测。例如使用SSE/AVX指令集同时进行多个标量点积运算。4.3 调试与可视化一个看不见的碰撞系统是难以调试的。必须实现可视化工具绘制包围盒在Debug渲染中用线框绘制每个碰撞体的AABB或OBB。用不同颜色表示静态/动态或者是否处于碰撞状态。绘制碰撞法线在碰撞点处绘制一条短线方向为碰撞法线长度与穿透深度相关。打印统计信息在屏幕上显示每帧处理的碰撞体总数、生成的候选对数量、实际发生的碰撞数量、检测耗时毫秒等。这是性能调优的黄金指标。单步调试与选择能够暂停游戏选择特定的碰撞体高亮显示它并打印其详细信息位置、大小、当前碰撞列表等。5. 常见陷阱、问题排查与进阶思考即使按照指南实现你也一定会遇到各种奇怪的问题。这里记录一些我踩过的坑和解决方案。5.1 浮点数精度误差与容差处理这是碰撞检测中最隐蔽的Bug来源。两个理论上刚好接触的物体由于浮点数计算误差可能被判定为“轻微穿透”或“微小分离”。症状物体在应该停下的地方轻微抖动或缓慢穿透。解决引入一个小的容差值Epsilon比如1e-6。在比较距离、深度时使用if (distance radiusSum EPSILON)而不是if (distance radiusSum)。在SAT算法中当投影距离d非常接近投影半径和rArB时可以认为它们刚好接触。注意容差值不能太大否则会错误地将明显分离的物体判定为碰撞。通常需要根据你的世界尺度来调整。5.2 高速物体穿透Tunneling当物体移动速度非常快时比如子弹它可能在一帧内从A点移动到B点完全穿过了另一个薄物体导致两帧的AABB都没有发生相交从而检测不到碰撞。症状高速运动的物体子弹、炮弹穿过了墙壁或敌人。解决连续碰撞检测CCD不检测物体在离散时间点的状态而是检测它们在一段时间内的运动轨迹是否相交。对于AABB可以计算其在本帧的“扫掠体”从上一帧AABB到本帧AABB的凸包然后与目标进行检测。计算量较大。子步长Sub-stepping将物理更新的时间步长deltaTime分成多个更小的子步长。在每个子步长内物体的位移变小穿透就不容易发生。这是最常用且相对简单的方法。扩大包围盒根据物体的最大速度适当扩大其包围盒比如在速度方向上加一个“厚度”但这会增加误报。5.3 复杂形状与凸分解我们的系统目前只处理了基本凸形状球、盒、胶囊。对于复杂的凹网格比如一个茶杯直接进行SAT或GJK检测是不行的因为算法只适用于凸体。解决将凹网格分解为多个凸体Convex Decomposition。有很多算法和工具可以做这件事如V-HACD库。然后一个复杂的碰撞体就由多个凸子碰撞体组成。检测时分别检测这些子碰撞体与目标的碰撞。只要有一个子碰撞体发生碰撞就认为整个物体发生了碰撞。代价碰撞体数量增加性能下降。需要权衡精度和性能。5.4 与渲染系统的同步碰撞体的变换位置、旋转需要与渲染模型的世界变换保持一致但更新时机可能不同。物理更新通常在固定时间步长进行而渲染是每帧一次。症状视觉上看到的模型和实际发生碰撞的边界对不上。最佳实践维护一个“渲染变换”和一个“物理变换”。物理系统在固定时间步长更新“物理变换”并检测碰撞。渲染时使用当前帧插值后的“渲染变换”介于上一物理状态和当前物理状态之间这样既能保证物理模拟的确定性又能实现平滑的视觉渲染。从零实现一个碰撞检测系统是一次深刻的修炼。它强迫你思考空间、几何、数据结构和性能的方方面面。当你看到自己编写的系统能让物体在屏幕上正确碰撞、反弹时那种成就感是使用现成引擎无法比拟的。更重要的是这份对底层的理解会让你在未来使用任何高级引擎时都具备一眼看穿问题本质的能力。