重新整理了四叉树/八叉树数据

Question

我工作的实施体素八叉树raycaster，而唯一剩下的重新排列数据来填充八叉树的叶级别，这样的数据，然后进行平均来构建树的较低水平。

我在2D（四叉树）的思想最初是为方便。我已下令像图中左侧的数据，我现在能重新安排它像右侧。例子是8x8。

但是，我意识到，我需要订购的节点顺序的数据，如下面的图中：

换句话说，我想从那里数据对应于这样的索引数组去：

[0  1  2  3  4  5  6  7  8  9 ... 63]

到一个数组，将有在该顺序中的数据：

[0  1  4  5  16 17 20 21 2  3 ... 63]

用于8x8四叉树的例子。

我无法弄清楚如何做到这一点。我的主要问题是处理任意树的大小。我大概可以硬编码一组，如果我知道的大小提前嵌套循环，但它显然不是一个伟大的或优雅的解决方案。我想有可能是一个递归的方式实现这一目标。

这一点，对于排序在一个画面描述数据的方式是什么我的快速和肮脏的草图。它主要通过跟踪的四个位置中的原始数据，然后踩着这些前瞻性为新的数组被填补工作。据我已经能够告诉，这工作正常，但不得延长我的需求：

 int w = 8; 
  int[] before = new int[w*w*w];
  int[] after = new int[w*w*w];
  for (int i=0; i<w*w*w; i++) {
    before[i] = i;
  }
  int toFill = 0;
  int front = 0;
  int back = w;
  int frontZ = w*w;
  int backZ = w*w + w;
  do {
   for (int i=0; i<w/2; i++) {
      for (int j=0; j<w/2; j++) {   
        after[toFill++] = front++;
        after[toFill++] = front++;
        after[toFill++] = back++;
        after[toFill++] = back++;

        after[toFill++] = frontZ++; 
        after[toFill++] = frontZ++; 
        after[toFill++] = backZ++;
        after[toFill++] = backZ++;
      }    
      front += w;
      back += w;
      frontZ += w;
      backZ += w;
    }
    front += w*w;
    back += w*w;
    frontZ += w*w;
    backZ += w*w;
  } while (toFill < w*w*w);
  for (int i=0; i<w*w*w; i++) {
    println("after " + i + " " + after[i]);
  }

Answer 1

对于我所说的问题，小灵通暗示我，它被称为Z顺序曲线。感谢的是，我发现这个问题：其中，在2D情况下的算法，Z-order-curve coordinates。我试了一下，和它的作品。

下面是3D情况的几个实现，以及：How to compute a 3D Morton number (interleave the bits of 3 ints)