基于密集型區域的八叉樹劃分算法

張佳杰，黃海端

河北聯合大學遷安學院，河北遷安 064400

基于密集型區域的八叉樹劃分算法

張佳杰，黃海端

河北聯合大學遷安學院，河北遷安 064400

虛擬場景中數據量的存儲是關系查找速度的關鍵問題，本文針對傳統八叉樹存儲的不足，采用密集型八叉樹組織場景，利用改進的八叉樹對虛擬場景進行劃分。實驗結果表明：此種八叉樹的劃分方法，充分發揮了空間劃分的優勢，節約了存儲空間，加快了場景的查找速度。

虛擬場景；密集型區域；八叉樹

注：本文系唐山市科技局項目（NO: 09130201C）

0 引言

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

1 八叉樹存儲結構

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

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

規則八叉樹的存儲結構用一個由九個字段的記錄來表示樹中的每個結點，如圖1所示。其中一個字段用來描述該結點的特性，其余的八個字段用來作為存放指向其八個子結點的指針。這是最普遍使用的表示樹形數據的存儲結構方式。

圖1 規則八叉樹的存儲結構

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

線性八叉樹注重考慮如何提高空間利用率。例如，采用深度優先次序遍歷一棵八叉樹，先將八叉樹轉換成一個線性表，表的每個元素對應一個結點，如圖2所示。對于葉結點可以用適當的方式來說明，如果不是葉結點就將其八個子結點值的平均值作為非葉結點的值。這樣，可以在內存中以緊湊的方式來代替指針表示線性表。

圖2 線性八叉樹的存儲結構

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

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

圖3 一對八式八叉樹的存儲結構

2 基于密集型區域八叉樹算法

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

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

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

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

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

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

圖4 密集型區域八叉樹的劃分過程

圖5為根據劃分過程產生的頂點樹。根據生成的頂點樹，可知基于密集型區域的八叉樹生成過程首先由根結點生成整個樹結構，然后再對網格模型進行劃分，當結點空間確定后，如果它是葉結點，可根據整個景物空間的三角片表來確定該結點空間的三角片表；如果不是，再查找它的子結點直至獲得它的三角片表，最終完成對整個虛擬場景的劃分。

3 實驗結果分析

圖6采用傳統八叉樹存儲結構和改進的八叉樹存儲結構進行存儲場景信息進行路徑搜索的實驗結果，很明顯看出針對密集型區域虛擬場景，由于采用改進的八叉樹存儲空間大大縮小，搜索速率明顯比傳統八叉樹存儲方式高。

圖5 密集型八叉樹劃分產生的頂點樹

圖6 基于傳統八叉樹與改進八叉樹的搜索速率比較

4 結論

本文將復雜場景組織成基于密集型區域八叉樹劃分方式的場景組織結構，針對八叉樹適合虛擬場景劃分的特點，采用了一種適合密集型區域的八叉樹劃分方法，進行場景劃分。通過與傳統八叉樹實驗證明了方法的有效性。

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