私はボクセル八分木レイキャスターの実装に取り組んでいます。残っているのは、データを再配置して八分木のリーフレベルに入力することです。これにより、データを平均してツリーの下位レベルを構築できます。
便宜上、最初は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木例の場合。
どうしたらいいのかわからない。私の主な問題は、任意のツリーサイズを処理することです。サイズを事前に知っていれば、ネストされたループのセットをハードコーディングすることもできますが、それは明らかに優れた、または洗練されたソリューションではありません。私はそれを達成するための再帰的な方法があるかもしれないと思っています。
これは、写真1で説明した方法でデータを並べ替えるための私の迅速で汚いスケッチです。これは基本的に、元のデータの4つの位置を追跡し、新しい配列がいっぱいになるとこれらを前に進めることで機能します。私が知る限り、これは問題なく機能しますが、私のニーズに拡張することはできません。
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]);
}