做游戏开发或者物理仿真这几年碰撞检测CollisionDetection绝对是最绕不开的一块硬骨头。你写一个角色移动写一个物体交互底层全靠它撑着。很多刚入行的朋友觉得碰撞检测就是“两个盒子有没有重叠”真做起来才发现坐标系、旋转、浮点误差、性能开销随便一个坑都能让你调一整天。这篇博文我会从碰撞检测的核心概念讲起把常见算法的数学原理、工程实现和优化思路一次性撸清楚。不管你是自研引擎、用Unity还是写WebGL这套底层逻辑都通用。内容会偏硬核一些但我会尽量用通俗的方式拆解争取让有基础的同学能直接上手刚接触的朋友也能看懂主干流程。1. 碰撞检测的基础先搞清楚我们要解决什么问题1.1 碰撞检测的本质是“求交集”碰撞检测说白了就是判断两个或多个几何体在空间中是否发生重叠。但这里有个特别容易被忽视的点我们讨论的“碰撞”通常分为两个层面一个是离散碰撞检测一个是连续碰撞检测。离散碰撞检测是在某个时间点上直接判断两个物体当前的状态是否有交集。就好比你每隔一帧拍一张照片看照片里两个物体是否重叠了。这种方式实现简单、性能友好但有一个经典问题叫隧穿效应——当一个物体运动速度足够快它可能在这一帧穿过了另一个物体下一帧已经跑到对面去了照片里永远拍不到重叠的画面。连续碰撞检测则是把时间因素考虑进去通过计算物体在某个时间区间内的运动轨迹与另一个物体的相交情况来精确找到首次接触的时间点。这种方式能彻底解决隧穿问题但计算量大得多。到底怎么取舍取决于你的应用场景后面我会详细展开。1.2 从数学上看碰撞检测的两种判定思路在数学层面碰撞判定有两大流派。第一种是精确几何相交测试直接对两个形状的几何参数进行方程求解比如球体之间求距离、平面与线段求交点。这种方式的优点是精准缺点是通用性差每换一种形状组合就要重写算法。第二种是分离轴定理Separating Axis Theorem简称SAT也是目前工业界使用最广的算法。SAT的核心思想很妙两个凸多边形如果不相交那一定存在一条直线即分离轴使得两个形状在这条轴上的投影没有重叠。反过来如果我们检查了所有可能的轴都找不出一个投影不重叠的轴那这两个形状必然相交。想象一下两个面团在案板上从左右两侧向中间推如果在某个角度上你看到两个面团在“光照投影”下的阴影没有交叠那它们肯定没碰到一起。这就是分离轴定理的直观理解。为什么大家都在用SAT而不是直接算交点因为投影运算比求解高维方程组要简单得多尤其在高精度浮点运算上SAT的数值稳定性也更可控。后面我会给出具体的实现代码。1.3 应用场景的差异决定技术选型碰撞检测听起来是个很窄的领域但实际上不同场景对它的要求差别非常大。游戏引擎里碰撞检测要的是实时性好一帧只有16毫秒的预算你还得分配给渲染、逻辑、动画碰撞系统能拿到的往往只有两三毫秒。所以引擎侧通常会用非常暴力的简化手段比如用胶囊体代替人形模型用球体代替爆炸范围追求的是“够用”而非“精确”。物理仿真比如刚体模拟、分子动力学则是精度优先物体之间的接触点、接触法线、穿透深度这些信息后续都要用于约束求解如果碰撞阶段就给错了数据整个物理系统的稳定性就崩了。这里用的算法往往更加麻烦比如用GJKGilbert-Johnson-Keerthi算法配合EPAExpanding Polytope Algorithm来精确求解穿透向量。CAD和机器人路径规划里比较侧重于连续碰撞检测和距离场计算因为一个机械臂的运动轨迹不可能靠“每步停下来判断有没有撞”去保证安全必须在运动规划阶段就算出整条轨迹与障碍物的最小距离。搞清楚场景再选方案比一头扎进某个算法的实现要重要得多。我在早期项目里就吃过亏——一开始就奔着精确求交去结果性能被拖垮后来改成两层检测Broad Phase加Narrow Phase问题迎刃而解。关于这个分层架构下一节细讲。2. 工程实践的核心架构Broad Phase 与 Narrow Phase 分工2.1 为什么必须把碰撞检测拆成两个阶段很多初学者会问我能不能直接把所有物体的网格都拿来做两两相交测试答案是能但性能会极其糟糕。假设场景里有1000个物体两两组合就是近50万对测试。如果每对测试都去做三角形级别的精确求交哪怕每对就算0.1毫秒一帧下来也直接卡死了。所以工业级碰撞系统都会把流程拆成两个阶段Broad Phase粗检测和Narrow Phase细检测。Broad Phase的目标不是找出“谁撞了谁”而是快速筛掉那些明显不可能碰撞的物体对输出一个“候选碰撞对列表”。这个阶段允许有误差甚至可以“宁错杀一千不放过一个”因为它的使命就是减少Narrow Phase的负担。Narrow Phase拿到候选对之后再对每对物体执行精确的几何相交测试得到实际碰撞点、碰撞法线、穿透深度等物理引擎需要的数据。这个架构有点像相亲。Broad Phase是先筛简历年龄、地域、收入这种硬性条件先把不可能的人过滤掉。Narrow Phase才是真正见面聊仔细看性格合不合。如果一上来就让所有人面对面聊天效率必然低下。2.2 Broad Phase 常用方案对比Broad Phase算法中最经典也最常用的三种方案是统一空间网格Uniform Grid、四叉树/八叉树Quadtree/Octree和排序扫描Sweep and Prune。统一空间网格就是把世界均匀切成一个个小格子每个物体落到它所在的格子中然后只检查同一个格子以及相邻格子里的物体对。实现极其简单适合大量物体均匀分布的场景。缺点也很明显如果物体大小差异悬殊格子尺寸就难以选择大物体会横跨很多格子导致性能急剧下降。八叉树则是把空间递归地划分成八份三维物体插入到能完整包含自己的最小节点中。这种结构对物体分布不均匀的场景表现很好比如室内场景里墙壁、家具、人物都在不同区域密集分布。但树结构的重建过程有额外开销对于大量动态移动的物体需要每帧更新节点索引处理不当会变成性能瓶颈。Sweep and Prune的思路更巧妙把物体在三个坐标轴上的投影区间分别排序然后检测区间重叠。如果两个物体在任意一个轴上的投影都不重叠那它们必然不相交反之如果在三个轴上都有重叠那么它们可能碰撞。这个算法在小规模场景中表现优雅不需要额外的空间开销但物体数量增多时排序的开销也会涨。三者的核心差异在下表里做了对比方案适用场景优势劣势Uniform Grid物体大小相近、分布均匀实现简单、空间局部性好物体大小差异大时性能骤降Octree动静混合、分布不均的复杂场景自适应性好动态更新有开销Sweep and Prune物体数量适中、运动规律无内存开销、稳定性好极端大量物体会退化2.3 Narrow Phase 的精确相交测试当Broad Phase筛选出候选对之后就轮到Narrow Phase上场了。这里针对不同的几何体组合有对应的经典算法球与球计算两球心距离与两球半径之和比较。AABB与AABB分别对比三个轴向上的区间是否有重叠。OBB与OBB用分离轴定理检测15条候选轴上的投影。凸多边形与凸多边形用GJK算法计算最近距离或用SAT直接判定是否相交。三角网格与三角网格通常先用BVHBounding Volume Hierarchy做加速再对具体三角形对求交。在自研引擎中我比较推荐的做法是Broad Phase用Dynamic OctreeNarrow Phase的主算法用GJK加上SAT做备用。GJK不像SAT那样需要显式枚举所有分离轴它通过迭代逼近单纯形Simplex来判定两个凸体的距离性能在很多情况下优于SAT。但GJK的缺点是无法直接给出穿透深度需要额外配合EPA算法才能获取这也是一些场景里选择SAT的原因。3. 核心算法拆解从AABB到SAT再到GJK3.1 最基础的AABB碰撞检测与实现AABBAxis-Aligned Bounding Box也就是轴对齐包围盒是碰撞检测里最简单的几何体。它要求包围盒的六个面分别与世界坐标系的三个轴平行这样描述一个盒子的数据极其简洁只要记录最小点坐标和最大点坐标即可。在JavaScript里判断两个AABB是否相交可以这样写function checkAABBs(a, b) { return ( a.minX b.maxX a.maxX b.minX a.minY b.maxY a.maxY b.minY a.minZ b.maxZ a.maxZ b.minZ ); }这段代码背后的逻辑很简单如果两个盒子在任何一个轴上都没有区间重叠那它们一定不相交。注意这里用的是“区间重叠”的判断而不是单纯比较某个坐标值因为你需要同时保证六个方向都不越界。AABB的优点是计算量极小适合用来做场景物体的初步包围体。缺点也很明显如果物体发生了旋转旋转后的OBB不再和坐标轴对齐AABB就会在物体外围产生额外间隙碰撞判定会失真。所以AABB一般用作Broad Phase的初级测试或者在物体不旋转的场景中使用。3.2 分离轴定理SAT的完整推理与代码当我们需要更精确地检测两个旋转矩形的碰撞AABB就力不从心了。这时SAT是更合适的选择。SAT的应用条件要求两个形状都是凸多边形。如果遇到凹多边形需要先将它分解为若干个凸多边形的组合再分别测试。前面我提到过SAT的核心如果存在投影不重叠的轴说明两形状分离。问题在于候选轴从哪里来数学推导告诉我们只要取两个凸多边形各自所有边的法线作为候选轴就能保证覆盖所有分离可能性。对于两个矩形每条边对应一条法线加起来最多十几条轴逐条投影判断即可。我用一个二维的SAT实现来演示function satCollision(verticesA, verticesB) { const axes getAxes(verticesA).concat(getAxes(verticesB)); for (let i 0; i axes.length; i) { const axis axes[i]; const projA project(verticesA, axis); const projB project(verticesB, axis); if (projA.min projB.max || projB.min projA.max) { return false; } } return true; }getAxes函数提取所有边的法线这里要注意法线需要归一化否则投影的长度会对分离判断造成误差。project函数将每个顶点投影到轴上并记录该形状投影区间的最小值和最大值。这段代码的数学复杂度主要在投影部分。投影点坐标 顶点坐标与单位法线的点积。用点积求投影的原理本质上就是计算顶点沿法线方向的“标量分量”。将每个顶点的标量分量取最小最大就得到了该形状在轴上的投影区间。SAT的实现细节里有个常见坑浮点误差。当两个形状几乎贴合时投影区间的边界可能只差0.0001直接比较会出现误判。工程上通常给比较加一个很小的容差值比如1e-6让判定更稳健。3.3 GJK算法现代物理引擎的宠儿SAT的实现直观但它的复杂度随顶点数上升在顶点较多的形状上千篇一律地列举所有边的法线效率不高。GJK算法是另一种更现代的选择。GJK的全称是Gilbert-Johnson-Keerthi三个数学家在1988年提出了这个算法。它不依赖显式枚举边和法线而是通过构建Minkowski差来判断两个凸体是否相交。Minkowski差是什么简单说将物体A的所有顶点坐标减去物体B的所有顶点坐标得到一个新的点集。这个新点集包围的区域就是Minkowski差。一个重要的性质是如果Minkowski差包含原点那么两个物体必然相交。GJK算法就是在Minkowski差内部迭代构造一个单纯形——二维是三角形三维是四面体——通过逐步向“更靠近原点”的方向扩展来判断原点是否被包含在内。如果某一步发现最接近原点的方向已经找不到更近的点那就判定为分离。GJK的优势在于它的迭代次数通常比较少而且没有SAT那样对顶点数的显式依赖性能更好。但是它的实现复杂度较高而且不能直接输出穿透深度需要配合EPA使用。如果只是做碰撞判定不需要穿透信息GJK是绝佳选择。我目前的自研引擎中Narrow Phase基本都用GJK只有需要处理圆形与多边形混合交集求穿透时才落回SAT加定制的胶囊体算法。4. 工程落地中的优化与精细调优4.1 减少计算量的几条关键路径算法本身选对了性能仍有很大提升空间。我从实践中总结了几条优化路径。第一能用简单包围体就不用复杂形状。在一个场景中90%的碰撞对是明显不可能发生碰撞的用“球包围体球包围体”或者“AABBAABB”的初筛就能大幅缩减计算量。所以我的引擎里每个物体通常同时维护多个层次的包围体从球体到AABB到精确网格逐层测试、逐层精简。第二空间划分结构要支持增量更新。很多刚接触的人会把八叉树每帧全量重建性能自然差。正确做法是运动物体每帧更新它所在的叶子节点只有跨越边界时才做节点间的移动静态物体完全不用动。这样可以把动态更新的开销压在城市级场景可接受的范围内。第三利用方向剔除Directional Culling。对于有明显方向性的检测比如子弹射出、激光照射可以用射线检测替代物体对物体的碰撞对检测。这可以用射线与BVH的遍历加速比直接遍历场景中所有物体要高效好几倍。4.2 连续碰撞检测的实现思路与适用场景隧穿问题如果要彻底解决就得用连续碰撞检测。现在主流的方案是**基于保守推进Conservative Advancement或基于射线扫描Sweep**的方法。拿高速子弹穿透墙壁的例子来说离散碰撞检测会看到子弹在墙前面下一帧子弹在墙后面永远没有“墙内”状态。连续碰撞检测会把子弹在这一帧内的运动轨迹看成一条线段然后判断这条线段与墙壁三角形网格是否相交以及交点的具体时间。实现连续碰撞有几种思路扫掠体Swept Volume将移动物体沿运动方向扫出一个体比如球体扫出来就是胶囊体再用这个扫掠体与静态物体做相交测试。实现相对简单适合子弹这类小而快的物体。CCDContinuous Collision Detection模式物理引擎会在Broad Phase中将速度较快的物体单独标记对这些物体启用特殊的时间段切片算法用多次步进的方式来近似连续碰撞。这种模式精度可控开销也可控Unity的PhysX和Bullet都内置了这种方案。人为限制最大速度和最小检测距离这是一种取巧但有效的办法。如果你能保证物体每帧移动距离不超过其最小包围体的尺寸那么离散碰撞检测就永远不会漏掉碰撞。很多2D游戏就是这么处理的。实际项目中我会给逻辑层提供三种碰撞检测接口const COLLISION_MODE { DISCRETE: discrete, // 离散检测性能最好 SWEEP: sweep, // 扫掠体检测速度快的物体用 CONTINUOUS: continuous // 完整连续检测精度最高 };然后根据物体类型自动分配模式比如场景中的子弹用SWEEP角色用DISCRETE关键交互道具用CONTINUOUS。这样既保证了体验又不至于所有物体都跑复杂的连续检测。4.3 浮点误差、穿透修正与胯部问题真实物理引擎里碰撞检测之后往往还跟着约束求解和碰撞响应。这时候浮点误差很容易导致一种经典问题物体明明检测到碰撞却在下一帧依然嵌入到另一个物体内部出现“抖动”或“穿透”。原因主要出在穿透深度的计算上。碰撞检测求出的穿透方向是法线方向但如果物体沿法线的移动量小于数值误差修正了也白修。实际工程里我通常会做一个**穿透修正Position Correction**操作在约束求解前额外推一步把物体沿法线外推比穿透深度略微多出1~2毫米的量让物理引擎有更大的容错空间。还有一种情况是法线方向震荡当物体正好落在某条棱边上两边三角形的法线都在参与判定计算出的碰撞法线会在两个方向间横跳导致物体看起来在“颤抖”。这类问题常见于把网格数据过于粗糙细分或者模型本身存在非流形边。解决方案是在Narrow Phase后加一个法线平滑或对法线角度做阈值滤波避免修正方向剧烈变化。4.4 性能预警与诊断工具碰撞检测一旦出现性能问题定位起来比较麻烦。我习惯在物理系统里埋一些性能探针Broad Phase耗时估算用于判断是否需要优化空间划分结构。Narrow Phase求交次数与候选对数用来发现是否Broad Phase缩水太少。穿透修正次数如果这个数值过高说明检测策略太激进或物体初速度太大。这样在性能分析器里就能直接看到瓶颈是发生在Broad Phase还是Narrow Phase从而针对性优化。5. 碰撞检测的场景案例分析从2D游戏到3D仿真5.1 2D游戏中的命中判定与平台跳跃先聊一个最常见的场景2D横版游戏里的平台跳跃。这个场景里的碰撞检测难点从AABB判定变成了“如何处理边界梯度”的问题。我遇到过不少新手用一套简单的AABB检测来做角色地面碰撞结果角色站在平台上会“抖”个不停或者跳起时总被平台卡住。原因在于平台是一个薄层角色的包围盒在垂直方向上的位置判定存在浮点误差导致本应站在平台上却检测为“没碰到”。解决方案是在Bottom方向的检测中用一条向下偏移零点多个像素的射线代替整段底部边界检测。这样纵向容错提升了不少又不会影响左右移动时的碰撞检测。实际在实现时我会为角色的AABB分别构建左右、上下四条射线根据速度方向只检测可能碰撞的那几条射线极大减少无效的检测调用。5.2 3D场景中的角色胶囊体与场景网格3D角色如果直接用网格模型参与碰撞检测是灾难级的性能浪费。工业和引擎界的通行做法是用胶囊体近似代替角色模型——一个圆柱加半球盖能够很好地逼近人体轮廓而且在数学上的碰撞计算也相当简单。胶囊体的碰撞检测通常是转化为“线段到物体最近距离”的问题。把胶囊体看成一条线段两端点分别是胶囊体半球的球心线段周围的半径区就是胶囊体实体。判断胶囊体是否撞上场景可以先求出线段与场景中三角面的最近距离再与胶囊体半径比较。这个做法的好处是计算量远低于对圆柱体做精确相交测试。我写过一个简化的胶囊体与AABB相交函数核心逻辑就是求线段与六个面中最近距的距离再判断是否小于半径运行效率比直接网格求交高一个数量级。5.3 物理沙盒中的刚体堆叠稳定物理沙盒最折磨人的场景是刚体堆叠比如往木箱上叠木箱。你可能会发现箱子堆到四五层的时候就开始“炸开”或者“互相嵌进去”。此类问题根源经常出现在碰撞检测给出的接触点不够精确。物体接触时接触点有多个物理引擎需要通过对这些接触点做约束求解来维持稳定。而接触点的数量和质量直接取决于Narrow Phase返回的接触流形。如果碰撞检测只返回一个点或者返回的点在法线方向上分布不均约束求解极易不稳定出现“跳跃”和“穿透”。为了提高堆叠稳定性我采取的办法是用GJK加EPA求出穿透多边形再从多边形中提取用于约束求解的多个支撑点。这样即使面对大量堆叠也能保持系统相对平稳。还有一个经验是对接触点设置一个微小的“接触容差”当物体间距离小于该容差时视为接触避免在松弛状态下反复弹跳。6. 常见问题与排查技巧实录6.1 碰撞检测的常见问题速查表现象可能原因解决思路高速物体会穿过薄墙离散检测导致隧穿改用连续碰撞或SWEEP模式物体卡在墙角抖动法线方向震荡或浮点误差加法线平滑增大接触容差子弹命中判定偏大包围球半径设置过大检查包围体尺寸与实际模型比例两个物体碰撞后轻微弹开穿透修正过度减小修正系数或只在特定轴上修正性能突然卡顿Broad Phase漏检导致Narrow Phase过载检查空间划分更新逻辑确认动态物体是否经常跨节点跳变6.2 排查碰撞问题时我的一线经验调试碰撞检测最痛苦的地方在于“不可见”的几何数据很难直接观察。所以我的工具链里一定会有一套可视化调试器能画出物体的包围体、碰撞法线、接触点、穿透深度。有了这些图形数据很多问题一眼就能看出来。比如我之前遇到过一个问题物体在A点看起来明显穿透了墙壁但碰撞系统没有报告任何碰撞。调试一开发现墙壁网格的AABB在构建时少了半边——因为美术模型在导入时法线朝向有一半是反的导致生成包围体的顶点数据不完整。后来我在导入流程里加了“顶点法线重计算”的步骤这类问题才算绝迹。另一条经验是碰撞检测问题不要只看Narrow Phase要先查Broad Phase是否把物体对正确筛出来了。很多底层逻辑错误发生在Broad Phase的索引更新中比如某个物体移动后没有更新它的叶子节点导致空间索引里的位置和实际位置脱节。6.3 性能瓶颈定位的思路如果物理系统的耗时异常增长可以先在物理步骤里用GPU计时或者CPU profile观察Broad Phase和Narrow Phase分别花了多少毫秒。如果Narrow Phase耗时占比过高说明Broad Phase的筛选不够狠可以降低包围体的膨胀系数如果Broad Phase耗时过高说明空间索引更新次数太多可能是因为动态物体频繁跨叶节点这时候要考虑改用更大的叶子节点尺寸或换一种空间划分算法。还有一个小技巧是在物理系统里按物体的运动速度分桶低速物体在Broad Phase里用AABB即可只有高速物体才送去扫掠检测。这样能在保证碰撞准确性的前提下尽可能降低单位时间内的计算量。写在最后我在碰撞检测这条路上踩过的坑比写过的代码还要多。最初以为“能判断相交就行”后来才发现碰撞检测只是物理系统的一个入口它后面牵动着稳定性、性能、可调试性等多重维度。如果你正在自研引擎或者想在现有引擎上深入理解物理模块我的建议是先从简单的AABB和球体检测写起理解Broad Phase与Narrow Phase的分工再逐步上手SAT和GJK。不要一上来就啃连续碰撞和接触流形那些东西需要足够的底层积累才能驾驭。最后分享一个小技巧当你调试碰撞检测问题时一定要先确保数据输入是对的。很多诡异问题最终查下来都是网格数据、包围盒尺寸或坐标变换出了问题而不是算法本身有bug。先画包围体、再画碰撞法线、最后看具体数据这套排查顺序能帮你省下一大半的调试时间。
