碰撞檢測技術及在橋梁視景仿真中的應用

袁麗娜 ， 趙貴斌

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

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

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

1 碰撞檢測概述

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

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

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

2 碰撞檢測算法

碰撞檢測算法可從時間域和空間域對其進行分類。

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

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

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

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

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

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

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

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

基于物體空間的碰撞檢測算法一直是人們研究的重點，已有相當的研究成果，如層次表示法、幾何推理、代數范式、空間劃分、解析方法和最優化方法等技術的應用，使碰撞檢測有了更好的實時效果?；谖矬w空間的碰撞檢測算法可進一步分為基于物體的不同表示模型和基于不同的空間結構的表示模型。

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

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

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

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

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

圖1 層次包圍球樹構建圖

圖2 AABB 包圍盒

圖3 OBB 層次樹

圖4 6-dop 包圍盒

圖5 凸包圍盒

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

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

3 碰撞檢測的優化[4]

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

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

圖6 網格分割示意圖

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

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

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

圖8 運動物體的凸殼

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

4 碰撞檢測在橋梁視景仿真中的應用

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

圖9 船橋模型

圖10 球覆蓋檢測

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

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

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

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

5 結 論

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

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

[2] 魏迎梅. 虛擬環境中碰撞檢測問題的研究[D]. 長沙：國防科學技術大學, 2000.

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

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

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

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