基于BVH的快速碰撞檢測技術的研究

卓 婧 關克平 黃曉峰

（上海海事大學商船學院 中國 上海 201306）

0 引言

交互式計算機圖形的應用通常涉及很多復雜的對象，這些對象可能是由數以千計的多邊形組成的，靜態或動態。碰撞檢測是碰撞響應的先決條件，為了避免系統的瓶頸并保證交互的實時性，檢測所需的時間越短越好。文獻[1]中介紹了為實現該目標，需要采用的有效數據結構和碰撞處理算法，文獻[2－3]中介紹與渲染中相類似的空間數據結構。用于計算機圖形，尤其是以碰撞檢測為目的的空間數據結構可看作空間分割技術或模型分割技術[4]?？臻g分割技術的例子有體元網格，八叉樹，K-d樹，R樹和二進制空間分割（BSP）樹等?？臻g分割技術的主要弱點在于它會多次引用包含在不同的子空間的相同對象。這一弊端正是模型分割技術所能彌補的。在這些技術當中，常用于碰撞檢測的一個有效的數據結構便是層次包圍盒（BVH）。

本文主要研究了如何為虛擬世界的物體開發一個改進的層次包圍盒，以及怎樣將得到的層次結構用于模型與周圍環境之間的碰撞檢測。

1 BVH的前期工作

目前，BVH技術在碰撞檢測和可變形物體的模擬領域中應用較廣。對于剛性物體而言，它們的形狀并不隨著時間的改變而改變，故形體的更新和修改并不必要。而可變形物體，特別是在高度動態的環境下，形狀需要隨著坐標的變化而不斷的更新和修改。

關于加速數據結構的議題通常和組建及遍歷密切相關。如果期望構建的結構能很好的適合快速遍歷，必然需要在構建上花費更多的時間。若在運行之前（預處理），構建只需要進行一次，時間會相應縮短。對于動態場景，運行期間有時可能需要重建結構，故上述情況并不適用。而且，如果變形嚴重，最好將結構完全重建。在這種情況下，更新過程將導致加速結構的惡化。

加速數據結構若要支持動態場景，需要考慮如下因素：

①重建或更新——對于動態場景可以完全重建或者結構更新。如果場景是部分或全部靜態的，則無需該操作。根據場景變化還可以考慮綜合的方法。

②完全或部分重建/更新——結構可以簡單地重建或更新。整體的重建（或更新）易進行，且可利用時間長，但場景的幾何條件較高，而部分重建（或更新）的幾何要求則較低。重建并不只是形態的重建，要以一定的標準來識別每一部分結構。

③如果更新加速結構的過程涉及到層級動作，則可用分層的方式處理。

在光線追蹤和碰撞檢測中，加速結構主要用來加快光線與對象以及對象與對象之間的交互過程。這兩個過程均涉及構建和遍歷，在預處理階段實現光線與對象之間的求交，在運行期間處理對象與對象之間的求交。圖1說明了在模擬環境中涉及到BVH的整個過程。

圖1 模擬環境中涉及BVH的過程

靜態場景中的光線追蹤問題已經得到很好的研究，但動態場景的光線追蹤仍待提升。下面，對動態場景中如何提高光線跟蹤能力的方法進行研究。

1）光線追蹤

原先，網格化和Kd樹作為光線追蹤的加速結構較普遍，兩種方法各有所長。

在構建時間方面，網格化優于K-d樹。但K-d樹較之網絡可以提供更高效的遍歷。BVH所需的構建時間可算在之前所提及的加速結構中，它的遍歷過程和Kd樹的過程極為相似。因此，近些年BVH正被逐漸考慮用于動態場景。從圖2可以看出，網格、BVH、K-d樹之間的比較（箭頭所指方向表示高值）。

圖2 三者的效果比較

改進光線追蹤的BVH方法有很多種，如利用早期的分割剪輯技術來生成BVH，使得它能能夠處理有重疊邊界的三角形[5]；分裂的BVH子樹（也稱多樣BVH）相比原始BVH、懶惰BVH[6]及其他類型消耗更少的內存。通常，這些方法主要依據的是更快的層次結構或有效的層次遍歷。

2）可變形物體

在手術模擬中，可變形物體用來代表人體以及內部器官。此外，它也可用于娛樂的計算機生成圖像（CGI）?？勺冃挝矬w的碰撞檢測是目前相當活躍的研究領域，與剛體的碰撞檢測相比，它面臨更多的困難：

·自相交

·隨著模型的變形，加速/空間數據結構需要定期和快速的更新/修改

·碰撞信息，例如滲透深度

雖然可變形物體的研究已經持續了一段時期，但目前并沒有發現效果突出的方法。原因在于每個應用程序需要的輸入類型不同，并且用于每種方法的碰撞信息也各異。和交互式光線追蹤相類似，用于可變形物體的數據結構需要頻繁的修改，可能會導致系統的瓶頸?？勺鱿鄳母倪M，如在碰撞檢測中利用桶樹逐步細化模型[7]，用快速修改替代懶惰修改[8]。

3）碰撞檢測

碰撞檢測的主要目的是，對占據同一個空間兩個或多個對象求交。在一般情況下，它包含兩步驟，即廣相檢測和窄相檢測。窄相檢測可以檢測出廣相檢測沒有考慮到的高潛在性的碰撞。

在涉及多個物體的碰撞模擬中，包圍盒應用較為普遍。包圍盒類型有的軸對齊包圍盒（AABB），方向包圍盒（OBB）和離散多面體（K-DOPs）以及定向多面體（or-DOPs）。此外，將OBB和K-DOPs進行組合可以彌補K-DOPs更新成本高的缺陷。碰撞檢測性能還取決于密封性和使用的包圍盒的簡單程度。

圖3 包圍盒的類型

實際上，可以把層次包圍盒看成一棵樹，而每個物體的包圍盒是其中的葉節點。具體來說，葉節點包含一些幾何數據，而內部結點則反映子結點的特性。文獻[1]中有說明用來處理碰撞的高效數據結構和算法需要哪些條件。

2 層次包圍盒構建的改進

為實現光線追蹤從靜態場景向動態的轉變，需要更快速地構建及改造/更新加速結構。以鉸接形式存在的模型，性能介于剛性和可變形物體之間，也就是說，它可能由剛性、鉸接形式共同組成，彎曲和移動會引起模型的表面變形。基于這一判斷，可以認為，動態場景的光線追蹤和可變形物體領域的進步可能也適合虛擬場景中的碰撞檢測。

圖4 光線追蹤、人體模型、可變形物體的發展趨勢

啟發式表面區域（SAH）通常用于光線追蹤中建立優化的樹結構[9]。但是，需要大量時間來評價和選擇結構的最佳分割位置，以確保它的質量。一個很有價值的搜索條件與拋物線插值技術相結合的引入[9]彌補了傳統SAH評估最佳分割位置的缺陷。當層次結構需要經常重建或從每一幀始徹底重建時，快速Kd樹的結構顯得非常有用。這是由于，許多次更新或修改之后，層次體的質量有降低的趨勢，需要重建。在每一幀始重建，消除了結構對更新和修改依賴。

先前，沒有太多關注層次包圍盒在動態場景光線追蹤中的應用。因為通常認為，層次包圍盒相比于Kd樹處于劣勢。然而，層次包圍盒已廣泛應用于可變形物體，這些物體具有不變的拓撲結構和三角形計數功能。以每幀始重建層次為目的，Wald建議，以前用于Kd樹中的快速和近似的構建技術可以搬到層次包圍盒上[10]。他進一步強調，層次包圍盒的一些獨特屬性使得它更實用：

·層次包圍盒的結點較少，操作起來更簡潔

·沒有重疊的三角形分割平面

·在層次包圍盒中，每個結點只被引用一次

3 本文所提出的方法

本階段的重點主要放在靜態場景的預處理階段上，它涉及加速結構的構建。各參考文獻中，大多數BVH的前期工作均使用自頂向下的方法。它對整個場景空間由整體到局部遞歸劃分構建，對運動物體由包含所有物體的整個集合到包含部分運動物體的集合子集、再到單個物體的方式組織。這種自頂向下的方法通常會得到一個層次結構良好、非常有效的結構。將自頂向下方法用于本研究，過程中有可能需要構建二進制樹，該樹使用了帶有中位數或稱為平均分割點的長軸。雖然BVH構建屬于預處理，但它的快速構建是交互應用中必不可少的?？紤]到完全重建是在動態場景中的光線追蹤下實現的，也要評估這種方法是否可以為碰撞檢測提供優勢。由此可見，層次包圍盒的完整重建已被用到動態場景的光線追蹤上，而對于可變形的物體，快速修改和層次結構的更新仍然應用很廣。第一階段的預期結果是個合適的層次構建，它涵蓋合適的分裂規則和啟發式策略。

4 結論

回顧動態場景中的光線追蹤，重點在于加速數據結構的快速性和有效性，以及BVH的重要性。本文并沒有把重點放在預處理和優化BVH上，而是更關注徹底重建過程，特別是動態場景中的重建。這些研究結果將被用于進一步研究BVH的基礎，它將朝向高效的碰撞檢測方向發展。

［1］黃通浪，唐敏，董金祥.一種快速精確的連續碰撞檢測算[J].浙江大學學報：工學版.2006年6月第40卷第6期.

［2］J.D.Foley,A.v.Dam,S.K.Feiner,and J.F [J].Hughes,Computer Graphics:Principles and Practice (in C),Addison-Wesley Longman Publishing Co.,Inc.,1996.

［3］劉天慧.光線跟蹤算法技術[M].清華大學出版社，2011，3.

［4］韓文君，趙偉.基于空間數據結構的快速碰撞檢測算法[J].長春工業大學學報：自然科學版.2007年12月第28卷第4期.

［5］M.Ernst,and G.Greiner,Early Split Clipping for Bounding Volume Hierarchies,Interactive Ray Tracing,2007[S].RT'07.IEEE Symposium on,2007,pp.73-78.

［6］W.Hunt,W.R.Mark,and D.Fussell,Fast and Lazy Build of Acceleration Structures from Scene Hierarchies,Interactive Ray Tracing,2007[J].RT'07.IEEE Symposium on,2007,pp.47-54.

［7］F.Ganovelli,J.Dingliana,and C.O'Sullivan,BucketTree:Improving collision detection between deformable objects,In SCCG2000 Spring Conf[M].on Comp.Graphics,2000.

［8］L.Kavan,and J.Dára,Fast Collision Detection for Skeletally Deformable Models[J].Computer Graphics Forum 24(2005)363-372.

［9］S.Hussain,and H.Grahn,Fast kd-Tree Construction for 3D-Rendering Algorithms Like Ray Tracing[M].Advances in Visual Computing,2007,pp.681-690.

［10］I.Wald,On fast Construction of SAH-based Bounding Volume Hierarchies,Interactive Ray Tracing,2007.RT'07[J].IEEE Symposium on,2007,pp.33-40.