Collision / Contact / Intersection
名詞collision。動詞collide。物理學詞彙。力學詞彙。
碰撞。兩個形狀，相互接觸。
名詞contact。動詞contact。物理學詞彙。力學詞彙。
碰觸。兩個形狀，接觸地點。
名詞intersection。數學詞彙。幾何學詞彙。
交集。兩個形狀，重疊區域。
動詞intersect。數學詞彙。幾何學詞彙。
相交。兩個形狀，相互交錯、相互重疊。
「偵測碰撞」等同「偵測交集是否為空集合」。
碰撞止於形狀邊界。相交深入形狀內部。電腦做計算，一切皆數學。儘管我們談論物理碰撞模擬，但是此處介紹數學相交演算法。
Narrow-phase Collision
兩個物體碰撞。根據物體形狀，有著各種演算法。
凸多面體有著高速演算法。大家把一個多面體切割成多個凸多面體，以便降低計算時間。
是否碰撞、侵入距離。
Convex Polygon Collision
二維凸多邊形碰撞。O(N)。
樸素算法：二維碰撞即是某兩條線段碰撞。枚舉各種線段配對，偵測是否碰撞。O(N²)。
不知名算法：兩個凸多邊形的交集，恰是凸多邊形。兩個凸多邊形的所有邊，涵蓋了交集的所有邊。保留交集的邊，捨棄其餘的邊，以此設計演算法。
一個凸多邊形的所有邊，恰好依照角度排序。實施merge sort，合併兩個凸多邊形的所有邊，依照角度排序。
依序掃描所有邊，每當凸多邊形更替，就偵測前邊與後邊是否碰撞。若碰撞，後邊是交集；若無碰撞，後邊不是交集。
上述過程是multi-pass。亦可改成one-pass，一邊合併、一邊偵測碰撞。
Convex Polyhedron Collision
三維凸多面體碰撞，有SAT和GJK兩種演算法，都是O(N²)。
樸素算法：三維碰撞即是某兩個三角形碰撞。枚舉各種三角形配對，偵測是否碰撞。O(N²)。
separating axis theorem：三角形碰撞改成影子碰撞。叉積改成點積，節省時間。
一、首先介紹影子。
三角形視作牆壁。另一個三角形視作飛鏢。碰撞視作飛鏢穿牆。
三角形頂點，投影到牆壁法向量，偵測影子碰撞。
二、三角形碰撞、影子碰撞，兩者不等價。
三角形為主角：
一、三角形碰撞，保證影子碰撞。
二、三角形無碰撞，不保證影子有無碰撞。
影子為主角：
三、影子碰撞，不保證三角形有無碰撞。
四、影子無碰撞，保證三角形無碰撞。
此演算法以影子為主角。因此採用第四個性質：影子無碰撞。
三、設計演算法。
凸多面體A，每一個面分別作為牆壁。
凸多面體A與B，每一個點皆投影到牆壁法向量。
偵測影子無碰撞。法向量朝外視作正向。投影處越外視作越高。A中最高點低於B中最低點，或者，B中最高點低於A中最低點。
四、援引hyperplane separation theorem。
兩個凸的形狀，能以任意超平面隔開，即無碰撞。
一旦影子無碰撞，立即結束演算法，節省時間。
Gilbert–Johnson–Keerthi algorithm：枚舉順序，朝向交集。以此減少枚舉數量，節省時間。
一、首先介紹Minkowski difference。
形狀A、形狀B，兩者的Minkowski difference，是形狀C。
A中一點，B中一點，兩者座標相減，得到C中一點。
A中一點，B中一點，枚舉各種配對，得到整個形狀。
二、如何利用Minkowski difference偵測碰撞呢？
兩個凸多面體的Minkowski difference，恰是一個凸多面體。
證明很簡單。凸的定義，寫成數學式子，相減一下就行了。
兩個凸多面體碰撞，那麼Minkowski difference包含原點。沒有碰撞，那麼不含原點。
證明很簡單。交點，座標相減是0。無交點，座標相減非0。
最後得到一個偵測碰撞演算法：先計算Minkowski difference，再判斷是否包含原點。
三、如何找出Minkowski difference，並且偵測碰撞呢？
樸素算法：求出整個Minkowski difference。
取巧算法：求出部分Minkowski difference，節省時間。
一邊建立四面體剖分，一邊移動至相鄰四面體。逐步靠近原點。
首先求出任意四個頂點，形成四面體。每回合找到一個新頂點，並且移動至相鄰四面體。逐步靠近原點。
Minkowski difference恰是凸的，四面體剖分恰是連通的，得以使用貪心法。只要逐步靠近原點，終會抵達最近之處。
補充說明一下。二維的情況下，移動過程可以視作Minkowski difference所有頂點實施binary search，找到最靠近原點的頂點。
所有頂點形成一條鏈。每回合找到一個新頂點，將鏈截成兩段，並且保留靠近原點的那一段。
四、如何找出Minkowski difference的新頂點呢？
找出一個朝向原點的方向向量。A中最高點、B中最低點，兩者相減，得到Minkowski difference的新頂點。
這宛如SAT。本來枚舉A的面，現在枚舉A與B的頂點。本來使用法向量，現在使用朝向交集的方向向量。由於走向原點，只需枚舉部分頂點，不需枚舉所有面，節省時間。
還可以順手偵測影子無碰撞，立即結束演算法。由於走向一致，只需檢查A中最高點低於B中最低點，不需檢查B中最高點低於A中最低點，又節省一半時間。
五、如何找出朝向原點的方向向量，進而求得新頂點呢？
求第一點：使用任意方向向量。例如X軸方向。
求第二點：使用反方向。
求第三點：前兩點形成線段。再與原點形成三角形。三角形法向量、線段向量，兩者叉積，得到朝向原點的向量。
求第四點：前三點形成三角形。三角形法向量，正向與反向，找出朝向原點者。
求後續各點：前四點形成四面體。三個新三角形、一個舊三角形。三個新三角形法向量，找出朝向原點者。任一皆可。
六、補充一下。GJK也能計算最短距離。
兩個凸多面體的最短距離，即是Minkowski difference與原點的最短距離。
四面體的移動過程當中，隨時計算四面體與原點的最短距離。
Farthest Point in a Direction
SAT和GJK都用到了「給定一個方向向量，找到凸多面體中的最高點」。
樸素算法：凸多面體的所有點，投影到方向向量，得到投影量，取最大值。O(N)。
凸多邊形：預先切成上鏈與下鏈。兩鏈都是單峰函數，無論方向向量為何。兩鏈分別實施bisection method求得極值，其中一個極值是最大值。O(logN)。
凸多面體：預先切成上殼與下殼。兩殼都是單峰函數，無論方向向量為何。使用quadtree儲存頂點，方便實施bisection method。O(N)。
Simple Polygon Collision
二維簡單多邊形碰撞。O(NlogN)。
Bentley–Ottmann algorithm：直接視作大量線段相交問題，直接使用其演算法。平移的掃描線，輔以二元搜尋樹。
Simple Polyhedron Collision
三維簡單多面體碰撞，好像是O(N²)。
Lin–Canny Algorithm：我沒有研究。
V-Clip：我沒有研究。
Bounding Volume
每個物體不分青紅皂白，實施SAT或CJK偵測碰撞，O(N)。
替物體設計簡易外框，得以迅速偵測碰撞，O(1)，節省時間。外框沒有碰撞，保證物體沒有碰撞，大可不必實施SAT或CJK。外框有碰撞，才實施SAT或CJK，偵測物體是否碰撞。
外框偵測碰撞，些微增加時間；物體偵測碰撞，大幅減少時間。剛體運動當中，少數時候有碰撞，多數時候沒有碰撞。利大於弊。
外框造型有三種：
bounding circle / bounding sphere：體積最小的球。紀錄中心座標、半徑。平均O(N)。
bounding box / bounding volume：體積最小的長方體，細分為AABB和OBB。
axis-aligned bounding box (AABB)：必須對齊世界座標軸。紀錄中心座標、長寬高。O(N)。
oriented bounding box (OBB)：不必對齊世界座標軸。記錄中心座標、長寬高、轉角。二維O(NlogN)。三維O(N³)。
剛體運動，適合採用OBB。OBB外框最貼切，誤判最少，節省最多時間。儘管OBB時間複雜度極高，但是剛體不會變形，只需預先計算一次。
柔體運動，不適合採用OBB。柔體隨時變形，重算太花時間。
Circle Collision / Sphere Collision
二維圓形碰撞、三維球體碰撞。O(1)。
樸素算法：圓心連線。若碰撞，圓心距離小於等於半徑相加。
Axis-aligned Box Collision / Axis-aligned Cuboid Collision
二維擺正長方形碰撞、三維擺正長方體碰撞。O(1)。
樸素算法：SAT。「A的X座標最大值」小於「B的X座標最小值」則無碰撞。AB對調，如法炮製。Y座標、Z座標，如法炮製。
Box Collision / Rectangular Cuboid Collision
二維長方形碰撞、三維長方體碰撞。O(1)。
樸素算法：SAT。A轉正，B隨之旋轉，檢查座標極值大小。B轉正，如法炮製。
Broad-phase Collision
大量物體碰撞。使用區域資料結構，儲存所有物體，節省時間。
樸素算法：枚舉所有物體配對。建立O(1)，偵測O(N²)。
uniform grid：找出每個物體的bounding sphere的直徑的最大值。建立網狀方格，格子寬度是直徑。每當發生碰撞，物體一定位在相同格子或相鄰格子。實施bucket sort，所有物體存入對應格子。建立O(N+Kᴰ)，偵測平均O(N+3ᴰ)。
quadtree / octree：當相同區域有多個物體，就遞迴分割區域，直到每個區域只有一個物體。首先（由葉往根）逐步擴大區域寬度，直到超過前述直徑。然後（由根往葉）檢查轄下所有區域所有物體。建立O(N+K2ᴰ)，偵測平均O(N+K)。
bounding region hierarchy / bounding volume hierarchy：物體計算AABB。外框依照物體位置排序。相鄰兩個外框不斷併成一個外框，形成二元樹。（由根往葉）先檢查大外框碰撞，再檢查小外框碰撞。建立O(DNlogN)，偵測平均O(N)。
當物體座標隨時改變，要嘛每次重算，要嘛使用動態資料結構。我沒有研究。Box2D作者正在實作，預計出現於下一版本。我到時候再來研究。
