譯者：劉鴻（lewis2012） 審校：王玥亭（玥亭）

為什麼在做遊戲引擎開發中要有算法存在，那是為了讓遊戲角色能夠有真實物理體驗，遊戲引擎需要有計算運動，碰撞，接觸點等相關的方程，有一套基本算法幫助角色實現這種效果。例如，Runge-Kutta方法使用數值積分法計算運動方程。Gilbert-Johnson-Keerthi（GJK）算法使用Minkowski差來進行碰撞檢測。 Sutherland-Hodgman算法通過剪切多邊形來識别碰撞接觸點。

數值積分方法

計算運動方程允許角色在空間中自由落體運動，就好像重力作用在這個角色上。運動方程使用的是牛頓第二定律：

和旋轉力：

遊戲引擎集成運動方程以獲得角色的速度和位移。引擎用連續循環來進行這個操作，這個循環包括以下步驟：

• 識别作用于對象的所有力和力矩。

• 取所有力和力矩的矢量和。

• 求解線性和角加速度的運動方程。

• 在時間上對加速度進行積分以得到線性速度和角速度。

• 在時間上對速度進行積分以得到線性位移和角位移。

如果角色擁有重力和扭矩力，則遊戲引擎連續循環将會産生物體下落和旋轉的感覺。

問題是加速度和速度的積分。計算機隻能通過使用數字積分技術來逼近積分的值。

遊戲引擎開發中使用了三種數值積分方法。他們分别是：

1.Euler法

2.Verlet方法

3.Runge-Kutta方法

Euler方法計算在一個時間間隔中的速度，并預測在t △下一速度。該方法實現起來很簡單，但它是最不準确的。下圖顯示了這種方法的缺點。你可能覺得，使得Δt越無限的小，得到的解就越準确。但是，值得考慮的實際問題是你能有多少時間來進行每步積分。

在Runge-Kutta方法是一個數字集成技術，提供更好的近似運動方程。與歐拉方法（其計算一個間隔的一個斜率）不同，Runge-Kutta計算四個不同的斜率，并将這四個斜率用作加權平均值。

這些斜率通常被稱為k1，k2，k3和k4，并且引擎需要在每個時間步長計算它們的值。

Runga-Kutta使用這些斜率作為加權平均值，從而更好地近似出物體的實際斜率和速度。然後使用該新斜率計算出對象的實際位置。

碰撞檢測

檢測沖突需要進行一定的權衡。因為簡單的碰撞檢測系統雖然快速但不精确的。而複雜的碰撞檢測系統是精确的，但是在計算上各種代價也是昂貴的。

在碰撞檢測期間，引擎用幾何量來限制遊戲角色。這被稱為包圍盒。最常見的是如下形式：

1. 球形包圍盒（spheres）

2. 帶方向的包圍盒（orientedbounding box）

3. 沿坐标軸的包圍盒（axis-alignedbounding boxes）

4. 凸包（Convex Hull）

碰撞檢測系統通過檢測邊界值是否相交來工作。使用球形包圍盒（spheres）

作為邊界檢測時候速度很快，但是會返回的許多錯誤檢測狀态。下圖中兩輛車實際并沒有碰撞，但是檢測系統會返回已經碰撞。

早在上世紀80年代，我能确信的說使用球形包圍盒作為檢測系統是可以接受的，但是現在，玩家可能會對許多錯誤檢測感到不滿意。

更精确的檢測系統應該采用凸包作為邊界檢測。

使用Gilbert-Johnson-Keerthi（GJK）算法計算凸包（Convex Hull）的交點。令人驚訝的是，這種算法包含的數學思想非常的簡單。算法通過計算它們的Minkowski差是否包含了原點來确定物體是否相交。下圖顯示了兩個凸包（Convex Hull）相交（左）。 由于Minkowski差（右）包括原點，算法檢測為物體相交，碰撞檢測返回真。

雖然GJK算法背後的數學思想是簡單的，它是它非常計算代價卻是昂貴的。

碰撞系統通過使用被稱為寬階段檢測和窄階段檢測的這種兩個階段檢測系統來避免每次碰撞檢測都使用GJK算法來進行檢測。

寬階段檢測系統使用球形包圍盒（spheres）檢測碰撞。這個階段是快速的，并把檢測到的所有可能的碰撞結果報告給窄階段。窄階段使用代價更昂貴和但是結果精确的GJK算法，這個階段将再次測試并報告碰撞檢測結果。

為了進一步減少GJK算法的調用，遊戲引擎解析了遊戲角色的空間狀态，并創建稱為一個樹狀結構的層次包圍盒（BVH）。

BVH算法解析每個對象的位置，并将它們分配給二叉樹中的特定節點。該算法遞歸地分析每個節點，直到每個節點包含最可能碰撞的兩個角色。

碰撞響應

碰撞檢測系統報告碰撞是否發生。不幸的是，它不報告Contact-Manifold（接觸點）的碰撞。contact-manifold對于确定碰撞角色的碰撞響應是必要的。遊戲引擎采用Sutherland-Hodgman算法來計算的兩個碰撞人物接觸點。該算法基于識别兩個多邊形，一個參考多邊行，一個觸發多邊形，如下圖。

算法中參考多邊形的部分作為參考平面。

一旦确定了參考多邊形，該算法通過使用剪切規則來測試每個參考平面上觸發多邊形的每個頂點。

算法終止時，生成其頂點是兩個碰撞多邊形的接觸點的新多邊形。

可視化遊戲引擎算法

現在你知道這些遊戲引擎算法，你可能想知道如何實現它們。一般的書本直接進入這些算法的實現，不提供視覺描述算法如何工作的。我認為，如果你可以看到一個算法的視覺表示，你可以實更容易和更快現它們。因此，我寫了幾個帖子，我為每個算法提供一個視覺解釋。我希望他們有幫助：

• 可視化Runge-Kutta方法

• 可視化GJK算法

• 可視化BVH算法

• 可視化Sutherland-Hodgman算法

【版權聲明】

原文作者未做權利聲明，視為共享知識産權進入公共領域，自動獲得授權。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!