八叉树背景网格

        八叉树背景网格生成算法（Octree Background Grid Generation Algorithm）是一种用于构建全六面体网格的算法。该算法基于八叉树数据结构，通过递归细分六面体来创建具有不同 Level的网格。由于这些网格的作用是填充满整个计算区域，因此被称为背景网格。

        具体地说，该算法将计算区域标记为一个大的六面体（Level 0），然后按照需求将这个六面体分成一些m*n*k的规则小六面体(Level 1)。这些小立方体被称为八叉树节点。在节点上，可以标记该节点是否需要进行递归细分，每细分一次，结点的Level + 1。越靠近近壁面网格，生成的背景网格越细致，这样可以确保近壁面网格被准确的捕捉到，从而提高计算精度。在实际的情况中，第一次细分（从Level 0到Level 1），m, n, k的值由用户按照需求来指定。而之后的细分，m=n=k=2，也就是说将一个六面体细分为八个小的六面体。

         在实现八叉树背景网格生成算法时，其核心是如何确定每个节点是否需要进行细分。一种常见的方法是使用自适应细分（Adaptive subdivision）策略：        

• 在生成背景网格前，会预先定义一系列的细分区域和细分Level。当某个结点在细分区域中，且该结点的Level数小于给定的细分Level数，就将其细分。

• 在生成背景网格前，会预先定义叶子结点Level的最小和最大值。与近壁面相交的结点的Level数必须在这个区间内。如果小于最小值，就将其细分。如果大于最大值，则给出细分过大的信息，让用户判断是否要继续背景网格的生成。

         自适应细分完成后，会出现相邻两个结点的Level数相差大于1的情况，这是不允许的。因此需要一个调整的过程，这个过程的作用是让相邻的两个结点Level数要么相等，要么相差1。

             左图中，A与C的Level数相差为2。注意左图中的C个数应该是8*8=64个，图中只展示了一个C。右图中，A与B的Level数相差为1。

      整个调整过程的算法如下：

      1）遍历所有的结点（包括中间节点和叶子结点）。记max level为所有结点中Level数最大的，min level为所有结点中Level数最小的。

      2）如果max level = min level或者max level = min level + 1，那么表明整个结果已经是满足要求的，直接退出。否则：

      3）对K进行循环，K 从 max level – 2，反向减小到min level，每次减小1：

            3.1）遍历所有的结点，找到结点Level = K的结点A。

            3.2）查找A的所有邻居结点。如果存在某个邻居结点B，其Level >= K + 2，那么就将A细分。

      4）将步骤3循环max level次。