深入剖析Box2DSharp碰撞管线DynamicTree宽相检测与GJK窄相检测完整指南【免费下载链接】Box2DSharpA C# port of Box2D项目地址: https://gitcode.com/gh_mirrors/bo/Box2DSharpBox2DSharp是一个经典的 Box2D 物理引擎 C# 移植版本。它的碰撞管线沿袭了业界标准的两阶段检测思路先由DynamicTree 宽相检测Broad Phase快速筛掉不可能碰撞的物体对再由GJK/EPA 窄相检测Narrow Phase精确求出接触点。本文将带你从全局到细节完整走读这条碰撞管线在源码中的实现路径。 一、碰撞管线全景一次物理帧发生了什么在每一帧物理模拟中碰撞检测按以下顺序执行AABB 更新每个刚体的包围盒AABB随移动更新宽相检测Broad Phase基于 DynamicTree 找出包围盒重叠的候选对窄相检测Narrow Phase对候选对做精确几何求交生成接触流形Manifold接触求解Contact Solving冲量求解器根据接触点施加法向/切向冲量。对应到源码目录这条链路分布在src/Collision/DynamicTree.cs—— 宽相核心的动态 AABB 树src/Collision/BroadPhase.cs—— 宽相管理器负责代理增删与配对上报src/Collision/DistanceAlgorithm.cs—— GJK/EPA 距离算法src/Collision/CollisionUtils.cs—— 各形状组合的精确碰撞算法src/Dynamics/ContactManager.cs—— 串联宽窄相管理接触对象生命周期 设计思想宽相用极廉价的操作处理多窄相对少量候选对做昂贵的精确计算这是所有 2D 物理引擎包括原版 Box2D共用的性能优化哲学。 二、宽相检测DynamicTree 动态树的工作原理宽相的关键数据结构是DynamicTree定义于 DynamicTree.cs它是一棵以 AABB 为叶节点的二叉树内部维护了三个核心机制2.1 节点池与空闲链表DynamicTree使用数组池ArrayPoolTreeNode.Shared管理节点内存通过一个空闲链表_freeList实现节点的快速分配/回收避免频繁 GC——这对每帧都在运行的物理引擎至关重要_treeNodes ArrayPoolTreeNode.Shared.Rent(_nodeCapacity); // Build a linked list for the free list2.2 插入、移动与重平衡插入Insert找到合适的兄弟节点在其下方创建父节点并自底向上调整树高移动MoveProxy当 AABB 移动后MoveProxy会比较新旧包围盒若树高超过一定阈值通常为2 * 树高则触发移除-重新插入保持树的平衡。这正是动态场景下宽相保持 O(log n) 性能的关键查询Query遍历所有与给定 AABB 相交的节点并通过回调把潜在碰撞对收集起来。BroadPhase类BroadPhase.cs在 DynamicTree 之上封装了代理Proxy概念public int CreateProxy(in AABB aabb, FixtureProxy userData) public void MoveProxy(int proxyId, in AABB aabb, in Vector2 displacement) public void UpdatePairs(IAddPairCallback callback)每帧流程为先批量MoveProxy记录位移最后调用一次UpdatePairs把本帧新增/删除的碰撞对通过回调交给ContactManager。 三、窄相检测GJK 与 EPA 如何工作窄相负责回答精确问题这两个形状真的接触了吗接触点在哪法线方向是什么3.1 GJK分离轴判定的迭代器GJKGilbert–Johnson–Keerthi算法在 DistanceAlgorithm.cs 中实现。其核心思想是在两个凸形状的闵可夫斯基差空间中判断原点是否位于其中。若原点在外部则两形状分离。算法并不显式构造闵可夫斯基差而是通过单纯形Simplex迭代逼近从支持点support point出发构造初始单纯形0~3 个顶点每一步求朝原点方向最远的支持点扩展单纯形用最近点算法更新单纯形判断原点是穿过了当前结构可能相交还是仍在外部分离最多迭代 20 次const int maxIters 20防止死循环。源码中可以看到典型的初始化流程var simplex new Simplex(); simplex.ReadCache(ref cache, proxyA, transformA, proxyB, transformB);SimplexCache单纯形缓存是性能亮点上一帧的单纯形顶点会缓存下来本帧直接热启动多数情况下 2~3 次迭代即可收敛。相关结构见 Simplex.cs 与 SimplexCache.cs。3.2 EPA从分离到相交的深入GJK 只能判断分离并给出分离方向。一旦检测到相交或需要精确距离/穿透深度需要EPAExpanding Polytope Algorithm扩展多面体算法把单纯形向外膨胀直到逼近闵可夫斯基差的真实表面从而获得精确的穿透深度与法线。此外Box2DSharp 还实现了TOITime of Impact碰撞时刻算法TimeOfImpact.cs用于高速物体的连续碰撞检测CCD通过二分 GJK 精确求出物体首次穿透的时刻防止高速物体穿透薄墙。 注意GJK/EPA 并非直接用来生成最终接触点。Box2D 的做法是用 GJK 判断是否可能相交若判定为可能相交则回退到下面的基于裁剪Clipping的精确算法来生成最多 2 个接触点。✂️ 四、精确碰撞算法Manifold 接触流形的生成真正把碰撞点算出来的是CollisionUtils静态类CollisionUtils.cs它按形状组合提供不同的算法形状组合方法算法要点圆 vs 圆CollideCircles求两圆心距小于半径和即接触多边形 vs 圆CollidePolygonAndCircle找最近分离边圆在边外或顶点内部分别处理多边形 vs 多边形CollidePolygons萨瑟兰-霍德曼裁剪取两个最可能的主面incidence face裁剪后保留穿透深度 0 的点边 vs 圆 / 边 vs 多边形对应方法单边处理 裁剪多边形裁剪后生成的结果存入Manifold接触流形见 Manifold.cspublic struct Manifold { public FixedArray2ManifoldPoint Points; // 最多 2 个接触点 public Vector2 LocalNormal; // 接触法线 public Vector2 LocalPoint; // 参考点面中心 public ManifoldType Type; // 圆/面A/面B public int PointCount; }每个接触点ManifoldPointManifoldPoint.cs记录了局部坐标点、法向冲量、切向冲量和一个用于跨帧匹配接触点的ContactIdContactID.cs。 为什么限制最多 2 个接触点这是 Box2D 的刻意取舍2 个接触点在 2D 下足以稳定求解同时保证求解器 O(1) 复杂度堆叠场景更稳定。 五、串联一切ContactManager 与接触工厂宽窄相的产物最终由 ContactManager.cs 接管。它内部维护了一张ContactRegister 注册表按形状类型对查表决定用哪个接触工厂Register(ShapeType.Circle, ShapeType.Circle, new CircleContactFactory()); Register(ShapeType.Polygon, ShapeType.Polygon, new PolygonContactFactory()); Register(ShapeType.Edge, ShapeType.Chain, ...); // ... 覆盖所有形状组合当宽相上报新配对时ContactManager调用对应工厂创建Contact对象基类见 Contact.csContact::Collide内部即调用CollisionUtils的精确算法生成 Manifold。接触对象再交给ContactSolverContactSolver.cs进行法向/切向冲量求解完成物理响应。 六、快速上手如何阅读与调试碰撞管线如果你想亲自跟进源码建议按此顺序阅读入口World.cs 中的Step方法观察每帧UpdatePairs的调用时机宽相DynamicTree.cs 的Query/MoveProxy配合 test/UnitTest/CollisionTest.cs 的单测理解树行为窄相DistanceAlgorithm.cs 的Distance主循环配合 Simplex.cs 的单纯形更新可视化调试Testbed 提供现成的可视化用例如 test/Testbed.TestCases/RayCast.cs射线检测、test/Testbed.TestCases/DynamicTree.cs动态树压力测试、test/Testbed.TestCases/TimeOfImpact.csCCD 演示。拉取源码即可运行git clone https://gitcode.com/gh_mirrors/bo/Box2DSharp打开Box2DSharp.slnTestbed 项目基于 OpenTk ImGui 提供实时渲染的测试场景是理解碰撞行为的最佳实验室。 七、总结阶段核心类作用复杂度特征宽相DynamicTree/BroadPhaseAABB 树查询候选对近似 O(log n)每帧大量执行窄相判定DistanceAlgorithmGJK/EPA判断相交、求穿透深度通常 2~8 次迭代收敛窄相精确CollisionUtils裁剪算法生成 Manifold 接触点仅对候选对执行求解ContactSolver冲量求解每帧固定开销Box2DSharp 的碰撞管线完整复刻了 Box2D 的经典架构DynamicTree 宽相检测负责快GJK/EPA 加裁剪的窄相检测负责准两者配合让 C# 开发者也能以极低的性能代价构建流畅的 2D 物理世界。理解这条管线你也就掌握了几乎所有 2D 游戏物理引擎的碰撞检测核心。【免费下载链接】Box2DSharpA C# port of Box2D项目地址: https://gitcode.com/gh_mirrors/bo/Box2DSharp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 深入剖析Box2DSharp碰撞管线：DynamicTree宽相检测与GJK窄相检测完整指南
深入剖析Box2DSharp碰撞管线DynamicTree宽相检测与GJK窄相检测完整指南【免费下载链接】Box2DSharpA C# port of Box2D项目地址: https://gitcode.com/gh_mirrors/bo/Box2DSharpBox2DSharp是一个经典的 Box2D 物理引擎 C# 移植版本。它的碰撞管线沿袭了业界标准的两阶段检测思路先由DynamicTree 宽相检测Broad Phase快速筛掉不可能碰撞的物体对再由GJK/EPA 窄相检测Narrow Phase精确求出接触点。本文将带你从全局到细节完整走读这条碰撞管线在源码中的实现路径。 一、碰撞管线全景一次物理帧发生了什么在每一帧物理模拟中碰撞检测按以下顺序执行AABB 更新每个刚体的包围盒AABB随移动更新宽相检测Broad Phase基于 DynamicTree 找出包围盒重叠的候选对窄相检测Narrow Phase对候选对做精确几何求交生成接触流形Manifold接触求解Contact Solving冲量求解器根据接触点施加法向/切向冲量。对应到源码目录这条链路分布在src/Collision/DynamicTree.cs—— 宽相核心的动态 AABB 树src/Collision/BroadPhase.cs—— 宽相管理器负责代理增删与配对上报src/Collision/DistanceAlgorithm.cs—— GJK/EPA 距离算法src/Collision/CollisionUtils.cs—— 各形状组合的精确碰撞算法src/Dynamics/ContactManager.cs—— 串联宽窄相管理接触对象生命周期 设计思想宽相用极廉价的操作处理多窄相对少量候选对做昂贵的精确计算这是所有 2D 物理引擎包括原版 Box2D共用的性能优化哲学。 二、宽相检测DynamicTree 动态树的工作原理宽相的关键数据结构是DynamicTree定义于 DynamicTree.cs它是一棵以 AABB 为叶节点的二叉树内部维护了三个核心机制2.1 节点池与空闲链表DynamicTree使用数组池ArrayPoolTreeNode.Shared管理节点内存通过一个空闲链表_freeList实现节点的快速分配/回收避免频繁 GC——这对每帧都在运行的物理引擎至关重要_treeNodes ArrayPoolTreeNode.Shared.Rent(_nodeCapacity); // Build a linked list for the free list2.2 插入、移动与重平衡插入Insert找到合适的兄弟节点在其下方创建父节点并自底向上调整树高移动MoveProxy当 AABB 移动后MoveProxy会比较新旧包围盒若树高超过一定阈值通常为2 * 树高则触发移除-重新插入保持树的平衡。这正是动态场景下宽相保持 O(log n) 性能的关键查询Query遍历所有与给定 AABB 相交的节点并通过回调把潜在碰撞对收集起来。BroadPhase类BroadPhase.cs在 DynamicTree 之上封装了代理Proxy概念public int CreateProxy(in AABB aabb, FixtureProxy userData) public void MoveProxy(int proxyId, in AABB aabb, in Vector2 displacement) public void UpdatePairs(IAddPairCallback callback)每帧流程为先批量MoveProxy记录位移最后调用一次UpdatePairs把本帧新增/删除的碰撞对通过回调交给ContactManager。 三、窄相检测GJK 与 EPA 如何工作窄相负责回答精确问题这两个形状真的接触了吗接触点在哪法线方向是什么3.1 GJK分离轴判定的迭代器GJKGilbert–Johnson–Keerthi算法在 DistanceAlgorithm.cs 中实现。其核心思想是在两个凸形状的闵可夫斯基差空间中判断原点是否位于其中。若原点在外部则两形状分离。算法并不显式构造闵可夫斯基差而是通过单纯形Simplex迭代逼近从支持点support point出发构造初始单纯形0~3 个顶点每一步求朝原点方向最远的支持点扩展单纯形用最近点算法更新单纯形判断原点是穿过了当前结构可能相交还是仍在外部分离最多迭代 20 次const int maxIters 20防止死循环。源码中可以看到典型的初始化流程var simplex new Simplex(); simplex.ReadCache(ref cache, proxyA, transformA, proxyB, transformB);SimplexCache单纯形缓存是性能亮点上一帧的单纯形顶点会缓存下来本帧直接热启动多数情况下 2~3 次迭代即可收敛。相关结构见 Simplex.cs 与 SimplexCache.cs。3.2 EPA从分离到相交的深入GJK 只能判断分离并给出分离方向。一旦检测到相交或需要精确距离/穿透深度需要EPAExpanding Polytope Algorithm扩展多面体算法把单纯形向外膨胀直到逼近闵可夫斯基差的真实表面从而获得精确的穿透深度与法线。此外Box2DSharp 还实现了TOITime of Impact碰撞时刻算法TimeOfImpact.cs用于高速物体的连续碰撞检测CCD通过二分 GJK 精确求出物体首次穿透的时刻防止高速物体穿透薄墙。 注意GJK/EPA 并非直接用来生成最终接触点。Box2D 的做法是用 GJK 判断是否可能相交若判定为可能相交则回退到下面的基于裁剪Clipping的精确算法来生成最多 2 个接触点。✂️ 四、精确碰撞算法Manifold 接触流形的生成真正把碰撞点算出来的是CollisionUtils静态类CollisionUtils.cs它按形状组合提供不同的算法形状组合方法算法要点圆 vs 圆CollideCircles求两圆心距小于半径和即接触多边形 vs 圆CollidePolygonAndCircle找最近分离边圆在边外或顶点内部分别处理多边形 vs 多边形CollidePolygons萨瑟兰-霍德曼裁剪取两个最可能的主面incidence face裁剪后保留穿透深度 0 的点边 vs 圆 / 边 vs 多边形对应方法单边处理 裁剪多边形裁剪后生成的结果存入Manifold接触流形见 Manifold.cspublic struct Manifold { public FixedArray2ManifoldPoint Points; // 最多 2 个接触点 public Vector2 LocalNormal; // 接触法线 public Vector2 LocalPoint; // 参考点面中心 public ManifoldType Type; // 圆/面A/面B public int PointCount; }每个接触点ManifoldPointManifoldPoint.cs记录了局部坐标点、法向冲量、切向冲量和一个用于跨帧匹配接触点的ContactIdContactID.cs。 为什么限制最多 2 个接触点这是 Box2D 的刻意取舍2 个接触点在 2D 下足以稳定求解同时保证求解器 O(1) 复杂度堆叠场景更稳定。 五、串联一切ContactManager 与接触工厂宽窄相的产物最终由 ContactManager.cs 接管。它内部维护了一张ContactRegister 注册表按形状类型对查表决定用哪个接触工厂Register(ShapeType.Circle, ShapeType.Circle, new CircleContactFactory()); Register(ShapeType.Polygon, ShapeType.Polygon, new PolygonContactFactory()); Register(ShapeType.Edge, ShapeType.Chain, ...); // ... 覆盖所有形状组合当宽相上报新配对时ContactManager调用对应工厂创建Contact对象基类见 Contact.csContact::Collide内部即调用CollisionUtils的精确算法生成 Manifold。接触对象再交给ContactSolverContactSolver.cs进行法向/切向冲量求解完成物理响应。 六、快速上手如何阅读与调试碰撞管线如果你想亲自跟进源码建议按此顺序阅读入口World.cs 中的Step方法观察每帧UpdatePairs的调用时机宽相DynamicTree.cs 的Query/MoveProxy配合 test/UnitTest/CollisionTest.cs 的单测理解树行为窄相DistanceAlgorithm.cs 的Distance主循环配合 Simplex.cs 的单纯形更新可视化调试Testbed 提供现成的可视化用例如 test/Testbed.TestCases/RayCast.cs射线检测、test/Testbed.TestCases/DynamicTree.cs动态树压力测试、test/Testbed.TestCases/TimeOfImpact.csCCD 演示。拉取源码即可运行git clone https://gitcode.com/gh_mirrors/bo/Box2DSharp打开Box2DSharp.slnTestbed 项目基于 OpenTk ImGui 提供实时渲染的测试场景是理解碰撞行为的最佳实验室。 七、总结阶段核心类作用复杂度特征宽相DynamicTree/BroadPhaseAABB 树查询候选对近似 O(log n)每帧大量执行窄相判定DistanceAlgorithmGJK/EPA判断相交、求穿透深度通常 2~8 次迭代收敛窄相精确CollisionUtils裁剪算法生成 Manifold 接触点仅对候选对执行求解ContactSolver冲量求解每帧固定开销Box2DSharp 的碰撞管线完整复刻了 Box2D 的经典架构DynamicTree 宽相检测负责快GJK/EPA 加裁剪的窄相检测负责准两者配合让 C# 开发者也能以极低的性能代价构建流畅的 2D 物理世界。理解这条管线你也就掌握了几乎所有 2D 游戏物理引擎的碰撞检测核心。【免费下载链接】Box2DSharpA C# port of Box2D项目地址: https://gitcode.com/gh_mirrors/bo/Box2DSharp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考