引言:碰撞检测是游戏开发中一个非常重要的技术点,优化碰撞检测性能,是提升游戏体验不可或缺的一环。开发者「我叫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 的实现过程和优化细节就不在本文展开了,可以先参看实际源码,后续有机会再详细展开分析,同时欢迎大家试用、反馈和提供好的建议。
往期精彩
文章来源:https://www.toymoban.com/news/detail-772976.html
文章来源地址https://www.toymoban.com/news/detail-772976.html
到了这里,关于深入分析物理引擎后,他写了一个轻量的 Cocos 3D 碰撞检测优化方案的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!