三维空间建模方法之Octree模型的生成算法

    什么是Octree模型？

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

    八叉树是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，将八个子节点所表示的体积元素加在一起就等于父节点的体积。

     Octree模型主要有两种生成算法，一种是基于三维阵列的生成算法，另外一种是基于表面填充的生成算法。下面是简单的介绍：

     1、基于三维阵列的生成算法

     三维阵列是对三维空间的一种最简单、最规则的空间分割方式，缺点是只能作为一种过渡表示，然后根据需要转换为其他模型，如Octree模型。

     2、基于表面填充的生成算法

      基于表面填充的Octree生成算法是平面域上线性四叉树生成算法的三维扩展。