問題タブ [octree]

私は地形エンジンのようなMinecraftを作成していますが、正確には八分木とは何か疑問に思っていました。私のエンジンでは、エンジンの各部分をチャンクまたは領域に分割しました。これは、私が読んだものから、それと関係があります。また、インデックスがゲーム内のパフォーマンスを向上させるかどうか、もしそうならどれくらいになるのだろうかと思っていました。パフォーマンスを向上させるための他のアイデア/方法をいただければ幸いです。裏面カリングはすでに含まれていることに注意してください。ボックスまたは側面が非表示になっている場合は、その側面を表示しないでください。

以前のいくつかの投稿で述べたように、私はマインクラフトのようなエンジンを作成しています。

地形を領域に分割し、カメラの視錐台にある領域のみをレンダリングします。各領域の頂点バッファーが bulit の場合、各ブロックが表示されているかどうかを確認し、表示されていない場合はバッファーに追加されません。表示されている場合は、どの側面が他のブロックに囲まれていないかを確認し、それらの面を構築します. また、反時計回りのカリングを有効にしています。

パフォーマンスを向上させる他の方法を提案できる人はいますか? 前述の理由が、フレーム レートが低い理由である可能性があります...また、このエンジンにインデックスを追加するとパフォーマンスが向上するかどうかも知りたいです。

また、これはメモリ割り当てとは何の関係もないと思います。

編集:わかりました、私はインデックスバッファを暗示しました。パフォーマンスは大幅に向上しましたが、さらに向上できると思います...

空間データ構造に関する本をアドバイスしてください。興味がありQuadtrees and Octreesます。

閉曲面の境界八分木を作成しました。面を含むすべての octree キューブは、同じレベルまで分割されます。したがって、すべてのリーフ ノードは同じサイズです。これらの各ターミナル キューブの隣人を見つけるのに助けが必要です。さまざまな論文を参照してみましたが、実際に実装する方法がわかりませんでした..Matlabで。現在、すべてのターミナル キューブを (octree データ構造を使用せずに) ボクセル キューブとして扱い、ブルート フォースを使用して、サーフェスを構成するキューブのリストに含まれる 26 個の可能な隣接キューブを見つけます。出力を得るには時間がかかります。私はプログラミングが初めてなので、葉ノードの隣接ノードをより効率的に見つける方法と、matlab でコーディングしてメソッドを実装する方法を誰かが提案してくれたら本当にありがたいです。ありがとう！！

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

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

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

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

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

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

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

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

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

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

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

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

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

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

これを4x4にして

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

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

私は、光線が反復的に通過する葉を与える、優れた光線と八分木の交差アルゴリズムを探しています。まだCUDAに飛び込みたくないので、CPUに実装することを計画しています:)

現時点では、私のボクセルレイキャスターは、XxYxZボクセルの非階層配列に対して3D DDA（Amanatides / Wooバージョン）を実行します。次の図に示すように、空のスペースがたくさんある場合、これはかなりコストがかかることを想像できます（明るい赤=より多くの作業:)）：

このタスクには2種類のアルゴリズムがあることをすでに理解しました。リーフから上に向かって機能するボトムアップと、基本的に深さ優先探索であるトップダウンです。

私はすでに2000年からRevellesのアルゴリズムを見つけました。これは、八分木探索のための効率的なパラメトリックアルゴリズムと呼ばれ、面白そうに見えますが、かなり古いものです。これはトップダウンアルゴリズムです。

最も人気のあるボトムアップアプローチは、K。Sung、レイトレーシング用のDDAオクトリートラバーサルアルゴリズム、Eurographics'91、North Holland-Elsevier、ISBN 0444 89096 3、p。73-85。問題は、ほとんどのDDA Octreeトラバーサルアルゴリズムが、octreeが同じ深さであることを期待していることです。これは、私が望んでいないことです。空のサブツリーは、nullポインターなどである必要があります。

私が読み通したSparseVoxelOctreesに関する最近の文献では、（特にSVOに関するLaineの作業は、GPUで実装されたバージョンのDDA（Amanatides / Wooスタイル）に基づいているようです。

さて、ここに私の質問があります：誰かが基本的な、飾り気のない光線-八分木交差アルゴリズムを実装した経験がありますか？あなたは何をお勧めします？

私は現在、私の学士論文プロジェクトのために八分木を実装しています。私の八分木は引数としてstd::vectorを取ります：

頂点をレンダリングしてカリングテストなどを行う前に、頂点を格納するために通常使用されるものを尋ねています。

私は今のところこれを非常に単純に保ちました、私が持っているのはグリッドをレンダリングする関数だけです。いくつかのスニペット：

これをレンダリングするとき、カスタム構造体GridVertexを使用します。これにより、posにD3DXVECTOR9、カラー値にDWORDが保存され、柔軟な頂点形式をGRIDFVFに設定してGPUに通知されます。しかし、私のOctreeでは、特定の頂点が私のOctree内のノード内にある場合など、テストを実行するための位置のみを保存したいと思います。したがって、SceneManagerという別のクラスを作成し、すべての値をstd :: vector内に格納し、最後にそれをOctreeクラスに渡すことを考えました。これにより、テストが実行され、チェックされた頂点がGPUに渡されます。これは固溶体でしょうか、それともこのようなものを実装するのに一般的なことでしょうか？前もって感謝します

KDTree のテンプレート化された実装を作成します。これは今のところ、BarnesHut 実装の Quadtree または Octree としてのみ機能するはずです。

ここで重要な点は設計です。ツリーが定義されている次元の数をテンプレート パラメーターとして指定し、いくつかの一般的なメソッドを宣言するだけで、自動的に正しい方法で動作します (テンプレートの特殊化が必要だと思います)。

2^2 (quadtree) または 2^3 (octree) ノードを持つために、テンプレートを特殊化したいと考えています。

誰かがいくつかのデザインのアイデアを持っていますか? 静的割り当てではなく動的メモリ割り当てを行うように制約されるため、継承を避けたいと思います。

ここで、N は 2 または 3 です

もう 1 つの問題は、quadtree には 4 つのノードがありますが 2 次元であり、octree には 8 つのノードがありますが 3 次元です。つまり、ノードの数は です2^dimension。これをテンプレート メタプログラミングで指定できますか? ループアンローラーが高速になるように、番号 4 と 8 を維持したいと思います。

ありがとうございました！

このウィキペディアの記事で説明されている手法を使用して四分木を構築しています。座標を 2 次元または 3 次元配列に格納しています。

Z オーダーで次のボックスの座標を計算するメソッドが必要です。デインターリーブよりも、ビットをインターリーブして 1 ずつ増やすことで機能しますが、これは非常に複雑になります。ビットをインターリーブせずに機能する記事の cmp_zorder(...) メトンに似た実装があることを願っています。

ボクセル レイキャスティング エンジンを開発するために opencl を使用しています。Crassinの Gigavoxels に似たようなことをしようとしています。この論文では、ボクセル データを格納するために octree を使用しています。今のところ、レンダリング データを含むリーフに到達するまで、octree 内を下降しようとしています。

私は 2 つの実装を作成しました。1 つは GPU 上の OpenCl で、もう 1 つは CPU 上の C++ です。私が経験している問題は、GPU でアルゴリズムが octree 内の葉に到達するまで間違った数のレベルを通過していることです。CPU バージョンで正しい結果が得られます。両方のバージョンのアルゴリズムは同じで、コードはほとんど同じです。

何が問題なのか知っていますか？ハードウェアの問題か、OpenCl の問題か、それとも何か間違っているのでしょうか? 3 つの異なる nVidia GPU で同じ結果が発生しています。

C++ コードは次のとおりです。

OpenCL コードは次のとおりです。

要求に応じて、extractOctreeNodeAddress を次に示します。

どちらの関数も、いくつかのビット操作を行うだけです。

OpenCL バージョン:

C++ バージョン:

こんにちは、面白いものを見つけました。単一の正確なピクセルとカメラの位置と向きで CPU と GPU のバージョンを比較するさまざまな変数を手動でテストしようとしました。以下のコードでプログラムを実行すると、ピクセルが白く印刷され、値 (> 5.5 は CPU の実装と比較して完全に間違っています) のようになりますが、最後の if 構造をコメントし、最初の if 構造のコメントを外すと、私が得た結果は赤です....これは私には少し説明がつきません。何か案は？