我正在实现一个体素八叉树的光线投射器,唯一剩下的就是重新排列数据以填充八叉树的叶级别,这样数据就可以平均分配到树的较低层中。
对于一个
我无法想出如何做到。我的主要问题是处理任意树大小。如果我事先知道大小,我可能可以硬编码一组嵌套的循环,但这显然不是一个好的或优雅的解决方案。我在考虑可能有一种递归方式来实现它。
这是我用于按照第一张图片描述的方式对数据进行排序的快速而肮脏的草图。它基本上通过跟踪原始数据中的四个位置,然后将这些位置向前移动,以填充新数组。据我所知,这样做是有效的,但不能满足我的需求。
为了方便起见,我最初考虑使用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]);
}