張佳杰，黃海端

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

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

張佳杰，黃海端

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

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

虛擬場景；密集型區(qū)域；八叉樹

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

0 引言

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

1 八叉樹存儲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

圖3 一對八式八叉樹的存儲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

[1]一種基于松散八叉樹的復(fù)雜場景可見性裁剪算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，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