3422人阅读
八叉树-Octree（19）
如何很好地表示出包含着成千上万物体的复杂场景，是设计系统必须要考虑的。这也是场景管理需要做得，给场景提供良好的层次关系，以便更好地进行筛选(Culling)和隐藏面消除(Hidden surface removal)。场景管理涉及到可视性处理(Visibility processing)和碰撞检测(Collision detection)，系统需要判断场景的哪些部分在视见约束体之内，另外如果两个物体有碰撞关系，则需要计算碰撞点的值。为了达到游戏中的实时效果，传统的技术不可能适用，因为场景己经非常复杂，如果只采用Z缓冲的方法进行可见性处理是不现实的。目前己经有了将场景分层的方法，可以把辅助数据结构应用于场景中，先把场景分区，再分物体，甚至一直分割到多边形。如在室内场景管理中有两个经常用到的层次体系:BSP(Binary Space Partitioning)树，这是八叉树的推广，和包围体树(Boundingvolume tree)。前者用于加速剔除，而后者主要用于碰撞检测。本节简单讨论如何使用层次体系进行更加高效的筛选以及可以采用什么样的数据结构来组织场景。1.2&场景的组织和管理场景的组织结构是渲染系统最基础和最重要的部分，也是一个实现的难点。它的决定会决定很多后续的工作，如碰撞检测，消隐，阴影等。首先要涉及到的概念是空间细分，空间细分考虑整个物体空间并且根据物体的空间占有(Object occupancy)对空间中的每一个点进行分类。可以把世界空间中的物体细分为立方体素(voxel)，再对体素进行分类。八叉树(octree)是一种描述三维空间的树状数据结构，它可以描述一个三维场景内物体的分布情况，并简单地将体素安排在层次结构中。因此场景管理可以在预处理的时候建立一棵树，这里可以忽略物体的表示方法，而把焦点集中在场景的划分上。在树建立起来之后，通过实时遍历这棵树来发现是否有两个物体占据了同一个空间而发生冲突，或者一个物体的空间是否不在视见约束体之内。这样，所有筛选等操作都可以简化为对树的遍历，这是一个线形时间的操作。另一种表示场景的数据结构是BSP树，它被广泛应用于室内场景的处理中，它使用一个分离面(splitting plane)对每一层一分为二，从而实现对空间的划分，其中用于分割的平面可以出现在任何方位。BSP的想法最早在Fuchs(1980)中被提出，起初的目的是为了解决实时地消除隐藏面。BSP可以说是八叉树的一般化。前人在这方面已经做了很多有效的工作，Fuchs首次将BSP技术中剖分平面的定侧性质应用于多边形场景的剖分，建立起空间二叉树结构.该二叉树的每一结点表示一个子空间及空间内所包含的多边形。在每一结点空间中，选取其中一平面作为剖分平面，将该空间继续剖分成正负两子空间，分别作为该结点的两个子结点，其中与剖分平面有交的多边形被分割成两个多边形，分别归入相应的子空间中。上述过程是一个递归过程，直至每一子空间仅包含一个多边形为止。与八叉树剖分相比，BSP树具有内存耗费小，剖分方式灵活，产生的无效区域较小的优点;且对大部分场景来说，BSP树较八叉树更为平衡。另外，由于是二分空间，因此方向性很强，在判断上要比八叉树容易，既可以代替Z-Buffer解决遮挡问题，因为BSP是可以确定物体的绘制顺序的，按照这个顺序就可以保证没有Z-Buffer也能够显示正确，还可以方便地执行碰撞检测。1、BSP Tree（Binary space partitioning）原理首先，将整个场景包围在一个AABB（外包盒）中，然后以递归形式将此外包盒分为若干比较小的盒子。通常是选取盒子的一个轴，生成与之垂直的平面，将其分为两个小盒子。一般是将盒子分为完全相同的两个部分。与分割平面相交的物体，或存储在此层次上，成为两个子集中的一员；或被这个平面分割成两个不同的物体。重复这个平面分割过程，就可以对每个AABB进行递归细分，直到满足某个标准。通常这个标准是用户定义的树的最大深度，或者是盒子内所包含的集合图元数量低于用户定义的某个值，或是到达叶子节点（全部节点都为凸包–最小凸多边形）。简单说来，这种思想就是以平面来递归分割场景的。场景中会有许多物体，我们以每个物体的每个Polygon当成一个平面，而每个平面会有正反两个面，就可把场景分两部分，先从第一个平面开始分，再从这分出的两部分各别再以同样方式细分……如此进行，就可把场景建构出一颗二叉树。将此思想简化到二维平面，就如下图所示，而在三维场景中的构建方式是与之类似的。（注：该图取自en.wikipedia.org）1、A 是树的根节点也是整个多边形面2、A 被分为B和C3、B 被分为D和E.4、D 被分为F和G，其中G是凸包（最小凸多边形），因此成为了该树的叶子节点，不可再分2、BSP Tree的存贮结构本例中BSP Tree的存贮结构用一个有（若干+2）个字段的记录来表示树中的每个结点。其中若干字段用来描述该结点的特性(本例中的特性为：节点的值和节点坐标)，其余的2个字段用来作为存放指向其2个子结点的指针。3、本例实现BSP Tree的若干关键技术及截图A、主界面：Main函数中使用while(true)产生类似Trinigy引擎中的渲染循环效果，等待用户输入操作。通过IF判断用户的输入并进行相应的操作。cin&&while(true){&&&&&&& if(choiced == 0)&& return 0;&&&&&&& else if(choiced == 1)&&&&&&& {&&&&&&&&&&&& …………&&&&&&& }…………}B、创建BSP Tree界面，需要用户输入递归次数和外包盒在三维场景中的坐标本例使用3层深度，外包盒坐标为（1,100,1,100,1,100）//定义BSP树节点类struct BSPTreeNode{&&& T //节点数据T xmin, //节点坐标，即六面体各顶点的坐标T ymin,T zmin,&&& BSPTreeNode &T& *left,* //该节点的个子结点,即左右两个子六面体节点}//创建BSP树int scale = -1;//切割平面属性初始化，根据切割平面属性决定当前切割的面是与X轴垂直的平面，还是Y轴的或Z轴的template &class T&void createBSPTree(BSPTreeNode&T& * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax){maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1scale++; //每递归一次就将切割平面属性+1，使下一次切割的平面更改一下if(3==scale) scale=0; //如果切割属性达到峰值，则初始化if(maxdepth&=0){root=new BSPTreeNode&T&();root-&xmin= //为节点坐标赋值…………double xm=(xmax-xmin)/2;double ym=(ymax-ymin)/2;double zm=(zmax-zmin)/2; //计算节点3个维度上的半边长//递归创建子树。if(0==scale) //切割属性为0，沿与X轴垂直的平面切割{//根据当前切割平面的属性决定其子结点的坐标&& createBSPTree(root-&left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);&& createBSPTree(root-&right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);}else if(1==scale) //切割属性为1，沿与Y轴垂直的平面切割…………else if(2==scale) //切割属性为2，沿与Z轴垂直的平面切割…………}}通过以上的方式循环切割当前节点产生BSP树，切割面的顺序为：(a) 沿与X轴垂直的平面切割(b) 沿与Y轴垂直的平面切割(c) 沿与Z轴垂直的平面切割依次循环C、创建成功后先序遍历此BSP Tree。int i=1;template &class T&void preOrder( BSPTreeNode&T& * & p){&&& if(p)&&& {cout&&i&&&.当前节点的值为：&&&p-&data&&&\n坐标为：&;cout&&& xmin: &&&p-&xmin&&& xmax: &&&p-&…………i+=1;&&&&&&& preOrder(p-&left);&&&&&&& preOrder(p-&right);&&& }}共7个节点D、查看此树的深度即查找左节点的个数template&class T&int depth(BSPTreeNode&T& *& p){&&& if(p == NULL) return -1;&&& int h = depth(p-&left);&&& return h+1;}4、BSP Tree和Octree对比a) BSP Tree使用1个面分割场景，而Octree使用3个面分割。b) BSP Tree每个节点有2个子结点，而Octree有8个子结点因此BSP Tree可以用在不论几维的场景中，都没有问题，而Octree则常用于三维场景（拓展到N维中就会十分复杂了）。///////////////////////////////////////////////////////////////////////////////////////////////////*Author : 张聪Date : Filename : bsptree.cppPlatform : VC++ 2005BSP树的实现功能：1、创建BSP树。此BSP树为满树，即所有节点/叶子全部创建。用户可以自定义此BSP树的深度和所处的三维场景中的位置。注a：由于创建树时为满树创建，故层数太大时创建时间可能会比较久，请耐心等待。注b：创建顺序为(1)切割平面左边的节点-(2)切割平面右边的节点-(1)-(2)……2、先序遍历BSP树。BSP树创建成功后用户可调用此子模块查看此BSP树，会显示每个结点的编号，值和在场景中的坐标。3、查看BSP树的深度。*/#include &iostream&//定义BSP树节点类template&class T&struct BSPTreeNode{T //节点数据T xmin, //节点坐标，即六面体各顶点的坐标T ymin,T zmin,BSPTreeNode &T& *left,* //该节点的个子结点,即左右两个子六面体节点BSPTreeNode //节点类(T nodeValue = T(),T xminValue = T(),T xmaxValue = T(),T yminValue = T(),T ymaxValue = T(),T zminValue = T(),T zmaxValue = T(),BSPTreeNode&T&* left_Node = NULL,BSPTreeNode&T&* right_Node = NULL ):data(nodeValue),xmin(xminValue),xmax(xmaxValue),ymin(yminValue),ymax(ymaxValue),zmin(zminValue),zmax(zmaxValue),left(left_Node),right(right_Node){}};//创建BSP树int scale = -1; //切割平面属性初始化，根据切割平面属性决定当前切割的面是与X轴垂直的平面，还是Y轴的或Z轴的template &class T&void createBSPTree(BSPTreeNode&T& * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax){cout&&&处理中，请稍候……&&&maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1scale++; //每递归一次就将切割平面属性+1，使下一次切割的平面更改一下if(3==scale) scale=0; //如果切割属性达到峰值，则初始化if(maxdepth&=0){root=new BSPTreeNode&T&();root-&data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现BSP树功能，简单赋值为。root-&xmin= //为节点坐标赋值root-&xmax=root-&ymin=root-&ymax=root-&zmin=root-&zmax=double xm=(xmax-xmin)/2;//计算节点个维度上的半边长double ym=(ymax-ymin)/2;double zm=(zmax-zmin)/2;//递归创建子树if(0==scale) //切割属性为，沿与X轴垂直的平面切割{createBSPTree(root-&left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);//根据当前切割平面的属性决定其子结点的坐标createBSPTree(root-&right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);}else if(1==scale) //切割属性为，沿与Y轴垂直的平面切割{createBSPTree(root-&left,maxdepth,xmin,xmax,ymin,ymax-ym,zmin,zmax);//根据当前切割平面的属性决定其子结点的坐标createBSPTree(root-&right,maxdepth,xmin,xmax,ymax-ym,ymax,zmin,zmax);}else if(2==scale) //切割属性为，沿与Z轴垂直的平面切割{createBSPTree(root-&left,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax-zm);//根据当前切割平面的属性决定其子结点的坐标createBSPTree(root-&right,maxdepth,xmin,xmax,ymin,ymax,zmax-zm,zmax);}}}int i=1;//先序遍历BSP树template &class T&void preOrder( BSPTreeNode&T& * & p){if(p){cout&&i&&&.当前节点的值为：&&&p-&data&&&\n坐标为：&;cout&&& xmin: &&&p-&xmin&&& xmax: &&&p-&cout&&& ymin: &&&p-&ymin&&& ymax: &&&p-&cout&&& zmin: &&&p-&zmin&&& zmax: &&&p-&i+=1;cout&&preOrder(p-&left);preOrder(p-&right);cout&&}}//求BSP树的深度template&class T&int depth(BSPTreeNode&T& *& p){if(p == NULL)return -1;int h = depth(p-&left);return h+1;}//计算单位长度，为查找点做准备int cal(int num){int result=1;if(1==num)result=1;else{for(int i=1;i&i++)result=2*}}//main函数int main (){BSPTreeNode&double& * rootNode = NULL;int choiced = 0;int maxdepth=0;while(true){double xmin,xmax,ymin,ymax,zmin,system(&cls&);cout&&&请选择操作：\n&;cout&&&1.创建BSP树 2.先序遍历BSP树\n&;cout&&&3.查看树深度0.退出 \n\n&;cin&&if(choiced == 0)return 0;else if(choiced == 1){system(&cls&);cout&&&请输入最大递归深度：&&&cin&&cout&&&请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax&&&cin&&xmin&&xmax&&ymin&&ymax&&zmin&&if(maxdepth&=0 || xmax&xmin || ymax&ymin || zmax&zmin || xmin&0 || ymin&0 ||zmin&0){scale = -1; //切割平面属性初始化createBSPTree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);}else{cout&&&输入错误！&;return 0;}}else if(choiced == 2){system(&cls&);cout&&&先序遍历BSP树结果：\n&;i=1;preOrder(rootNode);cout&&system(&pause&);}else if(choiced == 3){system(&cls&);int dep = depth(rootNode);cout&&&此BSP树的深度为&&&dep+1&&system(&pause&);}else{system(&cls&);cout&&&\n\n错误选择！\n&;system(&pause&);}}}
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：8262256次
积分：94333
积分：94333
排名：第8名
原创：1132篇
转载：2963篇
评论：1354条
(2)(4)(10)(2)(3)(13)(13)(4)(9)(62)(16)(8)(23)(9)(37)(73)(34)(31)(120)(128)(183)(23)(69)(75)(1)(171)(33)(148)(168)(145)(27)(144)(139)(208)(61)(59)(10)(10)(32)(2)(7)(34)(24)(9)(39)(25)(32)(46)(20)(44)(8)(21)(43)(49)(100)(113)(136)(35)(55)(15)(29)(41)(15)(50)(17)(20)(182)(206)(43)(27)(19)(17)(13)(1)(40)(5)(3)(4)(21)(71)(73)(19)(2)(2)(1)(1)(1)(6)(3)【转】3D游戏中的场景管理（八叉树和BSP树简介）
如何很好地表示出包含着成千上万物体的复杂场景，是设计系统必须要考虑的。这也是场景管理需要做得，给场景提供良好的层次关系，以便更好地进行筛选(Culling)和隐藏面消除(Hidden
surface removal)。场景管理涉及到可视性处理(Visibility
processing)和碰撞检测(Collision
detection)，系统需要判断场景的哪些部分在视见约束体之内，另外如果两个物体有碰撞关系，则需要计算碰撞点的值。
可见性剔除
为了达到游戏中的实时效果，传统的技术不可能适用，因为场景己经非常复杂，如果只采用Z缓冲的方法进行可见性处理是不现实的。目前己经有了将场景分层的方法，可以把辅助数据结构应用于场景中，先把场景分区，再分物体，甚至一直分割到多边形。如在室内场景管理中有两个经常用到的层次体系:BSP(Binary
Partitioning)树，这是八叉树的推广，和包围体树(Boundingvolume
tree)。前者用于加速剔除，而后者主要用于碰撞检测。
本节简单讨论如何使用层次体系进行更加高效的筛选以及可以采用什么样的数据结构来组织场景。
1.2 场景的组织和管理
场景的组织结构是渲染系统最基础和最重要的部分，也是一个实现的难点。它的决定会决定很多后续的工作，如碰撞检测，消隐，阴影等。
首先要涉及到的概念是空间细分，空间细分考虑整个物体空间并且根据物体的空间占有(Object
occupancy)对空间中的每一个点进行分类。可以把世界空间中的物体细分为立方体素(voxel)，再对体素进行分类。八叉树(octree)是一种描述三维空间的树状数据结构，它可以描述一个三维场景内物体的分布情况，并简单地将体素安排在层次结构中。
因此场景管理可以在预处理的时候建立一棵树，这里可以忽略物体的表示方法，而把焦点集中在场景的划分上。在树建立起来之后，通过实时遍历这棵树来发现是否有两个物体占据了同一个空间而发生冲突，或者一个物体的空间是否不在视见约束体之内。这样，所有筛选等操作都可以简化为对树的遍历，这是一个线形时间的操作。
另一种表示场景的数据结构是BSP树，它被广泛应用于室内场景的处理中，它使用一个分离面(splitting
plane)对每一层一分为二，从而实现对空间的划分，其中用于分割的平面可以出现在任何方位。BSP的想法最早在Fuchs(1980)中被提出，起初的目的是为了解决实时地消除隐藏面。BSP可以说是八叉树的一般化。前人在这方面已经做了很多有效的工作，Fuchs首次将BSP技术中剖分平面的定侧性质应用于多边形场景的剖分，建立起空间二叉树结构.该二叉树的每一结点表示一个子空间及空间内所包含的多边形。在每一结点空间中，选取其中一平面作为剖分平面，将该空间继续剖分成正负两子空间，分别作为该结点的两个子结点，其中与剖分平面有交的多边形被分割成两个多边形，分别归入相应的子空间中。上述过程是一个递归过程，直至每一子空间仅包含一个多边形为止。
与八叉树剖分相比，BSP树具有内存耗费小，剖分方式灵活，产生的无效区域较小的优点;且对大部分场景来说，BSP树较八叉树更为平衡。
另外，由于是二分空间，因此方向性很强，在判断上要比八叉树容易，既可以代替Z-Buffer解决遮挡问题，因为BSP是可以确定物体的绘制顺序的，按照这个顺序就可以保证没有Z-Buffer也能够显示正确，还可以方便地执行碰撞检测。
Tree（Binary space
partitioning）原理
首先，将整个场景包围在一个AABB（外包盒）中，然后以递归形式将此外包盒分为若干比较小的盒子。通常是选取盒子的一个轴，生成与之垂直的平面，将其分为两个小盒子。一般是将盒子分为完全相同的两个部分。与分割平面相交的物体，或存储在此层次上，成为两个子集中的一员；或被这个平面分割成两个不同的物体。重复这个平面分割过程，就可以对每个AABB进行递归细分，直到满足某个标准。通常这个标准是用户定义的树的最大深度，或者是盒子内所包含的集合图元数量低于用户定义的某个值，或是到达叶子节点（全部节点都为凸包&最小凸多边形）。
简单说来，这种思想就是以平面来递归分割场景的。场景中会有许多物体，我们以每个物体的每个Polygon当成一个平面，而每个平面会有正反两个面，就可把场景分两部分，先从第一个平面开始分，再从这分出的两部分各别再以同样方式细分……如此进行，就可把场景建构出一颗二叉树。
将此思想简化到二维平面，就如下图所示，而在三维场景中的构建方式是与之类似的。
（注：该图取自en.wikipedia.org）
是树的根节点也是整个多边形面
被分为B和C
被分为D和E.
被分为F和G，其中G是凸包（最小凸多边形），因此成为了该树的叶子节点，不可再分
Tree的存贮结构
Tree的存贮结构用一个有（若干+2）个字段的记录来表示树中的每个结点。其中若干字段用来描述该结点的特性(本例中的特性为：节点的值和节点坐标)，其余的2个字段用来作为存放指向其2个子结点的指针。
3、本例实现BSP
Tree的若干关键技术及截图
A、主界面：
Main函数中使用while(true)产生类似Trinigy引擎中的渲染循环效果，等待用户输入操作。通过IF判断用户的输入并进行相应的操作。
while(true)
if(choiced == 0)
else if(choiced == 1)
B、创建BSP Tree界面，需要用户输入递归次数和外包盒在三维场景中的坐标
本例使用3层深度，外包盒坐标为（1,100,1,100,1,100）
//定义BSP树节点类
struct BSPTreeNode
T //节点数据
T xmin, //节点坐标，即六面体各顶点的坐标
BSPTreeNode &T& *left,* //该节点的个子结点,即左右两个子六面体节点
//创建BSP树
int scale = -1;
//切割平面属性初始化，根据切割平面属性决定当前切割的面是与X轴垂直的平面，还是Y轴的或Z轴的
template &class T&
void createBSPTree(BSPTreeNode&T& * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
scale++; //每递归一次就将切割平面属性+1，使下一次切割的平面更改一下
if(3==scale) scale=0; //如果切割属性达到峰值，则初始化
if(maxdepth&=0)
root=new BSPTreeNode&T&();
root-&xmin= //为节点坐标赋值
double xm=(xmax-xmin)/2;
double ym=(ymax-ymin)/2;
double zm=(zmax-zmin)/2; //计算节点3个维度上的半边长
//递归创建子树。
if(0==scale) //切割属性为0，沿与X轴垂直的平面切割
//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root-&left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);
createBSPTree(root-&right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);
else if(1==scale) //切割属性为1，沿与Y轴垂直的平面切割
else if(2==scale) //切割属性为2，沿与Z轴垂直的平面切割
通过以上的方式循环切割当前节点产生BSP树，切割面的顺序为：
沿与X轴垂直的平面切割
沿与Y轴垂直的平面切割
沿与Z轴垂直的平面切割
C、创建成功后先序遍历此BSP Tree。
template &class T&
void preOrder( BSPTreeNode&T& * & p)
cout&&i&&".当前节点的值为："&&p-&data&&"\n坐标为：";
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
preOrder(p-&left);
preOrder(p-&right);
共7个节点。
D、查看此树的深度
即查找左节点的个数
template&class T&
int depth(BSPTreeNode&T& *& p)
if(p == NULL)
return -1;
int h = depth(p-&left);
return h+1;
Tree和Octree对比
Tree使用1个面分割场景，而Octree使用3个面分割。
Tree每个节点有2个子结点，而Octree有8个子结点
Tree可以用在不论几维的场景中，都没有问题，而Octree则常用于三维场景（拓展到N维中就会十分复杂了）。
#include &iostream&
//定义BSP树节点类
template&class T&
struct BSPTreeNode
T //节点数据
T xmin, //节点坐标，即六面体各顶点的坐标
BSPTreeNode &T& *left,*
//该节点的个子结点,即左右两个子六面体节点
BSPTreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
BSPTreeNode&T&* left_Node = NULL,
BSPTreeNode&T&* right_Node = NULL )
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
left(left_Node),
right(right_Node){}
//创建BSP树
int scale = -1;
//切割平面属性初始化，根据切割平面属性决定当前切割的面是与X轴垂直的平面，还是Y轴的或Z轴的
template &class T&
void createBSPTree(BSPTreeNode&T& * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
cout&&"处理中，请稍候……"&&
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
scale++; //每递归一次就将切割平面属性+1，使下一次切割的平面更改一下
if(3==scale) scale=0; //如果切割属性达到峰值，则初始化
if(maxdepth&=0)
root=new BSPTreeNode&T&();
root-&data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现BSP树功能，简单赋值为。
root-&xmin= //为节点坐标赋值
root-&xmax=
root-&ymin=
root-&ymax=
root-&zmin=
root-&zmax=
double xm=(xmax-xmin)/2;//计算节点个维度上的半边长
double ym=(ymax-ymin)/2;
double zm=(zmax-zmin)/2;
//递归创建子树
if(0==scale) //切割属性为，沿与X轴垂直的平面切割
createBSPTree(root-&left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root-&right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);
else if(1==scale) //切割属性为，沿与Y轴垂直的平面切割
createBSPTree(root-&left,maxdepth,xmin,xmax,ymin,ymax-ym,zmin,zmax);//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root-&right,maxdepth,xmin,xmax,ymax-ym,ymax,zmin,zmax);
else if(2==scale) //切割属性为，沿与Z轴垂直的平面切割
createBSPTree(root-&left,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax-zm);//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root-&right,maxdepth,xmin,xmax,ymin,ymax,zmax-zm,zmax);
//先序遍历BSP树
template &class T&
void preOrder( BSPTreeNode&T& * & p)
cout&&i&&".当前节点的值为："&&p-&data&&"\n坐标为：";
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
preOrder(p-&left);
preOrder(p-&right);
//求BSP树的深度
template&class T&
int depth(BSPTreeNode&T& *& p)
if(p == NULL)
return -1;
int h = depth(p-&left);
return h+1;
//计算单位长度，为查找点做准备
int cal(int num)
int result=1;
if(1==num)
for(int i=1;i&i++)
//main函数
int main ()
BSPTreeNode&double& * rootNode = NULL;
int choiced = 0;
int maxdepth=0;
while(true)
double xmin,xmax,ymin,ymax,zmin,
system("cls");
cout&&"请选择操作：\n";
cout&&"1.创建BSP树 2.先序遍历BSP树\n";
cout&&"3.查看树深度0.退出
if(choiced == 0)
else if(choiced == 1)
system("cls");
cout&&"请输入最大递归深度："&&
cout&&"请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax"&&
cin&&xmin&&xmax&&ymin&&ymax&&zmin&&
if(maxdepth&=0 || xmax&xmin || ymax&ymin || zmax&zmin || xmin&0 || ymin&0 ||zmin&0)
scale = -1;
//切割平面属性初始化
createBSPTree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
cout&&"输入错误！";
else if(choiced == 2)
system("cls");
cout&&"先序遍历BSP树结果：\n";
preOrder(rootNode);
system("pause");
else if(choiced == 3)
system("cls");
int dep = depth(rootNode);
cout&&"此BSP树的深度为"&&dep+1&&
system("pause");
system("cls");
cout&&"\n\n错误选择！\n";
system("pause");
1、对Octree的描述
Octree的定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8以外的数目。那么，这要用来做什么？想象一个立方体，我们最少可以切成多少个相同等分的小立方体？答案就是8个。再想象我们有一个房间，房间里某个角落藏着一枚金币，我们想很快的把金币找出来，聪明的你会怎么做？我们可以把房间当成一个立方体，先切成八个小立方体，然后排除掉没有放任何东西的小立方体，再把有可能藏金币的小立方体继续切八等份….如此下去，平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此，Octree就是用在3D空间中的场景管理，可以很快地知道物体在3D场景中的位置，或侦测与其它物体是否有碰撞以及是否在可视范围内。
2、实现Octree的原理
(1). 设定最大递归深度
(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体
(3). 依序将单位元元素丢入能被包含且没有子节点的立方体
(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体
(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。
(6). 重复3，直到达到最大递归深度。
3、Octree的存贮结构
本例中Octree的存贮结构用一个有（若干+八）个字段的记录来表示树中的每个结点。其中若干字段用来描述该结点的特性(本例中的特性为：节点的值和节点坐标)，其余的八个字段用来作为存放指向其八个子结点的指针。此外，还有线性存储和1托8式存储。
Tree和Octree对比
Tree将场景分割为1个面，而Octree分割为3个面。
Tree每个节点最多有2个子结点，而Octree最多有8个子结点
Tree可以用在不论几唯的场景中，而Octree则常用于三维场景
5、本例实现Octree的若干关键技术及截图
A、主界面：
Main函数中使用while(true)产生类似Trinigy引擎中的渲染循环效果，等待用户输入操作。通过IF判断用户的输入并进行相应的操作。
while(true)
if(choiced == 0)
else if(choiced == 1)
B、创建八叉树界面，需要用户输入递归次数和外包盒在三维场景中的坐标
本例使用3层深度，外包盒坐标为（1,100,1,100,1,100）
template&class T&
struct OctreeNode
T //节点数据
T xmin, //节点坐标，即六面体个顶点的坐标
OctreeNode &T& *top_left_front,*top_left_ //该节点的8个子结点,即个子六面体
OctreeNode &T& *top_right_front,*top_right_
OctreeNode &T& *bottom_left_front,*bottom_left_
OctreeNode &T& *bottom_right_front,*bottom_right_
树的结构图：
C、创建成功后先序遍历此八叉树。
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= //为节点坐标赋值
root-&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号节点的个数。
template &class T&
void preOrder( OctreeNode&T& * & p)
{ cout&&i&&".当前节点的值为："&&p-&data&&"\n坐标为：";
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
preOrder(p-&top_left_front);
preOrder(p-&top_left_back);
………………
E、查找点，需要用户输入坐标，本例使用坐标（80，80，80）
如果用户输入的点在场景外，则提示没有找到。如（200，2，200）
根据用户定义的最大递归深度和场景的坐标，计算一下该场景被分割后的最小6面体各边的边长，然后判断用户输入的坐标是在当前节点的哪一个子结点中并循环搜索，直到达到叶子节点。（代码较多，详情请见下面的源代码）
八叉树节点类的定义：
template&class T&
int depth(OctreeNode&T& *& p)
if(p == NULL)
return -1;
int h = depth(p-&top_left_front);
return h+1;
创建节点的函数：
Author&& : 张聪
Filename : octree.cpp
Platform : VC++ 2005
八叉树的实现
1、创建八叉树。
&& 此八叉树为满树，即所有节点/叶子全部创建。
&& 用户可以自定义此八叉树的深度和所处的三维场景中的位置。
&& 注a：由于创建树时为满树创建，故层数太大时创建时间可能会比较久，请耐心等待。
&& 注b：创建顺序为(1)上层左前节点-(2)上层右前节点-(3)上层右前节点-(4)上层右后节点
-(5)下层左前节点-(6)下层右前节点-(7)下层右前节点-(8)下层右后节点-(1)-(2)……
2、先序遍历八叉树。
&& 八叉树创建成功后用户可调用此子模块查看此八叉树，会显示每个结点的编号，值和在场景中的坐标。
3、查看八叉树的深度。
4、在场景中查找点。
用户首先输入要查找的坐标。
如果该点位于场景外则提示用户并返回，否则在场景中递归查找该点。
找到后输出该点所处的子结点的坐标和递归次数。
#include &iostream&
//定义八叉树节点类
template&class T&
struct OctreeNode
T //节点数据
T xmin, //节点坐标，即六面体个顶点的坐标
OctreeNode &T& *top_left_front,*top_left_ //该节点的个子结点,即个子六面体
OctreeNode &T& *top_right_front,*top_right_
OctreeNode &T& *bottom_left_front,*bottom_left_
OctreeNode &T& *bottom_right_front,*bottom_right_
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&&"处理中，请稍候……"&&
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth&=0)
root=new OctreeNode&T&();
root-&data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。
root-&xmin= //为节点坐标赋值
root-&xmax=
root-&ymin=
root-&ymax=
root-&zmin=
root-&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);
//先序遍历八叉树
template &class T&
void preOrder( OctreeNode&T& * & p)
cout&&i&&".当前节点的值为："&&p-&data&&"\n坐标为：";
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
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);
//求八叉树的深度
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)
for(int i=1;i&i++)
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;
if(x&xmax || x&xmin || y&ymax || y&ymin || z&zmax || z&zmin)
cout&&"该点不在场景中！"&&
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&&"找到该点！"&&"该点位于"&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
cout&&"节点内！"&&
cout&&"共经过"&&times&&"次递归！"&&
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&bottom_left_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&top_left_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&bottom_right_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&top_right_back,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&bottom_left_front,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&top_left_front,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
find(p-&bottom_right_front,x,y,z);
else if(x&(p-&xmax-xm) && y&(p-&ymax-ym) && z&(p-&zmax-zm))
cout&&"当前经过节点坐标："&&
cout&&" xmin: "&&p-&xmin&&" xmax: "&&p-&
cout&&" ymin: "&&p-&ymin&&" ymax: "&&p-&
cout&&" zmin: "&&p-&zmin&&" zmax: "&&p-&
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";
if(choiced == 0)
else if(choiced == 1)
system("cls");
cout&&"请输入最大递归深度："&&
cout&&"请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax"&&
cin&&xmin&&xmax&&ymin&&ymax&&zmin&&
if(maxdepth&=0 || xmax&xmin || ymax&ymin || zmax&zmin || xmin&0 || ymin&0 ||zmin&0)
tmaxdepth=cal(maxdepth);
txm=(xmax-xmin)/
tym=(ymax-ymin)/
tzm=(zmax-zmin)/
createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
cout&&"输入错误！";
else if(choiced == 2)
system("cls");
cout&&"先序遍历八叉树结果：\n";
preOrder(rootNode);
system("pause");
else if(choiced == 3)
system("cls");
int dep = depth(rootNode);
cout&&"此八叉树的深度为"&&dep+1&&
system("pause");
else if(choiced == 4)
system("cls");
cout&&"请输入您希望查找的点的坐标，顺序如下：x,y,z\n";
double x,y,z;
cin&&x&&y&&z;
cout&&endl&&"开始搜寻该点……"&&
find(rootNode,x,y,z);
system("pause");
system("cls");
cout&&"\n\n错误选择！\n";
system("pause");
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。