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