【USparkle專欄】如果你深懷絕技，愛“搞點研究”，樂于分享也博采眾長，我們期待你的加入，讓智慧的火花碰撞交織，讓知識的傳遞生生不息！

這是侑虎科技第1977篇文章，感謝作者南京周潤發供稿。歡迎轉發分享，未經作者授權請勿轉載。如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群：793972859）

作者主頁：

https://www.zhihu.com/people/xu-chen-71-65

射線檢測接口

游戲業務常見的需求就是做各種射線檢測/Overlap檢測/Sweep檢測，比如Character Movement Component。

下面例子是使用Visibility Channel做Line Trace，StaticMesh對其是Block的。

各種Trace，最終都調用到SceneTrace。

使用的TraceChannel，ObjectType等條件，最終都編碼成四個4B的Word，下面是TraceChannel的例子。

物理查詢，主要就是對AABB Tree的查詢。

SceneTrace

ReadLock

要對物理場景做查詢，首先加讀鎖。可以和其他Trace請求同時執行，但和寫物理場景操作互斥。

然后獲取加速結構Collection，里面有Static AABBTree和Dynamic AABBTree。

最后進到TSpatialAccelerationCollection::RaycastFast。

這里Types就是Buckets，TypeIdx是從0開始的下標，會逐個遍歷Buckets，然后對里面的每個AABBTree，調用RaycastFast函數。

注意第一個Bucket存了非常大的AABB，也就是說如果場景內有很多大的物體，是會拖慢射線檢測效率的。

TAABBTree::QueryImpl

比較大的函數，做AABBTree的遍歷。

AABBTree非葉節點的遍歷

經典的BVH檢測方式，先檢查射線和左右子樹AABB是否相交，然后根據相交情況，不斷對左右子樹做遍歷。加速方式為SIMD的應用，以及非遞歸的遍歷AABBTree。

示意圖如下：

SIMD版本的Slab算法值得一看，判斷射線與AABB是否相交，并計算射線在AABB內經過的距離。全程無if...else...。

里面的VectorMax和VectorSwizzle的組合比較巧妙，用于在三個數中取最大的。

Slab算法簡介

Slab算法（Slab Method）是計算機圖形學和物理引擎中用于檢測射線（Ray）與軸對齊包圍盒（AABB）是否相交的最經典、最高效的算法。

它的核心思想非常簡單直觀：將3D的AABB盒子看作是三組無限大的“平板對”（Slabs）的交集。

假設射線的起點為P，方向為Dir，把射線寫成時間t的方程：

射線進入每個“平板對”，都會有進入時間t0和離開時間t1，如果要與AABB發生重疊，三組t0和t1必定有都重疊的部分。

示意圖如下：

處理葉節點

對于一個Leave節點，射線檢測會執行RaycastFastSimd。

每個Leave節點默認最多有8個Element，它們沒有位置關系，因此要逐個對這些Element做射線檢測了。

對于Leave中的一個Element，計算和射線是否相交，會經過三道判斷。第一道是檢查Shape的AABB和射線是否相交，第二道是檢查Shape的Channel和QueryChannel是否是Overlap或者Block關系，第三道是真正檢查射線和Sphere、Box、凸包等幾何體是否相交。前兩道是輕量的，算BroadPhase，第三道很重，是NarrowPhase。

把Channel Response檢查放到中間也是挺有意思的。按照正常人類思考邏輯，應該是射線碰到一個Geometry后，再判斷這個Geometry對射線Channel響應是Block還是Overlap，但判斷射線和Shape相交的操作比較重，尤其是面對凸包。因此從代碼效率邏輯出發，就變成了不管Shape和射線是否真的相交，先判斷Geometry對Channel的響應，如果是Ignore，就直接不管了。具體做法如下：

第一道，射線和AABB Bounds檢查是否相交。

同樣的，用SIMD判斷射線和AABB是否相交，不再贅述。

第二道，射線檢測用的Channel和Geometry的ResponseChannel & BlockChannel是否有重疊。

ResponseChannel & BlockChannel是兩個int32，本身是每個Geometry的屬性，但AABBTree為了效率，在Payload里都緩存了一份，為UnionQueryFilterData和UnionSimFilterData，CachedUniqueIdx則是所屬UObject的UniqueIdx緩存。

具體的Channel Response過濾方法。

PrePreQueryFilter

首先從Word0中獲取射線檢測使用的Channel，然后檢查Geometry自身的Word1和Word2，分別是BlockingChannel和OverlapChannel，做bit and操作，看是否有交集。

注意這里的函數名是PrePreQueryFilter，說明后面還有PreQueryFilter流程。

射線和各種幾何體相交判斷

第三道，真正的射線和幾何體相交檢測。

PreQueryFilter

幾何檢測前，先執行一些自定義邏輯的Filter做過濾，判斷是否要做對Shape的射線檢測，可以做游戲業務相關的操作。注意到例子中的射線檢測是按照LineTrace BlockChannel做的，但目前OverlapChannel的Shape也還沒被排除，排除操作就是在PreQueryFilter階段做的，實際會調用FCollisionQueryFilterCallback::PreFilterBaseImp函數。

首先對比查詢的Channel，和Shape的OverlapChannel & BlockingChannel，判斷這次查詢是Touch還是Block，稱為CollisionQueryHitType。

如果是LineTraceSingle，那么只關心BlockingChannel，TouchChannel的Shape可以忽略。

查詢的Touch/Block和Shape的ResponseChannel比對通過后，再判斷IgnoreActors和IgnoreComponents是否需要過濾，LineTrace時通常會設置IgnoreActors。

FCollisionQueryFilterCallback::PreFilter檢查通過后，正式進入射線和幾何體相交計算。

世界空間坐標和Geometry局部空間坐標

此時射線的起點和方向都是世界坐標，在檢測前先變換到Geometry的坐標空間，后面計算起來會更加方便。比如對Box檢測時，直接用AABB射線檢測算法即可。

射線和不同幾何體相交計算

這里不僅要判斷是否相交，還要得到射線接觸的位置，初次接觸幾何體的距離，以及接觸點的法線。每個幾何體都實現了Raycast函數，觀察不同幾何體的實現。

TSphere

球形判斷是最簡單的。

令直線起點為P，方向為dir，直線方程為：

設圓心為C，半徑為R，直線和圓相交，需要滿足以下方程：

這是關于t的一元二次方程，用公式求出t即可。

有了時間t，就能快速求出交點坐標和交點法線了。

Tbox

最終執行的AABB，計算開銷比球體高些。

對于三組Slab，都分別計算進出時間t0、t1，然后取交集，得到時間t，再得到交點。法線總是XYZ三個方向，計算t0屬于哪個面即可。

FCapsule

Capsule可以想象成，到線段最短距離為r的點，形成的距離場，線段作為Capsule的軸心。

那么判斷射線和膠囊體是否相交，計算這個軸心線段到射線的最短距離即可，具體計算上，需要找出一對距離最近的點。

真正困難的地方在于，線段上的最近點，位于線段中間。直接貼一個已有算法，核心是找出兩個平面的相交線，理解起來需要點時間，但計算步驟并不多。

參考：

https://johnmayhk.wordpress.com/2012/02/02/shortest-distance-between-two-skew-lines/

如上所示，最短距離就是BD在MN上投影的長度，而MN同時垂直AB和CD，另外ABXCD得到的向量也同時垂直AB和CD，因此MN與（ABXCD）平行。由此可得到最短距離。

有了距離，就能解出兩個點了。

UE也實現了這個算法，封裝于SegmentDistToSegmentSafe函數，主要步驟如下：

當射線與Capsule相交后，還需要進一步求交點和normal。

分兩種情況：

1. 與上下兩個半球相交，normal從球心出發

2. 與中間圓柱體相交，計算圓柱體的normal

FConvex凸包

最復雜，使用了GJK算法，不再展開

和Shape發生碰撞后怎么辦？

當前的Hit類型是ChaosInterface::FLocationHit，先填充Hit的這幾個屬性：

之后再給個機會執行FCollisionQueryFilterCallback::PostFilter，如處理bDiscardInitialOverlaps過濾等。

然后把Time作為Distance記下，表示射線已經打了多遠，對后續Shape做射線檢測時，將從最新的Distance開始，繼續往后打射線。

回到AABB子樹的遍歷，如果要判斷多個子樹，但射線在之前已經Block了，就不用判斷之后的子樹了。

FHitResult的填充

FHitResult展開后有如下屬性，其中大部分在之前射線發生碰撞時已經可以得到，只有黃線畫出的幾個需要看下如何獲取。

PhysMat

命中點的物理材質，物理材質可以理解為類似渲染用的材質，只不過描述的是物體表面的摩擦力、密度等屬性。當前已經有了FaceIndex，而Geometry中記錄了FaceIndex和PhysicsMaterial的對應關系，因此可以得到PhysicsMaterial。

BoneName

命中點所屬骨骼的名稱。

對于示例中的StaticMesh，是沒有骨骼的，因此是None，只有對于SkeletalMesh，這個BoneName才有意義。

觀察SkeletalMesh的PhysicsAsset，多個骨骼上會掛接RigidBody，它們有各自對應的BodySetup，BoneName就存在BodySetup里。射線檢測時，可以根據命中的GeometryParticle獲取到BodyInstance，再獲取到BodySetup，最終得到BoneName。

HitItem & ElementIndex

都屬于一些Extra數據，不太重要。

HitItem是BodyInstance在整個PhysicsAsset中的序號，針對SkeletalMesh的情況。ElementIndex是Trace中Shape在Geometry的Shape數組中下標。對于示例中的StaticMeshComponent，它們都是0。

完整的LineTrace流程如下：

Overlap檢測

第二種碰撞檢測是Overlap檢測，比LineTrace更復雜些，會判斷一個體積內有沒有和其他物體相交。這里以Box碰撞體為例，需要傳入Box的位置和大小，區別于之前的LineTrace使用TraceChannel，這里使用了ObjectTypes，查詢Box范圍內重疊的其他Actor。但對于物理引擎而言，TraceChannel和ObjectTypes本質都是一樣的，都是CollisionChannel。

首先，把查詢的Geometry計算一個AABB包圍盒，傳入AABBTree做BroadPhase的檢測。

AABBTree的左右子樹Overlap

對左右子樹分別做AABB的碰撞檢測。

Leaf節點的處理

TAABBTreeLeafArray.OverlapFast

對Leaf中每個Payload Geometry，同樣先做AABB碰撞檢測。用了SIMD技術，四個Payload為一組。當AABB檢測通過后，依然先執行PrePreFilter，做Channel之類的判斷，再針對具體的Geometry Shape形狀，做Narrow Phase的Overlap檢測。

Shape可以有Sphere、Box、Capsule、凸包等各種幾何形狀，但它們都屬于凸包。要判斷兩個凸包是否Overlap，就要用GJK算法，UE的實現是GJKIntersection函數，自然也是SIMD實現。

GJK算法

關于GJK算法的詳細介紹，可以看這里：

看似簡單的復雜問題，奇怪而優雅的解決方式（GJK算法）

https://www.bilibili.com/video/BV16P4y1q7GZ/?spm_id_from=333.337.search-card.all.click&vd_source=43d3ce94d2854f1bf3d667631d4a0e98

總體過程是不斷通過Support函數，在兩個凸包上找一對點，計算閔可夫斯基差，然后讓形成的三角形包含原點。GJK算法有點復雜，不展開了，但不同Shape的Support函數實現可以看下，具體就是每個Shape的SupportCore函數。

所謂Support函數，就是給定一個方向，找到Shape在這個方向上最遠的一個點，下圖就是兩個例子。

簡單起見只看SupportCore普通版本，SIMD版本思想類似。

TBox

等價于對一個AABB求Support點。不難理解，AABB在某個方向上的最遠點必定是8個頂點之一，因此只要依次判斷三個軸，做三次方向二分即可，2^3 = 8。

TSphere

最簡單，球的中心加上半徑*方向即可。

FCapsule

看似復雜，實則和Sphere一樣簡單。Capsule的Support點必定出現在兩個半球上，因此首先根據Direction方向確定是哪個半球，然后類似Sphere處理即可。

FConvex

需要遍歷所有凸包的頂點，與方向做點乘，找到最遠的點。

這里實現也比較有意思，尋找凸包的Support點，理論上用啟發式的“爬山法”更快，即從上個Support點往后找鄰接點，不用遍歷所有頂點，而且UE是保存了邊的連接關系的：

那為什么不用爬山法？個人猜測是以下幾個原因：

• 直接遍歷Vertices數組，CPU Cache更友好，在頂點數量不多（也是大部分情況）情況下可能更快。

• 爬山法需要記錄上一次的Support點序號，但碰撞檢測可能多個線程并行，這樣就需要為每個線程都記錄一份上次的Support點了，實現有點麻煩，而且得保證線程安全。

如果要得到Overlap深度，就要使用GJKPenetration算法， 結合了GJK與EPA，這里不展開了。

Sweep檢測

最復雜的情況，以Box Sweep為示例，會得到Sweep路徑上發生重疊的物體。

BroadPhase

類似Overlap，但把Sweep經過的整個路徑，作為AABB，查詢與左右子樹的碰撞情況。

NarrowPhase

對于Leaf節點中的每個Geometry，同樣經過PrePreFilter，AABB檢測，PreFilter。

對Geometry中每個Shape的Sweep檢測，最后依然使用GJK算法。

如果是TriangleMesh復雜碰撞怎么辦？

首先，Shape就變成了FTriangleMeshImplicitObject，類似Mesh，沒有凸包的限制，可以表示任何形狀。因此，類似GJK這種精妙的幾何碰撞算法都不再適用，只能回歸最原始的三角形相交判斷。

Raycast & Overlap & Sweep

BroadPhase相同，使用AABBTree。

NarrowPhase不使用GJK算法了，而是每個TriangleMesh自己有一個BVH樹，用BVH的碰撞檢測方式。BVH子節點存儲了三角形，在檢測子節點內部碰撞時，采樣逐三角形檢測方式。

比如這個例子，BVH樹有379個節點，模型總共有5760個面，還是非常復雜的。

Tips

綜合上述碰撞檢測流程，可以對物理場景優化做一些指導：

• 游戲中物體都設置專門的Simple Collision，避免查詢復雜碰撞

• Shape的碰撞檢測效率排序：Sphere > Capsule > Box >> Convex >>>> Triangle Mesh，盡量用效率高的Shape做近似

• 避免太長的LineTrace，以及范圍太大的Overlap和Sweep

• LineTrace查詢的開銷最低，玩法上盡量用它

文末，再次感謝南京周潤發的分享， 作者主頁：https://www.zhihu.com/people/xu-chen-71-65， 如果您有任何獨到的見解或者發現也歡迎聯系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧