虛擬環境中碰撞檢測問題概述

摘要：硅撞檢測是計算機動畫，物理仿真，機器人學等領域的重要課題。文章首先介紹了碰撞檢測的基本步驟，然后從時間域和空間域等不同的角度對碰撞檢測算法進行了分類概連，最后闡述了碰撞檢測問題研究的重要意義。

關鍵詞：虛擬環境碰撞橙洲 相交 層次包圍盒.

中圖分類號；TP391.9 文獻標識碼：A 文章編號：1674-098X(2012)02(b)-0240-01

1碰撞檢測的基本步驟.

在虛擬環境中，碰撞檢測算法在處理包含大量物體的復雜場景時，首先將多數明顯不相交的物體對進行快速排除，然后再對可能相交的物體對進行進一步檢測，把這個過程統稱為碰撞檢測算法的初步檢測階段。而對于初步檢測階段的后繼階段，稱之為碰撞檢測算法的詳細檢測階段。

1.1初步檢測階段

當動態場景中物體的個數超過兩個，碰撞檢測遇到的最明顯的問題就是需要對所有N個物體進行兩兩求交檢測，其時間復雜度達到O(N2)。這個問題也被稱為“完全物體對檢測問題”。很明顯，這是任何碰撞檢測算法在處理多物體的場景時都會遇到的嚴重影響算法效率的問題。因此，當場景中物體個數較多時，非常有必要利用一些優化策略或方法來快速排除明顯不發生碰撞的物體，找出潛在的相交區域或潛在的相交物體對。空間剖分法是初步檢測階段所采用的技術之一，其基本思想是將場景均勻剖分成一個個小方塊區間，檢查這些小方塊內是否有物體存在，否則將不包括物體的區間剔除，從而快速判斷出潛在的相交區域。

1.2詳細檢測階段

碰撞檢測算法經過初步檢測階段確定了潛在的相交區域或潛在的相交物體對集合之后，轉入詳細檢測階段。詳細檢測階段根據已經確定的潛在的相交區域或潛在的相交物體對集合做進一步的相交檢測。這個過程分為兩個層次：一個是逐步求精層；另一個是精確求交層。逐步求精層通常采用兩種典型的加速技術：空間層次剖分技術和層次包圍盒樹技術。空間層次剖分技術與初步檢測階段的空間剖分技術相類似，但要把潛在的相交區域子空間繼續割分下去，直到找到相交物體的多邊形面片，而層次包圍盒樹技術是指算法利用預先建構好的物體層次包圍盒樹，通過遍歷物體對的層次包圍盒樹，遞歸檢測它們的層次包圍盒樹上各層節點包圍盒之間的相交情況，直到各一個層次樹的葉子節點，最終獲取物體對的相交檢測結果的技術。在精確求交層中，碰撞檢測算法主要處理多邊形面片減基本體素之間的精確相交檢測。基于多邊形表示的碰撞檢測算法在精確求交層中需要進行多邊形與多邊形之間的相交檢測。由于多邊形均可轉化為三角形，并且三角形之間的相交檢測更簡單，因而有很多研究工作集中于三角形之間的快速相交檢測。

2碰撞檢測算法分類

碰撞檢測算法種類繁多，本文從兩個角度對碰撞檢測算法進行分類：一是從時間域的角度來分；二是從空間域的角度來分。

2.1基于時間域的碰撞檢測算法

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

靜態碰撞檢測算法是指當場景中物體在整個時間軸上都不發生變化時，用來檢測在這個靜止狀態中各物體之間是否發生碰撞的算法。靜態碰撞檢測問題在計算幾何中有著廣泛的研究，一般對這類算法沒有實時性的要求，但是對算法精度要求較高；離散碰撞檢測算法則是指在時間軸的每個離散點t(m_o)，t(m₁)t(m_n)……上不斷地檢測場景中所有物體之間是否發生碰撞的算法。離散碰撞檢測算法在每一時間離散點上可以通過類似于靜態碰撞檢測算法的方祛來實現，它更注重算法的效率；連續碰撞檢測算法是指在一個連續的時間間隔(t(m_o)，t(m_n)內，判斷運動物體是否與其他物體相交的算法。該算法的研究一般涉及到四維時空問題或結構空間精確的建模問題，這類算法通常計算速度比較慢，尤其是在大規模場景中無法實現實時的碰撞檢測。

2.2基于空間域的碰撞檢測算法

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

2.2.1基于物體空間的碰撞檢測算法

基于物體空間的碰撞檢測算法一直是人們研究的重點，它可采用不同的空間結構來提高效率，根據所用空間結構的不同可將它們分為兩類：空間剖分法和層次包圍盒法。這兩類方怯都是通過盡可能減少進行精確求交的物體對或基本幾何元素的個數來提高算法效率的。不同的是，空間剖分法采用對整個場景的層次剖分技術來實現，場景的層次剖分方法主要有均勻剖分、BSP樹、k-d樹和八叉樹等。層次包圍盒琺則是對場景中每個物體建構合理的層次包圍盒樹來實現。物體的層次包圍盒可以根據其所采用包圍盒類型的不同來加以區分，主要包括包圍球、AABB包圍盒、OBB包圍盒以及k-DOPs包圍盒等。

2.2.2基于圖象空間的碰撞檢測算法

基于圖象空間的碰撞檢測算法一般利用圖形硬件對物體的二維圖象采樣和相應的深度信息來判別兩物體之間的相交情況。這類算法優勢在于能有效利用圖形硬件加速技術來減輕CPU的計算負擔，從而達到提高算法效率的目的。但是基于圖象空間的碰撞檢測算法由于其檢測結果的不精確性和依賴硬件支持而一直發展較慢。近些年，隨著圖形硬件計算性能的迅速增長，基于圖象空間的碰撞檢測算法進入了一個新的快速發展階段。Rossignac和Shinya等人在1991年前后開創性地提出了圖形硬件輔助碰撞檢測的方法。

3結語

在虛擬場景中，主要是如何解決碰撞檢測的實時性和精確性的矛盾，不同的應用場合，對實時性和精確性的要求不盡相同，因此大部分碰撞檢測算法都是針對具體的應用場合設計的，沒有一種算法適用于所有的情形。目前的碰撞檢測算法主要集中于在靜態環境下兩個物體之間碰撞檢測效率的研究，而對于動態環境下、復雜虛擬場景中虛擬對象之間的碰撞檢測問題，高效率的檢測算法還不多，因此快速有效的碰撞檢測算法對提高虛擬環境的真實性起著至關重要的作用。

參考文獻

[1]J.Cohen，M.Lin，D.Manocha，et a1.I-COLLIDE：An Interactive and ExactConMon Detection System for Large-Scale Envimnme nts.In Proc.0f theACM Interactive 3D Graphics ConI.，1995：189-196.

[2]S.Redon，A.Kheddar，S.Coquillart.Fast Continuous Collision Detectionbetween mgid Bodies.Compumr Graph-ics Forum，2002，2l(3)：279-287.

[3]郭海儒.基于OBB層次包圍盒樹的實時碰撞檢測算法.[太原理工大學碩士研究生學位論文].2004：7～19.