深入分析物理引擎后，他写了一个轻量的 Cocos 3D 碰撞检测优化方案

引言：碰撞检测是游戏开发中一个非常重要的技术点，优化碰撞检测性能，是提升游戏体验不可或缺的一环。开发者「我叫98K」写了一个轻量碰撞系统，用以改善 3D 游戏在不同平台遇到的碰撞性能问题和包体问题。下载和在线体验地址见文末。

98K物理-轻量碰撞系统是一个高性能轻量 3D 碰撞管理器，适用于 Cocos Creator 3.4 及以上版本，对 Mesh 模型和基本几何体提供高效的碰撞系统和射线检测系统，以提升游戏在不同平台上的 3D 碰撞检测性能，减少包体大小（尤其是 H5 平台）。

先通过在线体验，看几组应用效果：

http://www.cocospro.com/98K/

场景1，碰撞测试

场景1，1000射线测试

场景2，碰撞测试

场景2，1000射线测试

本文主要和大家详细介绍 98K 中最为重要的自定义碰撞系统的功能与使用、及其实现思路与技术要点，感兴趣的小伙伴可以深入了解。

功能特点

98K 的主要功能特点有：

• 多物体场景管理：Octree，对场景物体进行高效划分查询。

• 模型三角化管理：Kdtree，对物体表面进行高效划分查询。

• 通用 3D 碰撞计算：GJK+EPA，精确计算修正碰撞后的物体。

• 3D 角色控制器：3D 物体在场景碰撞系统下的自由移动。

• 高效射线检测：基于 Octree 和 Kdtree 对射线检测加速。

我们在 H5 环境下，对比 98K 和 Bullet，PhysX（由于 Cannon 对 mesh collider 支持不完善，不参与比较）。

虽然和 Bullet、PhysX 相比，98K 的功能还不够全面，但是在需要使用 3D 碰撞检测和射线检测的 MMO、SLG、FPS 等 3D 场景的游戏中，目前 98K 提供的功能已经可以满足需求，并且 98K 更加轻量，使用也更简单一些，可以替代 Bullet、PhysX。

使用方法

前一段时间孙二喵制作的 3D 跑酷游戏 Demo 就使用了 98K，我们以此为例，看看这一系统在实际游戏项目中的使用方法与效果。

源码下载：

https://store.cocos.com/app/detail/4084

在线体验：

http://learncocos.com/jare/?v=1.01

该游戏场景超过100万面，而且地形较不规则，使用 Bullet+Mesh Collider 整体开销会比较高，所以孙二喵使用了 98K，以获得更好性能。

相对于 Bullet Mesh Collider 初始化满和设置麻烦的缺点，98K 的 Mesh Collider 可以说是键设置。

我们可以制作1个小脚本，在编辑器环境下，给所有的 Mesh 都加上 98K 的碰撞组件。

然后把所有有 Object3D 碰撞组件的物体都加到我们的主场景下面。

进入场景后，再进行构建。

后续有需要增加和删减碰撞体，也可以通过 World 里的方法进行操作。

同时 98K 也提供了射线检测功能。我们可以通过射线检测地面，来处理跳跃等逻辑。

98K 的另外一个特点是使用了简单的数学公式，这部分可以进行定点数的处理，方便联机游戏处理帧同步，目前也已经有开发者进行了二次开发。

技术要点

接下来简单介绍一下 98K 中自定义碰撞系统的技术实现要点，以及我选择现在这个优化方案的思路与原因。

在造轮子前，得先了解轮子是怎么构成，才能更好的去改造。

功能分层结构图

物理引擎进行碰撞检测的基本流程包含三个环节：

• Board-Phase（粗略筛选碰撞对）

• Narrow-Phase（精确计算碰撞对）

• Resolve-Phase（修正碰撞速度位置）

Board-Phase

Board-Phase 的目标是快速排除掉不可能发生碰撞的物体对，以此提高后续碰撞检测的效率。空间划分是这一阶段最重要的部分。在游戏开发中，我们常用各种空间数据结构来加速计算。

多叉树：四叉树与八叉树

四叉树

四叉树是很常见的一种 2D 碰撞检测方法，实现手段也五花八门。不过在具体实现中要注意优化细节，控制建树时间消耗与建树空间大小，特别是在 JS 语言环境下。但四叉树的射线检测、区域检测效率比较高，树更新很快，会产生物体多次划分，空间占用大。

八叉树

八叉树虽然包围精确性没 BVH 高（可用状态压缩改善）、占用空间较大（过度划分），但是建树和增删非常快，很适合用作物体的筛选。目前 98K 使用了八叉树对模型包围盒进行空间划分，简单高效的建树比精确计算建树（比如 BVH 建树会有大量计算消耗）更加划算。缺点和四叉树一样，射线检测、区域检测较快，树更新很快， 会产生物体多次划分，空间占用大。

二叉树：BVH，BSP，k-d

BVH

四叉树和八叉树是以平均空间来划分物体，划分算法简单，而 BVH 是对当前物体集合进行空间的划分，追求左右空间大小相对均衡且无相交。BVH 构建的一般是二叉树，划分算法复杂。

主流物理引擎都有采用 BVH，因为其功能支持完备、查找精确性高、性能不俗。但是其在建树和增删改时要维护平衡树，消耗很大。针对这个问题，有一些时序性的空间优化方法，通过减少增删改达到优化目的，感兴趣的朋友可以参考各大物理引擎中的实现方法。

BSP

BSP（Binary Space Partitioning Tree），二维空间分割树，非常经典，1993年在知名游戏 DOOM 里第一次被应用，早期 CS 也是用 BSP 来做地形碰撞。BSP 通常通过计算得到一个合理的任意角度片面或者法线，然后对空间进行划分。标准的 BSP 虽然高效，但树构建非常消耗时间，通常都是编辑器预处理，比较适合静态模型或者静态场景使用。

k-d 树

k-d 树是一种特殊的 BSP 树，它基于动态计算的三个轴进行划分。k-d 树相比 BSP 可能精确性没那么高，但是建树时间大大减少，因为对轴划分算法简单，所以很适合使用。目前 98K 用 k-d 树方式来维护模型的三角形数据，用于碰撞和射线检测。

其他：SAP

SAP

SAP（Sweep And Prune) 又称为扫掠法，也是物理引擎的一种常用碰撞检测方式。SAP 比较轻便，增删改比较快，物体不会被多次划分，对静态模型是非常快。它唯一缺点是性能不太稳定，每次只能对单个轴进行扫描，有时会有大量物体投影重叠，导致查询不稳定。而且射线检测和区域检测，需要额外的扩展来优化，性能也一般，没上面各种树结构的方便和高效。

Narrow-Phase

在这个阶段，我们需要对筛选后的这些可能发生的碰撞进行精确计算，判定他们是否发生了碰撞，如果发生碰撞，还需计算出碰撞点、碰撞法线等细节。

几何计算

数学方法，从分离角度来判断碰撞，一般用于常见的几何图形之间的碰撞计算，速度非常快。良好的物理引擎必不可少这些数学方法，各大引擎都能找到它们的身影。

GJK + EPA

凸包算法，从重叠角度来探索碰撞。GJK 的原理核心是，当两个物体发生重叠时，它们必然有一个坐标相减为原点。GJK 检测出碰撞后，再用 EPA 在 GJK 构建的数据下，进一步计算出穿透的距离碰撞点和碰撞法线。

基本上主流物理引擎都有使用 GJK+EPA，和前面几何数学方法混合使用，可以大幅提升碰撞计算性能。98K 也是同时混合使用以上两种方法，支持基本几何模型计算，也能支持三角化 mesh 或者凸包化 mesh 的计算。

Resolve-Phase

在上一个阶段，我们已经确定了是否发生碰撞和碰撞的细节，最后阶段即是修正他们的位置和速度。这一过程非常耗时，目前 98K 只提供了简单高效的修正处理，更多重心还是放在解决现有的碰撞性能问题上。

98K 优化方案

物理引擎是一套复杂完整的过程，没办法在功能上做分割，所以一定程度上会造成不必要的性能消耗，例如 Resolve 阶段消耗就很大，过程中还有大量的必要变量缓存的计算也会带来一定消耗。而考虑到健壮和可读性，物理引擎代码的写法和缓存的用法也不会过于激进。

在某些项目——比如轻量化的 RPG、MMO、FPS 中，我们很多时候需要的是高效碰撞和修正，而并不需要完全真实的物理模拟效果（如果只需要简单重力效果或者碰撞效果，通常直接自己实现模拟）。

因此，98K 在算法、写法、缓存上对物理引擎几大模块进行了优化，使之更加精简高效。经过一系列的评估，98K 最终采用了以下方案：

• 优化1：八叉树，筛选物体

• 优化2：kdtree，筛选三角形

• 优化3：几何体，筛选三角形

• 优化4：GJK + EPA，筛选和计算

选用八叉树和 kdtree 做优化，不仅是因为它们性能较好，还因为它们可以为射线检测加速做支持，所以 98K 也实现了高性能的射线检测系统。

资源链接

• 点击文末【阅读原文】下载源码

https://store.cocos.com/app/detail/4035

• 在线试玩（注：该 Demo 性能并不是最优，最新优化工程的运行性能要快1倍以上）

http://www.cocospro.com/98K/

限于篇幅，98K 中定制的 octree、kdtree、GJK/EPA 的实现过程和优化细节就不在本文展开了，可以先参看实际源码，后续有机会再详细展开分析，同时欢迎大家试用、反馈和提供好的建议。

往期精彩