在描述三维场景的过程中常常用到一种名为八叉树的数据结构。描述三维空间的八叉树和描述二维空间的四叉树有相似之处，二维空间中正方形可以被分为四个相同形状的正方形，而三维空间中正方体可以被分为八个形状相同的正方体。
八叉树的每个结点表示一个正方体的体积元素，每一个结点有八个子节点，这种用于描述三维空间的树装结构叫做八叉树。为了便利的点云操作，八叉树OcTree被封装在PCL库中。
八叉树的计算原理
1. 设定最大递归深度
2. 找出场景的最大尺寸，并以此尺寸建立第一个立方体
3. 依序将单位元元素丢入能包含且没有子节点的立方体
4. 若没达到最大递归深度，就进行细分八等份，再讲该立方体所装的单位元元素全部分组给八个子立方体
5. 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体一样，则该子立方体停止细分
(因为根据空间分割理论，细分的空间所得到的分配必定较少，若是一样的数目，再怎么切，数目还是一样)
6. 重复3，知道到达最大递归深度
八叉树的数据结构
首先，八叉树是一种树(废话)，所以可以分析它的结点，和枝干数量，这里枝干数量永远是8。假设原目标(点云)被一个大立方体包含，八叉树的作用就是细分该大立方体，每个结点对应一个立方体空间(这里类似于四叉树)，八叉树的结点分为三类：
灰色结点：它对应的立方体部分被目标占据(非叶结点)
白色结点：它对应的立方体没有被目标占据(叶结点)
黑色结点：它对应的立方体完全被目标占据(叶结点)
对于非叶结点，数据结构以八元数法进行区分，分解为更小的子区块，每个区块有结点容量，当结点达到最大容量时结点停止分裂。
八叉树的存储结构
八叉树的存储结构一般分为三种：规则八叉树、线性八叉树和一对八式
规则八叉树，有九个字段，八个子叶结点，一个表征该结点灰白黑的结点，这种表示方式处于贮存空间考量，一般不使用。
线性八叉树，将八叉树转化为线性表，采用内存紧凑的方式进行表示。
一对八表示，使用指针表示，好处是顺序可以随机
八叉树的主要优缺点
优点，使用八叉树可以快速进行三维目标的集合运算，如交、并、补、差等，亦可快速进行最邻近区域或点的搜索。
缺点，存储空间消耗。
八叉树实现
虽然PCL中封装了八叉树OcTree类，但是我们也有不得不自己写的情况，下面代买是自己摘抄的(自己当然还是用PCL了)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include
usingnamespacestd;
//定义八叉树节点类
template
structOctreeNode
{
Tdata;//节点数据
Txmin,xmax;//节点坐标，即六面体个顶点的坐标
Tymin,ymax;
Tzmin,zmax;
OctreeNode*top_left_front,*top_left_back;//该节点的个子结点
OctreeNode*top_right_front,*top_right_back;
OctreeNode*bottom_left_front,*bottom_left_back;
OctreeNode*bottom_right_front,*bottom_right_back;
OctreeNode//节点类
(TnodeValue=T(),
TxminValue=T(),TxmaxValue=T(),
TyminValue=T(),TymaxValue=T(),
TzminValue=T(),TzmaxValue=T(),
OctreeNode*top_left_front_Node=NULL,
OctreeNode*top_left_back_Node=NULL,
OctreeNode*top_right_front_Node=NULL,
OctreeNode*top_right_back_Node=NULL,
OctreeNode*bottom_left_front_Node=NULL,
OctreeNode*bottom_left_back_Node=NULL,
OctreeNode*bottom_right_front_Node=NULL,
OctreeNode*bottom_right_back_Node=NULL)
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
top_left_front(top_left_front_Node),
top_left_back(top_left_back_Node),
top_right_front(top_right_front_Node),
top_right_back(top_right_back_Node),
bottom_left_front(bottom_left_front_Node),
bottom_left_back(bottom_left_back_Node),
bottom_right_front(bottom_right_front_Node),
bottom_right_back(bottom_right_back_Node){}
};
//创建八叉树
template
voidcreateOctree(OctreeNode*&root,intmaxdepth,doublexmin,doublexmax,doubleymin,doubleymax,doublezmin,doublezmax)
{
//cout<
maxdepth=maxdepth-1;//每递归一次就将最大递归深度-1
if(maxdepth>=0)
{
root=newOctreeNode();
cout<
//root->data =9;//为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为9。
cin>>root->data;//为节点赋值
root->xmin=xmin;//为节点坐标赋值
root->xmax=xmax;
root->ymin=ymin;
root->ymax=ymax;
root->zmin=zmin;
root->zmax=zmax;
doublexm=(xmax-xmin)/2;//计算节点个维度上的半边长
doubleym=(ymax-ymin)/2;
doublezm=(ymax-ymin)/2;
//递归创建子树，根据每一个节点所处(是几号节点)的位置决定其子结点的坐标。
createOctree(root->top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root->top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root->top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root->top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root->bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root->bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);
createOctree(root->bottom_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root->bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);
}
}
inti=1;
//先序遍历八叉树
template
voidpreOrder(OctreeNode*&p)
{
if(p)
{
cout<data<
cout
cout
cout
i+=1;
cout<
preOrder(p->top_left_front);
preOrder(p->top_left_back);
preOrder(p->top_right_front);
preOrder(p->top_right_back);
preOrder(p->bottom_left_front);
preOrder(p->bottom_left_back);
preOrder(p->bottom_right_front);
preOrder(p->bottom_right_back);
cout<
}
}
//求八叉树的深度
template
intdepth(OctreeNode*&p)
{
if(p==NULL)
return-1;
inth=depth(p->top_left_front);
returnh+1;
}
//计算单位长度，为查找点做准备
intcal(intnum)
{
intresult=1;
if(1==num)
result=1;
else
{
for(inti=1;i
result=2*result;
}
returnresult;
}
//查找点
intmaxdepth=0;
inttimes=0;
staticdoublexmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;
inttmaxdepth=0;
doubletxm=1,tym=1,tzm=1;
template
voidfind(OctreeNode*&p,doublex,doubley,doublez)
{
doublexm=(p->xmax-p->xmin)/2;
doubleym=(p->ymax-p->ymin)/2;
doublezm=(p->ymax-p->ymin)/2;
times++;
if(x>xmax||xymax||yzmax||z
{
cout<
return;
}
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)
{
cout<
cout
cout
cout
cout<
cout<
}
elseif(xxmax-xm)&&yymax-ym)&&zzmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->bottom_left_back,x,y,z);
}
elseif(xxmax-xm)&&yymax-ym)&&z>(p->zmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->top_left_back,x,y,z);
}
elseif(x>(p->xmax-xm)&&yymax-ym)&&zzmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->bottom_right_back,x,y,z);
}
elseif(x>(p->xmax-xm)&&yymax-ym)&&z>(p->zmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->top_right_back,x,y,z);
}
elseif(xxmax-xm)&&y>(p->ymax-ym)&&zzmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->bottom_left_front,x,y,z);
}
elseif(xxmax-xm)&&y>(p->ymax-ym)&&z>(p->zmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->top_left_front,x,y,z);
}
elseif(x>(p->xmax-xm)&&y>(p->ymax-ym)&&zzmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->bottom_right_front,x,y,z);
}
elseif(x>(p->xmax-xm)&&y>(p->ymax-ym)&&z>(p->zmax-zm))
{
cout<
cout
cout
cout
cout<
find(p->top_right_front,x,y,z);
}
}
//main函数
intmain()
{
OctreeNode*rootNode=NULL;
intchoiced=0;
while(true)
{
system(“cls”);
cout<
cout<
cout<
cout<
cin>>choiced;
if(choiced==0)
return0;
elseif(choiced==1)
{
system(“cls”);
cout<
cin>>maxdepth;
cout<
cin>>xmin>>xmax>>ymin>>ymax>>zmin>>zmax;
if(maxdepth>=0||xmax>xmin||ymax>ymin||zmax>zmin||xmin>0||ymin>0||zmin>0)
{
tmaxdepth=cal(maxdepth);
txm=(xmax-xmin)/tmaxdepth;
tym=(ymax-ymin)/tmaxdepth;
tzm=(zmax-zmin)/tmaxdepth;
createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
}
else
{
cout<
return0;
}
}
elseif(choiced==2)
{
system(“cls”);
cout<
i=1;
preOrder(rootNode);
cout<
system(“pause”);
}
elseif(choiced==3)
{
system(“cls”);
intdep=depth(rootNode);
cout<
system(“pause”);
}
elseif(choiced==4)
{
system(“cls”);
cout<
doublex,y,z;
cin>>x>>y>>z;
times=0;
cout<
find(rootNode,x,y,z);
system(“pause”);
}
else
{
system(“cls”);
cout<
system(“pause”);
}
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/205992.html原文链接：https://javaforall.net
