碰撞檢測技術(shù)及在橋梁視景仿真中的應(yīng)用

袁麗娜 ， 趙貴斌

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

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

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

1 碰撞檢測概述

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

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

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

2 碰撞檢測算法

碰撞檢測算法可從時間域和空間域?qū)ζ溥M行分類。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 AABB 包圍盒

圖3 OBB 層次樹

圖4 6-dop 包圍盒

圖5 凸包圍盒

（2） 基于圖像間的碰撞檢測算法

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

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

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

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

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

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

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

圖7 球體覆蓋碰撞檢測示意圖

圖8 運動物體的凸殼

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

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

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

圖9 船橋模型

圖10 球覆蓋檢測

圖11 船和橋墩的OBB 層次樹圖

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

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

將計算出的特征向量歸一化，這些向量就是 OBB 的方向向量 au、 av和 aw。找到OBB 的中 心及其半徑，計算出凸殼上的點在向量方向上的投影大小；找到每個方向上的最大值和最小值，從而確定包圍盒的大小和位置。

5 結(jié) 論

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

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

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

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

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

[5] 王志強, 洪嘉振, 楊 輝. 碰撞檢測問題研究綜述[J]. 軟件學(xué)報, 1999, 10(5)： 545-551.

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