八叉樹管理原理

一）基來源理用八叉樹來表示三維形體，并研究在這類表示下的各樣操作及應用是在進入80年月后才比較全面地展開起來的。這類方法，既能夠當作是四叉樹方法在三維空間的推行，也能夠以為是用三維體素陣列表示形體方法的一種改良

。八叉樹的邏輯構造以下：假定要表示的形體V能夠放在一個充分大的正方體C內，C的邊長為2n，形體VC,它的八叉樹能夠用以下的遞歸方法來定義：八叉樹的每個節(jié)點與

C的一個子立方體對應，樹根與

C自己相對應，假如

V=

C,那么

V的八叉樹僅有樹根，如果VM

C,則將

C平分為八個子立方體，每個子立方體與樹根的一個子節(jié)點

相對應。只需某個子立方體不是完整空白或完整為V所占有，就要被八平分（圖而對應的節(jié)點也就有了八個子節(jié)點。這樣的遞歸判斷、切割向來要進行到節(jié)點所對應的立方或是完整為V占有，或是其大小已經是早先定義的體素大小，并且對它與之交作必定的“舍入”，使體素或以為是空白的，或以為是V占有的。

2-5-1）,從體或是完整空白，V這樣所生成的八叉樹上的節(jié)點可分為三類：灰節(jié)點，它對應的立方體部分地為V所占有；白節(jié)點，它所對應的立方體中無V的內容；黑節(jié)點，它所對應的立方體全為V所占有。后兩類又稱為葉結點。形體V對于C的八叉樹的邏輯構造是這樣的：它是一顆樹，其上的節(jié)點要么是葉節(jié)點，要么就是有八個子節(jié)點的灰節(jié)點。根節(jié)點與C相對應，其他節(jié)點與C的某個子立方體相對應。因為八叉樹的構造與四叉樹的構造是這樣的相像，所以八叉樹的存貯構造方式能夠完整沿用四叉樹的有關方法。因此，依據不一樣的存貯方式，八叉樹也能夠分別稱為慣例的、線性的、一對八的八叉樹等等。此外，因為這類方法充分利用了形體在空上的有關性，所以，一般來說，它所占用的存貯空間要比三維體素陣列的少?？墒菍嵸|上它仍是使用了相當多的存貯，這其實不是八叉樹的主要長處。這一方法的主要長處在于能夠特別方便地實現(xiàn)有寬泛用途的會合運算（比如能夠求兩個物體的并、交、差等運算），而這些正是其他表示方法比較難以辦理或許需要耗資很多計算資源的地方。不單這樣，因為這類方法的有序性及分層性，因此對顯示精度和速度的均衡、隱線和隱面的除去等，帶來了很大的方便，特別實用。（二）八叉樹的存貯構造八叉樹有三種不一樣的存貯構造，分別是規(guī)則方式、線性方式以及一對八方式。相應的八叉樹也分別稱為規(guī)則八叉樹、線性八叉樹以及一對八式八叉樹。不一樣的存貯構造的空間利用率及運算操作的方便性是不一樣的。剖析表明，一對八式八叉樹長處更多一些。1、規(guī)則八叉樹規(guī)則八叉樹的存貯構造用一個有九個字段的記錄來表示樹中的每個結點。此中一個字段用來描繪該結點的特性（在當前假定下，只需描繪它是灰、白、黑三類結點中哪一類即可），其他的八個字段用來作為寄存指向其八個子結點的指針。這是最廣泛使用的表示樹形數(shù)據的存貯構造方式。規(guī)則八叉樹缺點許多，最大的問題是指針占用了大批的空間。假定每個指針要用兩個字節(jié)表示，而結點的描述用一個字節(jié)，那么寄存指針要占總的存貯量的94％。所以，這類方法固然十分自然，簡單掌握，但在存貯空間的使用率方面不很理想。2、線性八叉樹線性八叉樹著重考慮怎樣提升空間利用率。用某一早先確立的序次遍歷八叉樹（比如以深度第一的方式），將八叉樹變換成一個線性表（圖2-5-2），表的每個元素與一個結點相對應。對于結點的描繪能夠豐富一點，比如用適合的方式來說明它能否為葉結點，假如不是葉結點時還可用其八個子結點值的均勻值作為非葉結點的值等等。這樣，能夠在內存中以緊湊的方式來表示線性表，能夠不用指針或許僅用一個指針表示即可。線性八叉樹不單節(jié)儉存貯空間，對某些運算也較為方便?？墒菫榇烁冻龅拇鷥r是喪失了必定的靈巧性。例如為了存取屬于原圖形右下角的子圖形對應的結點，那么一定先遍歷了其他七個子圖形對應的全部結點后才能進行；不可以方便地以其他遍歷方式對樹的結點進行存取，導致了很多與此有關的運算效率變低。所以只管許多文章議論了這類八叉樹的應用，可是仍很難令人滿意3、一對八式的八叉樹一個非葉結點有八個子結點，為了確立起見，將它們分別標志為

0，1，2，

3，4，5，6，7。從上邊的介紹能夠看到，假如一個記錄與一個結點相對應，那么在這個記錄中描繪的是這個結點的八個子結點的特征值。而指針給出的則是該八個子結點所對應記錄的寄存處，并且還隱含地假定了這些子結點記錄寄存的序次。也就是說，即便某個記錄是不用要的（比如，該結點已經是葉結點），那么相應的存貯地點也一定安閑在那邊（圖2-5-3），以保證不會錯誤地存取到其他平輩結點的記錄。這樣自然會有必定的浪費，除非它是完整的八叉樹，即全部的葉結點均在同一層次出現(xiàn)，而在該層次之上的全部層中的結點均為非葉結點。為了戰(zhàn)勝這類缺點，有兩條門路能夠采用。一是增添計算量，在記錄中增添必定的信息，使計算工作適合減少或許更方便。1前節(jié)點的值為："<<p->data<<"/n坐標為：";2cout<<"xmin:"<<p->xmin<<"xmax:"<<p->xmax;3cout<<"ymin:"<<p->ymin<<"ymax:"<<p->ymax;4cout<<"zmin:"<<p->zmin<<"zmax:"<<p->zmax;5i+=1;6cout<<endl;7preOrder(p->top_left_front);8preOrder(p->top_left_back);9preOrder(p->top_right_front);10preOrder(p->top_right_back);11preOrder(p->bottom_left_front);12preOrder(p->bottom_left_back);13preOrder(p->bottom_right_front);14preOrder(p->bottom_right_back);15cout<<endl;16}}建八叉樹2.先序遍歷八叉樹/n";19cout<<"3.查察樹深度4.查找節(jié)點/n";20cout<<"0.退出/n/n";21cin>>choiced;22if(choiced==0)23return0;24elseif(choiced==1)25{26system("cls");27cout<<"請輸入最大遞歸深度："<<endl;28cin>>maxdepth;29cout<<"請輸入外包盒坐標，次序如xmin,xmax,ymin,ymax,zmin,zmax"<<endl;30cin>>xmin>>xmax>>ymin>>ymax>>zmin>>zmax;31if(maxdepth>=0||xmax>xmin||ymax>ymin||zmax>zmin||xmin>0||ymin>0||zmin>0)32{33tmaxdepth=cal(maxdepth);34txm=(xmax-xmin)/tmaxdepth;35tym=(ymax-ymin)/tmaxdepth;36tzm=(zmax-zmin)/tmaxdepth;37createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);38}39else40{41cout<<"輸入錯誤！42434445464748495051525354555657585960616263646566}}7879

return0;}}elseif(choiced==2){system("cls");cout<<"先序遍歷八叉樹結果：/n";i=1;preOrder(rootNode);cout<<endl;system("pause");}elseif(choiced==3){system("cls");intdep=depth(rootNode);cout<<"此八叉樹的深度為"<<dep+1<<endl;system("pause");}elseif(choiced==4){system("cls");cout<<"請輸入您希望查找的點的坐標，次序以下：doublex,y,z;cin>>x>>y>>z;times=0;x,y,z/n";cout<<endl<<"開始找尋該點............"<<endl;find(rootNode,x,y,z);system("pause");}else{system("cls");cout<<"/n/n錯誤選擇！/n";system("pause");}對于三維場景八叉樹的初步想法今日建冰跟我提起了一個很存心思的東西：八叉樹把一個立方體切三刀，橫一刀，豎兩刀（按坐標軸的方向切）一次小立方體，在分紅8塊。。向來往下遞歸，這就能夠使用一個八叉樹儲藏。

，就變?yōu)?/p>

8個邊長為一半的立方體。再切八叉樹儲藏的利處：在沒有東西的立方體，就不用再往下切，能節(jié)儉儲藏空間，運算資源管理方便，搜尋某一個小方塊的時候，能很方便的使用二分法查找深度到必定層次此后，基本能夠擬合全部的三維模型。對八叉樹的使用的初步想法：第一，對一個三維游戲的空間來說，z維的使用遠比x、y維少。若x、y維使用范圍是用到128就足夠了（自然這是在地面游戲的基礎上，不包含空戰(zhàn)）。所以，為了減少八叉樹的層次，我們能夠對八叉樹做一點點擴大：第一層不作為八叉樹的分叉儲藏，儲藏一個平面。這是一個由立方體拼成的平面。大家能夠想象一下平面拼起來的麻將。就是真實意義上的八叉樹，第一層平面上的每一個立方體，都是八叉樹的根節(jié)點，而后往下細分。假1024*1024*128，這只需要第一層4*4的立方體，而后每個立方體對應7層的八叉樹即可。對照起全八叉樹，只好形成1024*1024*1024的空間，需要10層的八叉樹，節(jié)儉了3層。

0-1024

，z維從第二層開始，如場景需要為其次，對于場景里面的物體操作。物體能夠用一個小八叉樹儲藏（八叉樹again），自然這個八叉樹的層次會少好多，最多可是5層。在場景中，以某一個元點（比如八叉樹的最左葉節(jié)點）作為場景的定位，而后判斷與場景訂交，只需要一個矩陣的乘法運算即可。效率很高自然，八叉樹的訂交會存在必定問題。在我臨時能想