如何使用C或C++结构建立八叉树的模型

以下程序摘自互联网，是C++的

如果要用C语言编写，则

（1）使用C结构建立八叉树的模型

1.typedef struct OctreeNode 2.{ 3. int value 4. struct OctreeNode *Up 5. struct OctreeNode *Down 6. struct OctreeNode *Left 7. struct OctreeNode *Right 8. struct OctreeNode *Front 9. struct OctreeNode *Back 10.}OctreeNode

（2）递归添加上下左右前后邻居，我这里只给一面

1.void AddUp(OctreeNode *Me, int v) 2.{ 3. Me->Up = (OctreeNode *)malloc(sizeof (OctreeNode)) 4. Me->Up->vvalue = v 5. Me->Up->Up = NULL 6. Me->Up->Down = Me 7. Me->Up->Front = NULL 8. OctreeMe->Up->Back = NULL 9. Me->Up->Right = NULL 10. Me->Up->Left = NULL 11.}

实现Octree的原理

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

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

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

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

个子立方体

(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止

细分，因为跟据空间分割理论，细分的空间所烂运得到的分配必定较少，若是一样数目，则再怎么切数目

还是一样，会造成无穷切割的情形。

(6). 重复3，直到达到最大递归深度。

#include <iostream.h>

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=1i<numi++)

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")

}

}

}

代码在C-free下测试可用

可以。python是解释型编程语言，可以编程颜色，用python的数值计算库来实现八叉树颜色比较方便简单，敏团所以八叉树颜色可以用python实现。python是一种具纯拿敏有动态语义的做枝、解释型的、面向对象的、通用的、开源的脚本编程语言,主要用于Web和应用程序开发。

Ogre引擎特性

以下文章节译自Gregory Junker所著作的《Pro OGRE 3D Programming》

引擎特性

Ogre几乎拥有了商业如陵3D渲染引擎的全部特性，甚至在某些方面超越了它们。

*全面并同等的支持OpenGL和Direct3D

*全面支持Windows，Linux以及Mac OS X平台

*简单并可扩展的对象框架，能方便的插入到已存在的应用程序框架中

*自动处理渲染状态和空间剪裁

*强大且成熟的材质管理和脚本系统，可以不动一行代码去进行材质维护

*支持所有纹理混合和绑定技术，同时支持对GPU编程技术，支持汇编语言和所有高级语言形式的各种着色语言，其中高级语言包括：Cg，HLSL和GLSL

*支持多种纹理图片格式，包括：PNG，TGA，DDS，TIF，GIF，JPG，同时支持特殊格式的纹理，其中包括：一维纹理（1D），容积纹理(Volumetric textures)，体积纹理（Cubemaps）和压缩的纹理格式如：DXTC

*全面支持渲染到纹理（Render-to-Texture）技术和投影纹理（贴花，Projective Texturing-decals）。

*全面支持材质LoD（细节层次，mipmapping）技术

*优化的二进制模型文件格式，同时支持手动和自动LoD生成

*同时拥有多种从商业或者开源3D模型软件导出到Ogre模型格式和动画格式的插件，其中包括官方以及用户提供的版本。

*全面支对顶点和索引缓存（vertex and index buffers）、顶点声明薯皮（vertex declarations）以及贴图缓存（buffer mappings）

*全面支持骨骼动画和姿态动画（pose动画，顶点动画的一种），每个顶点可以混合任渣手戚意数目的骨骼权重

*支持软件和硬件加速蒙皮

*支持静态几何体批次（static geometry batching）

*支持二次贝塞尔曲面（biquadric Bezier patches）

*给出以插件方式链接不同场景结构的接口，允许你使用适合自己应用程序的场景体系（ 基本的八叉树“octree”场景管理做为一个例子出现在插件中）

*高级可屏蔽场景查询系统（Advanced maskable scene-querying system）

*全面支持多种阴影技术，包括模版阴影（stencil），纹理阴影（texture），叠加阴影（additive），调制阴影（modulative），并且全部支持硬件加速

*高级插件[来源：GameRes.com]方式的粒子系统，可扩展的发射器（emitters），效果器（affectors），渲染器（renderers）（ParticleFX作为插件的例子被包含在工程里面）

*全面支持并且方便使用的天空盒（skyboxes），天空面（skyplanes），以及穹顶（skydomes）

*以精灵效果为基础（sprite-based）并得到渲染优化的公告栏（Billboarding）技术

*以单一队列为基础的渲染管理，允许全面 *** 作渲染执行顺序

*自动管理透明对象

*成熟且可扩展的资源管理和载入系统，文件系统支持的文件包括zip，pk3格式

Ogre 3D渲染引擎的开发团队用了4年时间完善了上面列出的所有功能，但只有到你真正的使用的时候才能展示它所拥有的广泛性和专业性。

---