1、八叉樹三維數(shù)據(jù)結構（一）基本原理用八叉樹來表示三維形體，并研究在這種表示下的各種操作及應用是在進入80年代后才比較全面地開展起來的。這種方法，既可以看成是四叉樹方法在三維空間的推廣，也可以認為是用三維體素陣列表示形體方法的一種改進。八叉樹的邏輯結構如下：假設要表示的形體V可以放在一個充分大的正方體C內，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的內容；黑節(jié)點，它所對應的立方體全為V所占據(jù)。后兩類又稱為葉結點。形體V關于C的八叉樹的邏輯結構是這樣的：它是一顆樹，其上的節(jié)點要么是葉節(jié)點，要么就是有八個子節(jié)點的灰節(jié)點。根節(jié)點與C相對應，其它節(jié)點與C的某個子立方體相對應。因為八叉樹的結構與四叉樹的結

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

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

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

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

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

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

9、 namespace std;19 /定義八叉樹節(jié)點類20 template<class T>21 struct OctreeNode22 23 T data; /節(jié)點數(shù)據(jù)24 T xmin,xmax; /節(jié)點坐標，即六面體個頂點的坐標25 T ymin,ymax;26 T zmin,zmax;27 OctreeNode <T> *top_left_front,*top_left_back; /該節(jié)點的個子結點,即個子六面體28 OctreeNode <T> *top_right_front,*top_right_back;29 OctreeNode <

10、;T> *bottom_left_front,*bottom_left_back;30 OctreeNode <T> *bottom_right_front,*bottom_right_back;31 OctreeNode /節(jié)點類32 (T nodeValue = T(),33 T xminValue = T(),T xmaxValue = T(),34 T yminValue = T(),T ymaxValue = T(),35 T zminValue = T(),T zmaxValue = T(),36 OctreeNode<T>* top_left_fro

11、nt_Node = NULL,37 OctreeNode<T>* top_left_back_Node = NULL,38 OctreeNode<T>* top_right_front_Node = NULL,39 OctreeNode<T>* top_right_back_Node = NULL,40 OctreeNode<T>* bottom_left_front_Node = NULL,41 OctreeNode<T>* bottom_left_back_Node = NULL,42 OctreeNode<T>* b

12、ottom_right_front_Node = NULL,43 OctreeNode<T>* bottom_right_back_Node = NULL )44 :data(nodeValue),45 xmin(xminValue),xmax(xmaxValue),46 ymin(yminValue),ymax(ymaxValue),47 zmin(zminValue),zmax(zmaxValue),48 top_left_front(top_left_front_Node),49 top_left_back(top_left_back_Node),50 top_right_f

13、ront(top_right_front_Node),51 top_right_back(top_right_back_Node),52 bottom_left_front(bottom_left_front_Node),53 bottom_left_back(bottom_left_back_Node),54 bottom_right_front(bottom_right_front_Node),55 bottom_right_back(bottom_right_back_Node)56 ;57 /創(chuàng)建八叉樹58 template <class T>59 void createO

14、ctree(OctreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)60 61 cout<<"處理中，請稍候"<<endl;62 maxdepth=maxdepth-1; /每遞歸一次就將最大遞歸深度-163 if(maxdepth>=0)64 65 root=new OctreeNode<T>();66 root->data = 9; /為節(jié)點賦值，

15、可以存儲節(jié)點信息，如物體可見性。由于是簡單實現(xiàn)八叉樹功能，簡單賦值為。67 root->xmin=xmin; /為節(jié)點坐標賦值68 root->xmax=xmax;69 root->ymin=ymin;70 root->ymax=ymax;71 root->zmin=zmin;72 root->zmax=zmax;73 double xm=(xmax-xmin)/2;/計算節(jié)點個維度上的半邊長74 double ym=(ymax-ymin)/2;75 double zm=(ymax-ymin)/2;76 /遞歸創(chuàng)建子樹，根據(jù)每一個節(jié)點所處（是幾號節(jié)點）的位置

16、決定其子結點的坐標。77 createOctree(root->top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);78 createOctree(root->top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);79 createOctree(root->top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);80 createOctree(root-&g

17、t;top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);81 createOctree(root->bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);82 createOctree(root->bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);83 createOctree(root->bottom_right_front,maxdept

18、h,xmax-xm,xmax,ymax-ym,ymax,zmin,zmax-zm);84 createOctree(root->bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);85 86 87 int i=1;88 /先序遍歷八叉樹89 template <class T>90 void preOrder( OctreeNode<T> * & p)91 92 if(p)93 94 cout<<i<<".當前節(jié)點的值為："<

19、<p->data<<"/n坐標為："95 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;96 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;97 cout<<" zmin: "<<p->zmin<<&quo

20、t; zmax: "<<p->zmax;98 i+=1;99 cout<<endl;100 preOrder(p->top_left_front);101 preOrder(p->top_left_back);102 preOrder(p->top_right_front);103 preOrder(p->top_right_back);104 preOrder(p->bottom_left_front);105 preOrder(p->bottom_left_back);106 preOrder(p->bott

21、om_right_front);107 preOrder(p->bottom_right_back);108 cout<<endl;109 110 111 /求八叉樹的深度112 template<class T>113 int depth(OctreeNode<T> *& p)114 115 if(p = NULL)116 return -1;117 int h = depth(p->top_left_front);118 return h+1;119 120 /計算單位長度，為查找點做準備121 int cal(int num)122

22、 123 int result=1;124 if(1=num)125 result=1;126 else127 128 for(int i=1;i<num;i+)129 result=2*result;130 131 return result;132 133 /查找點134 int maxdepth=0;135 int times=0;136 static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;137 int tmaxdepth=0;138 double txm=1,tym=1,tzm=1;139 template<cl

23、ass T>140 void find(OctreeNode<T> *& p,double x,double y,double z)141 142 double xm=(p->xmax-p->xmin)/2;143 double ym=(p->ymax-p->ymin)/2;144 double zm=(p->ymax-p->ymin)/2;145 times+;146 if(x>xmax | x<xmin | y>ymax | y<ymin | z>zmax | z<zmin)147 148 c

24、out<<"該點不在場景中！"<<endl;149 return;150 151 if(x<=p->xmin+txm && x>=p->xmax-txm && y<=p->ymin+tym && y>=p->ymax-tym && z<=p->zmin+tzm && z>=p->zmax-tzm )152 153 cout<<endl<<"找到該點！"<

25、;<"該點位于"<<endl;154 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;155 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;156 cout<<" zmin: "<<p->zmin<<"

26、zmax: "<<p->zmax;157 cout<<"節(jié)點內！"<<endl;158 cout<<"共經(jīng)過"<<times<<"次遞歸！"<<endl;159 160 else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm)161 162 cout<<"當前經(jīng)過節(jié)點坐標："&l

27、t;<endl;163 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;164 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;165 cout<<" zmin: "<<p->zmin<<" zmax: "<<p-&

28、gt;zmax;166 cout<<endl;167 find(p->bottom_left_back,x,y,z);168 169 else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm)170 171 cout<<"當前經(jīng)過節(jié)點坐標："<<endl;172 cout<<" xmin: "<<p->xmin<<" xmax: &quo

29、t;<<p->xmax;173 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;174 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;175 cout<<endl;176 find(p->top_left_back,x,y,z);177 178 else if(x>(p-

30、>xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm)179 180 cout<<"當前經(jīng)過節(jié)點坐標："<<endl;181 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;182 cout<<" ymin: "<<p->ymin<<" yma

31、x: "<<p->ymax;183 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;184 cout<<endl;185 find(p->bottom_right_back,x,y,z);186 187 else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm)188 189 cout

32、<<"當前經(jīng)過節(jié)點坐標："<<endl;190 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;191 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;192 cout<<" zmin: "<<p->zmin<<

33、;" zmax: "<<p->zmax;193 cout<<endl;194 find(p->top_right_back,x,y,z);195 196 else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm)197 198 cout<<"當前經(jīng)過節(jié)點坐標："<<endl;199 cout<<" xmin: "<<p->

34、xmin<<" xmax: "<<p->xmax;200 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;201 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;202 cout<<endl;203 find(p->bottom_left_fron

35、t,x,y,z);204 205 else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm)206 207 cout<<"當前經(jīng)過節(jié)點坐標："<<endl;208 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;209 cout<<" ymin: "<

36、;<p->ymin<<" ymax: "<<p->ymax;210 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;211 cout<<endl;212 find(p->top_left_front,x,y,z);213 214 else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z&

37、lt;(p->zmax-zm)215 216 cout<<"當前經(jīng)過節(jié)點坐標："<<endl;217 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;218 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;219 cout<<" zmin: &

38、quot;<<p->zmin<<" zmax: "<<p->zmax;220 cout<<endl;221 find(p->bottom_right_front,x,y,z);222 223 else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm)224 225 cout<<"當前經(jīng)過節(jié)點坐標："<<endl;226 cout<<

39、;" xmin: "<<p->xmin<<" xmax: "<<p->xmax;227 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;228 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;229 cout<<en

40、dl;230 find(p->top_right_front,x,y,z);231 232 233 /main函數(shù)234 int main ()235 236 OctreeNode<double> * rootNode = NULL;237 int choiced = 0;238 while(true)239 240 system("cls");241 cout<<"請選擇操作：/n"242 cout<<"1.創(chuàng)建八叉樹 2.先序遍歷八叉樹/n"243 cout<<"3.

41、查看樹深度 4.查找節(jié)點 /n"244 cout<<"0.退出/n/n"245 cin>>choiced;246 if(choiced = 0)247 return 0;248 else if(choiced = 1)249 250 system("cls");251 cout<<"請輸入最大遞歸深度："<<endl;252 cin>>maxdepth;253 cout<<"請輸入外包盒坐標，順序如下：xmin,xmax,ymin,ymax,z

42、min,zmax"<<endl;254 cin>>xmin>>xmax>>ymin>>ymax>>zmin>>zmax;255 if(maxdepth>=0 | xmax>xmin | ymax>ymin | zmax>zmin | xmin>0 | ymin>0 |zmin>0)256 257 tmaxdepth=cal(maxdepth);258 txm=(xmax-xmin)/tmaxdepth;259 tym=(ymax-ymin)/tmaxdepth

43、;260 tzm=(zmax-zmin)/tmaxdepth;261 createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);262 263 else264 265 cout<<"輸入錯誤！"266 return 0;267 268 269 else if(choiced = 2)270 271 system("cls");272 cout<<"先序遍歷八叉樹結果：/n"273 i=1;274 preOrder(rootNode);275 cout<<endl;276 system("pause");277 278 else if(choiced = 3)279 280 system("cls&qu