碰撞檢測（CD）在很多圖形應用中都有著極其重要的角色，CAD/CAM，游戲動畫，基于物理的建模，基本上所有的虛擬現實模擬都會用到，
我們常說的CD其實指的是Collision handling，可以分為三個部分：Collision detection，Collision determination，Collision response。Collision detection階段得到的是一個bool值，表示是否檢測到碰撞，Collsion determination 是找到碰撞的部位，Collision response則決定碰撞的物體做出的反應。
一個健壯的CD系統需要擁有下面的一些特性：
1.能夠處理大量多邊形的交互，無論近距離還是遠距離都能處理；
2.可以處理任意的多邊形湯（polygon soups），它不一定保證是凸的，也不一定包含鏈接信息；
3.模型能夠做剛體的運動，比如平移，旋轉，或者其他更復雜的運動；
4.提供有效的包圍體（Boundig volume），為幾何體創建合適的BV能夠提高算法的效率，當然BV的創建也要夠快；
一個大的游戲場景中可能有成百上千的運動物體，一個CD系統要能夠處理這樣的場景，如果場景中有n個運動的物體和m個靜止的物體，那么每一幀要進行檢測計算的次數就是：
首先是檢測所有靜止的物體和運行哦那個的物體是否有碰撞，然后是檢測運動的物體之間的碰撞。這是最暴力的算法，m和n的大小直接關系到計算量。
實際應用中，不可能使用這樣的計算，應為無法支付這樣的性能代價，特別是在大的場景中。
注意下面要討論的內容都指的剛體運動。
在一個×××游戲中，一輛車奔馳在路上，在碰撞檢測方面要做的就是車輪和路面的檢測，非別檢測每個輪子和地面mesh的碰撞，但有更簡單有效的方法。
將運動的物體近似成一組光線，對于上面的情形，我們可以在每個車輪上放一個光線，光線的原點就在輪子的最下端，當車輛只與地面進行接觸的時候，這種近似非常有效。
在車的運動過程中，不斷檢測光線到地面的距離distance，如果為0，則剛好在地面上，如果大于0,則車輪離開了地面，如果小于0,則車輪已經陷入地面了。通過計算distance，CD 系統還可以做出對應的碰撞處理，離開地面就落下來，陷入地面就升上去，如果場景更加復雜的話就要考慮更多的情況，比如要考慮車與墻面的碰撞，車于車之間的碰撞，就要在車體上放更多的光線了。
加速算法方面，最常用的就是層級表示（hierarchical representation）。整個環境場景可以用axis-aligned BSP樹來表示，然后接下來就是光線求交的問題了。當然還有其他的加速數據結構和算法，可以參考這里：Real-Rime Rendering (8) - 光線求交（Ray intersection）
在實際應用中，ray的原點通常不是在界面上，而是在物體里面，這樣當輪子陷入地面的時候，就能夠保證求得的distance為正值。
線段和標準的BSP樹能夠很有效的檢測到碰撞，一個線段可以表示一個點為從p0到p1，可能這個線段會和物體有很多交點，但第一個點就是就是這個線段與物體的碰撞點。注意在這種情況下BSP樹是依附于物體表面（surface aligned）的，而不是平行軸（axis-aligned）的。如下圖所示。每一個切面都和墻面或者地面平行。
這種方式的檢測很容易從質點擴展到球。只要將每個表面從法向向外擴展r。這樣的話碰撞檢測起來將是非常地快，而且對于不同半徑的球體，BSP樹都不用改變。假設場景中有個面的方程是 n·x+d=0,那么對這個面進行調整之后為n·x+d+/-r=0. +r還是-r取決于要檢測的面 。
游戲中的一個角色用一個球體來近似并不是那么合適，通常會用一個包圍角色的凸包（convex hull）或者圓柱來代替。
這里要說的碰撞檢測主要是關于兩個模型的。每一個模型都用層級的Bounding volumes來代表，對應不同的BVs，上層的代碼都是一樣的。
層級建樹
一種名為k-ary 樹的數據結構在這里會用到，在樹中每一個節點都有k個孩子，很多算法用的都是最簡單的情況，也就是二叉樹，即k=2,在樹中的每個非葉子節點都代表著一個BV，包含著以它為根的所有子節點。對于任意點的的bunding volume記為ABV，A的所有子節點的集合記為Ac 。
主要有三種建樹的方法：自底向下(bottom-up)，增量插入(incremental tree-insertion)，自頂向下(top-down)。為了建立有效、進湊的結構，通常BV是越小越好，對于CD，肯定也是如此。
自底向上的方法首先找到緊挨在一起的一組多邊形，然后用BV將其包裹起來，然后不斷地用新的BV去包裹老的BV，直到最后只有一個BV將整個物體都包住，這個BV也就是BVH樹的根。
增量插入地方法初始的時候是一棵空樹，然后不斷找出BV插入到樹中，這種方法的難點是在插入的時候并不是簡單地插入葉子節點，可能需要添加一個父節點，也就是一個父BV。
自頂向下的方法是最常用的，初始的時候是一個單節點的樹，這個節點是包含整個物體的BV，接下來要做的就是divide-and-conquer了。 將根分裂成k個部分，每個部分都生成一個BV將其包圍起來，然后不斷循環，到最后一個層級的BVH就建立了。
CD算法的一個很大的挑戰就是找到合適的BVs，還有就是一個高效平衡的樹結構。記住平衡樹是的最優的，因為每個葉子節點的深度都是一樣的，這意味著查找葉子節點的時間基本相同，而碰撞檢測的時間也就不會因為位置不同而出現很大的波動。但也有其他的情況，比如在某種情形下，某些部位經常會出現碰撞，則最好將其放在離樹根比較近的葉子上，而有些部位基本不會發生碰撞，那么最好將其放在離根遠的葉子上。
碰撞檢測算法
最簡單的情況是只判斷兩個物體是否相撞，則算法的停止條件就是范縣有兩個三角形有重疊。在下面的算法中，A和B是模型層級樹的根節點，TA表示A的葉子節點，基本的思路就是當重疊出現的時候，打開BV，遞歸調用函數進行檢測。
算法中分了很多中情況，第一種是兩個節點都是葉子節點的情況，第二種是兩個節點都不是葉子的情況，最后是當兩個節點有一個是葉子的情況。
時間復雜度
上面算法的復雜度主要由模型的BV和物體的運動?？偟臅r間計算公式如下：
nv：BV/BV重疊測試數；cv：單個BV/BV重疊所耗費時間；
np：圖形單元重疊測試數；cp：兩個圖形單元重疊所耗費時間；
nu：由于模型運動需要update的BV數量；cu：update一個bv所耗費的時間。
通過創建一個好的層級樹可以減少一些時間復雜度，但有時候都是一些trade-off，比如如果使用比較簡單的BV，檢測的時間會減少，但BV就不是最優的了。
在大的場景中的碰撞檢測如果還是用上面的方法并不是很現實，特別是在時間復雜度要求高的情況下，比如游戲。下面要介紹的是一種兩層的碰撞檢測系統，目標是處理復雜的大型場景。第一級檢測的是檢測場景中可能發生碰撞的物體，得到的結果傳到第二級，在第二級檢測中實現具體物體的碰撞檢測。
廣義相碰撞檢測 Broad Phase Collision Detection
第一級檢測的目標是盡量傳遞少的需要檢測的物體到第二層，這是一個High-level的檢測。
算法的開始首先將每一個物體用一個BV包圍住，然后用算法找到所有重疊的 BV/BV 。一個簡單的方法是每個物體都用一個AABB來包圍。為了防止BV的重新構造，AABB一定要足夠大，能夠包容住物體的剛體運動。劃分好AABB之后，檢測就可以很快的進行。
除了Box，球體也可以使用，而且是合理的，因為球體可以包含物體任意方向的旋轉。
掃描和修剪 Sweep and Prune
這里假設每個物體都有一個AABB包圍，在掃描修建算法中，使用了時間相干性（temporal coherence）。在這里，時間相干性質指的是物體在幀與幀之間的相對位置變化是相對小的，在這種情況下，上一幀所得到的碰撞檢測結果可以用于下一幀的計算，這個特性也可以稱為幀-幀相干性（Frame-to-frame coherence）。
如果兩個AABB是重疊的，那么這兩個AABB在各個軸上的投影也是重疊的，將物體投影到坐標軸上，可以將一個三維的問題降低到三個軸上的一維問題，這就是 Sweep and Prune的核心思想。
1.將物體的AABB分離到三個坐標軸上。得到若干個區間。
2.根據區間的終點坐標由小到大排序。
3.逐個遍歷排序結果，當遇到一個區間的起始點的時候，就將這個區間放到一個列表中；當遇到一個區間的終點時，就將這個區間從列表中清除。當在列表中存在區間，而又遇到一個新區間的起始點時，則遇到的區間與列表中的所有區間重疊。
4.如果一對物體在三個坐標軸上的區間都重疊，那么他們的AABB相疊。
注意，排序的算法最快可以到O（nlogn），找到覆蓋的區間的復雜為O（k），則整個算法的復雜度為O（nlogn+k）。由于時間的相干性，插入或者冒泡排序可以達到很高的效率，應為相對的重疊區域變化不會很大。
最終的時間可以控制在線性的時間，但當出現clumping的時候，排序的時間復雜度可能退化到O（n^2），這時候我們可以繞過某個軸的檢測，有時候這樣做是可行的。
real time rendering 3rd
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
