1. 項目概述為什么GJK算法是碰撞檢測的“硬核”選擇在Unity或Unreal Engine里做游戲碰撞檢測是繞不開的基礎。Unity自帶的Collider組件和Unreal的Collision組件用起來很方便點幾下鼠標兩個物體就能“砰”地一聲撞在一起。但當你需要處理自定義形狀、高速運動的物體或者想實現更精確的物理反饋時內置的近似檢測比如用包圍盒就可能不夠用了。你會發現兩個形狀明明沒有相交系統卻報告了碰撞或者高速子彈“穿”過了薄墻。這時候你就需要深入到幾何層面自己來實現一套精確的、支持凸多面體的碰撞檢測算法。而GJKGilbert–Johnson–Keerthi算法就是解決這個問題的“行業標準”答案。GJK算法聽起來很高深但它的核心思想卻異常巧妙它不直接計算兩個形狀是否相交而是通過一種叫做“閔可夫斯基差”的幾何操作將“兩個形狀是否相交”的問題轉化為了“一個點是否在另一個形狀內部”的問題更具體地說是判斷原點是否在閔可夫斯基差集內部。這個轉換是理解GJK的關鍵。算法本身則通過一種迭代尋找“支撐點”的方式在閔可夫斯基差集內部構建一個不斷逼近原點的單純形在2D中是三角形3D中是四面體從而高效地判斷出分離或相交。它的優勢在于對于凸體其計算復雜度與頂點數無關只與迭代次數有關因此非常高效被廣泛應用于從物理引擎到機器人學的各個領域。如果你正在開發一款需要自定義碰撞體比如一個復雜的飛船模型、實現布娃娃物理的精確關節碰撞或者優化AR/VR中虛擬物體的交互理解并實現GJK算法將讓你從“引擎使用者”變為“系統構建者”。本文將從零開始拆解GJK算法的每一步并提供可直接在UnityC#和Unreal EngineC中運行、調試的實戰代碼。我會分享我在實現過程中踩過的坑比如單純形退化、數值精度問題以及如何與EPAExpanding Polytope Algorithm算法結合獲取碰撞深度和法線讓你不僅能檢測到“是否碰撞”還能知道“撞得多深、從哪個方向撞的”。2. GJK算法核心原理深度拆解要理解GJK我們不能只停留在調用API的層面必須深入其幾何原理。這就像學開車不僅要會踩油門和剎車還得知道發動機和變速箱是怎么工作的這樣車壞了你才知道怎么修。2.1 從問題轉換開始閔可夫斯基差Minkowski Difference這是GJK算法的基石。給定兩個凸集形狀A和B它們的閔可夫斯基差集定義為A ? B { a - b | a ∈ A, b ∈ B }。通俗地講對于形狀A中的每一個點a減去形狀B中的每一個點b得到的所有可能結果構成的集合就是閔可夫斯基差集。這個操作的魔力在于一個關鍵性質如果兩個凸集A和B相交那么它們的閔可夫斯基差集必然包含原點0, 0, 0。反過來如果原點在差集內部那么A和B一定相交。如果原點不在差集內部那么A和B就是分離的并且從原點到差集最近點的向量就是它們的分離軸的負方向。注意這里說的“內部”包括邊界。也就是說如果兩個形狀剛好相切原點就在差集的邊界上。通過這個轉換我們就把一個“兩個形狀的關系”問題變成了一個“點和單個形狀的關系”問題。而判斷一個點原點是否在一個凸集中GJK提供了一種極其高效的迭代方法。2.2 算法的引擎支撐函數Support Function支撐函數是GJK迭代的“燃料”。對于一個凸形狀C和一個給定的方向向量d支撐函數Support(C, d)返回的是形狀C在方向d上最遠的點。數學表達是Support(C, d) argmax_{v ∈ C} (v · d)即點積最大的那個點。為什么需要它因為我們要在閔可夫斯基差集我們稱之為M中尋找點。根據定義M A ? B。那么M在方向d上的支撐點Support(M, d)可以通過分別計算A和B的支撐點來高效獲得Support(M, d) Support(A, d) - Support(B, -d)。這個性質太重要了它意味著我們不需要顯式地、耗費巨大資源去計算和存儲整個閔可夫斯基差集那可能是一個無限點集我們只需要知道原始形狀A和B的支撐函數就能動態地得到M在任意方向上的邊界點。在實現中為你的碰撞體實現一個高效的支撐函數是第一步。對于多邊形/多面體就是遍歷所有頂點找點積最大的。對于球體、膠囊體等則有解析解速度更快。2.3 迭代與終止單純形Simplex和包含判斷GJK算法通過迭代構建一個“單純形”來逼近原點。單純形是所在空間中最簡單的幾何體在2D中是線段、三角形在3D中是線段、三角形、四面體。算法流程可以概括為以下步驟我結合一個2D例子來說明這樣更直觀初始化選擇一個初始搜索方向d通常可以取兩個形狀中心點的向量差即d centerB - centerA。構建初始單純形它是一個包含單個點的集合這個點就是Support(M, d)。迭代循環 a.獲取新點根據當前搜索方向d通過支撐函數得到一個新點p Support(M, d)并將其加入單純形。 b.判斷方向計算點p到原點的向量點積p · d。如果p · d 0說明在當前搜索方向d上我們找到的支撐點p都無法讓單純形包含原點因為原點在d的相反側那么可以立即斷定原點不在M內即A和B分離。算法結束返回“無碰撞”。 c.更新單純形將新點p加入當前單純形。現在單純形可能包含2、32D或43D個點。我們需要判斷原點是否被這個新的單純形所“包圍”。 d.檢查包含這是GJK的核心子程序。我們需要判斷原點是否在當前單純形內部或邊界上。在2D中如果單純形是三角形我們就檢查原點是否在這個三角形內。同時更重要的是如果原點不在單純形內我們需要找到單純形中離原點最近的那個部分點、邊或面并丟棄單純形中遠離原點的點從而得到一個更小的、更靠近原點的單純形例如從三角形退化成包含原點的邊。然后基于這個新的、更小的單純形計算出一個新的搜索方向d這個方向是從這個最近的部分指向原點。 e.循環條件如果通過檢查發現原點已經在當前單純形內部對于2D三角形或3D四面體那么算法成功返回“碰撞”。否則用新的搜索方向d繼續下一次迭代。這個迭代過程就像是用一個不斷收縮的“網”去兜原點。每次迭代都朝著原點的方向優化這個網直到網住原點碰撞或者確定網不住分離。實操心得迭代次數需要設置一個上限比如32次防止在極端情況下如兩個幾乎平行且非常接近的面陷入無限循環。同時由于浮點數精度問題判斷“原點是否在單純形內”時需要引入一個很小的容差epsilon如1e-6。3. 實戰代碼解析從理論到可運行的C#/C理解了原理我們來看代碼。我會分別給出Unity (C#) 和 Unreal Engine (C) 的核心實現框架。為了聚焦于GJK本身我們假設碰撞體都是凸多邊形2D或凸多面體3D并用頂點列表表示。3.1 C#實現Unity版本在Unity中我們通常將GJK實現為一個靜態工具類。首先我們需要定義支撐函數和向量運算。using UnityEngine; using System.Collections.Generic; public static class GJKAlgorithm { // 容差用于處理浮點數精度 public const float EPSILON 1e-6f; // 支撐函數對于給定方向dir返回凸體vertices中點積最大的頂點 public static Vector3 Support(ListVector3 vertices, Vector3 dir) { float maxDot Mathf.NegativeInfinity; Vector3 supportPoint Vector3.zero; foreach (var vertex in vertices) { float dot Vector3.Dot(vertex, dir); if (dot maxDot) { maxDot dot; supportPoint vertex; } } return supportPoint; } // 閔可夫斯基差支撐點 public static Vector3 MinkowskiSupport(ListVector3 verticesA, ListVector3 verticesB, Vector3 dir) { Vector3 pointA Support(verticesA, dir); Vector3 pointB Support(verticesB, -dir); // 注意方向取反 return pointA - pointB; // A - B } // 核心GJK碰撞檢測函數 public static bool CheckCollision(ListVector3 verticesA, ListVector3 verticesB) { // 1. 初始化方向取中心差簡單有效 Vector3 centerA CalculateCenter(verticesA); Vector3 centerB CalculateCenter(verticesB); Vector3 d centerB - centerA; if (d.sqrMagnitude EPSILON) d Vector3.right; // 如果中心重合給一個默認方向 // 2. 初始化單純形列表 ListVector3 simplex new ListVector3(); Vector3 a MinkowskiSupport(verticesA, verticesB, d); simplex.Add(a); // 搜索方向取反指向原點 d -a; // 3. 開始迭代 int maxIterations 32; for (int i 0; i maxIterations; i) { Vector3 p MinkowskiSupport(verticesA, verticesB, d); // 如果新支撐點在d方向上的投影小于0則原點不可能在M內 if (Vector3.Dot(p, d) EPSILON) { return false; // 分離 } simplex.Add(p); // 調用子函數處理單純形并更新搜索方向d if (HandleSimplex(ref simplex, ref d)) { return true; // 碰撞 } } // 達到最大迭代次數通常視為未碰撞或需要更復雜的處理 Debug.LogWarning(GJK reached max iterations.); return false; } // 處理單純形這里是2D版本的核心3D版本更復雜 // 返回true表示原點在單純形內碰撞否則更新simplex和d private static bool HandleSimplex(ref ListVector3 simplex, ref Vector3 d) { // 此函數需要根據單純形點數1,2,3分別處理 // 由于篇幅這里給出2D情況下的邏輯示意3D需要實現包含四面體的判斷 // 實際應用中建議使用成熟的幾何庫或參考標準實現如Bullet Physics中的GJK // 此處代碼為示意完整實現需補充 // 1. 當simplex有2個點線段時找到線段上離原點最近的點更新d為原點指向該最近點的方向。 // 2. 如果最近點是線段端點則丟棄另一個點simplex保留該端點。 // 3. 當simplex有3個點三角形時檢查原點是否在三角形內通過重心坐標或邊法線。 // 4. 如果在三角形內返回true碰撞。 // 5. 如果不在找到離原點最近的邊丟棄對面的頂點simplex退化為該邊并更新d。 // 偽代碼邏輯 if (simplex.Count 2) { /* 處理線段 */ } else if (simplex.Count 3) { /* 處理三角形 */ } return false; // 默認返回未包含 } private static Vector3 CalculateCenter(ListVector3 vertices) { Vector3 sum Vector3.zero; foreach (var v in vertices) sum v; return sum / vertices.Count; } }上面的HandleSimplex函數是GJK的精華也是難點。一個健壯的實現需要正確處理各種退化情況比如單純形共線。在3D中情況更復雜需要判斷原點相對于線段、三角形、四面體的位置。網上有許多開源實現如Bullet, Box2D的GJK::Evaluate函數可供深入研究。3.2 C實現Unreal Engine版本在Unreal Engine中我們利用FVector等內置類型。邏輯與C#版完全一致只是語法和API不同。// GJK.h #pragma once #include CoreMinimal.h #include GameFramework/Actor.h #include GJK.generated.h UCLASS() class MYPROJECT_API UGJKFunctionLibrary : public UBlueprintFunctionLibrary { GENERATED_BODY() public: // 判斷兩個凸體頂點數組是否碰撞 UFUNCTION(BlueprintCallable, Category Collision|GJK) static bool GJKCheckCollision(const TArrayFVector VerticesA, const TArrayFVector VerticesB); private: static FVector Support(const TArrayFVector Vertices, const FVector Direction); static FVector MinkowskiSupport(const TArrayFVector VerticesA, const TArrayFVector VerticesB, const FVector Direction); static bool HandleSimplex(TArrayFVector Simplex, FVector Direction); static FVector CalculateCenter(const TArrayFVector Vertices); }; // GJK.cpp #include GJK.h #include limits const float EPSILON 1e-6f; FVector UGJKFunctionLibrary::Support(const TArrayFVector Vertices, const FVector Direction) { float MaxDot -std::numeric_limitsfloat::max(); FVector SupportPoint FVector::ZeroVector; for (const FVector Vertex : Vertices) { float Dot FVector::DotProduct(Vertex, Direction); if (Dot MaxDot) { MaxDot Dot; SupportPoint Vertex; } } return SupportPoint; } FVector UGJKFunctionLibrary::MinkowskiSupport(const TArrayFVector VerticesA, const TArrayFVector VerticesB, const FVector Direction) { FVector PointA Support(VerticesA, Direction); FVector PointB Support(VerticesB, -Direction); return PointA - PointB; } bool UGJKFunctionLibrary::GJKCheckCollision(const TArrayFVector VerticesA, const TArrayFVector VerticesB) { // 初始化方向 FVector CenterA CalculateCenter(VerticesA); FVector CenterB CalculateCenter(VerticesB); FVector D CenterB - CenterA; if (D.SizeSquared() EPSILON) D FVector::ForwardVector; // 初始化單純形 TArrayFVector Simplex; FVector A MinkowskiSupport(VerticesA, VerticesB, D); Simplex.Add(A); D -A; const int32 MaxIterations 32; for (int32 i 0; i MaxIterations; i) { FVector P MinkowskiSupport(VerticesA, VerticesB, D); if (FVector::DotProduct(P, D) EPSILON) { return false; // 分離 } Simplex.Add(P); if (HandleSimplex(Simplex, D)) { return true; // 碰撞 } } UE_LOG(LogTemp, Warning, TEXT(GJK reached max iterations.)); return false; } // HandleSimplex 的實現是GJK的核心此處省略詳細代碼需參考標準幾何算法實現。 // 其職責與C#版本描述一致根據單純形點數判斷原點包含性并更新單純形和搜索方向。 bool UGJKFunctionLibrary::HandleSimplex(TArrayFVector Simplex, FVector Direction) { // 實現原點對線段、三角形、四面體的最近點計算和包含性判斷。 // 這是一個需要細致編碼的部分建議參考《Real-Time Collision Detection》或開源物理引擎。 return false; } FVector UGJKFunctionLibrary::CalculateCenter(const TArrayFVector Vertices) { FVector Sum FVector::ZeroVector; for (const FVector V : Vertices) Sum V; return Vertices.Num() 0 ? Sum / Vertices.Num() : Sum; }在Unreal中你可以將這個函數庫暴露給藍圖方便地在任何地方調用檢測兩個自定義形狀的碰撞。4. 超越布爾檢測用EPA算法獲取碰撞信息GJK算法高效地給出了“是否碰撞”的布爾答案。但對于物理引擎來說這遠遠不夠。我們需要知道碰撞的深度穿透距離和法線碰撞方向以便計算碰撞響應讓物體被“推開”。這時就需要EPAExpanding Polytope Algorithm算法作為GJK的搭檔。EPA算法的思路很直觀當GJK確認碰撞即原點在閔可夫斯基差集M內部后EPA以GJK終止時得到的那個包含原點的單純形一個位于M邊界上的多面體為起點。因為這個單純形在M內部但原點在它內部所以我們需要擴展這個多面體使其不斷膨脹直到它的各個面緊貼M的邊界。最終離原點最近的那個面其外法線方向就是碰撞法線原點到該面的距離就是穿透深度。EPA的步驟簡述如下初始化將GJK最后得到的單純形一個四面體作為初始多面體Polytope。尋找最近面計算多面體每個面三角形到原點的距離點乘法線找到距離最近的那個面。獲取支撐點以這個最近面的外法線方向為d調用支撐函數Support(M, d)得到M邊界上的一個新點。判斷收斂計算這個新點到該最近面的距離。如果這個距離與當前最近面距離的差值小于某個容差說明我們已經足夠接近M的邊界算法收斂。此時該最近面的法線和距離就是我們要的碰撞信息。擴展多面體如果未收斂則將新點插入多面體。這需要像增量構造凸包一樣刪除所有從新點看過去“可見”的舊面即新點在該面法線指向的正半空間然后用新點與這些被刪除面的邊界邊組成新的三角形面添加到多面體中。循環回到步驟2繼續尋找新的最近面。EPA的實現比GJK更復雜因為它涉及到凸包的面管理、拓撲結構的變化。同樣數值穩定性是關鍵需要小心處理共面、共線的情況。注意事項EPA在物體剛好接觸穿透深度為0或穿透很淺時可能不穩定。在實際物理引擎中通常會結合GJK/EPA用于深度穿透而對于淺穿透或接觸則采用其他方法如分離軸定理SAT的變種來獲取更穩定的接觸信息。5. 性能優化與工程化實踐將GJK/EPA集成到游戲引擎中不能只考慮算法正確性還必須考慮性能、易用性和健壯性。5.1 支撐函數的優化支撐函數的性能至關重要因為GJK/EPA的每次迭代都要調用它多次。對于多邊形/多面體如果頂點數很多每次遍歷所有頂點是O(n)。可以采用以下優化緩存和增量更新如果物體在旋轉可以緩存物體局部空間的支撐點然后通過變換矩陣快速計算世界空間的支撐點。對于凸體在給定方向上最遠的頂點往往是固定的幾個“極值點”。使用GJK/EPA專用的數據結構如“凸包”對象它預計算并存儲了頂點、邊、面信息支撐函數可以利用凸包的法線錐或預計算的極值方向來加速。對于基本圖元球、盒、膠囊必須使用解析解絕對不要用頂點列表模擬。球體Support(sphere, d) center radius * normalize(d)。AABB軸對齊包圍盒根據d的每個分量的正負選擇min或max頂點。OBB定向包圍盒將方向d變換到OBB的局部空間然后在局部空間使用AABB的支撐函數再將結果變換回世界空間。膠囊體支撐點在兩個半球中心連線的線段上加上半球半徑的偏移。5.2 數值魯棒性處理浮點數精度是幾何算法的天敵。容差Epsilon所有相等性判斷如點積是否為0、距離是否小于某值都必須使用容差。容差值不能太小否則失去作用也不能太大否則影響精度。通常取1e-6到1e-4之間根據你的世界尺度調整。退化單純形在GJK迭代中可能會產生共線或共面的點例如三個點幾乎在一條直線上。你的HandleSimplex函數必須能檢測并正確處理這種情況否則會導致搜索方向錯誤甚至除零錯誤。一種常見策略是當檢測到退化時主動給搜索方向一個微小的隨機擾動。EPA的收斂性EPA可能在某些病理情況下收斂很慢或失敗例如物體穿透極深且形狀復雜。必須設置最大迭代次數如50-100次并在達到上限時采用備選方案比如返回一個基于當前最近面的近似結果或者直接使用GJK最后的方向作為一個近似的碰撞法線。5.3 與引擎集成碰撞查詢與響應在Unity/Unreal中你通常不會完全替換內置的碰撞系統而是將其用于特定場合。自定義Collider組件在Unity中你可以創建一個CustomGJKCollider組件它掛載在GameObject上定義其凸體形狀頂點列表或基本圖元參數。在FixedUpdate中你可以遍歷其他同類組件執行GJK檢測。作為Broad Phase的補充GJK/EPA是精確的Narrow Phase算法。在大規模場景中你仍然需要Broad Phase如動態AABB樹、空間網格來快速篩選出可能碰撞的對象對只對它們執行昂貴的GJK/EPA計算。獲取碰撞信息后一旦EPA返回了穿透深度和法線你就可以計算碰撞響應了。最簡單的響應是“投影修正”將發生穿透的物體沿著碰撞法線方向移動穿透深度的距離。更復雜的物理響應則涉及動量、摩擦力的計算這需要結合物體的質量、速度等屬性。6. 常見問題與調試技巧實錄自己實現GJK/EPA調試是最大的挑戰。問題往往不是“不工作”而是“在某些奇怪的角度不工作”。6.1 問題排查清單現象可能原因排查步驟與解決方案算法總是返回“無碰撞”1. 初始方向錯誤或為零向量。2. 支撐函數實現錯誤返回的點不是最遠點。3. 頂點數據坐標系不統一一個用局部坐標一個用世界坐標。1. 打印初始方向向量確保其不為零。可以嘗試固定一個方向如(1,0,0)測試。2. 單獨測試支撐函數給定一個簡單形狀如正方形和一個方向手動計算并驗證返回值是否正確。3. 確保傳入GJK的所有頂點都在同一個坐標系通常是世界坐標系下。在Unity/Unreal中需要將模型本地頂點通過Transform.TransformPoint轉換到世界空間。算法有時返回碰撞有時不返回間歇性1. 浮點數精度問題容差設置不當。2.HandleSimplex函數中對退化情況處理不完善。3. 迭代次數不足復雜形狀在達到最大迭代次數前未收斂。1. 適當增大EPSILON如從1e-6調到1e-4觀察是否穩定。在判斷點積p·d 0時使用容差。2. 在HandleSimplex中添加大量日志打印每次迭代后的單純形頂點和搜索方向。觀察在出錯的那一步單純形是否出現了異常如點非常接近。3. 增加最大迭代次數如64并記錄達到迭代上限的情況。算法陷入無限循環1. 搜索方向d未能有效更新導致每次迭代都獲得相同的支撐點。2. 在原點恰好位于閔可夫斯基差集邊界時判斷邏輯可能振蕩。1. 強制設置循環上限如100并在達到上限時中斷返回“未碰撞”或“錯誤”。這是必須做的安全措施。2. 檢查HandleSimplex中當原點在邊上或面上時的邏輯。確保在這種情況下能正確判斷為“包含”并返回true。EPA返回的穿透深度為NaN或極大值1. 在計算三角形面積或四面體體積時出現除零錯誤共線/共面。2. EPA擴展時新加入的點未能有效擴展多面體導致最近面計算錯誤。1. 在計算法線、面積、體積前先檢查邊長、面積是否大于一個極小閾值如1e-10否則視為退化情況采用備用方向或直接返回上次有效結果。2. 可視化EPA的多面體。在每次迭代中將多面體的面繪制出來Unity用Debug.DrawLine, Unreal用DrawDebugLine觀察其擴展過程是否合理。6.2 可視化調試你的最佳伙伴在3D空間中調試幾何算法光靠打印日志是遠遠不夠的。必須將中間過程畫出來。繪制支撐點在每次調用MinkowskiSupport后用不同顏色在世界空間中畫出點A、點B以及它們的差點P。這能幫你確認支撐函數是否正確以及搜索方向是否合理。繪制單純形在GJK的每次迭代后繪制當前的單純形2D為線段/三角形3D為線段/三角形/四面體。用明顯的顏色如紅色標出單純形觀察它如何向原點收縮。繪制搜索方向從原點畫一條射線方向為當前的搜索方向d長度適中。這能直觀顯示算法正在朝哪個方向“尋找”邊界。繪制EPA多面體用線框模式繪制EPA迭代過程中的多面體。你可以看到它如何從一個四面體開始像吹氣球一樣膨脹直到貼合碰撞邊界。在Unity中使用Debug.DrawLine,Debug.DrawRay在OnDrawGizmos或Update中繪制。在Unreal中使用DrawDebugLine,DrawDebugPoint等函數通常在Tick或特定調試函數中調用。這些可視化工具能讓你瞬間定位問題所在效率遠超盲目修改代碼。6.3 一個實用的調試技巧從2D開始如果你對3D GJK/EPA的實現感到頭疼一個極其有效的策略是先在2D平面上實現并調試通過。2D的GJK判斷原點是否在三角形內和EPA擴展多邊形在概念上與3D完全一致但幾何處理簡單得多可視化也更容易你可以在XY平面上畫圖。將2D版本徹底調通理解每一個細節后再擴展到3D你會發現自己面對的不是一個全新的問題而只是一個增加了維度的問題很多邏輯可以類比遷移。這是學習復雜幾何算法的一條捷徑。實現一個健壯的GJK/EPA碰撞檢測系統是一項有挑戰但回報豐厚的工作。它不僅能解決你項目中特定的碰撞問題更能讓你對計算機圖形學、計算幾何和物理引擎的核心機制有深刻的理解。當你看到自己編寫的代碼讓兩個復雜的自定義形狀產生精確的碰撞反應時那種成就感是使用現成組件無法比擬的。希望這篇結合了原理、代碼和實戰經驗的指南能為你鋪平這條路。 GJK算法實戰：從原理到Unity/Unreal碰撞檢測實現
1. 項目概述為什么GJK算法是碰撞檢測的“硬核”選擇在Unity或Unreal Engine里做游戲碰撞檢測是繞不開的基礎。Unity自帶的Collider組件和Unreal的Collision組件用起來很方便點幾下鼠標兩個物體就能“砰”地一聲撞在一起。但當你需要處理自定義形狀、高速運動的物體或者想實現更精確的物理反饋時內置的近似檢測比如用包圍盒就可能不夠用了。你會發現兩個形狀明明沒有相交系統卻報告了碰撞或者高速子彈“穿”過了薄墻。這時候你就需要深入到幾何層面自己來實現一套精確的、支持凸多面體的碰撞檢測算法。而GJKGilbert–Johnson–Keerthi算法就是解決這個問題的“行業標準”答案。GJK算法聽起來很高深但它的核心思想卻異常巧妙它不直接計算兩個形狀是否相交而是通過一種叫做“閔可夫斯基差”的幾何操作將“兩個形狀是否相交”的問題轉化為了“一個點是否在另一個形狀內部”的問題更具體地說是判斷原點是否在閔可夫斯基差集內部。這個轉換是理解GJK的關鍵。算法本身則通過一種迭代尋找“支撐點”的方式在閔可夫斯基差集內部構建一個不斷逼近原點的單純形在2D中是三角形3D中是四面體從而高效地判斷出分離或相交。它的優勢在于對于凸體其計算復雜度與頂點數無關只與迭代次數有關因此非常高效被廣泛應用于從物理引擎到機器人學的各個領域。如果你正在開發一款需要自定義碰撞體比如一個復雜的飛船模型、實現布娃娃物理的精確關節碰撞或者優化AR/VR中虛擬物體的交互理解并實現GJK算法將讓你從“引擎使用者”變為“系統構建者”。本文將從零開始拆解GJK算法的每一步并提供可直接在UnityC#和Unreal EngineC中運行、調試的實戰代碼。我會分享我在實現過程中踩過的坑比如單純形退化、數值精度問題以及如何與EPAExpanding Polytope Algorithm算法結合獲取碰撞深度和法線讓你不僅能檢測到“是否碰撞”還能知道“撞得多深、從哪個方向撞的”。2. GJK算法核心原理深度拆解要理解GJK我們不能只停留在調用API的層面必須深入其幾何原理。這就像學開車不僅要會踩油門和剎車還得知道發動機和變速箱是怎么工作的這樣車壞了你才知道怎么修。2.1 從問題轉換開始閔可夫斯基差Minkowski Difference這是GJK算法的基石。給定兩個凸集形狀A和B它們的閔可夫斯基差集定義為A ? B { a - b | a ∈ A, b ∈ B }。通俗地講對于形狀A中的每一個點a減去形狀B中的每一個點b得到的所有可能結果構成的集合就是閔可夫斯基差集。這個操作的魔力在于一個關鍵性質如果兩個凸集A和B相交那么它們的閔可夫斯基差集必然包含原點0, 0, 0。反過來如果原點在差集內部那么A和B一定相交。如果原點不在差集內部那么A和B就是分離的并且從原點到差集最近點的向量就是它們的分離軸的負方向。注意這里說的“內部”包括邊界。也就是說如果兩個形狀剛好相切原點就在差集的邊界上。通過這個轉換我們就把一個“兩個形狀的關系”問題變成了一個“點和單個形狀的關系”問題。而判斷一個點原點是否在一個凸集中GJK提供了一種極其高效的迭代方法。2.2 算法的引擎支撐函數Support Function支撐函數是GJK迭代的“燃料”。對于一個凸形狀C和一個給定的方向向量d支撐函數Support(C, d)返回的是形狀C在方向d上最遠的點。數學表達是Support(C, d) argmax_{v ∈ C} (v · d)即點積最大的那個點。為什么需要它因為我們要在閔可夫斯基差集我們稱之為M中尋找點。根據定義M A ? B。那么M在方向d上的支撐點Support(M, d)可以通過分別計算A和B的支撐點來高效獲得Support(M, d) Support(A, d) - Support(B, -d)。這個性質太重要了它意味著我們不需要顯式地、耗費巨大資源去計算和存儲整個閔可夫斯基差集那可能是一個無限點集我們只需要知道原始形狀A和B的支撐函數就能動態地得到M在任意方向上的邊界點。在實現中為你的碰撞體實現一個高效的支撐函數是第一步。對于多邊形/多面體就是遍歷所有頂點找點積最大的。對于球體、膠囊體等則有解析解速度更快。2.3 迭代與終止單純形Simplex和包含判斷GJK算法通過迭代構建一個“單純形”來逼近原點。單純形是所在空間中最簡單的幾何體在2D中是線段、三角形在3D中是線段、三角形、四面體。算法流程可以概括為以下步驟我結合一個2D例子來說明這樣更直觀初始化選擇一個初始搜索方向d通常可以取兩個形狀中心點的向量差即d centerB - centerA。構建初始單純形它是一個包含單個點的集合這個點就是Support(M, d)。迭代循環 a.獲取新點根據當前搜索方向d通過支撐函數得到一個新點p Support(M, d)并將其加入單純形。 b.判斷方向計算點p到原點的向量點積p · d。如果p · d 0說明在當前搜索方向d上我們找到的支撐點p都無法讓單純形包含原點因為原點在d的相反側那么可以立即斷定原點不在M內即A和B分離。算法結束返回“無碰撞”。 c.更新單純形將新點p加入當前單純形。現在單純形可能包含2、32D或43D個點。我們需要判斷原點是否被這個新的單純形所“包圍”。 d.檢查包含這是GJK的核心子程序。我們需要判斷原點是否在當前單純形內部或邊界上。在2D中如果單純形是三角形我們就檢查原點是否在這個三角形內。同時更重要的是如果原點不在單純形內我們需要找到單純形中離原點最近的那個部分點、邊或面并丟棄單純形中遠離原點的點從而得到一個更小的、更靠近原點的單純形例如從三角形退化成包含原點的邊。然后基于這個新的、更小的單純形計算出一個新的搜索方向d這個方向是從這個最近的部分指向原點。 e.循環條件如果通過檢查發現原點已經在當前單純形內部對于2D三角形或3D四面體那么算法成功返回“碰撞”。否則用新的搜索方向d繼續下一次迭代。這個迭代過程就像是用一個不斷收縮的“網”去兜原點。每次迭代都朝著原點的方向優化這個網直到網住原點碰撞或者確定網不住分離。實操心得迭代次數需要設置一個上限比如32次防止在極端情況下如兩個幾乎平行且非常接近的面陷入無限循環。同時由于浮點數精度問題判斷“原點是否在單純形內”時需要引入一個很小的容差epsilon如1e-6。3. 實戰代碼解析從理論到可運行的C#/C理解了原理我們來看代碼。我會分別給出Unity (C#) 和 Unreal Engine (C) 的核心實現框架。為了聚焦于GJK本身我們假設碰撞體都是凸多邊形2D或凸多面體3D并用頂點列表表示。3.1 C#實現Unity版本在Unity中我們通常將GJK實現為一個靜態工具類。首先我們需要定義支撐函數和向量運算。using UnityEngine; using System.Collections.Generic; public static class GJKAlgorithm { // 容差用于處理浮點數精度 public const float EPSILON 1e-6f; // 支撐函數對于給定方向dir返回凸體vertices中點積最大的頂點 public static Vector3 Support(ListVector3 vertices, Vector3 dir) { float maxDot Mathf.NegativeInfinity; Vector3 supportPoint Vector3.zero; foreach (var vertex in vertices) { float dot Vector3.Dot(vertex, dir); if (dot maxDot) { maxDot dot; supportPoint vertex; } } return supportPoint; } // 閔可夫斯基差支撐點 public static Vector3 MinkowskiSupport(ListVector3 verticesA, ListVector3 verticesB, Vector3 dir) { Vector3 pointA Support(verticesA, dir); Vector3 pointB Support(verticesB, -dir); // 注意方向取反 return pointA - pointB; // A - B } // 核心GJK碰撞檢測函數 public static bool CheckCollision(ListVector3 verticesA, ListVector3 verticesB) { // 1. 初始化方向取中心差簡單有效 Vector3 centerA CalculateCenter(verticesA); Vector3 centerB CalculateCenter(verticesB); Vector3 d centerB - centerA; if (d.sqrMagnitude EPSILON) d Vector3.right; // 如果中心重合給一個默認方向 // 2. 初始化單純形列表 ListVector3 simplex new ListVector3(); Vector3 a MinkowskiSupport(verticesA, verticesB, d); simplex.Add(a); // 搜索方向取反指向原點 d -a; // 3. 開始迭代 int maxIterations 32; for (int i 0; i maxIterations; i) { Vector3 p MinkowskiSupport(verticesA, verticesB, d); // 如果新支撐點在d方向上的投影小于0則原點不可能在M內 if (Vector3.Dot(p, d) EPSILON) { return false; // 分離 } simplex.Add(p); // 調用子函數處理單純形并更新搜索方向d if (HandleSimplex(ref simplex, ref d)) { return true; // 碰撞 } } // 達到最大迭代次數通常視為未碰撞或需要更復雜的處理 Debug.LogWarning(GJK reached max iterations.); return false; } // 處理單純形這里是2D版本的核心3D版本更復雜 // 返回true表示原點在單純形內碰撞否則更新simplex和d private static bool HandleSimplex(ref ListVector3 simplex, ref Vector3 d) { // 此函數需要根據單純形點數1,2,3分別處理 // 由于篇幅這里給出2D情況下的邏輯示意3D需要實現包含四面體的判斷 // 實際應用中建議使用成熟的幾何庫或參考標準實現如Bullet Physics中的GJK // 此處代碼為示意完整實現需補充 // 1. 當simplex有2個點線段時找到線段上離原點最近的點更新d為原點指向該最近點的方向。 // 2. 如果最近點是線段端點則丟棄另一個點simplex保留該端點。 // 3. 當simplex有3個點三角形時檢查原點是否在三角形內通過重心坐標或邊法線。 // 4. 如果在三角形內返回true碰撞。 // 5. 如果不在找到離原點最近的邊丟棄對面的頂點simplex退化為該邊并更新d。 // 偽代碼邏輯 if (simplex.Count 2) { /* 處理線段 */ } else if (simplex.Count 3) { /* 處理三角形 */ } return false; // 默認返回未包含 } private static Vector3 CalculateCenter(ListVector3 vertices) { Vector3 sum Vector3.zero; foreach (var v in vertices) sum v; return sum / vertices.Count; } }上面的HandleSimplex函數是GJK的精華也是難點。一個健壯的實現需要正確處理各種退化情況比如單純形共線。在3D中情況更復雜需要判斷原點相對于線段、三角形、四面體的位置。網上有許多開源實現如Bullet, Box2D的GJK::Evaluate函數可供深入研究。3.2 C實現Unreal Engine版本在Unreal Engine中我們利用FVector等內置類型。邏輯與C#版完全一致只是語法和API不同。// GJK.h #pragma once #include CoreMinimal.h #include GameFramework/Actor.h #include GJK.generated.h UCLASS() class MYPROJECT_API UGJKFunctionLibrary : public UBlueprintFunctionLibrary { GENERATED_BODY() public: // 判斷兩個凸體頂點數組是否碰撞 UFUNCTION(BlueprintCallable, Category Collision|GJK) static bool GJKCheckCollision(const TArrayFVector VerticesA, const TArrayFVector VerticesB); private: static FVector Support(const TArrayFVector Vertices, const FVector Direction); static FVector MinkowskiSupport(const TArrayFVector VerticesA, const TArrayFVector VerticesB, const FVector Direction); static bool HandleSimplex(TArrayFVector Simplex, FVector Direction); static FVector CalculateCenter(const TArrayFVector Vertices); }; // GJK.cpp #include GJK.h #include limits const float EPSILON 1e-6f; FVector UGJKFunctionLibrary::Support(const TArrayFVector Vertices, const FVector Direction) { float MaxDot -std::numeric_limitsfloat::max(); FVector SupportPoint FVector::ZeroVector; for (const FVector Vertex : Vertices) { float Dot FVector::DotProduct(Vertex, Direction); if (Dot MaxDot) { MaxDot Dot; SupportPoint Vertex; } } return SupportPoint; } FVector UGJKFunctionLibrary::MinkowskiSupport(const TArrayFVector VerticesA, const TArrayFVector VerticesB, const FVector Direction) { FVector PointA Support(VerticesA, Direction); FVector PointB Support(VerticesB, -Direction); return PointA - PointB; } bool UGJKFunctionLibrary::GJKCheckCollision(const TArrayFVector VerticesA, const TArrayFVector VerticesB) { // 初始化方向 FVector CenterA CalculateCenter(VerticesA); FVector CenterB CalculateCenter(VerticesB); FVector D CenterB - CenterA; if (D.SizeSquared() EPSILON) D FVector::ForwardVector; // 初始化單純形 TArrayFVector Simplex; FVector A MinkowskiSupport(VerticesA, VerticesB, D); Simplex.Add(A); D -A; const int32 MaxIterations 32; for (int32 i 0; i MaxIterations; i) { FVector P MinkowskiSupport(VerticesA, VerticesB, D); if (FVector::DotProduct(P, D) EPSILON) { return false; // 分離 } Simplex.Add(P); if (HandleSimplex(Simplex, D)) { return true; // 碰撞 } } UE_LOG(LogTemp, Warning, TEXT(GJK reached max iterations.)); return false; } // HandleSimplex 的實現是GJK的核心此處省略詳細代碼需參考標準幾何算法實現。 // 其職責與C#版本描述一致根據單純形點數判斷原點包含性并更新單純形和搜索方向。 bool UGJKFunctionLibrary::HandleSimplex(TArrayFVector Simplex, FVector Direction) { // 實現原點對線段、三角形、四面體的最近點計算和包含性判斷。 // 這是一個需要細致編碼的部分建議參考《Real-Time Collision Detection》或開源物理引擎。 return false; } FVector UGJKFunctionLibrary::CalculateCenter(const TArrayFVector Vertices) { FVector Sum FVector::ZeroVector; for (const FVector V : Vertices) Sum V; return Vertices.Num() 0 ? Sum / Vertices.Num() : Sum; }在Unreal中你可以將這個函數庫暴露給藍圖方便地在任何地方調用檢測兩個自定義形狀的碰撞。4. 超越布爾檢測用EPA算法獲取碰撞信息GJK算法高效地給出了“是否碰撞”的布爾答案。但對于物理引擎來說這遠遠不夠。我們需要知道碰撞的深度穿透距離和法線碰撞方向以便計算碰撞響應讓物體被“推開”。這時就需要EPAExpanding Polytope Algorithm算法作為GJK的搭檔。EPA算法的思路很直觀當GJK確認碰撞即原點在閔可夫斯基差集M內部后EPA以GJK終止時得到的那個包含原點的單純形一個位于M邊界上的多面體為起點。因為這個單純形在M內部但原點在它內部所以我們需要擴展這個多面體使其不斷膨脹直到它的各個面緊貼M的邊界。最終離原點最近的那個面其外法線方向就是碰撞法線原點到該面的距離就是穿透深度。EPA的步驟簡述如下初始化將GJK最后得到的單純形一個四面體作為初始多面體Polytope。尋找最近面計算多面體每個面三角形到原點的距離點乘法線找到距離最近的那個面。獲取支撐點以這個最近面的外法線方向為d調用支撐函數Support(M, d)得到M邊界上的一個新點。判斷收斂計算這個新點到該最近面的距離。如果這個距離與當前最近面距離的差值小于某個容差說明我們已經足夠接近M的邊界算法收斂。此時該最近面的法線和距離就是我們要的碰撞信息。擴展多面體如果未收斂則將新點插入多面體。這需要像增量構造凸包一樣刪除所有從新點看過去“可見”的舊面即新點在該面法線指向的正半空間然后用新點與這些被刪除面的邊界邊組成新的三角形面添加到多面體中。循環回到步驟2繼續尋找新的最近面。EPA的實現比GJK更復雜因為它涉及到凸包的面管理、拓撲結構的變化。同樣數值穩定性是關鍵需要小心處理共面、共線的情況。注意事項EPA在物體剛好接觸穿透深度為0或穿透很淺時可能不穩定。在實際物理引擎中通常會結合GJK/EPA用于深度穿透而對于淺穿透或接觸則采用其他方法如分離軸定理SAT的變種來獲取更穩定的接觸信息。5. 性能優化與工程化實踐將GJK/EPA集成到游戲引擎中不能只考慮算法正確性還必須考慮性能、易用性和健壯性。5.1 支撐函數的優化支撐函數的性能至關重要因為GJK/EPA的每次迭代都要調用它多次。對于多邊形/多面體如果頂點數很多每次遍歷所有頂點是O(n)。可以采用以下優化緩存和增量更新如果物體在旋轉可以緩存物體局部空間的支撐點然后通過變換矩陣快速計算世界空間的支撐點。對于凸體在給定方向上最遠的頂點往往是固定的幾個“極值點”。使用GJK/EPA專用的數據結構如“凸包”對象它預計算并存儲了頂點、邊、面信息支撐函數可以利用凸包的法線錐或預計算的極值方向來加速。對于基本圖元球、盒、膠囊必須使用解析解絕對不要用頂點列表模擬。球體Support(sphere, d) center radius * normalize(d)。AABB軸對齊包圍盒根據d的每個分量的正負選擇min或max頂點。OBB定向包圍盒將方向d變換到OBB的局部空間然后在局部空間使用AABB的支撐函數再將結果變換回世界空間。膠囊體支撐點在兩個半球中心連線的線段上加上半球半徑的偏移。5.2 數值魯棒性處理浮點數精度是幾何算法的天敵。容差Epsilon所有相等性判斷如點積是否為0、距離是否小于某值都必須使用容差。容差值不能太小否則失去作用也不能太大否則影響精度。通常取1e-6到1e-4之間根據你的世界尺度調整。退化單純形在GJK迭代中可能會產生共線或共面的點例如三個點幾乎在一條直線上。你的HandleSimplex函數必須能檢測并正確處理這種情況否則會導致搜索方向錯誤甚至除零錯誤。一種常見策略是當檢測到退化時主動給搜索方向一個微小的隨機擾動。EPA的收斂性EPA可能在某些病理情況下收斂很慢或失敗例如物體穿透極深且形狀復雜。必須設置最大迭代次數如50-100次并在達到上限時采用備選方案比如返回一個基于當前最近面的近似結果或者直接使用GJK最后的方向作為一個近似的碰撞法線。5.3 與引擎集成碰撞查詢與響應在Unity/Unreal中你通常不會完全替換內置的碰撞系統而是將其用于特定場合。自定義Collider組件在Unity中你可以創建一個CustomGJKCollider組件它掛載在GameObject上定義其凸體形狀頂點列表或基本圖元參數。在FixedUpdate中你可以遍歷其他同類組件執行GJK檢測。作為Broad Phase的補充GJK/EPA是精確的Narrow Phase算法。在大規模場景中你仍然需要Broad Phase如動態AABB樹、空間網格來快速篩選出可能碰撞的對象對只對它們執行昂貴的GJK/EPA計算。獲取碰撞信息后一旦EPA返回了穿透深度和法線你就可以計算碰撞響應了。最簡單的響應是“投影修正”將發生穿透的物體沿著碰撞法線方向移動穿透深度的距離。更復雜的物理響應則涉及動量、摩擦力的計算這需要結合物體的質量、速度等屬性。6. 常見問題與調試技巧實錄自己實現GJK/EPA調試是最大的挑戰。問題往往不是“不工作”而是“在某些奇怪的角度不工作”。6.1 問題排查清單現象可能原因排查步驟與解決方案算法總是返回“無碰撞”1. 初始方向錯誤或為零向量。2. 支撐函數實現錯誤返回的點不是最遠點。3. 頂點數據坐標系不統一一個用局部坐標一個用世界坐標。1. 打印初始方向向量確保其不為零。可以嘗試固定一個方向如(1,0,0)測試。2. 單獨測試支撐函數給定一個簡單形狀如正方形和一個方向手動計算并驗證返回值是否正確。3. 確保傳入GJK的所有頂點都在同一個坐標系通常是世界坐標系下。在Unity/Unreal中需要將模型本地頂點通過Transform.TransformPoint轉換到世界空間。算法有時返回碰撞有時不返回間歇性1. 浮點數精度問題容差設置不當。2.HandleSimplex函數中對退化情況處理不完善。3. 迭代次數不足復雜形狀在達到最大迭代次數前未收斂。1. 適當增大EPSILON如從1e-6調到1e-4觀察是否穩定。在判斷點積p·d 0時使用容差。2. 在HandleSimplex中添加大量日志打印每次迭代后的單純形頂點和搜索方向。觀察在出錯的那一步單純形是否出現了異常如點非常接近。3. 增加最大迭代次數如64并記錄達到迭代上限的情況。算法陷入無限循環1. 搜索方向d未能有效更新導致每次迭代都獲得相同的支撐點。2. 在原點恰好位于閔可夫斯基差集邊界時判斷邏輯可能振蕩。1. 強制設置循環上限如100并在達到上限時中斷返回“未碰撞”或“錯誤”。這是必須做的安全措施。2. 檢查HandleSimplex中當原點在邊上或面上時的邏輯。確保在這種情況下能正確判斷為“包含”并返回true。EPA返回的穿透深度為NaN或極大值1. 在計算三角形面積或四面體體積時出現除零錯誤共線/共面。2. EPA擴展時新加入的點未能有效擴展多面體導致最近面計算錯誤。1. 在計算法線、面積、體積前先檢查邊長、面積是否大于一個極小閾值如1e-10否則視為退化情況采用備用方向或直接返回上次有效結果。2. 可視化EPA的多面體。在每次迭代中將多面體的面繪制出來Unity用Debug.DrawLine, Unreal用DrawDebugLine觀察其擴展過程是否合理。6.2 可視化調試你的最佳伙伴在3D空間中調試幾何算法光靠打印日志是遠遠不夠的。必須將中間過程畫出來。繪制支撐點在每次調用MinkowskiSupport后用不同顏色在世界空間中畫出點A、點B以及它們的差點P。這能幫你確認支撐函數是否正確以及搜索方向是否合理。繪制單純形在GJK的每次迭代后繪制當前的單純形2D為線段/三角形3D為線段/三角形/四面體。用明顯的顏色如紅色標出單純形觀察它如何向原點收縮。繪制搜索方向從原點畫一條射線方向為當前的搜索方向d長度適中。這能直觀顯示算法正在朝哪個方向“尋找”邊界。繪制EPA多面體用線框模式繪制EPA迭代過程中的多面體。你可以看到它如何從一個四面體開始像吹氣球一樣膨脹直到貼合碰撞邊界。在Unity中使用Debug.DrawLine,Debug.DrawRay在OnDrawGizmos或Update中繪制。在Unreal中使用DrawDebugLine,DrawDebugPoint等函數通常在Tick或特定調試函數中調用。這些可視化工具能讓你瞬間定位問題所在效率遠超盲目修改代碼。6.3 一個實用的調試技巧從2D開始如果你對3D GJK/EPA的實現感到頭疼一個極其有效的策略是先在2D平面上實現并調試通過。2D的GJK判斷原點是否在三角形內和EPA擴展多邊形在概念上與3D完全一致但幾何處理簡單得多可視化也更容易你可以在XY平面上畫圖。將2D版本徹底調通理解每一個細節后再擴展到3D你會發現自己面對的不是一個全新的問題而只是一個增加了維度的問題很多邏輯可以類比遷移。這是學習復雜幾何算法的一條捷徑。實現一個健壯的GJK/EPA碰撞檢測系統是一項有挑戰但回報豐厚的工作。它不僅能解決你項目中特定的碰撞問題更能讓你對計算機圖形學、計算幾何和物理引擎的核心機制有深刻的理解。當你看到自己編寫的代碼讓兩個復雜的自定義形狀產生精確的碰撞反應時那種成就感是使用現成組件無法比擬的。希望這篇結合了原理、代碼和實戰經驗的指南能為你鋪平這條路。