文章目錄

• 前言
• 一、BVTree技術
• • 1.AABB包圍盒
  • 2.包圍球Sphere
  • 3.方向包圍盒OBB
  • 4.固定方向凸包FDH
• 二、GJK Tree
• • 1.Support函數
  • 2.明可夫斯基和（Minkowski Sum）
  • 3.單純形(Simplex)
• 總結

前言

碰撞檢測俗稱體積碰撞，這是實時渲染中不可忽視的一面。碰撞檢測讓客戶看來，應該非常我們的日常實際，不被察覺出來是最好的結果。

一、BVTree技術

BVTree技術的出現就是在模型外面建立分層的包圍盒，將問題分隔，以略微提升空間的復雜度為代價，大大降低了時間復雜度。BVTree根據實現的不同，可以包含AABBTree，Sphere Tree，OBB Tree，K-Dop Tree等。常見的包圍盒大體上有四種：AABB包圍盒、包圍球Sphere、方向包圍盒OBB、固定方向凸包FDH（K-dop）。

1.AABB包圍盒

AABB 包圍盒就是采用一個長方體將物體包裹起來，進行兩個物體的相交性檢測時僅檢測物體對應包圍盒（包裹物體的長方體）的相交性。

另外，AABB 包圍盒有一個重要特性，那就是包圍盒對應的長方體每一個面都是與某個坐標軸平面平行的，因此，AABB 包圍盒又稱了 軸對齊包圍盒 。

有了上述約定后，確定 AABB 包圍盒就簡單多了，僅需要記錄 6 個值即可，這 6 個值分別代表包圍盒在每個坐標軸上的最小值與最大值，即 xmin、xmax、ymin、ymax、zmin、zmax。

2.包圍球Sphere

包圍球碰撞檢測方法是用球體包圍整個幾何體, 無論是幾何體還是相交測試都很簡單; 但是它的緊密性太差。因為除了在3 個坐標軸上分布得比較均勻的幾何體外, 幾乎都會留下較大的空隙, 需要花費大量的預處理時間, 以構造一個好的層次結構逼近對象。當物體變形之后,包圍球樹需要重新計算。因此,它是使用得比較少的一種包圍盒。當對象發生旋轉運動時, 包圍球不需作任何更新, 這是包圍球的較優秀特性; 當幾何對象進行頻繁的旋轉運動時, 采用包圍球可能得到較好結果。

3.方向包圍盒OBB

OBB是包圍對象最小的長方體，這是較為常用的包圍盒，可以根據物體表面的頂點，通過主成分分析獲得特征向量（即OBB的主軸），以此建立包圍盒，相對而言，這種方式的較為緊密，但是生成和相交檢測較為復雜。而且OBB可以隨著人物的方向旋轉，也可以稱得上是會旋轉的AABB包圍盒。

4.固定方向凸包FDH

FDH是 AABB的變體，繼承了AABB的簡潔，被定義為包含該對象且它的所有面的法向量都取自一個固定的方向集合的凸包，FDH是最為緊密的一種，但是相交檢測最為復雜，可以用于軟體對象的碰撞檢測。在許多環境中，因為性能限制或者因為細節過于細微以至不易察覺，使用包圍盒進行碰撞檢測的結果直接看作最終結果的無限接近值也是一種選擇。在空間中，一般都有許多物體，通過簡單的計算，x個物體之間通過暴力求相互之間的碰撞檢測需要x（x-1）/2次，時間復雜度為O（x平方），這樣的性能開銷是難以接受的。

二、GJK Tree

GJK是一個迭代算法，但是如果事先給出穿透/分離向量，則它的收斂會很快，可以在常量時間內完成。在3D環境中，GJK可以取代SAT算法。GJK算法的最初目的是計算兩個凸體之間的距離，在兩個物體穿透深度比較小的情況下，可用它判定物體之間的碰撞。它也可以和別的算法相結合，用來檢測兩個物體之間深度穿透時候的碰撞情況。JK算法的優勢是：通過support函數，從而支持任何凸體形狀之間的碰撞檢測；相比SAT算法，你不需要一些額外的操作，比如增加特殊的代碼和算法處理曲面形狀。

1.Support函數

support函數，給定兩個凸體，該函數返回這兩個凸體明可夫斯基差形狀中的一個點。我們知道，物體1上的一個點，它的位置減去物體2上的一個點的位置，可以得到它們明可夫斯基差形狀上的一個點，但我們不希望每次都得到相同的點。如何保證做到這一點呢？我們可以給support函數傳遞一個參數，該參數表示一個方向(direction),方向不同，得到的點也不同。

在某個方向上選擇最遠的點有重要作用，因為這樣產生的單純形包含最大的空間區域，增加了算法快速返回的可能。另外，通過這種方式返回的點都在明可夫斯基差形狀的邊上。如果我們不能通過一個過原點的方向在單純形上增加一個點，則明可夫斯基差不過原點，這樣在物體不想交的情況下，算法會很快退出。

public Point support(Shape shape1, Shape shape2, Vector d) {// d is a vector direction (doesn't have to be normalized)// get points on the edge of the shapes in opposite directionsPoint p1 = shape1.getFarthestPointInDirection(d);Point p2 = shape2.getFarthestPointInDirection(d.negative());// perform the Minkowski DifferencePoint p3 = p1.subtract(p2);// p3 is now a point in Minkowski space on the edge of the Minkowski Differencereturn p3;}

2.明可夫斯基和（Minkowski Sum）

GJK算法中使用了明可夫斯基和的概念。明可夫斯基和很好理解，假設有兩個物體，它們的明可夫斯基和就是物體1上的所有點和物體2上的所有點的和集。用公式表示就是：
A + B = {a + b|a∈A, b∈B}
如果兩個物體都是凸體，它們的明可夫斯基和也是凸體。

對于減法，明可夫斯基和的概念也成立，這時也可稱作明可夫斯基差。
A – B = A + (-B) = {a + (– b)|a∈A, b∈B} = {a – b)|a∈A, b∈B}

3.單純形(Simplex)

我們不需要顯式計算物體之間的明可夫斯基差，只要知道它們的明可夫斯基差是否包含原點就ok了。如果包含原點，物體之間就相交，否則，則不相交。
我們可以在明可夫斯基差形成的物體內迭代的形成一個多面體(或多變形），并使這個多面體盡量包圍原點。如果這個多面體包含原點，顯然明可夫斯基差形成的物體必然包括原點。這個多面體就稱作單純形。

總結

同樣的還有以前常用的BSP Tree，這個還涉及到相應的檢測方式，我將在我的下一篇文章詳細簡紹。

GJK算法參考：heyuchang666 博主

總結

以上是生活随笔為你收集整理的游戏设计----常见的碰撞检测的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。