[譯]碰撞檢測之分離軸定理算法講解

本文翻譯自 @sevenson 的文章 Separating Axis Theorem (SAT) Explanation 。原文作者用的是ActionScript 3來編寫算法，不過文中主要講述的還是算法原理，我想一旦算法原理被我們掌握了，選擇什么編程語言來實現算法都是次要的事情了。 本人并非英文專業，所以文中翻譯得有不妥或疏漏之處，歡迎各位指正，謝謝！

正文如下：

分離軸定理（英文簡稱SAT）是一項用于檢測凸多邊形碰撞的技術。

我絕不是這個方面的專家，但當檢測碰撞的需求出現在我面前之后，我做了大量的閱讀并最終在ActionScript 3中實現了它。

我想，我應該把我所學到的分享給大家，希望大家不會在這方面被坑得很慘：）

當我發現我需要在flash中檢測多邊形碰撞時，我碰巧地遇到了一個叫“分離軸定理”的方法。但唯一的問題是，為了真正地掌握它，我可費了不少功夫。

在閱讀了大量有關碰撞檢測的資料，并參看了一些代碼示例后，這個方法總算被我領悟了。

為了幫助其他那些不精通數學的開發者，我想我應該寫下這一篇能快速闡明這個算法工作原理的簡短介紹。我還在下文引入了一個使用分離軸定理實現的demo，以及供大家下載并使用的ActionScript 3源代碼。 （譯者：demo和源代碼請到原文中查看和下載）

注意：分離軸定理需要一點數學向量的知識，所以在深究這個算法前，你最好復習一下這方面的內容。

算法簡述

從根本上來講，分離軸定理（以及其他碰撞算法）的用途就是去檢測并判斷兩個圖形之間是否有間隙。分離軸定理中用到的方法使算法本身顯得十分獨特。

我所聽到過分離軸定理的最好類比方式是這樣的：

假想你拿一個電筒從不同的角度照射到兩個圖形上，那么會有怎樣的一系列的陰影投射到它們之后的墻壁上呢？

如果你用這個方式從每一個角度上對這兩個圖形進行處理，并都找不到任何的間隙，那么這兩個圖形就一定接觸。如果你找到了一個間隙，那么這兩個圖形就顯而易見地沒有接觸。

從編程的角度來講，從每個可能的角度上去檢測會使處理變得十分密集。不過幸運的是，由于多邊形的性質，你只需要檢測其中幾個關鍵的角度。

你需要檢測的角度數量就正是這個多邊形的邊數。也就是說，你所需檢測的角度最大數量就是你要檢測碰撞的兩個多邊形邊數之和。舉個例子，兩個五邊形就需要檢測10個角度。

如何在代碼中實現

這是一個簡易但比較啰嗦的方法，以下是基本的步驟：

步驟一：從需要檢測的多邊形中取出一條邊，并找出它的法向量（垂直于它的向量），這個向量將會是我們的一個“投影軸”。

步驟二：循環獲取第一個多邊形的每個點，并將它們投影到這個軸上。（記錄這個多邊形投影到軸上的最高和最低點）

步驟三：對第二個多邊形做同樣的處理。

步驟四：分別得到這兩個多邊形的投影，并檢測這兩段投影是否重疊。

如果你發現了這兩個投影到軸上的“陰影”有間隙，那么這兩個圖形一定沒有相交。但如果沒有間隙，那么它們則可能接觸，你需要繼續檢測直到把兩個多邊形的每條邊都檢測完。如果你檢測完每條邊后，都沒有發現任何間隙，那么它們是相互碰撞的。

這個算法基本就是如此的。

順帶提一下，如果你記錄了哪個軸上的投影重疊值最小（以及重疊了多少），那么你就能用這個值來分開這兩個圖形。

那么如何處理圓呢？

在分離軸定理中，檢測圓與檢測多邊形相比，會有點點奇異，但仍然是可以實現的。

最值得注意的是，圓是沒有任何的邊，所以是沒有明顯的用于投影的軸。但它有一條“不是很明顯的”的投影軸。這條軸就是途經圓心和多邊形上離圓心最近的頂點的直線。

在這以后就是按套路遍歷另一個多邊形的每條投影軸，并檢測是否有投影重疊。

噢，對了，萬一你想知道如何把圓投影到軸上，那你只用簡單地把圓心投影上去，然后加上和減去半徑就能得到投影長度了。

優點與不足

和其他的碰撞檢測技術一樣，分離軸定理算法有它自己的優點和不足。以下是其一些優點和不足的簡要概述：

優點

（譯者：原來老外也喜歡先談優點啊～>～）

• 分離軸定理算法十分得快——它完美地使用了基本的數學向量知識。只要間隙一旦被檢測出來，那么你就能馬上得出結果，消除不必要的運算。
• 分離軸定理算法十分得準——至少據我所知是這樣的。（譯者：突然感覺作者好不靠譜啊，囧……）

不足

• 分離軸定理算法只適用于凸多邊形——復雜的圖形（譯者：指的是凹多邊形，比如五角星）無法使用此方法，除非你把它們分成一些小的凸多邊形，然后依次檢驗這些小的多邊形。
• 分離軸定理算法無法告訴你是那條邊發生的碰撞——僅僅是告訴你重疊了多少和分開它們所需的最短距離。

可能這個算法會有更多優點和不足之處，但是我想這應該是最主要的幾個了。

總結

我希望這篇文章能幫助你了解到分離軸定理算法。我已經盡可能地不提供過多的信息并講解得十分簡明了。（我絕不是數學方面的專家，所以如果我遺漏了什么，我深表歉意）

以下是一些幫助我理解分離軸定理算法的頁面：

• harverycartel.org ——有更多詳細的表述以及很多很酷的示例。我在這個頁面上學到了很多。
• GPWiki.org ——有不錯的講解和代碼示例，我用這些代碼作為編寫自己代碼的基礎。
• Tony Pa ——向量教程，學習向量的不錯資源。
• GameDev.net forum ——一個論壇成員寫的分離軸定理碰撞檢測系統，帶給了我一些計算方面的想法。

以下是譯者補充的內容

我將文中的算法用JavaScript實現了一遍，大家有興趣的話，可以到下面提供的鏈接中下載源代碼或查看在線demo。

源代碼下載

查看在線Demo

 

來自：http://blog.csdn.net/yorhomwang/article/details/54869018