八叉树管理原理

1、八叉树三维数据结构（一）基本原理用八叉树来表示三维形体，并研究在这种表示下的各种操作及应用是在进入80年代后才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。八叉树的逻辑结构如下：假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2 n，形体V C，它的八叉树可以用以下的递归方法来定义：八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果VC，那么V的八叉树仅有树根，如果VC，则将C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分（

2、图2-5-1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。如此所生成的八叉树上的节点可分为三类：灰节点，它对应的立方体部分地为V所占据；白节点，它所对应的立方体中无V的内容；黑节点，它所对应的立方体全为V所占据。后两类又称为叶结点。形体V关于C的八叉树的逻辑结构是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与C相对应，其它节点与C的某个子立方体相对应。因为八叉树的结构与四叉树的结

3、构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。因而，根据不同的存贮方式，八叉树也可以分别称为常规的、线性的、一对八的八叉树等等。另外，由于这种方法充分利用了形体在空上的相关性，因此，一般来说，它所占用的存贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮，这并不是八叉树的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可以求两个物体的并、交、差等运算)，而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。不仅如此，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡、隐线和隐面的消除等，带来了很大的方便，特别有用

4、。（二）八叉树的存贮结构八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。推荐精选1、规则八叉树规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可)，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节

5、表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。2、线性八叉树线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表（图2-5-2），表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。线性八叉树不仅节省存贮空间，对某些运算也较为方便。但是为此付出的代价是

6、丧失了一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点，那么必须先遍历了其余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但是仍很难令人满意3、一对八式的八叉树一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(

7、例如，该结点已是叶结点)，那么相应的存贮位置也必须空闲在那里（图2-5-3），以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。推荐精选为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一定的信息，使计算工作适当减少或者更方便。推荐精选/八叉树的实现1 /功能：2 /1、创建八叉树。3 /此八叉树为满树，即所有节点/叶子全部创建。4 /用户可以自定义此八叉树的深度和所处的三维场景中的位置。5 /注a：由于创建树时为满树创建，故层数太大时创建时间可能会比较久，请耐心等

8、待。6 /注b：创建顺序为(1)上层左前节点-(2)上层右前节点-(3)上层右前节点-(4)上层右后节点7 /-(5)下层左前节点-(6)下层右前节点-(7)下层右前节点-(8)下层右后节点-(1)-(2)8 /2、先序遍历八叉树。9 /八叉树创建成功后用户可调用此子模块查看此八叉树，会显示每个结点的编号，值和在场景中的坐标。10 /3、查看八叉树的深度。11 /4、在场景中查找点。12 /用户首先输入要查找的坐标。13 /如果该点位于场景外则提示用户并返回，否则在场景中递归查找该点。14 /找到后输出该点所处的子结点的坐标和递归次数。1516 #include 17 using namesp

9、ace std;18 /定义八叉树节点类19 template20 struct OctreeNode21 22 T data; /节点数据23 T xmin,xmax; /节点坐标，即六面体个顶点的坐标24 T ymin,ymax;25 T zmin,zmax;26 OctreeNode *top_left_front,*top_left_back; /该节点的个子结点,即个子六面体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 /节点类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 /创建八叉树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; /为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。66 root-xmin=xmin; /为节点坐标赋值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;/计算节点个维度上的半边长73 double ym=(ymax-ymin)/2;74 double zm=(ymax-ymin)/2;75 /递归创建子树，根据每一个

15、节点所处（是几号节点）的位置决定其子结点的坐标。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.当前节点的值为：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节点内！endl;157 cout共经过times次递归！endl;158 159 else if(xxmax-xm) & yymax-ym) & zzmax-zm)推荐精选160 161 cout当前经过节点坐标：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当前经过节点坐标：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当前经过节点坐标：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当前经过节点坐标：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当前经过节点坐标：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当前经过节点坐标：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当前经过节点坐标：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当前经过节点坐标：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函数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.创建八叉树 2.先序遍历八叉树/n;242 cout3.查看树深度 4.查找节点 /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先序遍历八叉树结果：/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