引言：碰撞檢測是游戲開發(fā)中一個非常重要的技術(shù)點，優(yōu)化碰撞檢測性能，是提升游戲體驗不可或缺的一環(huán)。開發(fā)者「我叫98K」寫了一個輕量碰撞系統(tǒng)，用以改善 3D 游戲在不同平臺遇到的碰撞性能問題和包體問題。下載和在線體驗地址見文末。

98K物理-輕量碰撞系統(tǒng)是一個高性能輕量?3D 碰撞管理器，適用于 Cocos Creator 3.4 及以上版本，對?Mesh?模型和基本幾何體提供高效的碰撞系統(tǒng)和射線檢測系統(tǒng)，以提升游戲在不同平臺上的 3D 碰撞檢測性能，減少包體大?。ㄓ绕涫?H5 平臺）。

先通過在線體驗，看幾組應(yīng)用效果：

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

場景1，碰撞測試

場景1，1000射線測試

場景2，碰撞測試

場景2，1000射線測試

本文主要和大家詳細介紹 98K 中最為重要的自定義碰撞系統(tǒng)的功能與使用、及其實現(xiàn)思路與技術(shù)要點，感興趣的小伙伴可以深入了解。

功能特點

98K 的主要功能特點有：

• 多物體場景管理：Octree，對場景物體進行高效劃分查詢。

• 模型三角化管理：Kdtree，對物體表面進行高效劃分查詢。

• 通用 3D 碰撞計算：GJK+EPA，精確計算修正碰撞后的物體。

• 3D 角色控制器：3D 物體在場景碰撞系統(tǒng)下的自由移動。

• 高效射線檢測：基于 Octree 和 Kdtree 對射線檢測加速。

我們在 H5 環(huán)境下，對比 98K 和 Bullet，PhysX（由于 Cannon 對 mesh collider 支持不完善，不參與比較）。

雖然和 Bullet、PhysX?相比，98K 的功能還不夠全面，但是在需要使用 3D 碰撞檢測和射線檢測的 MMO、SLG、FPS?等 3D 場景的游戲中，目前 98K 提供的功能已經(jīng)可以滿足需求，并且 98K 更加輕量，使用也更簡單一些，可以替代 Bullet、PhysX。

使用方法

前一段時間孫二喵制作的?3D 跑酷游戲?Demo 就使用了 98K，我們以此為例，看看這一系統(tǒng)在實際游戲項目中的使用方法與效果。

源碼下載：

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

在線體驗：

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

該游戲場景超過100萬面，而且地形較不規(guī)則，使用 Bullet+Mesh Collider 整體開銷會比較高，所以孫二喵使用了 98K，以獲得更好性能。

相對于 Bullet Mesh Collider 初始化滿和設(shè)置麻煩的缺點，98K 的 Mesh Collider 可以說是鍵設(shè)置。

我們可以制作1個小腳本，在編輯器環(huán)境下，給所有的 Mesh 都加上 98K 的碰撞組件。

然后把所有有 Object3D 碰撞組件的物體都加到我們的主場景下面。

進入場景后，再進行構(gòu)建。

后續(xù)有需要增加和刪減碰撞體，也可以通過 World 里的方法進行操作。

同時 98K 也提供了射線檢測功能。我們可以通過射線檢測地面，來處理跳躍等邏輯。

98K 的另外一個特點是使用了簡單的數(shù)學(xué)公式，這部分可以進行定點數(shù)的處理，方便聯(lián)機游戲處理幀同步，目前也已經(jīng)有開發(fā)者進行了二次開發(fā)。

技術(shù)要點

接下來簡單介紹一下 98K 中自定義碰撞系統(tǒng)的技術(shù)實現(xiàn)要點，以及我選擇現(xiàn)在這個優(yōu)化方案的思路與原因。

在造輪子前，得先了解輪子是怎么構(gòu)成，才能更好的去改造。

功能分層結(jié)構(gòu)圖

物理引擎進行碰撞檢測的基本流程包含三個環(huán)節(jié)：

• Board-Phase（粗略篩選碰撞對）

• Narrow-Phase（精確計算碰撞對）

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

Board-Phase

Board-Phase 的目標(biāo)是快速排除掉不可能發(fā)生碰撞的物體對，以此提高后續(xù)碰撞檢測的效率?？臻g劃分是這一階段最重要的部分。在游戲開發(fā)中，我們常用各種空間數(shù)據(jù)結(jié)構(gòu)來加速計算。

多叉樹：四叉樹與八叉樹

四叉樹

四叉樹是很常見的一種 2D 碰撞檢測方法，實現(xiàn)手段也五花八門。不過在具體實現(xiàn)中要注意優(yōu)化細節(jié)，控制建樹時間消耗與建樹空間大小，特別是在 JS 語言環(huán)境下。但四叉樹的射線檢測、區(qū)域檢測效率比較高，樹更新很快，會產(chǎn)生物體多次劃分，空間占用大。

八叉樹

八叉樹雖然包圍精確性沒 BVH 高（可用狀態(tài)壓縮改善）、占用空間較大（過度劃分），但是建樹和增刪非常快，很適合用作物體的篩選。目前 98K 使用了八叉樹對模型包圍盒進行空間劃分，簡單高效的建樹比精確計算建樹（比如 BVH 建樹會有大量計算消耗）更加劃算。缺點和四叉樹一樣，射線檢測、區(qū)域檢測較快，樹更新很快， 會產(chǎn)生物體多次劃分，空間占用大。

二叉樹：BVH，BSP，k-d

BVH

四叉樹和八叉樹是以平均空間來劃分物體，劃分算法簡單，而 BVH 是對當(dāng)前物體集合進行空間的劃分，追求左右空間大小相對均衡且無相交。BVH 構(gòu)建的一般是二叉樹，劃分算法復(fù)雜。

主流物理引擎都有采用 BVH，因為其功能支持完備、查找精確性高、性能不俗。但是其在建樹和增刪改時要維護平衡樹，消耗很大。針對這個問題，有一些時序性的空間優(yōu)化方法，通過減少增刪改達到優(yōu)化目的，感興趣的朋友可以參考各大物理引擎中的實現(xiàn)方法。

BSP

BSP（Binary Space Partitioning Tree），二維空間分割樹，非常經(jīng)典，1993年在知名游戲 DOOM 里第一次被應(yīng)用，早期 CS 也是用 BSP 來做地形碰撞。BSP 通常通過計算得到一個合理的任意角度片面或者法線，然后對空間進行劃分。標(biāo)準(zhǔn)的 BSP 雖然高效，但樹構(gòu)建非常消耗時間，通常都是編輯器預(yù)處理，比較適合靜態(tài)模型或者靜態(tài)場景使用。

k-d 樹

k-d 樹是一種特殊的 BSP 樹，它基于動態(tài)計算的三個軸進行劃分。k-d 樹相比 BSP 可能精確性沒那么高，但是建樹時間大大減少，因為對軸劃分算法簡單，所以很適合使用。目前 98K 用 k-d 樹方式來維護模型的三角形數(shù)據(jù)，用于碰撞和射線檢測。

其他：SAP

SAP

SAP（Sweep And Prune) 又稱為掃掠法，也是物理引擎的一種常用碰撞檢測方式。SAP 比較輕便，增刪改比較快，物體不會被多次劃分，對靜態(tài)模型是非?？?。它唯一缺點是性能不太穩(wěn)定，每次只能對單個軸進行掃描，有時會有大量物體投影重疊，導(dǎo)致查詢不穩(wěn)定。而且射線檢測和區(qū)域檢測，需要額外的擴展來優(yōu)化，性能也一般，沒上面各種樹結(jié)構(gòu)的方便和高效。

Narrow-Phase

在這個階段，我們需要對篩選后的這些可能發(fā)生的碰撞進行精確計算，判定他們是否發(fā)生了碰撞，如果發(fā)生碰撞，還需計算出碰撞點、碰撞法線等細節(jié)。

幾何計算

數(shù)學(xué)方法，從分離角度來判斷碰撞，一般用于常見的幾何圖形之間的碰撞計算，速度非?？?。良好的物理引擎必不可少這些數(shù)學(xué)方法，各大引擎都能找到它們的身影。

GJK + EPA

凸包算法，從重疊角度來探索碰撞。GJK 的原理核心是，當(dāng)兩個物體發(fā)生重疊時，它們必然有一個坐標(biāo)相減為原點。GJK 檢測出碰撞后，再用 EPA 在 GJK 構(gòu)建的數(shù)據(jù)下，進一步計算出穿透的距離碰撞點和碰撞法線。

基本上主流物理引擎都有使用 GJK+EPA，和前面幾何數(shù)學(xué)方法混合使用，可以大幅提升碰撞計算性能。98K 也是同時混合使用以上兩種方法，支持基本幾何模型計算，也能支持三角化 mesh 或者凸包化 mesh 的計算。

Resolve-Phase

在上一個階段，我們已經(jīng)確定了是否發(fā)生碰撞和碰撞的細節(jié)，最后階段即是修正他們的位置和速度。這一過程非常耗時，目前 98K 只提供了簡單高效的修正處理，更多重心還是放在解決現(xiàn)有的碰撞性能問題上。

98K 優(yōu)化方案

物理引擎是一套復(fù)雜完整的過程，沒辦法在功能上做分割，所以一定程度上會造成不必要的性能消耗，例如 Resolve 階段消耗就很大，過程中還有大量的必要變量緩存的計算也會帶來一定消耗。而考慮到健壯和可讀性，物理引擎代碼的寫法和緩存的用法也不會過于激進。

在某些項目——比如輕量化的?RPG、MMO、FPS?中，我們很多時候需要的是高效碰撞和修正，而并不需要完全真實的物理模擬效果（如果只需要簡單重力效果或者碰撞效果，通常直接自己實現(xiàn)模擬）。

因此，98K 在算法、寫法、緩存上對物理引擎幾大模塊進行了優(yōu)化，使之更加精簡高效。經(jīng)過一系列的評估，98K 最終采用了以下方案：

• 優(yōu)化1：八叉樹，篩選物體

• 優(yōu)化2：kdtree，篩選三角形

• 優(yōu)化3：幾何體，篩選三角形

• 優(yōu)化4：GJK?+?EPA，篩選和計算

選用八叉樹和?kdtree?做優(yōu)化，不僅是因為它們性能較好，還因為它們可以為射線檢測加速做支持，所以?98K?也實現(xiàn)了高性能的射線檢測系統(tǒng)。

資源鏈接

• 點擊文末【閱讀原文】下載源碼

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

• 在線試玩（注：該 Demo 性能并不是最優(yōu)，最新優(yōu)化工程的運行性能要快1倍以上）

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

限于篇幅，98K 中定制的 octree、kdtree、GJK/EPA 的實現(xiàn)過程和優(yōu)化細節(jié)就不在本文展開了，可以先參看實際源碼，后續(xù)有機會再詳細展開分析，同時歡迎大家試用、反饋和提供好的建議。

往期精彩

文章來源地址http://www.zghlxwxcb.cn/news/detail-772976.html