碰撞檢測

通信通道中的碰撞檢測

就是計算機邊發送數據邊檢測通道上的信號電壓大小。

當一個站檢測到的信號電壓擺動值超過了一定的門限值時，就會認為匯流排上至少有兩個站同時在發送數據，表示產生了碰撞。在發生碰撞的時候，匯流排上傳輸信號產生了嚴重的失真，無法從中恢復出有用的信息來。每一個正在發送數據的站，一旦發現匯流排上產生了碰撞，就立即停止發送，以免繼續浪費資源，再等待一段時間后再次發送。

以太網取51.2μs為爭用期長度。對於10Mb/s乙太網，在爭用期內可發送512bit，即64B。則乙太網在發送數據時，若前64B沒有衝突，則後續的數據就不會發生衝突。如果發生衝突了一定是在發送的前64B以內。由於一檢測到衝突就立即中止發送，這時已經發出去的數據一定小於64B，因此，乙太網規定最短有效長為64B，凡長度小於64B的幀都是由於衝突而異常中止的無效幀。

發送數據的站一旦發現發生碰撞時，除了立即停止發送數據外，還要繼續發送若干比特的認為干擾信號，以便讓所有用戶都知道已經發生了碰撞。

3D遊戲中的碰撞檢測

碰撞檢測在3D遊戲中至關重要，好的碰撞檢測要求人物在場景中可以平滑移動，遇到一定高度內的台階可以自動上去，而過高的台階則把人擋住，遇到斜率較小的斜坡可以上去，斜率過大則把人擋住，在各種前進方向被擋住的情況下都要儘可能地讓人物沿合理的方向滑動而不是被迫停下。在滿足這些要求的同時還要做到足夠精確和穩定，防止人物在特殊情況下穿牆而掉出場景。

碰撞檢測做得好了是應該的，不易被人注意到，因為這符合我們日常生活中的常識。做得差了卻很容易讓人發現，人物經常被卡住不能前進或者人物穿越了障礙。所以大部分人都覺得寫碰撞檢測代碼是件吃力不討好的事情，演演算法複雜、容易出bug、不容易出彩。下面還是回到正題，看看我們該如何解決這個難題。

早期3D遊戲的碰撞檢測多數基於格子或者BSP樹，基於格子的系統實現簡單但精度不夠，不屬於嚴格意義的3D碰撞檢測。基於BSP樹的碰撞檢測一度十分流行，演演算法基本已經成熟定型，但它的固有缺點卻使它不太適合現在的遊戲。BSP樹需要很長的預處理時間不適合載入時計算，BSP劃分經常會產生原多邊形數三到四倍的多邊形，考慮到不用保存法線、顏色、uv等信息也要增加將近一倍的資源容量，在一個大的遊戲中將模型資源的容量從200M增加到400M相信是大部分人都不願接受的。目前對於任意複雜三角形集合（mesh）的碰撞檢測多數基於BVTree（bounding volume tree），具體可以是aabb tree，obb tree或者K-dop tree，這也是當今各種物理引擎和碰撞檢測引擎流行的做法。

上面是碰撞檢測按數據結構不同的分類，按檢測方式又可以分為離散點的碰撞檢測和連續碰撞檢測（CCD continuous collision detection）。離散點的碰撞檢測是指定某一時刻T的兩個靜態碰撞體，看它們之間是否交迭，如果沒有交迭則返回它們最近點的距離，如果交迭則返回交迭深度，交迭方向等。連續碰撞檢測則是分別指定在T1、T2兩個時刻兩個碰撞體的位置，看它們在由T1運動到T2時刻的過程中是否發生碰撞，如果碰撞則返回第一碰撞點的位置和法線。連續碰撞檢測是最為自然的碰撞檢測，可以大大方便碰撞響應邏輯的編寫，可以很容易避免物體發生交迭或者穿越。離散點的碰撞檢測則沒有那麼友好，當檢測到碰撞時兩個物體已經發生了交迭，如果其中有三角形網格對象那麼已經有許多三角形發生了交迭，如何將兩個交迭的對象分開並按合理的方式運動是一個挑戰。雖然連續碰撞檢測是最自然的方式，但它的實現非常複雜，運算開銷也很大，所以目前大部分成熟的物理引擎和碰撞檢測引擎還是採用了基於離散點的碰撞檢測，為了避免物體交迭過深或者彼此穿越，大多都要採用比較小的模擬步長。

目前成功商業3D遊戲普遍採用的碰撞檢測是採用BSP樹及包裝盒方式。簡單講就是採用一個描述用的正方體或者球型體包裹住3D物體對象整體（或者是主要部分），之後根據“描述用”包裝盒的距離、位置等信息來計算是否發生碰撞。