八叉树管理原理

一）基来源理用八叉树来表示三维形体，并研究在这类表示下的各样操作及应用是在进入80年月后才比较全面地展开起来的。这类方法，既能够当作是四叉树方法在三维空间的推行，也能够以为是用三维体素阵列表示形体方法的一种改良

。八叉树的逻辑构造以下：假定要表示的形体V能够放在一个充分大的正方体C内，C的边长为2n，形体VC,它的八叉树能够用以下的递归方法来定义：八叉树的每个节点与

C的一个子立方体对应，树根与

C自己相对应，假如

V=

C,那么

V的八叉树仅有树根，如果VM

C,则将

C平分为八个子立方体，每个子立方体与树根的一个子节点

相对应。只需某个子立方体不是完整空白或完整为V所占有，就要被八平分（图而对应的节点也就有了八个子节点。这样的递归判断、切割向来要进行到节点所对应的立方或是完整为V占有，或是其大小已经是早先定义的体素大小，并且对它与之交作必定的“舍入”，使体素或以为是空白的，或以为是V占有的。

2-5-1）,从体或是完整空白，V这样所生成的八叉树上的节点可分为三类：灰节点，它对应的立方体部分地为V所占有；白节点，它所对应的立方体中无V的内容；黑节点，它所对应的立方体全为V所占有。后两类又称为叶结点。形体V对于C的八叉树的逻辑构造是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与C相对应，其他节点与C的某个子立方体相对应。因为八叉树的构造与四叉树的构造是这样的相像，所以八叉树的存贮构造方式能够完整沿用四叉树的有关方法。因此，依据不一样的存贮方式，八叉树也能够分别称为惯例的、线性的、一对八的八叉树等等。此外，因为这类方法充分利用了形体在空上的有关性，所以，一般来说，它所占用的存贮空间要比三维体素阵列的少。可是实质上它仍是使用了相当多的存贮，这其实不是八叉树的主要长处。这一方法的主要长处在于能够特别方便地实现有宽泛用途的会合运算（比如能够求两个物体的并、交、差等运算），而这些正是其他表示方法比较难以办理或许需要耗资很多计算资源的地方。不单这样，因为这类方法的有序性及分层性，因此对显示精度和速度的均衡、隐线和隐面的除去等，带来了很大的方便，特别实用。（二）八叉树的存贮构造八叉树有三种不一样的存贮构造，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不一样的存贮构造的空间利用率及运算操作的方便性是不一样的。剖析表明，一对八式八叉树长处更多一些。1、规则八叉树规则八叉树的存贮构造用一个有九个字段的记录来表示树中的每个结点。此中一个字段用来描绘该结点的特性（在当前假定下，只需描绘它是灰、白、黑三类结点中哪一类即可），其他的八个字段用来作为寄存指向其八个子结点的指针。这是最广泛使用的表示树形数据的存贮构造方式。规则八叉树缺点许多，最大的问题是指针占用了大批的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么寄存指针要占总的存贮量的94％。所以，这类方法固然十分自然，简单掌握，但在存贮空间的使用率方面不很理想。2、线性八叉树线性八叉树着重考虑怎样提升空间利用率。用某一早先确立的序次遍历八叉树（比如以深度第一的方式），将八叉树变换成一个线性表（图2-5-2），表的每个元素与一个结点相对应。对于结点的描绘能够丰富一点，比如用适合的方式来说明它能否为叶结点，假如不是叶结点时还可用其八个子结点值的均匀值作为非叶结点的值等等。这样，能够在内存中以紧凑的方式来表示线性表，能够不用指针或许仅用一个指针表示即可。线性八叉树不单节俭存贮空间，对某些运算也较为方便。可是为此付出的代价是丧失了必定的灵巧性。例如为了存取属于原图形右下角的子图形对应的结点，那么一定先遍历了其他七个子图形对应的全部结点后才能进行；不可以方便地以其他遍历方式对树的结点进行存取，导致了很多与此有关的运算效率变低。所以只管许多文章议论了这类八叉树的应用，可是仍很难令人满意3、一对八式的八叉树一个非叶结点有八个子结点，为了确立起见，将它们分别标志为

0，1，2，

3，4，5，6，7。从上边的介绍能够看到，假如一个记录与一个结点相对应，那么在这个记录中描绘的是这个结点的八个子结点的特征值。而指针给出的则是该八个子结点所对应记录的寄存处，并且还隐含地假定了这些子结点记录寄存的序次。也就是说，即便某个记录是不用要的（比如，该结点已经是叶结点），那么相应的存贮地点也一定安闲在那边（图2-5-3），以保证不会错误地存取到其他平辈结点的记录。这样自然会有必定的浪费，除非它是完整的八叉树，即全部的叶结点均在同一层次出现，而在该层次之上的全部层中的结点均为非叶结点。为了战胜这类缺点，有两条门路能够采用。一是增添计算量，在记录中增添必定的信息，使计算工作适合减少或许更方便。1前节点的值为："<<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.查找节点/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块。。向来往下递归，这就能够使用一个八叉树储藏。

，就变为

8个边长为一半的立方体。再切八叉树储藏的利处：在没有东西的立方体，就不用再往下切，能节俭储藏空间，运算资源管理方便，搜寻某一个小方块的时候，能很方便的使用二分法查找深度到必定层次此后，基本能够拟合全部的三维模型。对八叉树的使用的初步想法：第一，对一个三维游戏的空间来说，z维的使用远比x、y维少。若x、y维使用范围是用到128就足够了（自然这是在地面游戏的基础上，不包含空战）。所以，为了减少八叉树的层次，我们能够对八叉树做一点点扩大：第一层不作为八叉树的分叉储藏，储藏一个平面。这是一个由立方体拼成的平面。大家能够想象一下平面拼起来的麻将。就是真实意义上的八叉树，第一层平面上的每一个立方体，都是八叉树的根节点，而后往下细分。假1024*1024*128，这只需要第一层4*4的立方体，而后每个立方体对应7层的八叉树即可。对照起全八叉树，只好形成1024*1024*1024的空间，需要10层的八叉树，节俭了3层。

0-1024

，z维从第二层开始，如场景需要为其次，对于场景里面的物体操作。物体能够用一个小八叉树储藏（八叉树again），自然这个八叉树的层次会少好多，最多可是5层。在场景中，以某一个元点（比如八叉树的最左叶节点）作为场景的定位，而后判断与场景订交，只需要一个矩阵的乘法运算即可。效率很高自然，八叉树的订交会存在必定问题。在我临时能想