問題タブ [octree]

3D 再構成のためにあまり最適化せずに完全な octree 実装をコーディングしましたが、ツリー構造に含まれるポインターが多すぎて、256^3 を超えるボクセルをサポートできません。

理論的には、非ツリー構造の場合、vector<bool>ボクセルあたり約 1 ビットを使用する を使用した場合、非ツリー構造は 8GB メモリで 2k^3 をサポートできるため、これはより受け入れられます。

ただし、最適化された octree 構造は、次の理由から、これと同等またはそれ以上のことができるはずです。

1. すべてのボクセルを保存する必要はありません。これは、凝縮によって近くの同じ値のボクセルが圧縮される可能性があるためです。

2. ポインター自体がすでにかなりの量のバイトを使用しているため、ポインターをあまり使用しないでください。

3. octree のノード/ボクセル比はかなり低くなければなりません。

完全な octree の場合、ノード番号は として計算できます(s^3 -1) / 7。はsボリューム解像度で、2 のべき乗です。たとえば、 の場合、ボクセルの 4x4x4 グリッドを表すために octree にノードがs = 4必要です。1 + 8 = 9

これらの仕様を満たす C++ の octree 実装を知っている人はいますか?

多くのポインターを格納する複雑なツリー データ構造をコーディングしています。ポインター自体は多くのスペースを占有しますが、これは私が期待しているものです。

ですから、これに関する例があるかどうかを尋ねるためにここにいます。例: 64 ビット データ型の場合、ポインターが指しているデータが確実に連続している場合、32 ビット以下のポインターを使用できますか?

リンクされたデータ構造の透過的なポインター圧縮という論文を見つけましたが、もっと簡単な解決策があると思いました。

アップデート：

オクトリーです。GPU に関するこれに関する論文はGigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large And Detailed Scenesで、GPU では 15 ビット ポインターを使用します。

私は、ツリー ノードが次元の長さ (2 のべき乗) でテンプレート化されている octree の実装に取り​​組んでいます。

また、データを指すように N = 0 (葉) に特化しています。

(余談ですが、親ポインターを除外する N_MAX の特殊化もおそらく必要だと思います。そうしないと、C++ は無限に増加する N の型を生成しますか?しかし、それは私の質問にはあまり関係ありません。)

オクツリーが占有する 3D 空間で光線に沿って進む関数を作成したいので、表向きはルート ノード (既知の型を持つ) へのポインターを保持し、ルートからオクツリーを毎回トラバースすることができます。ステップ。ただし、現在のノードを追跡できる、より「ローカル」なオプションを希望します。これにより、可能であればツリーの下位から開始できるため、octree の上位ノードを不必要にトラバースすることを回避できます。

しかし、スライスを経験しないように、その型ポインターが何であるか (またはこれを実装する他の方法) がわからない。

ディメンションは単純に として実装できるため、テンプレートに縛られていませんlong const。しかし、葉がinodeとは異なる子タイプを持つようにする方法がわかりません。

ご協力いただきありがとうございます！

アップデート

これに似た方法ではなく、このようにしたい理由は、各ノードの変数のためですcount。カウントが 0 の場合、キューブ全体をジャンプしたいので、葉を通過する時間を無駄にします。私は空であることを知っています。(これはレイトレーシング ボクセル エンジン用です。)

そこで、次のようにoctree構造体を作成しました。

私が抱えている懸念はデストラクタにあります...
それは子供たちのデストラクタと呼ばれるのでしょうか、それとも私はそれを自分でしなければならないのでしょうか？

物理シミュレーションを行うシーン内のスペースをセグメント化するために、軸に沿ったバウンディング ボックスの octree を使用しています。近距離にある小さなオブジェクトと同様です。実際には、シーンには数キロしか離れていませんが、数キロメートル離れているため、これは多くの空のスペースを意味します。基本的に、バウンディング ボックスを保存するために 2 ギガの RAM を浪費しています。空のセクターの場合。実際に何かを含むセクターにのみメモリを割り当てたい (AABB へのポインターにするため) が、それは octree を再作成するためにフレームごとに数千の割り当てを意味します。プールを使用する場合割り当てによる速度低下に対抗するために、アプリケーションに 2 ギガの RAM を割り当てていることを意味します。これを達成する他の方法はありますか?

二分木トラバーサルの方法でアプローチしようとしましたが、反復オクトツリートラバーサルの手順を理解できません。私の問題では、子ポインターと親ポインターを持つ octree ノードがあり、反復してリーフノードのみをスタックに格納したいと考えています。また、反復トラバーサルは再帰トラバーサルよりも高速ですか?

OpenGL4.3.0でボクセルレイキャスターを実装しています。同じサイズの3Dテクスチャにfloat値の256x256x256ボクセルデータセットを保存する基本バージョンがあります。

ただし、八分木を使用してLODスキームを作成したいと思います。ホスト側の1D配列にデータを保存しています。ルートのインデックスは0、ルートの子のインデックスは1〜8、次のレベルのインデックスは9〜72などです。八分木には全部で9つのレベルがあります（最後のレベルは完全な256x256x256の解像度を持っています）。octreeは常に満杯になるため、構造は暗黙的であり、ポインターを格納する必要はありません。ボクセルごとに1つのfloat値のみです。1Dインデックス作成とトラバーサルアルゴリズムがすべて設定されています。

私の問題は、これをテクスチャに保存する方法がわからないことです。GL_TEXTURE_MAX_SIZEは、イン​​デックス付けを理解した1D配列アプローチを使用するには小さすぎます（16384）。これを3Dテクスチャに保存する必要があり、そこに1D配列を詰め込もうとするとどうなるかわかりません。また、無駄にならないようにサイズと1D->3D変換スキームを選択する方法もわかりません。空間または時間。

私の質問は、誰かがこの八分木構造全体を1つの3Dテクスチャに格納するための優れた戦略を持っているかどうか、そしてその場合、どのように寸法を選択してインデックスを作成するかです。

私はXNAで小さなMinecraftスタイルのゲームを開発しています。ボクセルモードを生成するので、マトリックス「ワールド」を最大限に最適化することを目指しています。これは私が探しているものです。たとえば、「XnaでOctreeを使用する方法は？」です。残念ながら、私はグーグルや他でこれに関するチュートリアルを見つけていません...この技術がよく使われているので、私はこれが奇妙だと思います！

各ボックスにブロックがあるかどうかを示すビット（1または0）を含む100x100x100マトリックスを回転させたいと思います。これはチュートリアル「Octree」ですか？これを行う必要がありますか？または、誰かが私に八分木行列への変換行列3Dの例を見せてもらえますか？

千ありがとうございます。

私はボクセル八分木レイキャスターの実装に取り​​組んでいます。残っているのは、データを再配置して八分木のリーフレベルに入力することです。これにより、データを平均してツリーの下位レベルを構築できます。

便宜上、最初は2D（四分木）で考えています。図面の左のようにデータを並べ替えてありますが、現在は右のように並べ替えることができます。例は8x8です。

ただし、次の図のように、ノード順にデータを並べ替える必要があることに気付きました。

言い換えると、データが次のようなインデックスに対応する配列から移動したいと思います。

次の順序でデータを持つ配列に：

四分8x8木例の場合。

どうしたらいいのかわからない。私の主な問題は、任意のツリーサイズを処理することです。サイズを事前に知っていれば、ネストされたループのセットをハードコーディングすることもできますが、それは明らかに優れた、または洗練されたソリューションではありません。私はそれを達成するための再帰的な方法があるかもしれないと思っています。

これは、写真1で説明した方法でデータを並べ替えるための私の迅速で汚いスケッチです。これは基本的に、元のデータの4つの位置を追跡し、新しい配列がいっぱいになるとこれらを前に進めることで機能します。私が知る限り、これは問題なく機能しますが、私のニーズに拡張することはできません。

この問題に遭遇したとき、nVidia (「効率的なスパース ボクセル オクトリー」)の人々がボクセルのことを行っていたように、スパース オクトリーの実装を作成するのに苦労していました。

octree のリーフがどこにあるかを示す byte 型 (8 ビットのみ) のビットフィールドがあります (1 はリーフを意味し、0 はリーフがないことを意味し、8 つのノードが接続されている --> 8 ビット)。私が今やりたいことは、葉の位置の配列を返すことです。私の現在の実装では、while ループを使用して、LSB が設定されているかどうかを確認しています。入力はその後 1 シフトされます。だからここに私がそれを行う方法があります：

これは見栄えがよくなく、気になる点が 2 つあります。

• この while ループは for ループを模倣しています
• 結果の配列は 8 つの値よりも小さくなる可能性が高いですが、サイズ変更にはコストがかかります

結果[2,4,6]は 42 のようになると思い(0010 1010)ます。

まだ読みやすい、よりエレガントなソリューションを提供できる人はいますか?

結果

以前に実装した octree リーフ カウントの関数を使用して、配列を適切なサイズに設定しています。