Real-Rime Rendering (9) - 碰撞檢測(cè)（Collision Detection）

提要

       碰撞檢測(cè)（CD）在很多圖形應(yīng)用中都有著極其重要的角色，CAD/CAM，游戲動(dòng)畫(huà)，基于物理的建模，基本上所有的虛擬現(xiàn)實(shí)模擬都會(huì)用到，

      我們常說(shuō)的CD其實(shí)指的是Collision handling，可以分為三個(gè)部分：Collision detection，Collision determination，Collision response。Collision detection階段得到的是一個(gè)bool值，表示是否檢測(cè)到碰撞，Collsion determination 是找到碰撞的部位，Collision response則決定碰撞的物體做出的反應(yīng)。

       一個(gè)健壯的CD系統(tǒng)需要擁有下面的一些特性： 

1.能夠處理大量多邊形的交互，無(wú)論近距離還是遠(yuǎn)距離都能處理；

2.可以處理任意的多邊形湯（polygon soups），它不一定保證是凸的，也不一定包含鏈接信息；

3.模型能夠做剛體的運(yùn)動(dòng)，比如平移，旋轉(zhuǎn)，或者其他更復(fù)雜的運(yùn)動(dòng)；

4.提供有效的包圍體（Boundig volume），為幾何體創(chuàng)建合適的BV能夠提高算法的效率，當(dāng)然BV的創(chuàng)建也要夠快；

      一個(gè)大的游戲場(chǎng)景中可能有成百上千的運(yùn)動(dòng)物體，一個(gè)CD系統(tǒng)要能夠處理這樣的場(chǎng)景，如果場(chǎng)景中有n個(gè)運(yùn)動(dòng)的物體和m個(gè)靜止的物體，那么每一幀要進(jìn)行檢測(cè)計(jì)算的次數(shù)就是：

首先是檢測(cè)所有靜止的物體和運(yùn)行哦那個(gè)的物體是否有碰撞，然后是檢測(cè)運(yùn)動(dòng)的物體之間的碰撞。這是最暴力的算法，m和n的大小直接關(guān)系到計(jì)算量。

實(shí)際應(yīng)用中，不可能使用這樣的計(jì)算，應(yīng)為無(wú)法支付這樣的性能代價(jià)，特別是在大的場(chǎng)景中。

注意下面要討論的內(nèi)容都指的剛體運(yùn)動(dòng)。

光線碰撞檢測(cè) Collision Detection  with Rays

        在一個(gè)×××游戲中，一輛車(chē)奔馳在路上，在碰撞檢測(cè)方面要做的就是車(chē)輪和路面的檢測(cè)，非別檢測(cè)每個(gè)輪子和地面mesh的碰撞，但有更簡(jiǎn)單有效的方法。

        將運(yùn)動(dòng)的物體近似成一組光線，對(duì)于上面的情形，我們可以在每個(gè)車(chē)輪上放一個(gè)光線，光線的原點(diǎn)就在輪子的最下端，當(dāng)車(chē)輛只與地面進(jìn)行接觸的時(shí)候，這種近似非常有效。

         在車(chē)的運(yùn)動(dòng)過(guò)程中，不斷檢測(cè)光線到地面的距離distance，如果為0，則剛好在地面上，如果大于0,則車(chē)輪離開(kāi)了地面，如果小于0,則車(chē)輪已經(jīng)陷入地面了。通過(guò)計(jì)算distance，CD 系統(tǒng)還可以做出對(duì)應(yīng)的碰撞處理，離開(kāi)地面就落下來(lái)，陷入地面就升上去，如果場(chǎng)景更加復(fù)雜的話(huà)就要考慮更多的情況，比如要考慮車(chē)與墻面的碰撞，車(chē)于車(chē)之間的碰撞，就要在車(chē)體上放更多的光線了。

        加速算法方面，最常用的就是層級(jí)表示（hierarchical representation）。整個(gè)環(huán)境場(chǎng)景可以用axis-aligned BSP樹(shù)來(lái)表示，然后接下來(lái)就是光線求交的問(wèn)題了。當(dāng)然還有其他的加速數(shù)據(jù)結(jié)構(gòu)和算法，可以參考這里：Real-Rime Rendering (8) - 光線求交（Ray intersection）

       在實(shí)際應(yīng)用中，ray的原點(diǎn)通常不是在界面上，而是在物體里面，這樣當(dāng)輪子陷入地面的時(shí)候，就能夠保證求得的distance為正值。

用DSP 樹(shù)處理動(dòng)態(tài)碰撞檢測(cè) Dynamic CD using BSP Trees

        線段和標(biāo)準(zhǔn)的BSP樹(shù)能夠很有效的檢測(cè)到碰撞，一個(gè)線段可以表示一個(gè)點(diǎn)為從p0到p1，可能這個(gè)線段會(huì)和物體有很多交點(diǎn)，但第一個(gè)點(diǎn)就是就是這個(gè)線段與物體的碰撞點(diǎn)。注意在這種情況下BSP樹(shù)是依附于物體表面（surface aligned）的，而不是平行軸（axis-aligned）的。如下圖所示。每一個(gè)切面都和墻面或者地面平行。

       這種方式的檢測(cè)很容易從質(zhì)點(diǎn)擴(kuò)展到球。只要將每個(gè)表面從法向向外擴(kuò)展r。這樣的話(huà)碰撞檢測(cè)起來(lái)將是非常地快，而且對(duì)于不同半徑的球體，BSP樹(shù)都不用改變。假設(shè)場(chǎng)景中有個(gè)面的方程是 n·x+d=0,那么對(duì)這個(gè)面進(jìn)行調(diào)整之后為n·x+d+/-r=0. +r還是-r取決于要檢測(cè)的面 。

         游戲中的一個(gè)角色用一個(gè)球體來(lái)近似并不是那么合適，通常會(huì)用一個(gè)包圍角色的凸包（convex hull）或者圓柱來(lái)代替。

層級(jí)碰撞檢測(cè) General Hierarchical Collision Detection

       這里要說(shuō)的碰撞檢測(cè)主要是關(guān)于兩個(gè)模型的。每一個(gè)模型都用層級(jí)的Bounding volumes來(lái)代表，對(duì)應(yīng)不同的BVs，上層的代碼都是一樣的。

       層級(jí)建樹(shù)

       一種名為k-ary 樹(shù)的數(shù)據(jù)結(jié)構(gòu)在這里會(huì)用到，在樹(shù)中每一個(gè)節(jié)點(diǎn)都有k個(gè)孩子，很多算法用的都是最簡(jiǎn)單的情況，也就是二叉樹(shù)，即k=2,在樹(shù)中的每個(gè)非葉子節(jié)點(diǎn)都代表著一個(gè)BV，包含著以它為根的所有子節(jié)點(diǎn)。對(duì)于任意點(diǎn)的的bunding volume記為ABV，A的所有子節(jié)點(diǎn)的集合記為Ac 。

      主要有三種建樹(shù)的方法：自底向下(bottom-up)，增量插入(incremental tree-insertion)，自頂向下(top-down)。為了建立有效、進(jìn)湊的結(jié)構(gòu)，通常BV是越小越好，對(duì)于CD，肯定也是如此。

       自底向上的方法首先找到緊挨在一起的一組多邊形，然后用BV將其包裹起來(lái)，然后不斷地用新的BV去包裹老的BV，直到最后只有一個(gè)BV將整個(gè)物體都包住，這個(gè)BV也就是BVH樹(shù)的根。

        增量插入地方法初始的時(shí)候是一棵空樹(shù)，然后不斷找出BV插入到樹(shù)中，這種方法的難點(diǎn)是在插入的時(shí)候并不是簡(jiǎn)單地插入葉子節(jié)點(diǎn)，可能需要添加一個(gè)父節(jié)點(diǎn)，也就是一個(gè)父BV。

       自頂向下的方法是最常用的，初始的時(shí)候是一個(gè)單節(jié)點(diǎn)的樹(shù)，這個(gè)節(jié)點(diǎn)是包含整個(gè)物體的BV，接下來(lái)要做的就是divide-and-conquer了。 將根分裂成k個(gè)部分，每個(gè)部分都生成一個(gè)BV將其包圍起來(lái)，然后不斷循環(huán)，到最后一個(gè)層級(jí)的BVH就建立了。

       CD算法的一個(gè)很大的挑戰(zhàn)就是找到合適的BVs，還有就是一個(gè)高效平衡的樹(shù)結(jié)構(gòu)。記住平衡樹(shù)是的最優(yōu)的，因?yàn)槊總€(gè)葉子節(jié)點(diǎn)的深度都是一樣的，這意味著查找葉子節(jié)點(diǎn)的時(shí)間基本相同，而碰撞檢測(cè)的時(shí)間也就不會(huì)因?yàn)槲恢貌煌霈F(xiàn)很大的波動(dòng)。但也有其他的情況，比如在某種情形下，某些部位經(jīng)常會(huì)出現(xiàn)碰撞，則最好將其放在離樹(shù)根比較近的葉子上，而有些部位基本不會(huì)發(fā)生碰撞，那么最好將其放在離根遠(yuǎn)的葉子上。

       碰撞檢測(cè)算法

        最簡(jiǎn)單的情況是只判斷兩個(gè)物體是否相撞，則算法的停止條件就是范縣有兩個(gè)三角形有重疊。在下面的算法中，A和B是模型層級(jí)樹(shù)的根節(jié)點(diǎn)，TA表示A的葉子節(jié)點(diǎn)，基本的思路就是當(dāng)重疊出現(xiàn)的時(shí)候，打開(kāi)BV，遞歸調(diào)用函數(shù)進(jìn)行檢測(cè)。

          算法中分了很多中情況，第一種是兩個(gè)節(jié)點(diǎn)都是葉子節(jié)點(diǎn)的情況，第二種是兩個(gè)節(jié)點(diǎn)都不是葉子的情況，最后是當(dāng)兩個(gè)節(jié)點(diǎn)有一個(gè)是葉子的情況。

       時(shí)間復(fù)雜度

             上面算法的復(fù)雜度主要由模型的BV和物體的運(yùn)動(dòng)?？偟臅r(shí)間計(jì)算公式如下：

nv：BV/BV重疊測(cè)試數(shù)；cv：?jiǎn)蝹€(gè)BV/BV重疊所耗費(fèi)時(shí)間；

np：圖形單元重疊測(cè)試數(shù)；cp：兩個(gè)圖形單元重疊所耗費(fèi)時(shí)間；

nu：由于模型運(yùn)動(dòng)需要update的BV數(shù)量；cu：update一個(gè)bv所耗費(fèi)的時(shí)間。

通過(guò)創(chuàng)建一個(gè)好的層級(jí)樹(shù)可以減少一些時(shí)間復(fù)雜度，但有時(shí)候都是一些trade-off，比如如果使用比較簡(jiǎn)單的BV，檢測(cè)的時(shí)間會(huì)減少，但BV就不是最優(yōu)的了。

多物體碰撞檢測(cè)系統(tǒng) A Multiple Objects CD System

        在大的場(chǎng)景中的碰撞檢測(cè)如果還是用上面的方法并不是很現(xiàn)實(shí)，特別是在時(shí)間復(fù)雜度要求高的情況下，比如游戲。下面要介紹的是一種兩層的碰撞檢測(cè)系統(tǒng)，目標(biāo)是處理復(fù)雜的大型場(chǎng)景。第一級(jí)檢測(cè)的是檢測(cè)場(chǎng)景中可能發(fā)生碰撞的物體，得到的結(jié)果傳到第二級(jí)，在第二級(jí)檢測(cè)中實(shí)現(xiàn)具體物體的碰撞檢測(cè)。

廣義相碰撞檢測(cè) Broad Phase Collision Detection

        第一級(jí)檢測(cè)的目標(biāo)是盡量傳遞少的需要檢測(cè)的物體到第二層，這是一個(gè)High-level的檢測(cè)。

        算法的開(kāi)始首先將每一個(gè)物體用一個(gè)BV包圍住，然后用算法找到所有重疊的 BV/BV 。一個(gè)簡(jiǎn)單的方法是每個(gè)物體都用一個(gè)AABB來(lái)包圍。為了防止BV的重新構(gòu)造，AABB一定要足夠大，能夠包容住物體的剛體運(yùn)動(dòng)。劃分好AABB之后，檢測(cè)就可以很快的進(jìn)行。

        除了Box，球體也可以使用，而且是合理的，因?yàn)榍蝮w可以包含物體任意方向的旋轉(zhuǎn)。

掃描和修剪  Sweep and Prune

        這里假設(shè)每個(gè)物體都有一個(gè)AABB包圍，在掃描修建算法中，使用了時(shí)間相干性（temporal coherence）。在這里，時(shí)間相干性質(zhì)指的是物體在幀與幀之間的相對(duì)位置變化是相對(duì)小的，在這種情況下，上一幀所得到的碰撞檢測(cè)結(jié)果可以用于下一幀的計(jì)算，這個(gè)特性也可以稱(chēng)為幀-幀相干性（Frame-to-frame coherence）。

         如果兩個(gè)AABB是重疊的，那么這兩個(gè)AABB在各個(gè)軸上的投影也是重疊的，將物體投影到坐標(biāo)軸上，可以將一個(gè)三維的問(wèn)題降低到三個(gè)軸上的一維問(wèn)題，這就是 Sweep and Prune的核心思想。

1.將物體的AABB分離到三個(gè)坐標(biāo)軸上。得到若干個(gè)區(qū)間。
2.根據(jù)區(qū)間的終點(diǎn)坐標(biāo)由小到大排序。
3.逐個(gè)遍歷排序結(jié)果，當(dāng)遇到一個(gè)區(qū)間的起始點(diǎn)的時(shí)候，就將這個(gè)區(qū)間放到一個(gè)列表中；當(dāng)遇到一個(gè)區(qū)間的終點(diǎn)時(shí)，就將這個(gè)區(qū)間從列表中清除。當(dāng)在列表中存在區(qū)間，而又遇到一個(gè)新區(qū)間的起始點(diǎn)時(shí)，則遇到的區(qū)間與列表中的所有區(qū)間重疊。

4.如果一對(duì)物體在三個(gè)坐標(biāo)軸上的區(qū)間都重疊，那么他們的AABB相疊。

注意，排序的算法最快可以到O（nlogn），找到覆蓋的區(qū)間的復(fù)雜為O（k），則整個(gè)算法的復(fù)雜度為O（nlogn+k）。由于時(shí)間的相干性，插入或者冒泡排序可以達(dá)到很高的效率，應(yīng)為相對(duì)的重疊區(qū)域變化不會(huì)很大。

         最終的時(shí)間可以控制在線性的時(shí)間，但當(dāng)出現(xiàn)clumping的時(shí)候，排序的時(shí)間復(fù)雜度可能退化到O（n^2），這時(shí)候我們可以繞過(guò)某個(gè)軸的檢測(cè)，有時(shí)候這樣做是可行的。

參考 

real time rendering 3rd