1

これは私が過去数時間考えていたものです。これはマインドエクササイズです。

だから私は今日の八分木が何であるかを学びました！とても興味深い！ボクセルに解決される八分木を実装する方法を考えてきました。

今、頭を抱えることができない最大の問題は、八分木の位置を参照することです。

免責事項：最初に、問題を視覚化するために2D平面で四分木を使用します。第二に、私はここで正しい専門用語を理解していません。親である八分木の細分化は「ブランチ」であり、子のみである細分化（この場合はボクセルに解決されます）は葉"。第三に、四分木の枝の各スペースに、左から右に上から下に番号を付けます{1,2,3,4}

16x16のユニットスペースを定義する四分木があるとしましょう。場所[16,16]にボクセルを保存しています。

4->4->4->4

ここで、位置[4,4]にボクセルを追加するとします。（注：ゼロから開始します）

1->4->1->1
4->4->4->4

ここで、ボクセルが格納されているかどうかを確認するために[16,8]をチェックしたいとします。前の方法を使用して、これらのブランチを技術的にトラバースします。

4->1->1->1

ただし、4-> 1にはデータが割り当てられていないため、空です。（使用されていないため、細分化されません）。

私の質問はこれになります、どうすれば四分木をすばやく横断してボクセルを見つけることができますか？

私の最初で最も簡単な方法は、上記で使用した形式でブランチを移動することです。

// Pseudo-code
Class Quadtree {
Quadtree Parent;
Quadtree c[4]; // children
};

Quadtree test1;
test1.c[4].c[4].c[4].c[4];
Quadtree test2;
test2.c[1].c[4].c[1].c[1];

ここでの問題は、voxelArray [16] [16]、voxelArray [4] [4]、またはvoxelArray[16][8]の方がはるかに高速であるということです。はるかに大きな四分木（256x256）を使用すると、深さが増加します（4から8）。ネストされた配列はまだ2つのメモリ操作です。（クアッドツリーの場合、実際には、アクセサーのようなものを使用して、子が条件付きロジックで存在することを確認することに注意してください）

私の2番目の考えは、四分木をボクセル自体として保存することでした。たとえば、2x2の配列があるとすると、空の場合は次のようになります。

{0, 0, 0, 0}

位置[1,1]にボクセルを追加すると、次のようになります。

{0, 0, 0, 1}

四分木を保存すると、次のようになります。

{1/*q*/, 0, 0, 0, 1}

これを4x4にして

{0/*q*/, 0, 0, 0, 
 0/*q*/, 0, 0, 0, 
 0/*q*/, 0, 0, 0, 
 1/*q*/, 0, 0, 1}

データに直接アクセスできるようになりましたが、クアッドツリーのメモリのコンパクトさが失われ、多くのロジック操作を実行できます。IMOこれは、0の大きな領域と1の小さなグループがある場合にのみうまく機能します。

ボクセルをquadtree/octreeに格納することにより、すべてをループするときにパフォーマンスが向上しますが、直接アクセスするとパフォーマンスが低下します。

ここに画像の説明を入力してください

4

2 に答える 2

1

クワッドキーを計算してから、各ボクセルをハッシュすることができます。アイデアは、寸法の複雑さを軽減することです。たとえば、ハミルトンパス、z曲線、またはヒルベルト曲線を探すことができます。このパスは平面を完全に横断しますが、技術的にはまだカーブです。

于 2012-04-10T09:59:32.963 に答える
1

これは、回答というよりも拡張されたコメントです。しかし、それはあなたに役立つかもしれません。またはそうではないかもしれません。あなたの例：

{0, 0, 0, 0}

空の四分木を示しているのではなく、4つの象限すべてが最初の（そして唯一の）レベルで値0を持っている四分木を示しています。これ：

{}

空の四分木を示しています。これ：

{0, 0, 0, {1,0,1,0}}

は、3つの象限がすべて0で、4番目の象限がチェス盤（小さいものではありますが）である四分木を示しています。これ：

{{1,{1,0,0,0},0,{1,1,1,{0,0,0,1}}}, 0, 0, {1,0,1,0}}

トリッキーになり始めていますが、あなたは今までに私のドリフトを取得します。

一部の言語（Lisp、Matlab、Mathematicaなど）では、これらの図を直接実装して操作することができます。多くの言語では、ポインタや値のコレクションとしてクアッドツリーを実装します。

于 2012-04-10T10:31:12.650 に答える