八叉樹管理原理

1、八叉樹三維數(shù)據(jù)結(jié)構(gòu)（一）基本原理用八叉樹來表示三維形體，并研究在這種表示下的各種操作及應(yīng)用是在進(jìn)入80年代后才比較全面地開展起來的。這種方法，既可以看成是四叉樹方法在三維空間的推廣，也可以認(rèn)為是用三維體素陣列表示形體方法的一種改進(jìn)。八叉樹的邏輯結(jié)構(gòu)如下：假設(shè)要表示的形體V可以放在一個(gè)充分大的正方體C內(nèi)，C的邊長(zhǎng)為2 n，形體V C，它的八叉樹可以用以下的遞歸方法來定義：八叉樹的每個(gè)節(jié)點(diǎn)與C的一個(gè)子立方體對(duì)應(yīng)，樹根與C本身相對(duì)應(yīng)，如果VC，那么V的八叉樹僅有樹根，如果VC，則將C等分為八個(gè)子立方體，每個(gè)子立方體與樹根的一個(gè)子節(jié)點(diǎn)相對(duì)應(yīng)。只要某個(gè)子立方體不是完全空白或完全為V所占據(jù)，就要被八等分（

2、圖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é)

3、構(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ì)顯示精度和速度的平衡、隱線和隱面的消除等，帶來了很大的方便，特別有用

4、。（二）八叉樹的存貯結(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é)

5、表示，而結(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à)是

6、喪失了一定的靈活性。例如為了存取屬于原圖形右下角的子圖形對(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è)記錄是不必要的(

7、例如，該結(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)減少或者更方便。推薦精選/八叉樹的實(shí)現(xiàn)1 /功能：2 /1、創(chuàng)建八叉樹。3 /此八叉樹為滿樹，即所有節(jié)點(diǎn)/葉子全部創(chuàng)建。4 /用戶可以自定義此八叉樹的深度和所處的三維場(chǎng)景中的位置。5 /注a：由于創(chuàng)建樹時(shí)為滿樹創(chuàng)建，故層數(shù)太大時(shí)創(chuàng)建時(shí)間可能會(huì)比較久，請(qǐng)耐心等

8、待。6 /注b：創(chuàng)建順序?yàn)?1)上層左前節(jié)點(diǎn)-(2)上層右前節(jié)點(diǎn)-(3)上層右前節(jié)點(diǎn)-(4)上層右后節(jié)點(diǎn)7 /-(5)下層左前節(jié)點(diǎn)-(6)下層右前節(jié)點(diǎn)-(7)下層右前節(jié)點(diǎn)-(8)下層右后節(jié)點(diǎn)-(1)-(2)8 /2、先序遍歷八叉樹。9 /八叉樹創(chuàng)建成功后用戶可調(diào)用此子模塊查看此八叉樹，會(huì)顯示每個(gè)結(jié)點(diǎn)的編號(hào)，值和在場(chǎng)景中的坐標(biāo)。10 /3、查看八叉樹的深度。11 /4、在場(chǎng)景中查找點(diǎn)。12 /用戶首先輸入要查找的坐標(biāo)。13 /如果該點(diǎn)位于場(chǎng)景外則提示用戶并返回，否則在場(chǎng)景中遞歸查找該點(diǎn)。14 /找到后輸出該點(diǎn)所處的子結(jié)點(diǎn)的坐標(biāo)和遞歸次數(shù)。1516 #include 17 using namesp

9、ace std;18 /定義八叉樹節(jié)點(diǎn)類19 template20 struct OctreeNode21 22 T data; /節(jié)點(diǎn)數(shù)據(jù)23 T xmin,xmax; /節(jié)點(diǎn)坐標(biāo)，即六面體個(gè)頂點(diǎn)的坐標(biāo)24 T ymin,ymax;25 T zmin,zmax;26 OctreeNode *top_left_front,*top_left_back; /該節(jié)點(diǎn)的個(gè)子結(jié)點(diǎn),即個(gè)子六面體27 OctreeNode *top_right_front,*top_right_back;28 OctreeNode *bottom_left_front,*bottom_left_back;29 Octre

10、eNode *bottom_right_front,*bottom_right_back;30 OctreeNode /節(jié)點(diǎn)類31 (T nodeValue = T(),32 T xminValue = T(),T xmaxValue = T(),33 T yminValue = T(),T ymaxValue = T(),34 T zminValue = T(),T zmaxValue = T(),35 OctreeNode* top_left_front_Node = NULL,36 OctreeNode* top_left_back_Node = NULL,37 OctreeNode*

11、top_right_front_Node = NULL,38 OctreeNode* top_right_back_Node = NULL,39 OctreeNode* bottom_left_front_Node = NULL,推薦精選40 OctreeNode* bottom_left_back_Node = NULL,41 OctreeNode* bottom_right_front_Node = NULL,42 OctreeNode* bottom_right_back_Node = NULL )43 :data(nodeValue),44 xmin(xminValue),xmax(x

12、maxValue),45 ymin(yminValue),ymax(ymaxValue),46 zmin(zminValue),zmax(zmaxValue),47 top_left_front(top_left_front_Node),48 top_left_back(top_left_back_Node),49 top_right_front(top_right_front_Node),50 top_right_back(top_right_back_Node),51 bottom_left_front(bottom_left_front_Node),52 bottom_left_back

13、(bottom_left_back_Node),53 bottom_right_front(bottom_right_front_Node),54 bottom_right_back(bottom_right_back_Node)55 ;56 /創(chuàng)建八叉樹57 template 58 void createOctree(OctreeNode * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)59 60 cout處理中，請(qǐng)稍候=0)63 64 root=new

14、OctreeNode();65 root-data = 9; /為節(jié)點(diǎn)賦值，可以存儲(chǔ)節(jié)點(diǎn)信息，如物體可見性。由于是簡(jiǎn)單實(shí)現(xiàn)八叉樹功能，簡(jiǎn)單賦值為。66 root-xmin=xmin; /為節(jié)點(diǎn)坐標(biāo)賦值67 root-xmax=xmax;68 root-ymin=ymin;69 root-ymax=ymax;70 root-zmin=zmin;71 root-zmax=zmax;72 double xm=(xmax-xmin)/2;/計(jì)算節(jié)點(diǎn)個(gè)維度上的半邊長(zhǎng)73 double ym=(ymax-ymin)/2;74 double zm=(ymax-ymin)/2;75 /遞歸創(chuàng)建子樹，根據(jù)每一個(gè)

15、節(jié)點(diǎn)所處（是幾號(hào)節(jié)點(diǎn)）的位置決定其子結(jié)點(diǎn)的坐標(biāo)。76 createOctree(root-top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);77 createOctree(root-top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);78 createOctree(root-top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);推薦精選79 createOctree(r

16、oot-top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);80 createOctree(root-bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);81 createOctree(root-bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);82 createOctree(root-bottom_right_front,maxdepth,xmax-xm,

17、xmax,ymax-ym,ymax,zmin,zmax-zm);83 createOctree(root-bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);84 85 86 int i=1;87 /先序遍歷八叉樹88 template 89 void preOrder( OctreeNode * & p)90 91 if(p)92 93 couti.當(dāng)前節(jié)點(diǎn)的值為：data/n坐標(biāo)為：;94 cout xmin: xmin xmax: xmax;95 cout ymin: ymin ymax: ymax;96

18、cout zmin: zmin zmax: zmax;97 i+=1;98 couttop_left_front);100 preOrder(p-top_left_back);101 preOrder(p-top_right_front);102 preOrder(p-top_right_back);103 preOrder(p-bottom_left_front);104 preOrder(p-bottom_left_back);105 preOrder(p-bottom_right_front);106 preOrder(p-bottom_right_back);107 coutendl;

19、108 109 110 /求八叉樹的深度111 template112 int depth(OctreeNode *& p)113 114 if(p = NULL)115 return -1;116 int h = depth(p-top_left_front);推薦精選117 return h+1;118 119 /計(jì)算單位長(zhǎng)度，為查找點(diǎn)做準(zhǔn)備120 int cal(int num)121 122 int result=1;123 if(1=num)124 result=1;125 else126 127 for(int i=1;inum;i+)128 result=2*result;129

20、 130 return result;131 132 /查找點(diǎn)133 int maxdepth=0;134 int times=0;135 static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;136 int tmaxdepth=0;137 double txm=1,tym=1,tzm=1;138 template139 void find(OctreeNode *& p,double x,double y,double z)140 141 double xm=(p-xmax-p-xmin)/2;142 double ym=(p-yma

21、x-p-ymin)/2;143 double zm=(p-ymax-p-ymin)/2;144 times+;145 if(xxmax | xymax | yzmax | zzmin)146 147 cout該點(diǎn)不在場(chǎng)景中！endl;148 return;149 150 if(xxmin+txm & x=p-xmax-txm & yymin+tym & y=p-ymax-tym & zzmin+tzm & z=p-zmax-tzm )151 152 coutendl找到該點(diǎn)！該點(diǎn)位于endl;153 cout xmin: xmin xmax: xmax;154 cout ymin: ymin

22、ymax: ymax;155 cout zmin: zmin zmax: zmax;156 cout節(jié)點(diǎn)內(nèi)！endl;157 cout共經(jīng)過times次遞歸！endl;158 159 else if(xxmax-xm) & yymax-ym) & zzmax-zm)推薦精選160 161 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;162 cout xmin: xmin xmax: xmax;163 cout ymin: ymin ymax: ymax;164 cout zmin: zmin zmax: zmax;165 coutbottom_left_back,x,y,z);167 168 else

23、 if(xxmax-xm) & yymax-ym) & z(p-zmax-zm)169 170 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;171 cout xmin: xmin xmax: xmax;172 cout ymin: ymin ymax: ymax;173 cout zmin: zmin zmax: zmax;174 couttop_left_back,x,y,z);176 177 else if(x(p-xmax-xm) & yymax-ym) & zzmax-zm)178 179 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;180 cout xmin: xmin xmax: xmax;181

24、 cout ymin: ymin ymax: ymax;182 cout zmin: zmin zmax: zmax;183 coutbottom_right_back,x,y,z);185 186 else if(x(p-xmax-xm) & yymax-ym) & z(p-zmax-zm)187 188 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;189 cout xmin: xmin xmax: xmax;190 cout ymin: ymin ymax: ymax;191 cout zmin: zmin zmax: zmax;192 couttop_right_back,x,y,z);194

25、195 else if(xxmax-xm) & y(p-ymax-ym) & zzmax-zm)196 197 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;198 cout xmin: xmin xmax: xmax;199 cout ymin: ymin ymax: ymax;200 cout zmin: zmin zmax: zmax;201 coutbottom_left_front,x,y,z);203 推薦精選204 else if(xxmax-xm) & y(p-ymax-ym) & z(p-zmax-zm)205 206 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;207 cout xmin:

26、xmin xmax: xmax;208 cout ymin: ymin ymax: ymax;209 cout zmin: zmin zmax: zmax;210 couttop_left_front,x,y,z);212 213 else if(x(p-xmax-xm) & y(p-ymax-ym) & zzmax-zm)214 215 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;216 cout xmin: xmin xmax: xmax;217 cout ymin: ymin ymax: ymax;218 cout zmin: zmin zmax: zmax;219 coutbottom_rig

27、ht_front,x,y,z);221 222 else if(x(p-xmax-xm) & y(p-ymax-ym) & z(p-zmax-zm)223 224 cout當(dāng)前經(jīng)過節(jié)點(diǎn)坐標(biāo)：endl;225 cout xmin: xmin xmax: xmax;226 cout ymin: ymin ymax: ymax;227 cout zmin: zmin zmax: zmax;228 couttop_right_front,x,y,z);230 231 232 /main函數(shù)233 int main ()234 235 OctreeNode * rootNode = NULL;236 i

28、nt choiced = 0;237 while(true)238 239 system(cls);240 cout請(qǐng)選擇操作：/n;241 cout1.創(chuàng)建八叉樹 2.先序遍歷八叉樹/n;242 cout3.查看樹深度 4.查找節(jié)點(diǎn) /n;243 coutchoiced;245 if(choiced = 0)246 return 0;247 else if(choiced = 1)推薦精選248 249 system(cls);250 cout請(qǐng)輸入最大遞歸深度：maxdepth;252 cout請(qǐng)輸入外包盒坐標(biāo)，順序如下：xmin,xmax,ymin,ymax,zmin,zmaxxminx

29、maxyminymaxzminzmax;254 if(maxdepth=0 | xmaxxmin | ymaxymin | zmaxzmin | xmin0 | ymin0 |zmin0)255 256 tmaxdepth=cal(maxdepth);257 txm=(xmax-xmin)/tmaxdepth;258 tym=(ymax-ymin)/tmaxdepth;259 tzm=(zmax-zmin)/tmaxdepth;260 createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);261 262 else263 26

30、4 cout輸入錯(cuò)誤！;265 return 0;266 267 268 else if(choiced = 2)269 270 system(cls);271 cout先序遍歷八叉樹結(jié)果：/n;272 i=1;273 preOrder(rootNode);274 coutendl;275 system(pause);276 277 else if(choiced = 3)278 279 system(cls);280 int dep = depth(rootNode);281 cout此八叉樹的深度為dep+1endl;282 system(pause);283 284 else if(choiced = 4)285 286 system(cls);287 coutxyz;290 times=0;291 coutendl開始搜尋該點(diǎn)endl;292 find(rootNode,x,y,z);293 system(pause);294