§2.5 三維數(shù)據(jù)結(jié)構(gòu)
一、八叉樹三維數(shù)據(jù)結(jié)構(gòu)
（一）基本原理
用八叉樹來表示三維形體，并研究在這種表示下的各種操作及應(yīng)用是在進入80年代后才比較全面地開展起來的。這種方法，既可以看成是四叉樹方法在三維空間的推廣，也可以認(rèn)為是用三維體素陣列表示形體方法的一種改進。
八叉樹的邏輯結(jié)構(gòu)如下：
假設(shè)要表示的形體V可以放在一個充分大的正方體C內(nèi)，C的邊長為2n，形體VC，它的八叉樹可以用以下的遞歸方法來定義：
八叉樹的每個節(jié)點與C的一個子立方體對應(yīng)，樹根與C本身相對應(yīng)，如果V＝C，那么V的八叉樹僅有樹根，如果V≠C，則將C等分為八個子立方體，每個子立方體與樹根的一個子節(jié)點相對應(yīng)。只要某個子立方體不是完全空白或完全為V所占據(jù)，就要被八等分（圖2-5-1），從而對應(yīng)的節(jié)點也就有了八個子節(jié)點。這樣的遞歸判斷、分割一直要進行到節(jié)點所對應(yīng)的立方體或是完全空白，或是完全為V占據(jù)，或是其大小已是預(yù)先定義的體素大小，并且對它與V之交作一定的“舍入”，使體素或認(rèn)為是空白的，或認(rèn)為是V占據(jù)的。
如此所生成的八叉樹上的節(jié)點可分為三類：
灰節(jié)點，它對應(yīng)的立方體部分地為V所占據(jù)；
白節(jié)點，它所對應(yīng)的立方體中無V的內(nèi)容；
黑節(jié)點，它所對應(yīng)的立方體全為V所占據(jù)。
后兩類又稱為葉結(jié)點。形體V關(guān)于C的八叉樹的邏輯結(jié)構(gòu)是這樣的：它是一顆樹，其上的節(jié)點要么是葉節(jié)點，要么就是有八個子節(jié)點的灰節(jié)點。根節(jié)點與C相對應(yīng)，其它節(jié)點與C的某個子立方體相對應(yīng)。
因為八叉樹的結(jié)構(gòu)與四叉樹的結(jié)構(gòu)是如此的相似，所以八叉樹的存貯結(jié)構(gòu)方式可以完全沿用四叉樹的有關(guān)方法。因而，根據(jù)不同的存貯方式，八叉樹也可以分別稱為常規(guī)的、線性的、一對八的八叉樹等等。
另外，由于這種方法充分利用了形體在空上的相關(guān)性，因此，一般來說，它所占用的存貯空間要比三維體素陣列的少。但是實際上它還是使用了相當(dāng)多的存貯，這并不是八叉樹的主要優(yōu)點。這一方法的主要優(yōu)點在于可以非常方便地實現(xiàn)有廣泛用途的集合運算(例如可以求兩個物體的并、交、差等運算)，而這些恰是其它表示方法比較難以處理或者需要耗費許多計算資源的地方。不僅如此，由于這種方法的有序性及分層性，因而對顯示精度和速度的平衡、隱線和隱面的消除等，帶來了很大的方便，特別有用。
（二）八叉樹的存貯結(jié)構(gòu)
八叉樹有三種不同的存貯結(jié)構(gòu)，分別是規(guī)則方式、線性方式以及一對八方式。相應(yīng)的八叉樹也分別稱為規(guī)則八叉樹、線性八叉樹以及一對八式八叉樹。不同的存貯結(jié)構(gòu)的空間利用率及運算操作的方便性是不同的。分析表明，一對八式八叉樹優(yōu)點更多一些。
1、規(guī)則八叉樹
規(guī)則八叉樹的存貯結(jié)構(gòu)用一個有九個字段的記錄來表示樹中的每個結(jié)點。其中一個字段用來描述該結(jié)點的特性(在目前假定下，只要描述它是灰、白、黑三類結(jié)點中哪一類即可)，其余的八個字段用來作為存放指向其八個子結(jié)點的指針。這是最普遍使用的表示樹形數(shù)據(jù)的存貯結(jié)構(gòu)方式。
規(guī)則八叉樹缺陷較多，最大的問題是指針占用了大量的空間。假定每個指針要用兩個字節(jié)表示，而結(jié)點的描述用一個字節(jié)，那么存放指針要占總的存貯量的94％。因此，這種方法雖然十分自然，容易掌握，但在存貯空間的使用率方面不很理想。
2、線性八叉樹
線性八叉樹注重考慮如何提高空間利用率。用某一預(yù)先確定的次序遍歷八叉樹(例如以深度第一的方式)，將八叉樹轉(zhuǎn)換成一個線性表（圖2-5-2），表的每個元素與一個結(jié)點相對應(yīng)。對于結(jié)點的描述可以豐富一點，例如用適當(dāng)?shù)姆绞絹碚f明它是否為葉結(jié)點，如果不是葉結(jié)點時還可用其八個子結(jié)點值的平均值作為非葉結(jié)點的值等等。這樣，可以在內(nèi)存中以緊湊的方式來表示線性表，可以不用指針或者僅用一個指針表示即可。
線性八叉樹不僅節(jié)省存貯空間，對某些運算也較為方便。但是為此付出的代價是喪失了一定的靈活性。例如為了存取屬于原圖形右下角的子圖形對應(yīng)的結(jié)點，那么必須先遍歷了其余七個子圖形對應(yīng)的所有結(jié)點后才能進行；不能方便地以其它遍歷方式對樹的結(jié)點進行存取，導(dǎo)致了許多與此相關(guān)的運算效率變低。因此盡管不少文章討論了這種八叉樹的應(yīng)用，但是仍很難令人滿意。
3、一對八式的八叉樹
一個非葉結(jié)點有八個子結(jié)點，為了確定起見，將它們分別標(biāo)記為0，1，2，3，4，5，6，7。從上面的介紹可以看到，如果一個記錄與一個結(jié)點相對應(yīng)，那么在這個記錄中描述的是這個結(jié)點的八個子結(jié)點的特性值。而指針給出的則是該八個子結(jié)點所對應(yīng)記錄的存放處，而且還隱含地假定了這些子結(jié)點記錄存放的次序。也就是說，即使某個記錄是不必要的(例如，該結(jié)點已是葉結(jié)點)，那么相應(yīng)的存貯位置也必須空閑在那里（圖2-5-3），以保證不會錯誤地存取到其它同輩結(jié)點的記錄。這樣當(dāng)然會有一定的浪費，除非它是完全的八叉樹，即所有的葉結(jié)點均在同一層次出現(xiàn)，而在該層次之上的所有層中的結(jié)點均為非葉結(jié)點。
為了克服這種缺陷，有兩條途徑可以采納。一是增加計算量，在記錄中增加一定的信息，使計算工作適當(dāng)減少或者更方便。