視頻遊戲物理教程 - 第二部分：固體物體的碰撞檢測

這是我們關於視頻遊戲物理的三部分系列的第二部分。 對於本系列的其餘部分，請參閱：

第一部分：剛體動力學簡介
第三部分：約束剛體模擬

在本系列的第一部分中，我們探索了剛體及其運動。 然而，在那次討論中，對象並沒有相互影響。 如果沒有一些額外的工作，模擬的剛體可以直接穿過彼此，或者“相互穿透”，這在大多數情況下是不可取的。

為了更真實地模擬固體物體的行為，我們必須檢查它們是否在每次移動時相互碰撞，如果它們發生碰撞，我們必須做一些事情，例如施加改變它們速度的力，所以他們會朝相反的方向移動。 這就是理解碰撞物理對遊戲開發者來說特別重要的地方。

在第二部分中，我們將介紹碰撞檢測步驟，該步驟包括在散佈在 2D 或 3D 世界中的可能大量物體之間尋找碰撞的物體對。 在下一期也是最後一期中，我們將更多地討論“解決”這些碰撞以消除相互滲透。

對於本文中提到的線性代數概念的複習，您可以參考第 I 部分的線性代數速成課程。

電子遊戲中的碰撞物理

在剛體模擬的上下文中，當兩個剛體的形狀相交時，或者當這些形狀之間的距離低於一個小的公差時，就會發生碰撞。

如果我們的模擬中有n 個物體，那麼通過成對測試檢測碰撞的計算複雜度是O ( n 2 ) ，這個數字讓計算機科學家畏縮不前。 成對測試的數量隨著物體的數量呈二次方增加，並且確定任意位置和方向的兩個形狀是否發生碰撞已經不便宜了。 為了優化碰撞檢測過程，我們一般將其分為兩個階段：寬階段和窄階段。

廣義階段負責從模擬中的整組剛體中找到可能發生碰撞的剛體對，並排除肯定不會發生碰撞的剛體對。 這一步必須能夠很好地隨著剛體的數量而擴展，以確保我們保持在O ( n 2 )時間複雜度之下。 為了實現這一點，這個階段通常使用空間分區以及為碰撞建立上限的邊界體積。

窄相作用於寬相發現的可能發生碰撞的剛體對。 這是一個細化步驟，我們確定碰撞是否實際發生，並且對於發現的每個碰撞，我們計算將用於稍後解決碰撞的接觸點。

在接下來的部分中，我們將討論一些可用於廣義階段和狹義階段的算法。

寬相

在電子遊戲碰撞物理的廣泛階段，我們需要確定哪些剛體對可能發生碰撞。 這些物體可能有復雜的形狀，比如多邊形和多面體，我們可以做的是用更簡單的形狀來包圍物體。 如果這些包圍體不相交，那麼實際形狀也不會相交。 如果它們相交，那麼實際的形狀可能會相交。

一些流行的包圍體類型是定向包圍盒 (OBB)、2D 中的圓和 3D 中的球體。 讓我們看一下最簡單的包圍盒之一：軸對齊包圍盒 (AABB) 。

AABB 深受物理程序員的喜愛，因為它們簡單且提供良好的權衡。 一個二維的 AABB 可以用 C 語言中這樣的結構來表示：

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

min字段表示框左下角的位置， max字段表示右上角。

要測試兩個 AABB 是否相交，我們只需確定它們的投影是否在所有坐標軸上相交：

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

此代碼與 Box2D 引擎（版本 2.3.0）中的b2TestOverlap函數具有相同的邏輯。 它以兩個順序計算兩個軸上兩個 AABB 的min和max之間的差異。 如果這些值中的任何一個大於零，則 AABB 不會相交。

儘管 AABB 重疊測試很便宜，但如果我們仍然對每個可能的對進行成對測試，它也無濟於事，因為我們仍然有不合需要的O ( n 2 )時間複雜度。 為了最大限度地減少 AABB 重疊測試的數量，我們可以使用某種空間分區，它的工作原理與加快查詢的數據庫索引相同。 （地理數據庫，如 PostGIS，實際上對其空間索引使用類似的數據結構和算法。）但是，在這種情況下，AABB 將不斷移動，因此通常我們必須在模擬的每一步之後重新創建索引。

有很多空間劃分算法和數據結構可以用於此，例如統一網格、2D 中的四叉樹、3D 中的八叉樹和空間散列。 讓我們仔細看看兩種流行的空間分區算法：排序和掃描，以及包圍體層次結構 (BVH)。

排序和掃描算法

排序和掃描方法（也稱為掃描和修剪）是物理程序員在剛體模擬中最喜歡的選擇之一。 例如，Bullet Physics 引擎在btAxisSweep3類中實現了此方法。

一個 AABB 在單個坐標軸上的投影本質上是一個區間[ b , e ] （即開始和結束）。 在我們的模擬中，我們將有很多剛體，因此會有很多 AABB，這意味著很多間隔。 我們想找出哪些區間相交。

在排序和掃描算法中，我們將所有b和e值插入到一個列表中，並按它們的標量值升序排序。 然後我們掃描或遍歷列表。 每當遇到b值時，其對應的區間就會存儲在單獨的活動區間列表中，而每當遇到e值時，其對應的區間就會從活動區間列表中刪除。 在任何時候，所有活動區間都相交。 （查看 David Baraff 的博士論文，第 52 頁了解詳細信息。我建議使用此在線工具查看 postscript 文件。）間隔列表可以在模擬的每個步驟中重複使用，我們可以有效地重新排序這個列表使用插入排序，它擅長對幾乎排序的列表進行排序。

在二維和三維中，如上所述，在單個坐標軸上運行排序和掃描將減少必須執行的直接 AABB 相交測試的數量，但在一個坐標軸上的回報可能比在另一個坐標軸上更好。 因此，實現了排序和掃描算法的更複雜的變體。 在他的書Real-Time Collision Detection （第 336 頁）中，Christer Ericson 提出了一種有效的變體，他將所有 AABB 存儲在一個數組中，並且對於每次運行的排序和掃描，選擇一個坐標軸，數組按以下方式排序使用快速排序，所選軸中 AABB 的min 。 然後，遍歷數組並執行 AABB 重疊測試。 為了確定應該用於排序的下一個軸，計算 AABB 中心的方差，並選擇方差較大的軸進行下一步。

動態包圍體樹

另一種有用的空間劃分方法是動態邊界體積樹，也稱為Dbvt 。 這是一種包圍體層次結構。

Dbvt 是一棵二叉樹，其中每個節點都有一個 AABB，它限制了其子節點的所有 AABB。 剛體本身的 AABB 位於葉節點中。 通常，通過給出我們想要檢測交叉點的 AABB 來“查詢” Dbvt。 此操作是有效的，因為不與查詢的 AABB 相交的節點的子節點不需要進行重疊測試。 因此，AABB 衝突查詢從根開始，並且僅針對與查詢的 AABB 相交的 AABB 節點遞歸地繼續遍歷樹。 樹可以通過樹旋轉來平衡，就像在 AVL 樹中一樣。

Box2D 在b2DynamicTree類中有一個複雜的 Dbvt 實現。 b2BroadPhase類負責執行廣泛階段，它使用b2DynamicTree的一個實例來執行 AABB 查詢。

窄相

在視頻遊戲碰撞物理的廣泛階段之後，我們有一組可能發生碰撞的剛體對。 因此，對於每一對，給定兩個物體的形狀、位置和方向，我們需要確定它們是否真的發生了碰撞； 如果它們相交或者它們的距離是否低於一個小的公差值。 我們還需要知道碰撞體之間的接觸點，因為這是稍後解決碰撞所需要的。

凸面和凹面形狀

作為視頻遊戲物理學的一般規則，確定兩個任意形狀是否相交或計算它們之間的距離並非易事。 然而，在確定它的硬度方面至關重要的一個屬性是形狀的凸度。 形狀可以是凸形或凹形，而凹形更難處理，因此我們需要一些策略來處理它們。

在凸形中，形狀內任意兩點之間的線段始終完全落在形狀內。 然而，對於凹形（或“非凸形”）形狀，對於連接該形狀中的點的所有可能線段，情況並非如此。 如果你能找到至少一個完全不在形狀之外的線段，那麼這個形狀就是凹的。

在計算上，希望所有形狀在模擬中都是凸的，因為我們有很多強大的距離和相交測試算法可以處理凸形狀。 但並非所有對像都是凸的，通常我們以兩種方式解決它們：凸包和凸分解。

形狀的凸包是完全包含它的最小凸形狀。 對於二維的凹多邊形，這就像在每個頂點上敲釘子並在所有釘子周圍纏繞橡皮筋。 要計算多邊形或多面體的凸包，或者更一般地，計算一組點，一個好的算法是quickhull算法，它的平均時間複雜度為O ( n log n ) 。

顯然，如果我們用凸包來表示一個凹物體，它就會失去它的凹屬性。 諸如“鬼”碰撞之類的不良行為可能會變得明顯，因為對象仍將具有凹形圖形表示。 例如，汽車通常是凹形的，如果我們用凸包來物理表示它，然後在上面放一個盒子，這個盒子可能看起來像是漂浮在上面的空間中。

通常，凸包通常足以表示凹對象，因為不切實際的碰撞不是很明顯，或者它們的凹屬性對於所模擬的任何內容都不是必需的。 但是，在某些情況下，我們可能希望讓凹形物體在物理上表現得像一個凹形。 例如，如果我們使用凸包來物理表示一個碗，我們將無法在其中放入任何東西。 物體只會漂浮在它上面。 在這種情況下，我們可以使用凹形的凸分解。

凸分解算法接收一個凹形並返回一組凸形，其並集與原始凹形相同。 一些凹形只能用大量的凸形來表示，而這些凸形的計算和使用成本可能會變得過高。 但是，近似值通常足夠好，因此，諸如V-HACD 之類的算法會從凹多面體中生成一小組凸多面體。

然而，在許多 collisons 物理案例中，凸分解可以由藝術家手工製作。 這消除了使用分解算法對性能征稅的需要。 由於性能是實時模擬中最重要的方面之一，因此為複雜的圖形對象創建非常簡單的物理表示通常是一個好主意。 下圖顯示了使用九個凸形對 2D 汽車進行的一種可能的凸分解。

測試交叉點 - 分離軸定理

分離軸定理(SAT) 指出兩個凸形不相交當且僅當存在至少一個軸，該軸上的形狀的正交投影不相交。

但是，通常在 2D 中找到一條線或在 3D 中找到一條分隔兩個形狀的平面在視覺上更直觀，這實際上是相同的原理。 與 2D 中的線正交的向量，或 3D 中平面的法線向量，可以用作“分離軸”。

遊戲物理引擎有許多不同類別的形狀，例如圓形（3D 中的球體）、邊（單線段）和凸多邊形（3D 中的多面體）。 對於每一對形狀類型，它們都有特定的碰撞檢測算法。 其中最簡單的可能是圓環算法：

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

儘管 SAT 適用於圓，但檢查它們的中心之間的距離是否小於它們的半徑之和要簡單得多。 出於這個原因，SAT 用於特定形狀類對的碰撞檢測算法，例如凸多邊形與凸多邊形（或 3D 中的多面體）。

對於任何一對形狀，我們可以測試無數個軸的分離度。 因此，確定首先測試哪個軸對於高效的 SAT 實施至關重要。 幸運的是，當測試一對凸多邊形是否碰撞時，我們可以使用邊緣法線作為潛在的分離軸。 邊的法線向量n垂直於邊向量，並且指向多邊形之外。 對於每個多邊形的每條邊，我們只需要找出另一個多邊形的所有頂點是否都在邊的前面。

如果任何測試通過——也就是說，對於任何邊，如果另一個多邊形的所有頂點都在它前面——那麼多邊形不會相交。 線性代數為這個測試提供了一個簡單的公式：給定第一個形狀的邊，頂點a和b ，另一個形狀的頂點v ，如果( v - a ) · n大於零，則頂點在前面的邊緣。

對於多面體，我們可以使用面法線以及每個形狀的所有邊組合的叉積。 這聽起來需要測試很多東西。 但是，為了加快速度，我們可以緩存我們使用的最後一個分離軸，並在接下來的模擬步驟中再次嘗試使用它。 如果緩存的分離軸不再分離形狀，我們可以從與前一個面或邊相鄰的面或邊開始搜索新軸。 這是有效的，因為身體在步驟之間通常不會移動或旋轉太多。

Box2D 在 b2CollidePolygon.cpp 中的多邊形-多邊形碰撞檢測算法中使用 SAT 測試兩個凸多邊形是否相交。

計算距離 - Gilbert-Johnson-Keerthi 算法

在許多碰撞物理案例中，我們想要考慮的對像不僅是它們實際上相交，而且它們彼此非常接近，這需要我們知道它們之間的距離。 Gilbert-Johnson-Keerthi (GJK) 算法計算兩個凸形之間的距離以及它們最近的點。 這是一種優雅的算法，通過支持函數、Minkowski 和和單純形來隱式表示凸形狀，如下所述。

支持功能

支持函數s A ( d )返回形狀A邊界上的一個點，該點在向量d上具有最高投影。 在數學上，它與d的點積最高。 這稱為支持點，此操作也稱為支持映射。 在幾何上，該點是形狀上沿d方向的最遠點。

在多邊形上找到支撐點相對容易。 對於向量d的支持點，您只需遍歷其頂點並找到與d具有最高點積的那個，如下所示：

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

然而，支持函數的真正威力在於它可以輕鬆處理圓錐、圓柱和橢圓等形狀。 直接計算這些形狀之間的距離是相當困難的，如果沒有像 GJK 這樣的算法，您通常必須將它們離散化為多邊形或多面體以使事情變得更簡單。 但是，這可能會導致進一步的問題，因為多面體的表面不如球體的表面那麼光滑，除非多面體非常詳細，這可能導致碰撞檢測期間的性能不佳。 其他不良副作用也可能出現； 例如，“多面體”球體可能滾動不順暢。

要獲得以原點為中心的球體的支持點，我們只需對d進行歸一化（即計算d / || d || ，它是長度為 1（單位長度）的向量，仍然指向同一方向d ) 然後我們將它乘以球體半徑。

查看 Gino van den Bergen 的論文以找到更多關於圓柱體和圓錐體以及其他形狀的支撐函數示例。

當然，我們的對象會在模擬空間中從原點發生位移和旋轉，因此我們需要能夠計算變換形狀的支撐點。 我們使用仿射變換T ( x ) = R x + c來位移和旋轉我們的對象，其中c是位移向量， R是旋轉矩陣。 這種變換首先圍繞原點旋轉對象，然後平移它。 變換後的形狀A的支持函數為：

閔可夫斯基和

兩個形狀A和B的Minkowski 和定義為：

這意味著我們計算A和B中包含的所有點的總和。 結果就像用B膨脹A 。

同樣，我們將Minkowski 差定義為：

我們也可以將其寫為A與-B的 Minkowski 和：

對於凸A和B ， A⊕B也是凸的。

Minkowski 差異的一個有用特性是，如果它包含空間的原點，則形狀相交，如上圖所示。 這是為什麼？ 因為如果兩個形狀相交，它們至少有一個共同點，它們在空間中的同一位置，它們的區別是零向量，實際上就是原點。

Minkowski 差異的另一個很好的特點是，如果它不包含原點，則原點和 Minkowski 差異之間的最小距離就是形狀之間的距離。

兩個形狀之間的距離定義為：

換句話說， A和B之間的距離是從A到B的最短向量的長度。 該向量包含在A⊖B中，它是長度最小的向量，因此也是最接近原點的向量。

明確地構建兩個形狀的 Minkowski 和通常並不簡單。 幸運的是，我們也可以在這裡使用支持映射，因為：

單純形

GJK 算法迭代地搜索最接近原點的 Minkowski 差上的點。 它通過在每次迭代中構建一系列更接近原點的單純形來實現這一點。 單純形（或更具體地說，整數k的k-單純形）是 k 維空間中k + 1 個仿射獨立點的凸包。 也就是說，如果兩點不能重合，三點也不能在同一直線上，如果有四點，它們也不能在同一平面上。 因此，0-單純形是點，1-單純形是線段，2-單純形是三角形，3-單純形是四面體。 如果我們從單純形中刪除一個點，我們將其維度減一，如果我們將一個點添加到一個單純形，我們將其維度增加一。

GJK 在行動

讓我們把這些放在一起，看看 GJK 是如何工作的。 為了確定兩個形狀A和B之間的距離，我們首先取它們的 Minkowski 差A⊖B 。 我們正在搜索結果形狀上離原點最近的點，因為到該點的距離是原始兩個形狀之間的距離。 我們在A⊖B中選擇一些點v ，這將是我們的距離近似值。 我們還定義了一個空點集W ，它將包含當前測試單純形中的點。

然後我們進入一個循環。 我們首先得到支持點w = s A⊖B (- v ) ，即A⊖B上投影到v上的點最接近原點。

如果|| w || 和||沒有太大區別v || 並且它們之間的角度沒有太大變化（根據一些預定義的公差），這意味著算法已經收斂，我們可以返回|| v || 作為距離。

否則，我們將w添加到W 。 如果W的凸包（即單純形）包含原點，則形狀相交，這也意味著我們完成了。 否則，我們在單純形中找到最接近原點的點，然後我們將v重置為這個新的最接近的近似值。 最後，我們刪除了W中任何對最近點計算沒有貢獻的點。 （例如，如果我們有一個三角形，並且離原點最近的點位於它的一條邊上，我們可以從W中刪除不是該邊的頂點的點。）然後我們重複這些相同的步驟，直到算法收斂。

下圖顯示了 GJK 算法四次迭代的示例。 藍色對象表示 Minkowski 差A⊖B ，綠色向量是v 。 你可以在這裡看到v如何在離原點最近的點上磨練。

有關 GJK 算法的詳細和深入解釋，請查看 Gino van den Bergen 的論文A Fast and Robust GJK Implementation for Collision Detection of Convex Objects 。 dyn4j 物理引擎的博客也有一篇關於 GJK 的精彩文章。

Box2D 在 b2Distance.cpp 中的b2Distance函數中實現了 GJK 算法。 它僅在影響計算期間使用 GJK 在其算法中進行連續碰撞檢測（我們將進一步討論這個主題）。

Chimpunk 物理引擎使用 GJK 進行所有碰撞檢測，其實現在 cpCollision.c 中的GJK函數中。 如果 GJK 算法報告相交，它仍然需要知道接觸點是什麼，以及穿透深度。 為此，它使用了擴展多面體算法，我們將在接下來進行探索。

確定穿透深度 - 擴展多面體算法

如上所述，如果形狀A和B相交，GJK 將在 Minkowski 差A⊖B內生成包含原點的單純形W。 在這個階段，我們只知道形狀相交，但是在許多碰撞檢測系統的設計中，希望能夠計算出我們有多少相交，以及我們可以將哪些點用作接觸點，這樣我們以現實的方式處理碰撞。 擴展多面體算法(EPA) 允許我們從 GJK 停止的地方開始獲取該信息：使用包含原點的單純形。

穿透深度是最小平移向量(MTV) 的長度，這是我們可以平移相交形狀以將其與其他形狀分開的最小向量。

當兩個形狀相交時，它們的閔可夫斯基差包含原點，而閔可夫斯基差邊界上離原點最近的點就是MTV。 EPA 算法通過將 GJK 給我們的單純形擴展為多邊形來找到該點； 用新的頂點連續細分它的邊緣。

首先，我們找到最接近原點的單純形的邊，並在垂直於邊的方向（即垂直於邊並指向多邊形外部）計算 Minkowski 差中的支持點。 然後我們通過添加這個支持點來分割這條邊。 我們重複這些步驟，直到向量的長度和方向沒有太大變化。 一旦算法收斂，我們就有了 MTV 和穿透深度。

將 GJK 與 EPA 結合使用，我們可以獲得碰撞的詳細描述，無論對像是否已經相交，或者只是足夠接近以被視為碰撞。

EPA 算法在同樣由 Gino van den Bergen 撰寫的論文Proximity Queries and Penetration Depth Computation on 3D Game Objects中進行了描述。 dyn4j 博客也有一篇關於 EPA 的文章。

連續碰撞檢測

迄今為止介紹的視頻遊戲物理技術對模擬的靜態快照執行碰撞檢測。 這稱為離散碰撞檢測，它忽略了先前步驟和當前步驟之間發生的情況。 因此，可能無法檢測到某些碰撞，尤其是對於快速移動的物體。 這個問題被稱為隧道。

連續碰撞檢測技術試圖找出兩個物體何時在模擬的前一個步驟和當前步驟之間發生碰撞。 他們計算碰撞時間，因此我們可以及時返回並處理該點的碰撞。

撞擊時間（或接觸時間） t c是兩個物體之間的距離為零的時刻。 如果我們可以寫一個函數來計算兩個物體之間的時間距離，我們想要找到的是這個函數的最小根。 因此，影響計算的時間是一個尋根問題。

對於影響計算的時間，我們考慮上一步在時間t i -1和當前步驟在時間t i的身體狀態（位置和方向）。 為了使事情更簡單，我們假設步驟之間的線性運動。

讓我們假設形狀是圓形來簡化問題。 對於半徑為r 1和r 2的兩個圓C 1和C 2 ，其中它們的質心x 1和x 2與它們的質心重合（即它們自然地圍繞它們的質心旋轉），我們可以寫出距離函數作為：

考慮步驟之間的線性運動，我們可以為C 1從t i -1到t i的位置編寫以下函數

它是從x 1 ( t i -1 )到x 1 ( t i )的線性插值。 x 2也可以這樣做。 對於這個區間，我們可以寫另一個距離函數：

將此表達式設置為零，您將得到一個關於t的二次方程。 根可以直接使用二次公式找到。 如果圓不相交，則二次公式將無解。 如果他們這樣做，它可能會導致一兩個根。 如果它只有一個根，則該值就是影響時間。 如果它有兩個根，最小的一個是撞擊時間，另一個是圓分開的時間。 注意這裡的影響時間是一個從0到1的數字。它不是以秒為單位的時間； 它只是一個數字，我們可以用來將物體的狀態插入到發生碰撞的精確位置。

非圓的連續碰撞檢測

為其他類型的形狀編寫距離函數很困難，主要是因為它們的距離取決於它們的方向。 出於這個原因，我們通常使用迭代算法，在每次迭代中將對象移動得越來越近，直到它們接近到足以被認為發生碰撞。

保守的推進算法迭代地向前移動物體（並旋轉它們）。 在每次迭代中，它都會計算位移的上限。 原始算法在 Brian Mirtich 的博士論文（第 2.3.2 節）中提出，它考慮了物體的彈道運動。 Erwin Coumans（子彈物理引擎的作者）的這篇論文提出了一個更簡單的版本，它使用恆定的線速度和角速度。

該算法計算形狀A和B之間的最近點，從一個點到另一個點繪製一個向量，並將速度投影到該向量上以計算運動的上限。 它保證身體上的任何點都不會超出這個投影。 然後它將物體向前推進這個量並重複，直到距離低於一個小的公差值。

在某些情況下，可能需要太多次迭代才能收斂，例如，當其中一個物體的角速度太高時。

解決碰撞

一旦檢測到碰撞，就需要以逼真的方式改變碰撞對象的運動，例如使它們相互反彈。 在本理論的下一部分也是最後一部分中，我們將討論一些解決視頻遊戲中碰撞的流行方法。

參考

如果您有興趣更深入地了解碰撞物理，例如碰撞檢測算法和技術，那麼 Christer Ericson 的Real-Time Collision Detection一書是必備之物。

由於碰撞檢測嚴重依賴幾何，Toptal 的文章Computational Geometry in Python: From Theory to Application是對該主題的出色介紹。