袁麗娜 ， 趙貴斌

（1. 北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191； 2. 五邑大學(xué)機(jī)電工程學(xué)院，廣東 江門(mén) 529020）

碰撞檢測(cè)(Collision Detection)及優(yōu)化是視景仿真技術(shù)中一項(xiàng)非常重要的技術(shù)，是影響視景仿真系統(tǒng)逼真度和現(xiàn)實(shí)感的重要因素。碰撞檢測(cè)問(wèn)題是基于現(xiàn)實(shí)生活中一個(gè)普遍存在的事實(shí)：兩個(gè)不可穿透的對(duì)象不可能共享相同的空間區(qū)域。因此，碰撞檢測(cè)的基本任務(wù)是確定兩個(gè)或多個(gè)物體彼此之間是否發(fā)生接觸或穿透。碰撞檢測(cè)涉及到3D 空間、幾何模型表示、分層數(shù)據(jù)結(jié)構(gòu)、測(cè)試方法等，它實(shí)質(zhì)上是通過(guò)判斷兩個(gè)物體之間的距離（即距離檢測(cè)）或重疊與相交（即碰撞檢測(cè)）情況來(lái)實(shí)現(xiàn)的[1]。

在計(jì)算機(jī)圖形學(xué)和仿真系統(tǒng)中，碰撞檢測(cè)是一個(gè)最為基本且重要的組成部分，主要應(yīng)用領(lǐng)域包括視景仿真系統(tǒng)、虛擬制造、計(jì)算機(jī)動(dòng)畫(huà)、游戲、機(jī)器人技術(shù)、CAD /CAM 等。隨著計(jì)算機(jī)硬件和軟件的發(fā)展，虛擬物體越來(lái)越逼真，動(dòng)作也越來(lái)越細(xì)膩，這就要求虛擬物體要用更精細(xì)的模型來(lái)表示，由此也要消耗更多的時(shí)間進(jìn)行虛擬物體的碰撞檢測(cè)，這就對(duì)檢測(cè)算法提出更高的要求，故對(duì)碰撞檢測(cè)技術(shù)的研究就顯得尤為重要。

1 碰撞檢測(cè)概述

通常碰撞檢測(cè)分為靜態(tài)碰撞檢測(cè)、偽動(dòng)態(tài)碰撞檢測(cè)和動(dòng)態(tài)碰撞檢測(cè)。其中，靜態(tài)碰撞檢測(cè)是判斷某一活動(dòng)對(duì)象在某個(gè)特定的位置和方向上是否與環(huán)境中的對(duì)象相交；偽動(dòng)態(tài)碰撞檢測(cè)是根據(jù)活動(dòng)對(duì)象的運(yùn)動(dòng)路徑檢測(cè)它是否在某一離散的采樣位置方向上與環(huán)境中的對(duì)象相交；動(dòng)態(tài)碰撞檢測(cè)則是檢測(cè)活動(dòng)對(duì)象掃過(guò)的空間區(qū)域是否與環(huán)境中的對(duì)象相交。三者的側(cè)重點(diǎn)各不相同，靜態(tài)碰撞檢測(cè)一般沒(méi)有實(shí)時(shí)性的要求，在計(jì)算幾何中有著廣泛的研究；動(dòng)態(tài)碰撞檢測(cè)的研究一般都考慮到四維時(shí)空問(wèn)題并要求結(jié)構(gòu)空間精確的建模；而偽動(dòng)態(tài)碰撞檢測(cè)有關(guān)于時(shí)間點(diǎn)和運(yùn)動(dòng)參數(shù)之間的信息，可以通過(guò)開(kāi)發(fā)時(shí)空相關(guān)性獲得較好的性能。虛擬環(huán)境中的碰撞檢測(cè)一般屬于偽動(dòng)態(tài)碰撞檢測(cè)的范圍[2]。大多數(shù)的仿真系統(tǒng)中的碰撞檢測(cè)也屬于偽動(dòng)態(tài)碰撞檢測(cè)的范疇。

仿真環(huán)境中的碰撞檢測(cè)問(wèn)題可簡(jiǎn)化描述為：碰撞檢測(cè)系統(tǒng)的輸入模型為環(huán)境對(duì)象和活動(dòng)對(duì)象的幾何模型，模型由基本的幾何元素構(gòu)成。環(huán)境對(duì)象可以是剛體對(duì)象，也可以是彈性體對(duì)象，它們的位置和方向不發(fā)生變化，但彈性體對(duì)象在外力的作用下可發(fā)生形變?；顒?dòng)對(duì)象可以在仿真環(huán)境中自由運(yùn)動(dòng)，方向和大小完全取決于仿真過(guò)程或者用戶(hù)控制的輸入設(shè)備，很難用關(guān)于時(shí)間的運(yùn)動(dòng)方程來(lái)表示，只能得到某一時(shí)間采樣點(diǎn)相對(duì)于前一時(shí)間采樣點(diǎn)或一固定參照物的運(yùn)動(dòng)信息（旋轉(zhuǎn)角度和平移量）表示。其任務(wù)是確定在某一時(shí)刻兩個(gè)幾何模型是否發(fā)生干涉，即判斷它們的交集是否為空，一旦碰撞發(fā)生，還需確定碰撞點(diǎn)[2]。

碰撞檢測(cè)的開(kāi)始一般是假設(shè)當(dāng)前仿真環(huán)境中物體還未發(fā)生碰撞，再根據(jù)用戶(hù)的操作，開(kāi)始更新移動(dòng)對(duì)象的位置。若有碰撞發(fā)生，則將對(duì)象回移到移動(dòng)前的位置，則避免了它穿越被碰撞物。如果兩個(gè)完全封閉的多面體發(fā)生碰撞時(shí)，其中一個(gè)多面體至少會(huì)有一個(gè)面與另一個(gè)多面體的至少一個(gè)面發(fā)生相交。若能在碰撞發(fā)生時(shí)立刻檢測(cè)到相交，然后將兩個(gè)物體的位置稍做調(diào)整，則可消除碰撞現(xiàn)象。以上是實(shí)現(xiàn)碰撞檢測(cè)的基本方法[3]。

2 碰撞檢測(cè)算法

碰撞檢測(cè)算法可從時(shí)間域和空間域?qū)ζ溥M(jìn)行分類(lèi)。

從時(shí)間域的角度，碰撞檢測(cè)算法可分為靜態(tài)碰撞檢測(cè)算法、離散碰撞檢測(cè)算法和連續(xù)碰撞檢測(cè)算法三類(lèi)。

靜態(tài)碰撞檢測(cè)算法是指當(dāng)場(chǎng)景中物體在整個(gè)時(shí)間軸t 上都不發(fā)生變化時(shí)，用于檢測(cè)在這個(gè)靜止?fàn)顟B(tài)中各物體之間是否發(fā)生碰撞的算法。靜態(tài)碰撞檢測(cè)問(wèn)題在計(jì)算幾何中有著廣泛的應(yīng)用與研究，一般對(duì)這類(lèi)算法沒(méi)有實(shí)時(shí)性的要求，但對(duì)算法精度要求較高。

離散碰撞檢測(cè)算法則是指在時(shí)間軸的每個(gè) 離散點(diǎn) nttt ,,,10… 上不斷地檢測(cè)場(chǎng)景中所有物體 之間是否發(fā)生碰撞的算法。從本質(zhì)上說(shuō)，離散碰撞檢測(cè)算法在每一時(shí)間離散點(diǎn)上可以通過(guò)類(lèi)似于靜態(tài)碰撞檢測(cè)算法的方法來(lái)實(shí)現(xiàn)的，但它更注重算法效率。從整個(gè)時(shí)間軸來(lái)看，由于算法的時(shí)間離散特性，這類(lèi)算法至少存在以下兩個(gè)問(wèn)題：① 存在刺穿現(xiàn)象。當(dāng)時(shí)間步長(zhǎng)過(guò)大時(shí)，兩物體可能在發(fā)生了一定深度的刺穿后才被檢測(cè)到已發(fā)生碰撞，因此無(wú)法保證物體的運(yùn)動(dòng)真實(shí)性；② 存在碰撞遺漏的情況。對(duì)于較狹窄的物體，當(dāng)運(yùn)動(dòng)物體在相鄰時(shí)間離散點(diǎn)上的兩個(gè)位置恰好處于該狹窄物體兩側(cè)時(shí)，離散算法將無(wú)法正確地檢測(cè)出物體所發(fā)生的碰撞。

連續(xù)碰撞檢測(cè)算法是指在一個(gè)連續(xù)的時(shí)間 間隔[ t0, tn]內(nèi)，判斷運(yùn)動(dòng)物體是否與其他物體相 交的算法。連續(xù)碰撞檢測(cè)算法的研究一般涉及到四維時(shí)空問(wèn)題及結(jié)構(gòu)空間精確的建模，這類(lèi)算法能較好地解決離散碰撞檢測(cè)算法存在的上述兩個(gè)問(wèn)題，但通常計(jì)算速度比較慢，尤其是在大規(guī)模場(chǎng)景中很難實(shí)現(xiàn)實(shí)時(shí)碰撞檢測(cè)。

離散碰撞檢測(cè)算法盡管存在一些問(wèn)題，但由于其檢測(cè)過(guò)程的快速性能較好地迎合大多數(shù)對(duì)實(shí)時(shí)碰撞檢測(cè)的需求，所以仍是目前碰撞檢測(cè)算法研究的重點(diǎn)和熱點(diǎn)。此外，人們還可通過(guò)一些優(yōu)化方法在一定程度上減輕或降低離散碰撞檢測(cè)算法的上述兩個(gè)問(wèn)題的影響。例如，采用自適應(yīng)步長(zhǎng)技術(shù)和可中斷的碰撞檢測(cè)技術(shù)等來(lái)改善這兩個(gè)問(wèn)題。因此，在視景仿真系統(tǒng)中大多采用離散算法作為系統(tǒng)的碰撞檢測(cè)算法。

從空間域的角度來(lái)分，碰撞檢測(cè)算法大體可分為兩大類(lèi)：一類(lèi)是基于物體空間的碰撞檢測(cè)算法；一類(lèi)是基于圖像空間的碰撞檢測(cè)算法。這兩類(lèi)算法的主要區(qū)別是利用物體三維幾何特性進(jìn)行相交判斷還是利用物體二維投影的圖像加上深度信息來(lái)進(jìn)行相交分析。

基于圖像空間的碰撞檢測(cè)算法是一類(lèi)較新的算法，它能有效地利用圖形硬件的繪制加速功能來(lái)提高碰撞檢測(cè)算法的效率。近幾年圖形硬件技術(shù)的飛速發(fā)展，圖形加速卡在性能不斷迅速提高的同時(shí)甚至出現(xiàn)了可編程的功能，使得基于圖像空間的碰撞檢測(cè)算法進(jìn)入了一個(gè)新的發(fā)展階段。

（1） 基于物體空間的碰撞檢測(cè)算法

基于物體空間的碰撞檢測(cè)算法一直是人們研究的重點(diǎn)，已有相當(dāng)?shù)难芯砍晒?，如層次表示法、幾何推理、代?shù)范式、空間劃分、解析方法和最優(yōu)化方法等技術(shù)的應(yīng)用，使碰撞檢測(cè)有了更好的實(shí)時(shí)效果?；谖矬w空間的碰撞檢測(cè)算法可進(jìn)一步分為基于物體的不同表示模型和基于不同的空間結(jié)構(gòu)的表示模型。

物體的表示模型不同，所采用的碰撞檢測(cè)算法就不同。因此，合理的選擇物體的表示模型能提高碰撞檢測(cè)算法的效率。目前在三維圖形和CAD/CAM 領(lǐng)域中存在多種幾何表示模型，但最主要的是多邊形表示模型和非多邊形表示模型。

面向不同表示模型的碰撞檢測(cè)技術(shù)各有特點(diǎn)，算法效率也各有不同。合理的空間結(jié)構(gòu)選擇可提高碰撞檢測(cè)算法的效率，根據(jù)所用空間結(jié)構(gòu)的不同可將碰撞檢測(cè)算法分為兩類(lèi)：空間剖分法(Space Partition)和層次包圍盒樹(shù)(Hierarchical Bounding Volume Trees)。這兩類(lèi)方法都是通過(guò)盡可能減少進(jìn)行精確求交的物體或圖元對(duì)數(shù)來(lái)提高算法的效率。不同的是，空間剖分法采用對(duì)整個(gè)場(chǎng)景的層次剖分來(lái)實(shí)現(xiàn)簡(jiǎn)化，而層次包圍盒樹(shù)是對(duì)場(chǎng)景中的每個(gè)物體構(gòu)建合理的層次包圍盒樹(shù)來(lái)實(shí)現(xiàn)簡(jiǎn)化。

場(chǎng)景的層次剖分方法主要有均勻剖分、BSP樹(shù)、k-d 樹(shù)和八叉樹(shù)(Octree)等?；谶@些空間剖分技術(shù)的碰撞檢測(cè)算法也頻繁出現(xiàn)，但這類(lèi)碰撞檢測(cè)算法在處理不同的場(chǎng)景和具有不同形狀及復(fù)雜度的物體時(shí)較難保持比較一致的檢測(cè)效率。

物體的層次包圍體樹(shù)可以根據(jù)其所采用包圍體類(lèi)型的不同來(lái)加以區(qū)分，主要包括層次包圍球樹(shù)、AABB 層次樹(shù)、OBB 層次樹(shù)、k-dop 層次樹(shù)、QuoSpo 層次樹(shù)、凸塊層次樹(shù)以及混合層次包圍體樹(shù)等。圖1～圖5 分別給出了層次包圍球、AABB 盒、OBB 層次樹(shù)、6-dop 包圍盒、凸包圍盒的示意圖。

建構(gòu)物體層次包圍體樹(shù)既可采取自頂向下的策略，也可自底向上來(lái)進(jìn)行。目前基于層次包圍體樹(shù)的算法多數(shù)采取自頂向下的方式來(lái)建構(gòu)物體的層次包圍體樹(shù)。

圖1 層次包圍球樹(shù)構(gòu)建圖

圖2 AABB 包圍盒

圖3 OBB 層次樹(shù)

圖4 6-dop 包圍盒

圖5 凸包圍盒

（2） 基于圖像間的碰撞檢測(cè)算法

基于圖像空間的碰撞檢測(cè)算法一般利用圖形硬件對(duì)物體的二維圖像采樣和相應(yīng)的深度信息來(lái)判別兩個(gè)物體之間的相交情況。這類(lèi)算法的優(yōu)勢(shì)在于能有效利用圖形硬件加速技術(shù)來(lái)減輕CPU 的計(jì)算負(fù)荷，從而達(dá)到提高算法效率的目的?；趫D像空間的碰撞檢測(cè)算法由于其檢測(cè)結(jié)果的不精確性和對(duì)于硬件支持的依賴(lài)而一直發(fā)展較慢。近年，隨著圖形硬件計(jì)算性能的迅速增長(zhǎng)，基于圖像空間的碰撞檢測(cè)算法也隨之進(jìn)入了一個(gè)新的快速發(fā)展階段。

3 碰撞檢測(cè)的優(yōu)化[4]

消減碰撞檢測(cè)中不必要的數(shù)據(jù)及計(jì)算，可大大提高碰撞檢測(cè)的效率；通過(guò)運(yùn)動(dòng)填充、檢測(cè)預(yù)判也可節(jié)省用于碰撞檢測(cè)的時(shí)間。

消減數(shù)據(jù)的方法有網(wǎng)格分割法和球體覆蓋法等方式。網(wǎng)格分割是將虛擬空間劃分成規(guī)則的格網(wǎng)，由此將場(chǎng)景中的物體分割成更小的群組（如圖6）。此方法的目的是為了減少系統(tǒng)進(jìn)行碰撞檢測(cè)時(shí)實(shí)體與實(shí)體的比較次數(shù)，每當(dāng)移動(dòng)一個(gè)物體，就計(jì)算出該物體所在的網(wǎng)格；對(duì)于實(shí)體相互疊置的情況，雖然是三維場(chǎng)景，亦可采用映射二維網(wǎng)格來(lái)分割場(chǎng)景。

圖6 網(wǎng)格分割示意圖

球體覆蓋是用球形近似地表示物體或物體的一部分，然后再判斷這些包圍球是否相交。這樣僅僅需要測(cè)試兩個(gè)球體中心的距離是否小于它們的半徑和，若小于即表示發(fā)生了碰撞，如圖7。如果用球心距離的平方與半徑和的平方進(jìn)行比較，這樣可取得更好的計(jì)算效率，因此可在計(jì)算距離時(shí)除去復(fù)雜的開(kāi)方運(yùn)算。若檢測(cè)到發(fā)生了碰撞，那么就進(jìn)一步提高精度，將大的球體分割成一系列小的球體，并檢查各小球體是否發(fā)生碰撞。通過(guò)不斷地分割檢查直到得到滿(mǎn)意的近似值為止。

細(xì)節(jié)的丟失往往會(huì)造成仿真效果失真現(xiàn)象發(fā)生，因此在進(jìn)行仿真時(shí)應(yīng)高度重視這個(gè)問(wèn)題。在仿真系統(tǒng)中物體的運(yùn)動(dòng)就是物體從一個(gè)空間坐標(biāo)點(diǎn)直接跳躍到另一個(gè)空間坐標(biāo)點(diǎn)。所謂“平滑的”移動(dòng)也是通過(guò)減少跳動(dòng)的距離來(lái)實(shí)現(xiàn)的。物體運(yùn)動(dòng)得越快，它在固定的時(shí)間段內(nèi)跳過(guò)的距離就越大。如果物體在兩幀之間跳過(guò)的距離過(guò)大，就會(huì)發(fā)生“細(xì)節(jié)丟失”現(xiàn)象。因?yàn)?，其它物體有可能在此時(shí)間內(nèi)經(jīng)過(guò)該物體跳過(guò)的空間。因此，需將檢測(cè)延伸至運(yùn)動(dòng)的間隙，也就是運(yùn)動(dòng)間隙填充。為了解決“細(xì)節(jié)丟失”問(wèn)題，須建立一個(gè)圍繞物體的凸殼，該凸殼包圍了物體移動(dòng)所經(jīng)過(guò)的空間。當(dāng)檢測(cè)碰撞時(shí)，可用凸殼代替實(shí)體的實(shí)際形狀（見(jiàn)圖8）。

圖7 球體覆蓋碰撞檢測(cè)示意圖

圖8 運(yùn)動(dòng)物體的凸殼

碰撞檢測(cè)的預(yù)判斷是通過(guò)找出每一實(shí)體上位于其它實(shí)體內(nèi)的頂點(diǎn)來(lái)檢測(cè)碰撞的。例如，若實(shí)體的一個(gè)頂點(diǎn)位于另一實(shí)體內(nèi)，就可知它們存在碰撞，無(wú)須進(jìn)行任何多邊形相交的檢測(cè)。雖然，此方法不足以完全確定一個(gè)碰撞的發(fā)生，但它確實(shí)比多邊形比較的方法快多了。另一種預(yù)判斷的方法是判斷兩個(gè)實(shí)體的包圍盒是否相互疊置，若相互疊置，再用平面分割實(shí)體的方法進(jìn)行檢測(cè)。

4 碰撞檢測(cè)在橋梁視景仿真中的應(yīng)用

這里以船舶與橋墩的碰撞為例說(shuō)明碰撞檢測(cè)在視景仿真的應(yīng)用。在該例中采用柱體來(lái)構(gòu)造橋墩的模型，以凸多面體來(lái)構(gòu)造船舶模型（見(jiàn)圖9）。由于在視景仿真中物體的運(yùn)動(dòng)特性與現(xiàn)實(shí)的物體運(yùn)動(dòng)特性有許多不同，在視景仿真中物體的運(yùn)動(dòng)是以幀的方式在時(shí)間流里進(jìn)行空間的躍動(dòng)，仿真中在同樣距離的運(yùn)動(dòng)中設(shè)置的幀數(shù)越多越接近現(xiàn)實(shí)的物體運(yùn)動(dòng)，但同樣會(huì)帶來(lái)更多的仿真計(jì)算和渲染時(shí)間。在該例中先使用球體覆蓋技術(shù)（見(jiàn)圖10）和檢測(cè)預(yù)判斷來(lái)優(yōu)化檢測(cè)計(jì)算，再使用OBB 層次樹(shù)來(lái)進(jìn)行碰撞檢測(cè)（見(jiàn)圖11），得到了理想的效果。

圖9 船橋模型

圖10 球覆蓋檢測(cè)

圖11 船和橋墩的OBB 層次樹(shù)圖

首先計(jì)算出可能會(huì)與船舶發(fā)生碰撞的橋墩以及船舶的凸殼，假設(shè)可以得到n 個(gè)三角形，記 做△ pkqkrk，其中 pk、qk和 rk分別是三角形k的三個(gè)頂點(diǎn)；可以將三角形k 的面積記作 ak，k = 1,2,3,… , n ，那么凸殼的整個(gè)面積就可以記作aH，三角形i 的質(zhì)心為 mi= ( pi+ qi+ ri)/3。整個(gè)凸殼的質(zhì)心 mH是所有三角形質(zhì)點(diǎn)的加權(quán)平 均值

給出計(jì)算3×3 協(xié)方差矩陣的公式c，其特征向量就是所求包圍盒的方向向量

將計(jì)算出的特征向量歸一化，這些向量就是 OBB 的方向向量 au、 av和 aw。找到OBB 的中 心及其半徑，計(jì)算出凸殼上的點(diǎn)在向量方向上的投影大?。徽业矫總€(gè)方向上的最大值和最小值，從而確定包圍盒的大小和位置。

5 結(jié) 論

隨著計(jì)算機(jī)硬件的快速發(fā)展，普通的PC 機(jī)具有了更好的性能，在圖形顯示和運(yùn)行速度方面有了顯著的提升，以前在普通PC 機(jī)無(wú)法完成的仿真現(xiàn)在也能夠順利實(shí)現(xiàn)了，而隨著軟件的發(fā)展和仿真系統(tǒng)的廣泛應(yīng)用，關(guān)于碰撞檢測(cè)算法的研究也越來(lái)越深入，仿真系統(tǒng)也有了更好的細(xì)節(jié)表現(xiàn)。

[1] 丁 佳. 大型復(fù)雜場(chǎng)景中快速碰撞檢測(cè)技術(shù)的研究[D]. 成都： 電子科技大學(xué), 2007.

[2] 魏迎梅. 虛擬環(huán)境中碰撞檢測(cè)問(wèn)題的研究[D]. 長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué), 2000.

[3] 涂 超. 虛擬空間中的碰撞檢測(cè)[J]. 武漢理工大學(xué)學(xué)報(bào), 2001, 11(11)： 84-87.

[4] 涂 超, 顏輝武. 碰撞檢測(cè)技術(shù)研究[J]. 計(jì)算機(jī)工程與應(yīng)用. 2001, 19： 142-143.

[5] 王志強(qiáng), 洪嘉振, 楊 輝. 碰撞檢測(cè)問(wèn)題研究綜述[J]. 軟件學(xué)報(bào), 1999, 10(5)： 545-551.

[6] 徐 剛, 陸廷金, 耿汝波. 高速虛擬仿真物體的碰撞檢測(cè)方法[J]. 彈箭與制導(dǎo)學(xué)報(bào), 2008, 28(1)： 323-326.