? ? ? ? 這里介紹的是“基元”之間的碰撞檢測凉当，所謂“基元”就是線段枣申、三角形、矩形看杭、平面忠藤、圓、橢圓等各種常見的泊窘、能用一兩個數(shù)學公式表示的圖形熄驼∠窈“基元碰撞檢測”是游戲開發(fā)中常用的手段，用數(shù)學公式求解碰撞結果瓜贾，能讓我們系統(tǒng)性的理解其中的原理诺祸。大家也不用擔心，里面用到的數(shù)學公式祭芦，充其量高中筷笨、大一都學過，都屬于“空間解析幾何”范疇龟劲。
-----------------------------------------------? ?華麗的分割線? ?----------------------------------------------
好接下來開始最簡單的胃夏，“2D線段”與“2D線段”之間的碰撞檢測。注意這里是“線段”昌跌，不是“直線”或者“射線”仰禀，如果搞不清的，建議先搜索一下蚕愤。
先說結果：
? ? ? ? 1.?兩根“線段”之間如果有正常的“相交”答恶，那么結果應該是一個點。
? ? ? ? 2. 在以下情況下沒有交點：平行萍诱、但不重合悬嗓；在很遠處相交，不在線段范圍內(nèi)裕坊。
? ? ? ??3. 如果重合包竹，我們需要特殊處理。
推導過程：
假設在2D坐標系中籍凝，有一條線段周瞎，如下圖所示：
? ? ? ? 起點為P1，坐標為（Xp1饵蒂， Yp1）
? ? ? ? 終點為Q1堰氓，坐標為（Xq1，Yq1）
那么從P1到Q1有一個向量V1苹享，可以表示為 V1 = Q1 - P1，反過來浴麻，Q1 = P1 + V1得问。這個應該很好理解。
好软免，接下來宫纬，對于該線段上任意一個點P，我們可以用如下“參數(shù)方程”表示：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P = P1 + t * V1? ? ? ? ? ? ? ? ? t ∈ [0, 1]?
把V1 = Q1 - P1替代進去膏萧，我們可以得到：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P = P1 + t * (Q1 - P1)? ? ? ? t ∈ [0, 1]
見下圖
其中 t 為變參漓骚，它的范圍是0~1蝌衔，兩邊都是閉區(qū)間，我們可以把它理解為0~100的一個百分比蝌蹂。
? ? ? ? 當?t=0?的時候噩斟，P = P1 + 0 * V1， ==>?P = P1孤个，即P點與P1點重合剃允。
? ? ? ? 當?t=1?的時候，P = P1 + 1 * V1齐鲤， ==>?P = P1 + V1 = P1 + (Q1 - P1) = Q1斥废，即P點與Q1點重合。
? ? ? ? 如果 t=0.5给郊，P = P1 + 0.5 * （P2 - P1） = 0.5 * （P2 + P1）牡肉，即線段的中點，就是50%的位置淆九。
如果 t 超出這個范圍统锤，那么點雖然在該線段所處的“直線”上，但“不在線段范圍內(nèi)”吩屹。如下圖跪另，t > 1。
-----------------------------------------------? ?華麗的分割線? ?----------------------------------------------
接下來我們把第二根線段放進去煤搜，P2 -> Q2免绿，我們可以得到：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? V2 = Q2 - P2
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P = P2 + s * V2? ? ? ? ? ? ? ? ? s ∈ [0, 1]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??P = P2 + s * (Q2 - P2)? ? ? ? s ∈ [0, 1]
大家注意兩根線段的“參數(shù)方程”有點小區(qū)別，我們在第一個方程中用了變參 t擦盾，在第二個方程中用了變參 s嘲驾，以此表示兩個不同的變量，切不可都寫成 t迹卢，否則最后聯(lián)立方程組的時候辽故，會傻傻分不清楚。（仔細想想為什么腐碱？）
-----------------------------------------------? ?華麗的分割線? ?----------------------------------------------
有了以上基礎誊垢，我們就可以開始計算兩根線段之間的碰撞點了。
假設兩根線段相交于點P症见，那么：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??P = P1 + t * V1? ? ? ? ? ? ? ? ? ?t ∈ [0, 1]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??P = P2 + s * V2? ? ? ? ? ? ? ? ? s ∈ [0, 1]
兩個等式左邊都是P喂走，那么我們可以令他們相等：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??P1 + V1 * t =?P2 + V2 * s
把等式處理一下，得到：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??t * V1 – s * V2 = P2 – P1
到目前為止谋作，我們還不能直接求解該方程芋肠，因為這是一個“二元一次方程”，有兩個變量：t 和 s遵蚜，卻只有一個等式帖池，所以是無法得到唯一解的（這可是常識哦）奈惑，我們需要繼續(xù)處理一下。
因為每個點其實有兩個坐標值（x睡汹，y）肴甸，我們可以得到：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??t * V1.x – s * V2.x = （P2 – P1）.x?= P12.x
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??t * V1.y – s * V2.y = （P2 – P1）.y?= P12.y
哈，現(xiàn)在我們就有兩個方程帮孔，構成一個方程組雷滋，來求解兩個變量了。如果到這里文兢，你已經(jīng)會繼續(xù)處理了（比如消元法晤斩、代入法），那就不用繼續(xù)往下看了姆坚，下面我用行列式（線性代數(shù)）來求得 t 和 s 澳泵。
-----------------------------------------------? ?華麗的分割線? ?----------------------------------------------
根據(jù)以上方程，令：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??A = | V1.x? ?V2.x? ?|
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ?| V1.y? ?V2.y? ?|
如果線性代數(shù)還有點印象的話兼呵，對此應該能理解兔辅，行列式不是矩陣，行列式雖然寫起來跟矩陣差不多击喂、有一大堆值维苔，但其實它的結果就是一個數(shù)值：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??A =?V1.x *?V2.y -?V2.x *?V1.y
繼續(xù)：
? ? ? ? ? ? ?T = | P12.x? ?V2.x? ?|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? S = | V1.x? ?P12.x? ?|
? ? ? ? ? ? ? ? ? ? | P12.y? ?V2.y? ?|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? | V1.y? ?P12.y? ?|
? ? ? ? ? ? ?T = P12.x * V2.y - V2.x * P12.y? ? ? ? ? ? ? ? ? ? ? ? ? ?S = V1.x * P12.y - P12.x * V1.y
最終結果：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? { t = T / A
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? {?s = S / A
再回過來看方程，P = P1 + V1 * t =?P2 + V2 * s懂昂，說明線段1在?t 比例?處與線段2相交介时，這個位置是線段2的?s 比例?處。
貌似我們很容易就得到結果了凌彬，且慢沸柔！還有一些情況要判斷：首先這里有除法，那除0是必須要處理的铲敛，如果A = 0褐澎，就無法求得 t 和 s 。這種情況下伐蒋，其實是兩根線段“平行”或者“重合”工三，我們來推導一下：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? A =?V1.x *?V2.y -?V2.x *?V1.y = 0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? V1.x *?V2.y = V2.x *?V1.y
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? V2.y / V2.x = V1.y / V1.x
y/x，結果就是這根線段或直線的“斜率”先鱼。如果兩根線段的“斜率”相等徒蟆，那可不就是“平行”或“重合”嗎？所以型型，算完 A，先別著急算 T 和 S全蝶，如果A = 0闹蒜，那函數(shù)可能就要返回False了寺枉，認為沒有相交。
如果A不等于0绷落，就可以繼續(xù)得到 t 和 s姥闪。接著我們要判斷?t 和 s的范圍，前面我們說過砌烁，t ∈ [0, 1]? &&? s ∈ [0, 1]筐喳，才是相交在兩個線段范圍內(nèi)，如果任一條件不滿足函喉，仍然不是“線段相交”避归，而是“直線相交”或“射線相交”。
-----------------------------------------------? ?華麗的分割線? ?----------------------------------------------
原理講完了管呵，求解部分的偽代碼如下：
? ? ? ? ? ??A =?V1.x *?V2.y -?V2.x *?V1.y
? ? ? ? ? ??if (A == 0)? ? ? ? ? ? ? return Parallel Or SuperPosition;
? ? ? ? ? ??T = P12.x * V2.y - V2.x * P12.y
? ? ? ? ? ??t = T / A
? ? ? ? ? ??if ( t < 0 || t > 1 )? ? ?return No Intersection;
? ? ? ? ? ??S = V1.x * P12.y - P12.x * V1.y
? ? ? ? ? ??s = S / A
? ? ? ? ? ??if ( s < 0 || s > 1 )? ? return No Intersection;
? ? ? ? ? ??P = P1 + t * V1
? ? ? ? ? ??return P;? ? ? ? ? ? ? ? ? // P就是最終交點
