八叉樹管理原理

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

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

C的一個(gè)子立方體對應(yīng)，樹根與

C自己相對應(yīng)，假如

V=

C,那么

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

C,則將

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

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

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

0，1，2，

3，4，5，6，7。從上邊的介紹能夠看到，假如一個(gè)記錄與一個(gè)結(jié)點(diǎn)相對應(yīng)，那么在這個(gè)記錄中描繪的是這個(gè)結(jié)點(diǎn)的八個(gè)子結(jié)點(diǎn)的特征值。而指針給出的則是該八個(gè)子結(jié)點(diǎn)所對應(yīng)記錄的寄存處，并且還隱含地假定了這些子結(jié)點(diǎn)記錄寄存的序次。也就是說，即便某個(gè)記錄是不用要的（比如，該結(jié)點(diǎn)已經(jīng)是葉結(jié)點(diǎn)），那么相應(yīng)的存貯地點(diǎn)也一定安閑在那邊（圖2-5-3），以保證不會(huì)錯(cuò)誤地存取到其他平輩結(jié)點(diǎn)的記錄。這樣自然會(huì)有必定的浪費(fèi)，除非它是完整的八叉樹，即全部的葉結(jié)點(diǎn)均在同一層次出現(xiàn)，而在該層次之上的全部層中的結(jié)點(diǎn)均為非葉結(jié)點(diǎn)。為了戰(zhàn)勝這類缺點(diǎn)，有兩條門路能夠采用。一是增添計(jì)算量，在記錄中增添必定的信息，使計(jì)算工作適合減少或許更方便。1前節(jié)點(diǎn)的值為："<<p->data<<"/n坐標(biāo)為：";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é)點(diǎn)/n";20cout<<"0.退出/n/n";21cin>>choiced;22if(choiced==0)23return0;24elseif(choiced==1)25{26system("cls");27cout<<"請輸入最大遞歸深度："<<endl;28cin>>maxdepth;29cout<<"請輸入外包盒坐標(biāo)，次序如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<<"輸入錯(cuò)誤！42434445464748495051525354555657585960616263646566}}7879

return0;}}elseif(choiced==2){system("cls");cout<<"先序遍歷八叉樹結(jié)果：/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<<"請輸入您希望查找的點(diǎn)的坐標(biāo)，次序以下：doublex,y,z;cin>>x>>y>>z;times=0;x,y,z/n";cout<<endl<<"開始找尋該點(diǎn)............"<<endl;find(rootNode,x,y,z);system("pause");}else{system("cls");cout<<"/n/n錯(cuò)誤選擇！/n";system("pause");}對于三維場景八叉樹的初步想法今日建冰跟我提起了一個(gè)很存心思的東西：八叉樹把一個(gè)立方體切三刀，橫一刀，豎兩刀（按坐標(biāo)軸的方向切）一次小立方體，在分紅8塊。。向來往下遞歸，這就能夠使用一個(gè)八叉樹儲(chǔ)藏。

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

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

0-1024

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