前段時間，項目中需要改進一下碰撞算法。我查了很多資料。。最後完成了http://hi.baidu.com/jrsnail/blog/item/007e9c7faf1ba90328388a8d.html這個對我影響很大。。
我們以前的算法是用的凸包算法。就是檢測點是否在一個矩形中。算法分析：http://kevinew.blog.sohu.com/14735858.html有詳細介紹，通過左轉判定公式，隻需判斷 x1*y2-x2*y1 的正負值,為正說明 p1 到 p2 為左轉. 其實就是判斷一個向量到另一個向量是逆時針轉還是順時針轉 ，如果點d在矩形邊四條邊的左邊或都在四條邊的右邊，說明這個點在矩形内。。。
這個是我們以前的算法，後來，我把算法改成了分離軸算法，
這一系列的文章并不是我的原創,如果有同仁需要檢視英文的原文的話,位址我曾經給出過，英文水準是有限的,如果有什麼地方沒有翻譯清楚,可以向發郵件或者直接留言.
需要說明的是這裡的範例都是基于OPENGL的代碼。
2D多邊形碰撞檢測和回報
介紹
這是一篇論證如何在2D動作遊戲中執行碰撞檢測的文章（Mario,宇宙入侵者等），為了保證它的高效性和精确性，碰撞檢測是以多邊形為基礎的，而不是以sprite為基礎。這是兩種不同的設計途徑。
基于sprite的檢測執行的是檢測sprites的像素的交叉，以這種方式來檢測碰撞。多邊形是使用向量數學來精确的計算點，時間和碰撞的方向。當多邊形隻是一種近似sprite自身的時候，它就超越了sprite系統。
表現出了更精确的實體現象，例如彈性，摩擦，在一個随機的形狀中來處理斜坡。
碰撞檢測相對一個高速的sprite來講是更加的精确的。在一個基于sprite的系統中，對象有可以在一個強力的跳躍中因為速度太快而互相穿越。
這是一個基于向量數學的系統，是以可以擴充到3D，但是一個sprite碰撞系統被完全的限制到了2D中。
特色：
因為運算法則的限制，系統隻能操作凸多邊形，例如三角形，矩形，五邊形，圓形。在一個非凸多邊形中，你可以将這些多邊形分成三角形來處理。
無論是快速或者慢速的多邊形，他的處理方式都是一樣的。不管對象的移動有多快，碰撞也不會丢失的。他也可以來處理交疊，分開已經交叉的對象。
裡面的範例也有線段的交叉。這可以用來模拟子彈。
它也提供了一些簡單的實體系統，模拟彈力，一些基本的摩擦力和靜摩擦力。在斜坡上的一些特性它也可以模拟。
這裡也有一個剛體系統的例子，引用的是Chrsi Hecker的實體文章。
局限性：
碰撞的種類，我的意思是它不能順序的處理碰撞。在一個快速的對象中這可能會有問題。一旦一個碰撞被檢測了，它便會直線的離開。你可以檢測到第一個碰撞并處理它，然後再找到其他的碰撞。但是在一個2D的動作遊戲中，這是很具有殺傷力的。
必要條件：
一些普通的原料，一個編譯器，範例是基于GLUT（GL開發包）的架構，是以需要下載下傳一個小的GLUT SDK和一個相容opengl的顯示卡。
你還需要對向量數學有一個基本的了解。這裡的文章不準備對點乘進行講解，但是它可以幫助你對向量的操作有更好的了解。
對于剛體，你需要對Chris Hecker的文章仔細的閱讀一下。它需要你付出更多，但是它是值得的，并不是多麼的困難。
内容清單：
文章1：分離軸的方法
文章2：擴充應用于碰撞回報的分離軸的方法。
文章3：對快速移動的對象來檢測他的碰撞。
文章4：基本的Arcade碰撞回報
文章5：處理旋轉
文章6：計算碰撞點
文章7：剛體動力學。
分離軸的方法：
這是碰撞檢測的核心，原理是非常簡單的，也非常的容易實作。它也是快速和穩定的，因為沒有除法在運算中被使用。我将會帶給大家一個簡單的兩個BOX碰撞測試的例子。
一些碰撞算法 該運算法則試着來确定兩個對象中的一個合适的面。如果有這樣的一個面存在，如果有這樣的面存在，說明對象是分離的，沒有交叉。
為了确定對象是否是分離的。隻要将這個對象投影到這個平面的法線上，然後比較它們之間的間隔看他們是否交叉。
是以，很明顯有無數個邊能夠适合這兩個分離的對象，但是已經證明你隻要測試少數的幾個面就可以了，對于上面圖形中的兩個BOX，你可以看到邊的法線是形狀B的邊。
從上面的這些形狀中可以發現，那些即将被測試的分離面是兩個BOX的邊的法線。對于這兩個BOX而言，你隻需要測試4個分離的面。在這4個面中，一旦你發現一個分離面分隔了這兩個BOX。你就可以知道了這兩個BOX是分離的。然後傳回一個沒有碰撞的标記。
如果這4個面沒有分隔這兩個BOX，那麼這兩個BOX肯定是交叉的，說明他們有一個碰撞。
擴 展到一般的多邊形，該運算法則仍然是适用的。隻不過是測試的邊變化了。那些分離的面的法線是和每個多邊形的邊的垂直方向是平行的。在下面的圖形中，你可以 看到有兩個分離面被測試。在紅色的面被測試的時候，你可以看到那兩個間隔是交叉的，但是在藍色的被測試的時候，間隔并沒有交叉。所有藍色的面是分離面，對 象是以是沒有交叉的。
一些碰撞算法 現在，我們已經有一個檢測他們是否碰撞的法則了。這些代碼也能夠被擴充為3D。
所有的分隔軸都需要被測試
計算的是每一個多邊形所在的軸的間隔（分離面的法線）
測試這些間隔是否交叉。
bool Intersect(Polygon A, Polygon B)
{
for(I = 0; I < A.num_edges; I ++)
{
Vector N = Vector(-A.EdgeDir[I].y, A.EdgeDir[I].x);
if (AxisSeparatePolygons(N, A, B))
return false;
}
for(I = 0; I < B.num_edges; I ++)
{
Vector N = Vector(-B.EdgeDir[i].y, B.EdgeDir[I].x);
if (AxisSeparatePolygons (N, A, B))
return false;
}
return true;
}
void CalculateInterval(Vector Axis, Polygon P, float& min, float& max)
{
float d = Axis dot P.vertex[0];
min = max = d;
for(I = 0; I < P.num_vertices; I ++)
{
float d = P.vertex[I] dot Axis;
if (d < min)
min = d;
else
if(d > max)
max = d;
}
}
到這裡，這個計算兩個2D多邊形碰撞的運算法則是非常快和穩定的。邊的方向不一定是機關化的，是以你可以避免将邊的方向都存儲起來，你可以直接根據多邊形的頂點來建構這些邊的方向。
for(J = A.num_vertices-1, I = 0; I < A.num_vertices; J = I, I ++)
{
Vector E = A.vertex[I] – A.vertex[J];
Vector N = Vector(-E.y, E.x);
if (AxisSeparatePolygons(N, A, B))
return false;
}
最先看到是英文版的算法。。後來進一步了解算法時，發現了這個文章。。覺得講的挺詳細，，就記了下來。。英文網站是：
http://www.gamedev.net/page/resources/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604