卓 婧 關(guān)克平 黃曉峰

（上海海事大學(xué)商船學(xué)院 中國(guó) 上海 201306）

0 引言

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

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

1 BVH的前期工作

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

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

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

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

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

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

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

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

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

1）光線追蹤

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

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

圖2 三者的效果比較

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

2）可變形物體

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

·自相交

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

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

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

3）碰撞檢測(cè)

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

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

圖3 包圍盒的類(lèi)型

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

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

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

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

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

先前，沒(méi)有太多關(guān)注層次包圍盒在動(dòng)態(tài)場(chǎng)景光線追蹤中的應(yīng)用。因?yàn)橥ǔＵJ(rèn)為，層次包圍盒相比于Kd樹(shù)處于劣勢(shì)。然而，層次包圍盒已廣泛應(yīng)用于可變形物體，這些物體具有不變的拓?fù)浣Y(jié)構(gòu)和三角形計(jì)數(shù)功能。以每幀始重建層次為目的，Wald建議，以前用于Kd樹(shù)中的快速和近似的構(gòu)建技術(shù)可以搬到層次包圍盒上[10]。他進(jìn)一步強(qiáng)調(diào)，層次包圍盒的一些獨(dú)特屬性使得它更實(shí)用：

·層次包圍盒的結(jié)點(diǎn)較少，操作起來(lái)更簡(jiǎn)潔

·沒(méi)有重疊的三角形分割平面

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

3 本文所提出的方法

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

4 結(jié)論

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

［1］黃通浪，唐敏，董金祥.一種快速精確的連續(xù)碰撞檢測(cè)算[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版.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］劉天慧.光線跟蹤算法技術(shù)[M].清華大學(xué)出版社，2011，3.

［4］韓文君，趙偉.基于空間數(shù)據(jù)結(jié)構(gòu)的快速碰撞檢測(cè)算法[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版.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.