卓 婧 關克平 黃曉峰

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

0 引言

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

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

1 BVH的前期工作

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

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

加速數(shù)據(jù)結(jié)構(gòu)若要支持動態(tài)場景，需要考慮如下因素：

①重建或更新——對于動態(tài)場景可以完全重建或者結(jié)構(gòu)更新。如果場景是部分或全部靜態(tài)的，則無需該操作。根據(jù)場景變化還可以考慮綜合的方法。

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

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

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

圖1 模擬環(huán)境中涉及BVH的過程

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

1）光線追蹤

原先，網(wǎng)格化和Kd樹作為光線追蹤的加速結(jié)構(gòu)較普遍，兩種方法各有所長。

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

圖2 三者的效果比較

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

2）可變形物體

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

·自相交

·隨著模型的變形，加速/空間數(shù)據(jù)結(jié)構(gòu)需要定期和快速的更新/修改

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

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

3）碰撞檢測

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

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

圖3 包圍盒的類型

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

2 層次包圍盒構(gòu)建的改進

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

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

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

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

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

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

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

3 本文所提出的方法

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

4 結(jié)論

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

［1］黃通浪，唐敏，董金祥.一種快速精確的連續(xù)碰撞檢測算[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］韓文君，趙偉.基于空間數(shù)據(jù)結(jié)構(gòu)的快速碰撞檢測算法[J].長春工業(yè)大學學報：自然科學版.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.