八叉樹管理原理

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

2、圖2-5-1），從而對應的節(jié)點也就有了八個子節(jié)點。這樣的遞歸判斷、分割一直要進行到節(jié)點所對應的立方體或是完全空白，或是完全為V占據(jù)，或是其大小已是預先定義的體素大小，并且對它與V之交作一定的“舍入”，使體素或認為是空白的，或認為是V占據(jù)的。如此所生成的八叉樹上的節(jié)點可分為三類：灰節(jié)點，它對應的立方體部分地為V所占據(jù)；白節(jié)點，它所對應的立方體中無V的內(nèi)容；黑節(jié)點，它所對應的立方體全為V所占據(jù)。后兩類又稱為葉結(jié)點。形體V關(guān)于C的八叉樹的邏輯結(jié)構(gòu)是這樣的：它是一顆樹，其上的節(jié)點要么是葉節(jié)點，要么就是有八個子節(jié)點的灰節(jié)點。根節(jié)點與C相對應，其它節(jié)點與C的某個子立方體相對應。因為八叉樹的結(jié)構(gòu)與四叉樹的結(jié)

3、構(gòu)是如此的相似，所以八叉樹的存貯結(jié)構(gòu)方式可以完全沿用四叉樹的有關(guān)方法。因而，根據(jù)不同的存貯方式，八叉樹也可以分別稱為常規(guī)的、線性的、一對八的八叉樹等等。另外，由于這種方法充分利用了形體在空上的相關(guān)性，因此，一般來說，它所占用的存貯空間要比三維體素陣列的少。但是實際上它還是使用了相當多的存貯，這并不是八叉樹的主要優(yōu)點。這一方法的主要優(yōu)點在于可以非常方便地實現(xiàn)有廣泛用途的集合運算(例如可以求兩個物體的并、交、差等運算)，而這些恰是其它表示方法比較難以處理或者需要耗費許多計算資源的地方。不僅如此，由于這種方法的有序性及分層性，因而對顯示精度和速度的平衡、隱線和隱面的消除等，帶來了很大的方便，特別有用

4、。（二）八叉樹的存貯結(jié)構(gòu)八叉樹有三種不同的存貯結(jié)構(gòu)，分別是規(guī)則方式、線性方式以及一對八方式。相應的八叉樹也分別稱為規(guī)則八叉樹、線性八叉樹以及一對八式八叉樹。不同的存貯結(jié)構(gòu)的空間利用率及運算操作的方便性是不同的。分析表明，一對八式八叉樹優(yōu)點更多一些。推薦精選1、規(guī)則八叉樹規(guī)則八叉樹的存貯結(jié)構(gòu)用一個有九個字段的記錄來表示樹中的每個結(jié)點。其中一個字段用來描述該結(jié)點的特性(在目前假定下，只要描述它是灰、白、黑三類結(jié)點中哪一類即可)，其余的八個字段用來作為存放指向其八個子結(jié)點的指針。這是最普遍使用的表示樹形數(shù)據(jù)的存貯結(jié)構(gòu)方式。規(guī)則八叉樹缺陷較多，最大的問題是指針占用了大量的空間。假定每個指針要用兩個字節(jié)

5、表示，而結(jié)點的描述用一個字節(jié)，那么存放指針要占總的存貯量的94。因此，這種方法雖然十分自然，容易掌握，但在存貯空間的使用率方面不很理想。2、線性八叉樹線性八叉樹注重考慮如何提高空間利用率。用某一預先確定的次序遍歷八叉樹(例如以深度第一的方式)，將八叉樹轉(zhuǎn)換成一個線性表（圖2-5-2），表的每個元素與一個結(jié)點相對應。對于結(jié)點的描述可以豐富一點，例如用適當?shù)姆绞絹碚f明它是否為葉結(jié)點，如果不是葉結(jié)點時還可用其八個子結(jié)點值的平均值作為非葉結(jié)點的值等等。這樣，可以在內(nèi)存中以緊湊的方式來表示線性表，可以不用指針或者僅用一個指針表示即可。線性八叉樹不僅節(jié)省存貯空間，對某些運算也較為方便。但是為此付出的代價是

6、喪失了一定的靈活性。例如為了存取屬于原圖形右下角的子圖形對應的結(jié)點，那么必須先遍歷了其余七個子圖形對應的所有結(jié)點后才能進行；不能方便地以其它遍歷方式對樹的結(jié)點進行存取，導致了許多與此相關(guān)的運算效率變低。因此盡管不少文章討論了這種八叉樹的應用，但是仍很難令人滿意3、一對八式的八叉樹一個非葉結(jié)點有八個子結(jié)點，為了確定起見，將它們分別標記為0，1，2，3，4，5，6，7。從上面的介紹可以看到，如果一個記錄與一個結(jié)點相對應，那么在這個記錄中描述的是這個結(jié)點的八個子結(jié)點的特性值。而指針給出的則是該八個子結(jié)點所對應記錄的存放處，而且還隱含地假定了這些子結(jié)點記錄存放的次序。也就是說，即使某個記錄是不必要的(

7、例如，該結(jié)點已是葉結(jié)點)，那么相應的存貯位置也必須空閑在那里（圖2-5-3），以保證不會錯誤地存取到其它同輩結(jié)點的記錄。這樣當然會有一定的浪費，除非它是完全的八叉樹，即所有的葉結(jié)點均在同一層次出現(xiàn)，而在該層次之上的所有層中的結(jié)點均為非葉結(jié)點。推薦精選為了克服這種缺陷，有兩條途徑可以采納。一是增加計算量，在記錄中增加一定的信息，使計算工作適當減少或者更方便。推薦精選/八叉樹的實現(xiàn)1 /功能：2 /1、創(chuàng)建八叉樹。3 /此八叉樹為滿樹，即所有節(jié)點/葉子全部創(chuàng)建。4 /用戶可以自定義此八叉樹的深度和所處的三維場景中的位置。5 /注a：由于創(chuàng)建樹時為滿樹創(chuàng)建，故層數(shù)太大時創(chuàng)建時間可能會比較久，請耐心等

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

9、ace std;18 /定義八叉樹節(jié)點類19 template20 struct OctreeNode21 22 T data; /節(jié)點數(shù)據(jù)23 T xmin,xmax; /節(jié)點坐標，即六面體個頂點的坐標24 T ymin,ymax;25 T zmin,zmax;26 OctreeNode *top_left_front,*top_left_back; /該節(jié)點的個子結(jié)點,即個子六面體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é)點類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處理中，請稍候=0)63 64 root=new

14、OctreeNode();65 root-data = 9; /為節(jié)點賦值，可以存儲節(jié)點信息，如物體可見性。由于是簡單實現(xiàn)八叉樹功能，簡單賦值為。66 root-xmin=xmin; /為節(jié)點坐標賦值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;/計算節(jié)點個維度上的半邊長73 double ym=(ymax-ymin)/2;74 double zm=(ymax-ymin)/2;75 /遞歸創(chuàng)建子樹，根據(jù)每一個

15、節(jié)點所處（是幾號節(jié)點）的位置決定其子結(jié)點的坐標。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.當前節(jié)點的值為：data/n坐標為：;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 /計算單位長度，為查找點做準備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 /查找點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該點不在場景中！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找到該點！該點位于endl;153 cout xmin: xmin xmax: xmax;154 cout ymin: ymin

22、ymax: ymax;155 cout zmin: zmin zmax: zmax;156 cout節(jié)點內(nèi)！endl;157 cout共經(jīng)過times次遞歸！endl;158 159 else if(xxmax-xm) & yymax-ym) & zzmax-zm)推薦精選160 161 cout當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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當前經(jīng)過節(jié)點坐標：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請選擇操作：/n;241 cout1.創(chuàng)建八叉樹 2.先序遍歷八叉樹/n;242 cout3.查看樹深度 4.查找節(jié)點 /n;243 coutchoiced;245 if(choiced = 0)246 return 0;247 else if(choiced = 1)推薦精選248 249 system(cls);250 cout請輸入最大遞歸深度：maxdepth;252 cout請輸入外包盒坐標，順序如下：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輸入錯誤！;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開始搜尋該點endl;292 find(rootNode,x,y,z);293 system(pause);294