八叉树三维数据结构及示例程序

八叉树三维数据结构及示例程序(24 页)Good is good, but better carries it.精益求精，善益求善。八叉树三维数据结构（一）基本原理 用八叉树来表示三维形体，并讨论在这种表示下的各种操作及应用是在进入 80 年代后才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。 八叉树的逻辑结构如下： 假设要表示的形体 V 可以放在一个充分大的正方体 C 内，C 的边长为 2 n ，形体 V C ，它的八叉树可以用以下的递归方法来定义： 八叉树的每个节点与 C 的一个子立方体对应，树根与 C 本身相对应，假如 V＝C，那么V 的八叉树仅有树根，假如 V≠C，则将 C 等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为 V 所占据，就要被八等分（图2-5-1），从而对应的节点也就有了八个子节点。这样的递归推断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为 V 占据，或是其大小已是预先定义的体素大小，并且对它与 V 之交作一定的“舍入”，使体素或认为是空白的，或认为是 V 占据的。 如此所生成的八叉树上的节点可分为三类： 灰节点，它对应的立方体部分地为 V 所占据； 白节点，它所对应的立方体中无 V 的内容； 黑节点，它所对应的立方体全为 V 所占据。 后两类又称为叶结点。形体 V 关于 C 的八叉树的逻辑结构是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与 C 相对应，其它节点与C 的某个子立方体相对应。 因为八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。因而，根据不同的存贮方式，八叉树也可以分别称为常规的、线性的、一对八的八叉树等等。 另外，由于这种方法充分利用了形体在空上的相关性，因此，一般来说，它所占用的存贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮，这并不是八叉树的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可以求两个物体的并、交、差等运算)，而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。不仅如此，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡、隐线和隐面的消除等，带来了很大的方便，特别有用。（二）八叉树的存贮结...