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

2019-11-14 09:46:30

字體：大中小

供稿：網(wǎng)友

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

正文如下：

多邊形碰撞

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

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

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

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

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

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

注意：分離軸定理需要一點(diǎn)數(shù)學(xué)向量的知識，所以在深究這個算法前，你最好復(fù)習(xí)一下這方面的內(nèi)容。

算法簡述

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

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

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

投影問題

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

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

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

角度選取

如何在代碼中實(shí)現(xiàn)

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

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

步驟一圖解

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

步驟二圖解

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

步驟三圖解

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

步驟四圖解

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

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

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

那么如何處理圓呢？

在分離軸定理中，檢測圓與檢測多邊形相比，會有點(diǎn)點(diǎn)奇異，但仍然是可以實(shí)現(xiàn)的。

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

圓的投影軸

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

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

優(yōu)點(diǎn)與不足

和其他的碰撞檢測技術(shù)一樣，分離軸定理算法有它自己的優(yōu)點(diǎn)和不足。以下是其一些優(yōu)點(diǎn)和不足的簡要概述：

優(yōu)點(diǎn)

（譯者：原來老外也喜歡先談優(yōu)點(diǎn)啊～>～）

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

不足

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

可能這個算法會有更多優(yōu)點(diǎn)和不足之處，但是我想這應(yīng)該是最主要的幾個了。

總結(jié)

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

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

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

以下是譯者補(bǔ)充的內(nèi)容

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