八叉树管理原理.doc

八叉树三维数据结构
（一）基本原理
用八叉树来表示三维形体，并研究在这种表示下的各种操作及应用是在进入80年代后才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。
八叉树的逻辑结构如下：
假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2 n，形体V C，它的八叉树可以用以下的递归方法来定义：
八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果V＝C，那么V的八叉树仅有树根，如果V≠C，则将C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分（图2-5-1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是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 //八叉树的实现
2 //功能：
3 //1、创建八叉树。
4 //此八叉树为满树，即所有节点/叶子全部创建。
5 //用户可以自定义此八叉树的深度和所处的三维场景中的位置。
6 //注a：由于创建树时为满树创建，故层数太大时创建时间可能会比较久，请耐心等待。
7 //注b：创建顺序为(1)上层左前节点-(2)上层右前节点-(3)上层右前节点-(4)上层右后节点
8 //-(5)下层左前节点-(6)下层右前节点-(7)下层右前节点-(8)下层右后节点-(1)-(2)……
9 //2、先序遍历八叉树。
10 //八叉树创建成功后用户可调用此子模块查看此八叉树，会显示每个结点的编号，值和在场景中的坐标。
11 //3、查看八叉树的深度。
12 //4、在场景中查找点。
13 //用户首先输入要查找的坐标。
14 //如果该点位于场景外则提示用户并返回，否则在场景中递归查找该点。
15 //找到后输出该点所处的子结点的坐标和递归次数。
16
17 #include <iostream>
18 using namespace std;
19 //定义八叉树节点类
20 template<class T>
21 struct OctreeNode
22 {
23 T data; //节点数据
24 T xmin,xmax; //节点坐标，即六面体个顶点的坐标
25 T ymin,ymax;
26 T zmin,zmax;
27 OctreeNode <T> *top_left_front,*top_left_back; //该节点的个子结点,即个子六面体
28 OctreeNode <T> *top_right_front,*top_right_back;
29 OctreeNode <T> *bottom_left_front,*bottom_left_back;
30 OctreeNode <T> *bottom_right_front,*bottom_right_back;
31 OctreeNode //节点类
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_front_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>* bottom_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_front(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 //创建八叉树
58 template <class T>
59 void createOctree(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; //每递归一次就将最大递归深度-1
63 if(maxdepth>=0)
64 {
65 root=new OctreeNode<T>();
66 root->data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。
67 root->xmin=xmin; //为节点坐标赋值
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;//计算节点个维度上的半边长
74 double ym=(ymax-ymin)/2;
75 double zm=(ymax-ymin)/2;
76 //递归创建子树，根据每一个节点所处（是几号节点）的位置决定其子结点的坐标。
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->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,maxdepth,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<<".当前节点的值为："<<p->data<<"/n坐标为：";
95 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
96 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
97 cout<<" zmin: "<<p->zmin<<" 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->bottom_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 {
123 int result=1;
124 if(1==num)
125 result=1;
126 else
127 {
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<class 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 cout<<"该点不在场景中！"<<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<<"找到该点！"<<"该点位于"<<endl;
154 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
155 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
156 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
157 cout<<"节点内！"<<endl;
158 cout<<"共经过"<<times<<"次递归！"<<endl;
159 }
160 else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
161 {
162 cout<<"当前经过节点坐标："<<endl;
163 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
164 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
165 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->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<<"当前经过节点坐标："<<endl;
172 cout<<" xmin: "<<p->xmin<<" xmax: "<<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->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
179 {
180 cout<<"当前经过节点坐标："<<endl;
181 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
182 cout<<" ymin: "<<p->ymin<<" ymax: "<<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<<"当前经过节点坐标："<<endl;
190 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
191 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
192 cout<<" zmin: "<<p->zmin<<" 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<<"当前经过节点坐标："<<endl;
199 cout<<" xmin: "<<p->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_front,x,y,z);
204 }
205 else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
206 {
207 cout<<"当前经过节点坐标："<<endl;
208 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
209 cout<<" ymin: "<<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<(p->zmax-zm))
215 {
216 cout<<"当前经过节点坐标："<<endl;
217 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
218 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
219 cout<<" zmin: "<<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<<"当前经过节点坐标："<<endl;
226 cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
227 cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
228 cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
229 cout<<endl;
230 find(p->top_right_front,x,y,z);
231 }
232 }
233 //main函数
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.创建八叉树 2.先序遍历八叉树/n";
243 cout<<"3.查看树深度 4.查找节点 /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,zmin,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;
260 tzm=(zmax-zmin)/tmaxdepth;
261 createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
262 }
263 else
264 {
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");
281 int dep = depth(rootNode);
282 cout<<"此八叉树的深度为"<<dep+1<<endl;
283 system("pause");
284 }
285 else if(choiced == 4)
286 {
287 system("cls");
288 cout<<"请输入您希望查找的点的坐标，顺序如下：x,y,z/n";
289 double x,y,z;
290 cin>>x>>y>>z;
291 times=0;
292 cout<<endl<<"开始搜寻该点……"<<endl;
293 find(rootNode,x,y,z);
294 system("pause");
295 }
296 else
297 {
298 system("cls");
299 cout<<"/n/n错误选择！/n";
300 system("pause");
301 }
302 }
303 }

关于三维场景八叉树的初步想法
今天建冰跟我提起了一个很有意思的东西：八叉树

把一个立方体切三刀，横一刀，竖两刀（按坐标轴的方向切），就变成8个边长为一半的立方体。再切一次小立方体，在分成8块。。。
一直往下递归，这就可以使用一个八叉树储存。

八叉树储存的好处：
1.在没有东西的立方体，就不用再往下切，能节省储存空间，运算资源
2.管理方便，搜索某一个小方块的时候，能很方便的使用二分法查找
3.深度到一定层次以后，基本可以拟合所有的三维模型。

对八叉树的使用的初步想法：
首先，对一个三维游戏的空间来说，z维的使用远比x、y维少。若x、y维使用范围是0-1024，z维用到128就足够了（当然这是在地面游戏的基础上，不包括空战）。
所以，为了减少八叉树的层次，我们可以对八叉树做一点点扩充：第一层不作为八叉树的分叉储存，储存一个平面。这是一个由立方体拼成的平面。大家可以想象一下平面拼起来的麻将。从第二层开始，就是真正意义上的八叉树，第一层平面上的每一个立方体，都是八叉树的根节点，然后往下细分。假如场景需要为1024*1024*128，这只需要第一层4*4的立方体，然后每个立方体对应7层的八叉树即可。对比起全八叉树，只能形成1024*1024*1024的空间，需要10层的八叉树，节约了3层。

其次，对于场景里面的物体操作。
物体可以用一个小八叉树储存（八叉树again），当然这个八叉树的层次会少很多，最多不过5层。在场景中，以某一个元点（譬如八叉树的最左叶节点）作为场景的定位，然后判断与场景相交，只需要一个矩阵的乘法运算即可。效率很高

当然，八叉树的相交会存在一定问题。在我暂时能想到的范围里，由于八叉树的储存不完全是以元点为单位的，会有很多节点没有延伸到最底层（当然这个最底层是必须为定义好的有限层），取相交矩阵的时候，必须把其延伸到最底层，才能取出这个矩阵（或者用一些特殊算法取）。这还是在一个物体的情况下。当有多个物体的时候，两种解决方法：其一，把物体的占用空间存进场景八叉树，这样每个物体的占用空间场景都知道，只要在场景空间里面判断是否有交集即可。其二，以相对坐标的形式，遍历两个物体相交的元点是否有重叠占用。