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