基于密集型區(qū)域的八叉樹(shù)劃分算法

張佳杰，黃海端

河北聯(lián)合大學(xué)遷安學(xué)院，河北遷安 064400

基于密集型區(qū)域的八叉樹(shù)劃分算法

張佳杰，黃海端

河北聯(lián)合大學(xué)遷安學(xué)院，河北遷安 064400

虛擬場(chǎng)景中數(shù)據(jù)量的存儲(chǔ)是關(guān)系查找速度的關(guān)鍵問(wèn)題，本文針對(duì)傳統(tǒng)八叉樹(shù)存儲(chǔ)的不足，采用密集型八叉樹(shù)組織場(chǎng)景，利用改進(jìn)的八叉樹(shù)對(duì)虛擬場(chǎng)景進(jìn)行劃分。實(shí)驗(yàn)結(jié)果表明：此種八叉樹(shù)的劃分方法，充分發(fā)揮了空間劃分的優(yōu)勢(shì)，節(jié)約了存儲(chǔ)空間，加快了場(chǎng)景的查找速度。

虛擬場(chǎng)景；密集型區(qū)域；八叉樹(shù)

注：本文系唐山市科技局項(xiàng)目（NO: 09130201C）

0 引言

隨著虛擬現(xiàn)實(shí)技術(shù)的日益成熟，虛擬場(chǎng)景越來(lái)越復(fù)雜，要存儲(chǔ)的數(shù)據(jù)量也越來(lái)越大，迫切需要一種高效存儲(chǔ)結(jié)構(gòu)解決這一問(wèn)題。八叉樹(shù)是一種較常用的空間數(shù)據(jù)組織結(jié)構(gòu)，目前，研究者們主要針對(duì)分布較松散的區(qū)域采用八叉樹(shù)進(jìn)行可見(jiàn)性裁剪，來(lái)減少確定對(duì)象的處理時(shí)間以及存儲(chǔ)空間。而對(duì)于密集型區(qū)域的場(chǎng)景數(shù)據(jù)，采用傳統(tǒng)的八叉樹(shù)存儲(chǔ)結(jié)構(gòu)進(jìn)行劃分其查找時(shí)間和存儲(chǔ)空間的代價(jià)較大。針對(duì)這一問(wèn)題，提出了一種基于密集型區(qū)域的八叉樹(shù)劃分算法。通過(guò)實(shí)驗(yàn)分析此種八叉樹(shù)的劃分方法，充分發(fā)揮了空間劃分的優(yōu)勢(shì)，節(jié)約了存儲(chǔ)空間，加快了場(chǎng)景的查找速度。

1 八叉樹(shù)存儲(chǔ)結(jié)構(gòu)

八叉樹(shù)（Octree）是一種用于描述三維空間的樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，也是由四叉樹(shù)推廣到三維空間而形成的一種三維柵格數(shù)據(jù)結(jié)構(gòu)。八叉樹(shù)的每個(gè)結(jié)點(diǎn)表示一個(gè)正方體的體積元素，每個(gè)結(jié)點(diǎn)有八個(gè)子結(jié)點(diǎn)，將八個(gè)子結(jié)點(diǎn)所表示的體積元素加在一起就等于父結(jié)點(diǎn)的體積。用八叉樹(shù)來(lái)表示三維形體，可以認(rèn)為是用三維體積陣列表示形體方法的一種改進(jìn)。它作為一種場(chǎng)景組織方法，廣泛應(yīng)用于虛擬現(xiàn)實(shí)系統(tǒng)，可顯著減少對(duì)場(chǎng)景中多邊形進(jìn)行排序的時(shí)間。Octree用于3D空間中管理場(chǎng)景時(shí)，可以快速確定物體在3D場(chǎng)景中的位置，是否在可視范圍內(nèi)，并偵測(cè)是否與其它物體有碰撞產(chǎn)生。

傳統(tǒng)八叉樹(shù)是將一個(gè)立方體的三維空間均勻的分割成8個(gè)單元，其根表示了整個(gè)場(chǎng)景，如果8個(gè)子空間內(nèi)的物體屬性相同就不再劃分。否則，將該子空間再細(xì)分為八個(gè)空間，如此遞歸下去，直到每個(gè)子空間內(nèi)物體的屬性均相同或達(dá)到規(guī)定的限差為止。傳統(tǒng)八叉樹(shù)有三種不同的類(lèi)型，分別為規(guī)則八叉樹(shù)、線性八叉樹(shù)和一對(duì)八式八叉樹(shù)。

規(guī)則八叉樹(shù)的存儲(chǔ)結(jié)構(gòu)用一個(gè)由九個(gè)字段的記錄來(lái)表示樹(shù)中的每個(gè)結(jié)點(diǎn)，如圖1所示。其中一個(gè)字段用來(lái)描述該結(jié)點(diǎn)的特性，其余的八個(gè)字段用來(lái)作為存放指向其八個(gè)子結(jié)點(diǎn)的指針。這是最普遍使用的表示樹(shù)形數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)方式。

圖1 規(guī)則八叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

規(guī)則八叉樹(shù)的最大問(wèn)題是指針占用了大量的空間。假設(shè)每個(gè)指針占用兩個(gè)字節(jié)，結(jié)點(diǎn)的描述占用一個(gè)字節(jié)，那么只是指針的存儲(chǔ)就要占去存儲(chǔ)空間的94%。因此，盡管規(guī)則八叉樹(shù)方法自然，并且容易掌握，但由于其在存儲(chǔ)空間的使用率方面很差，開(kāi)發(fā)者很少使用這種方法。

線性八叉樹(shù)注重考慮如何提高空間利用率。例如，采用深度優(yōu)先次序遍歷一棵八叉樹(shù)，先將八叉樹(shù)轉(zhuǎn)換成一個(gè)線性表，表的每個(gè)元素對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，如圖2所示。對(duì)于葉結(jié)點(diǎn)可以用適當(dāng)?shù)姆绞絹?lái)說(shuō)明，如果不是葉結(jié)點(diǎn)就將其八個(gè)子結(jié)點(diǎn)值的平均值作為非葉結(jié)點(diǎn)的值。這樣，可以在內(nèi)存中以緊湊的方式來(lái)代替指針表示線性表。

圖2 線性八叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

線性八叉樹(shù)運(yùn)算起來(lái)比較方便，而且節(jié)省了存儲(chǔ)空間。但是喪失了一定的靈活性，增加了各結(jié)點(diǎn)的遍歷時(shí)間。例如，要存取某圖形右下角的子圖形對(duì)應(yīng)的結(jié)點(diǎn)，必須先遍歷前面的七個(gè)子圖形對(duì)應(yīng)的所有結(jié)點(diǎn)后才能進(jìn)行，降低了運(yùn)算效率。因此，盡管線性八叉樹(shù)的應(yīng)用在很多文章中都進(jìn)行了討論，但是仍很難達(dá)到令人滿意的效果。

一對(duì)八式的八叉樹(shù)是指非葉結(jié)點(diǎn)均有八個(gè)子結(jié)點(diǎn)，將八個(gè)子結(jié)點(diǎn)分別標(biāo)記為0，1，2，3，4，5，6，7。一對(duì)八式的存儲(chǔ)結(jié)構(gòu)中一個(gè)記錄對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，記錄描述該結(jié)點(diǎn)的八個(gè)子結(jié)點(diǎn)的特性值，指針描述該八個(gè)子結(jié)點(diǎn)所對(duì)應(yīng)記錄的存放處，并且在指針中還隱含了這些子結(jié)點(diǎn)記錄存放的次序，如圖3所示。這樣造成了空間的浪費(fèi)，即使該結(jié)點(diǎn)已是葉結(jié)點(diǎn)，它相應(yīng)的存儲(chǔ)位置也必須保留，為的是保證存取的準(zhǔn)確性。這種方法只適合完全八叉樹(shù)，而該完全八叉樹(shù)還必須滿足所有的葉結(jié)點(diǎn)均在同一層次出現(xiàn)，而在該層次之上的所有層中的結(jié)點(diǎn)均為非葉結(jié)點(diǎn)。

圖3 一對(duì)八式八叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

2 基于密集型區(qū)域八叉樹(shù)算法

為了解決八叉樹(shù)存儲(chǔ)空間浪費(fèi)以及遍歷時(shí)間長(zhǎng)的問(wèn)題，提出基于密集型區(qū)域八叉樹(shù)的存儲(chǔ)方式。密集型區(qū)域八叉樹(shù)的網(wǎng)格劃分算法是對(duì)每個(gè)子空間重新建立最小包圍盒，這樣避免了在建立頂點(diǎn)樹(shù)時(shí)，由于該部分頂點(diǎn)在空間上分布不均勻而導(dǎo)致樹(shù)的深度的增加，進(jìn)而減少了存儲(chǔ)空間，加快了網(wǎng)格模型數(shù)據(jù)的讀取速度。另外，由于建立了頂點(diǎn)的最小包圍盒，在誤差較小時(shí)，只有空間距離比較近的頂點(diǎn)才會(huì)聚合在一起；而相距較遠(yuǎn)的頂點(diǎn)只有在深層次簡(jiǎn)化時(shí)才會(huì)聚合，這些特點(diǎn)在一定程度上保證了簡(jiǎn)化時(shí)網(wǎng)格模型的逼真度。

密集型區(qū)域八叉樹(shù)劃分方法的算法描述如下：

1 ）找出場(chǎng)景的最大尺寸，使用包圍盒方法建立模型的最小包圍盒；

2 ）以包圍盒的X軸、Y軸、Z軸方向的中分面作為分割基準(zhǔn)，將包圍盒平均劃分為八個(gè)子包圍盒，在每個(gè)子包圍盒中將緊湊部分的物體用更小的包圍盒包圍，進(jìn)行進(jìn)一步的劃分；

3 ）如果每個(gè)子空間內(nèi)存在物體的屬性不相同或未達(dá)到規(guī)定的限差，則重新從1）開(kāi)始進(jìn)行劃分，直到子包圍盒物體跟上一層包圍盒物體一樣為止。否則，劃分結(jié)束，并對(duì)劃分后的每一個(gè)結(jié)點(diǎn)記錄下一結(jié)點(diǎn)的編號(hào)、劃分標(biāo)志、結(jié)點(diǎn)在頂點(diǎn)樹(shù)中的深度以及它所含的景物面片表的入口指針。

下面是根據(jù)生成虛擬場(chǎng)景的二維地圖，采用密集型區(qū)域八叉樹(shù)的劃分算法劃分虛擬場(chǎng)景的過(guò)程及生成的頂點(diǎn)樹(shù)，劃分過(guò)程共分為三步如圖4所示：

圖4 密集型區(qū)域八叉樹(shù)的劃分過(guò)程

圖5為根據(jù)劃分過(guò)程產(chǎn)生的頂點(diǎn)樹(shù)。根據(jù)生成的頂點(diǎn)樹(shù)，可知基于密集型區(qū)域的八叉樹(shù)生成過(guò)程首先由根結(jié)點(diǎn)生成整個(gè)樹(shù)結(jié)構(gòu)，然后再對(duì)網(wǎng)格模型進(jìn)行劃分，當(dāng)結(jié)點(diǎn)空間確定后，如果它是葉結(jié)點(diǎn)，可根據(jù)整個(gè)景物空間的三角片表來(lái)確定該結(jié)點(diǎn)空間的三角片表；如果不是，再查找它的子結(jié)點(diǎn)直至獲得它的三角片表，最終完成對(duì)整個(gè)虛擬場(chǎng)景的劃分。

3 實(shí)驗(yàn)結(jié)果分析

圖6采用傳統(tǒng)八叉樹(shù)存儲(chǔ)結(jié)構(gòu)和改進(jìn)的八叉樹(shù)存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)場(chǎng)景信息進(jìn)行路徑搜索的實(shí)驗(yàn)結(jié)果，很明顯看出針對(duì)密集型區(qū)域虛擬場(chǎng)景，由于采用改進(jìn)的八叉樹(shù)存儲(chǔ)空間大大縮小，搜索速率明顯比傳統(tǒng)八叉樹(shù)存儲(chǔ)方式高。

圖5 密集型八叉樹(shù)劃分產(chǎn)生的頂點(diǎn)樹(shù)

圖6 基于傳統(tǒng)八叉樹(shù)與改進(jìn)八叉樹(shù)的搜索速率比較

4 結(jié)論

本文將復(fù)雜場(chǎng)景組織成基于密集型區(qū)域八叉樹(shù)劃分方式的場(chǎng)景組織結(jié)構(gòu)，針對(duì)八叉樹(shù)適合虛擬場(chǎng)景劃分的特點(diǎn)，采用了一種適合密集型區(qū)域的八叉樹(shù)劃分方法，進(jìn)行場(chǎng)景劃分。通過(guò)與傳統(tǒng)八叉樹(shù)實(shí)驗(yàn)證明了方法的有效性。

[1]一種基于松散八叉樹(shù)的復(fù)雜場(chǎng)景可見(jiàn)性裁剪算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2007，19(12)：1595-1598.

[2]Liu Xiaoyue,Zhang Jiajie,Chen Lei.The Application of Improved A* Algorithm to Path Planning of Virtual Environment [C].Sanya,ACC，2009，1：28-31.

TP39

A

1674-6708（2012）59-0138-02