我正在实现一个体素八叉树光线投射器，唯一剩下的就是重新排列数据以填充八叉树的叶级别，以便可以对数据进行平均以构建树的较低级别。
为了方便起见，我最初考虑的是 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]);
}