叉树Octree原理及简单实现（C++版）

1、对Octree的描述

Octree的定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8以外的数目。那么，这要用来做什么？想象一个立方体，我们最少可以切成多少个相同等分的小立方体？答案就是8个。再想象我们有一个房间，房间里某个角落藏着一枚金币，我们想很快的把金币找出来，聪明的你会怎么做？我们可以把房间当成一个立方体，先切成八个小立方体，然后排除掉没有放任何东西的小立方体，再把有可能藏金币的小立方体继续切八等份….如此下去，平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此，Octree就是用在3D空间中的场景管理，可以很快地知道物体在3D场景中的位置，或侦测与其它物体是否有碰撞以及是否在可视范围内。

2、实现Octree的原理

(1). 设定最大递归深度

(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体

(3). 依序将单位元元素丢入能被包含且没有子节点的立方体

(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体

(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。

(6). 重复3，直到达到最大递归深度。
3、Octree的存贮结构

本例中Octree的存贮结构用一个有（若干+八）个字段的记录来表示树中的每个结点。其中若干字段用来描述该结点的特性(本例中的特性为：节点的值和节点坐标)，其余的八个字段用来作为存放指向其八个子结点的指针。此外，还有线性存储和1托8式存储。

4、BSP Tree和Octree对比

a) BSP Tree将场景分割为1个面，而Octree分割为3个面。

b) BSP Tree每个节点最多有2个子结点，而Octree最多有8个子结点

因此BSP Tree可以用在不论几唯的场景中，而Octree则常用于三维场景

5、本例实现Octree的若干关键技术及截图

A、主界面：

Main函数中使用while(true)产生类似Trinigy引擎中的渲染循环效果，等待用户输入操作。通过IF判断用户的输入并进行相应的操作。

[Copy to clipboard][-]View Code CPP

1
2
3
4
5
6
7
8
9
10
11



cin>>choiced;
while(true)
{
if(choiced == 0)
return 0;
else if(choiced == 1)
{
…………
}
…………
}

B、创建八叉树界面，需要用户输入递归次数和外包盒在三维场景中的坐标

本例使用3层深度，外包盒坐标为（1,100,1,100,1,100）

[Copy to clipboard][-]View Code CPP

1
2
3
4
5
6
7
8
9
10
11
12
13



template<class T>
struct OctreeNode
{
T data; //节点数据
T xmin,xmax; //节点坐标，即六面体个顶点的坐标
T ymin,ymax;
T zmin,zmax;
OctreeNode <T> *top_left_front,*top_left_back; //该节点的8个子结点,即个子六面体
OctreeNode <T> *top_right_front,*top_right_back;
OctreeNode <T> *bottom_left_front,*bottom_left_back;
OctreeNode <T> *bottom_right_front,*bottom_right_back;
…………
};

树的结构图：

C、创建成功后先序遍历此八叉树。

[Copy to clipboard][-]View Code CPP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19



void createOctree(OctreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth>=0)
{
root=new OctreeNode<T>();
root->xmin=xmin; //为节点坐标赋值
root->xmax=xmax;
………………
double xm=(xmax-xmin)/2;
double ym=(ymax-ymin)/2;
double zm=(ymax-ymin)/2; //计算节点3个维度上的半边长

//递归创建子树，根据每一个节点所处（是几号节点）的位置决定其子结点的坐标。
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);
……………… //8个子结点
}
}

共产生了73个节点，由于比较多，没有截出全部结果。

D、查看此树的深度

即查找1号节点的个数。

[Copy to clipboard][-]View Code CPP

1
2
3
4
5
6
7
8
9
10
11
12
13
14



int i=1;
template <class T>
void preOrder( OctreeNode<T> * & p)
{
if(p)
{ cout<<i<<".当前节点的值为："<<p->data<<"\n坐标为：";
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
…………
i+=1;
preOrder(p->top_left_front);
preOrder(p->top_left_back);
………………
}
}

E、查找点，需要用户输入坐标，本例使用坐标（80，80，80）

如果用户输入的点在场景外，则提示没有找到。如（200，2，200）

根据用户定义的最大递归深度和场景的坐标，计算一下该场景被分割后的最小6面体各边的边长，然后判断用户输入的坐标是在当前节点的哪一个子结点中并循环搜索，直到达到叶子节点。（代码较多，详情请见下面的源代码）

6、源代码

八叉树节点类的定义：

[Copy to clipboard][-]View Code CPP

1
2
3
4
5
6
7
8



template<class T>
int depth(OctreeNode<T> *& p)
{
if(p == NULL)
return -1;
int h = depth(p->top_left_front);
return h+1;
}

创建节点的函数：

/*
Author : 张聪
Date : 2008/05/01
Filename : octree.cpp
Platform : VC++ 2005

八叉树的实现
功能：
1、创建八叉树。
此八叉树为满树，即所有节点/叶子全部创建。
用户可以自定义此八叉树的深度和所处的三维场景中的位置。
注a：由于创建树时为满树创建，故层数太大时创建时间可能会比较久，请耐心等待。
注b：创建顺序为(1)上层左前节点-(2)上层右前节点-(3)上层右前节点-(4)上层右后节点
-(5)下层左前节点-(6)下层右前节点-(7)下层右前节点-(8)下层右后节点-(1)-(2)……
2、先序遍历八叉树。
八叉树创建成功后用户可调用此子模块查看此八叉树，会显示每个结点的编号，值和在场景中的坐标。
3、查看八叉树的深度。
4、在场景中查找点。
用户首先输入要查找的坐标。
如果该点位于场景外则提示用户并返回，否则在场景中递归查找该点。
找到后输出该点所处的子结点的坐标和递归次数。
*/

#include <iostream>

using namespace std;

//定义八叉树节点类
template<class T>
struct OctreeNode
{
T data; //节点数据
T xmin,xmax; //节点坐标，即六面体个顶点的坐标
T ymin,ymax;
T zmin,zmax;
OctreeNode <T> *top_left_front,*top_left_back; //该节点的个子结点,即个子六面体
OctreeNode <T> *top_right_front,*top_right_back;
OctreeNode <T> *bottom_left_front,*bottom_left_back;
OctreeNode <T> *bottom_right_front,*bottom_right_back;

OctreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
OctreeNode<T>* top_left_front_Node = NULL,
OctreeNode<T>* top_left_back_Node = NULL,
OctreeNode<T>* top_right_front_Node = NULL,
OctreeNode<T>* top_right_back_Node = NULL,
OctreeNode<T>* bottom_left_front_Node = NULL,
OctreeNode<T>* bottom_left_back_Node = NULL,
OctreeNode<T>* bottom_right_front_Node = NULL,
OctreeNode<T>* 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 <class T>
void createOctree(OctreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
cout<<"处理中，请稍候……"<<endl;
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth>=0)
{
root=new OctreeNode<T>();
root->data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。
root->xmin=xmin; //为节点坐标赋值
root->xmax=xmax;
root->ymin=ymin;
root->ymax=ymax;
root->zmin=zmin;
root->zmax=zmax;
double xm=(xmax-xmin)/2;//计算节点个维度上的半边长
double ym=(ymax-ymin)/2;
double zm=(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);
}

}

int i=1;
//先序遍历八叉树
template <class T>
void preOrder( OctreeNode<T> * & p)
{
if(p)
{
cout<<i<<".当前节点的值为："<<p->data<<"\n坐标为：";
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
i+=1;
cout<<endl;
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<<endl;
}
}

//求八叉树的深度
template<class T>
int depth(OctreeNode<T> *& p)
{
if(p == NULL)
return -1;
int h = depth(p->top_left_front);
return h+1;
}

//计算单位长度，为查找点做准备
int cal(int num)
{
int result=1;
if(1==num)
result=1;
else
{
for(int i=1;i<num;i++)
result=2*result;
}
return result;
}

//查找点
int maxdepth=0;
int times=0;
static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;

int tmaxdepth=0;
double txm=1,tym=1,tzm=1;
template<class T>
void find(OctreeNode<T> *& p,double x,double y,double z)
{
double xm=(p->xmax-p->xmin)/2;
double ym=(p->ymax-p->ymin)/2;
double zm=(p->ymax-p->ymin)/2;

times++;

if(x>xmax || x<xmin || y>ymax || y<ymin || z>zmax || z<zmin)
{
cout<<"该点不在场景中！"<<endl;
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<<endl<<"找到该点！"<<"该点位于"<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<"节点内！"<<endl;
cout<<"共经过"<<times<<"次递归！"<<endl;
}
else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_left_back,x,y,z);
}
else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_left_back,x,y,z);
}
else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_right_back,x,y,z);
}
else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_right_back,x,y,z);
}
else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_left_front,x,y,z);
}
else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_left_front,x,y,z);
}
else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_right_front,x,y,z);
}
else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_right_front,x,y,z);
}

}

//main函数
int main ()
{
OctreeNode<double> * rootNode = NULL;
int choiced = 0;
while(true)
{
system("cls");
cout<<"请选择操作：\n";
cout<<"1.创建八叉树 2.先序遍历八叉树\n";
cout<<"3.查看树深度 4.查找节点 \n";
cout<<"0.退出\n\n";
cin>>choiced;
if(choiced == 0)
return 0;
else if(choiced == 1)
{
system("cls");
cout<<"请输入最大递归深度："<<endl;
cin>>maxdepth;
cout<<"请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax"<<endl;
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<<"输入错误！";
return 0;
}
}
else if(choiced == 2)
{
system("cls");
cout<<"先序遍历八叉树结果：\n";
i=1;
preOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 3)
{
system("cls");
int dep = depth(rootNode);
cout<<"此八叉树的深度为"<<dep+1<<endl;
system("pause");
}
else if(choiced == 4)
{
system("cls");
cout<<"请输入您希望查找的点的坐标，顺序如下：x,y,z\n";
double x,y,z;
cin>>x>>y>>z;
times=0;
cout<<endl<<"开始搜寻该点……"<<endl;
find(rootNode,x,y,z);
system("pause");
}
else
{
system("cls");
cout<<"\n\n错误选择！\n";
system("pause");
}
}
}