問題タブ [octree]

GLSL (v450) のコンピューティング シェーダーで、リアルタイムのレイ マーチングを使用するレベル アルゴリズムを使用して、octree をトラバースしようとしています。私はなんとかそれを横断し、画像を取得しましたが、私の fps は非常に低く、約 0 ～ 5 fps です。アルゴリズムの疑似コードは再帰的なものなので、スタックを使用してループに変換しました (GLSL では再帰が許可されていないため)。問題は、このループを動的に均一にしないとすぐに、約 30 ～ 40 のこの巨大な fps 低下が発生することです。

スタックで共有属性を使用すると、この fps を元に戻すことができます。これは、グローバル変数の計算シェーダーでのみ使用できます。

ワークグループ内のすべてのスレッド間で共有および使用できるようにします。問題は、ループを動的に均一にする必要があるように見えるため、これらをbarrier()および/またはmemoryBarrierShared()関数と同期できないことです (共有変数の下を参照してください www.opengl.org/wiki/Compute_Shader)。同期できないため、画像がピクセル化されてちらつきます。

このアルゴリズムを動的に均一なループに変換する方法はありますか? ループが動的に均一でなくなると fps が低下するのはなぜですか?

以下は、メインループの私のコードです。

ここに問題があります: 並列に処理される多数のポリゴン (三角形) を含むジオメトリ メッシュがあるため、特定の領域のポリゴン データを取得する効率的な方法が必要です。つまり、バウンディング ボックス {(x_min, y_min,z_min),(x_max,y_max,z_max)}, この立方体領域の内側 (または部分的に内側) にあるすべてのポリゴンを含むポリゴンのリストを取得する必要があります。出来ますか？

バウンディング ボックスの頂点は、一連の均一なデカルト グリッド上に配置されます。私が自分自身を明確にしたかどうかはわかりませんが、全体のアイデアはどういうわけか八分木のデータ構造に似ていますが、八分木の各ノードにポリゴンのリストを格納する必要があります。

したがって、ノードに 2*2 サブノードがある場合、それはクワッドツリー (2*2=4) と呼ばれます。ノードに 2*2*2 サブノードがある場合、それは octree (2*2*2=8) と呼ばれます。したがって、2D で作業する場合は 4 分木を使用することをお勧めします。3D では 8 分木を使用することをお勧めします。

しかし、3D で任意の数のサブノードを持つツリーはありますか? n n n サブノードを持つツリーのように。それは何と呼ばれており、これに関する科学的研究はすでにありますか?

前もって感謝します。

記事Advanced Octrees 2: ノード表現では、次のように述べられています。

ノードの AABB は、以前のように明示的に格納することも、ロケーション コード内に暗黙的に格納されたノードのツリーの深さから計算することもできます。ノードのツリーの深さをロケーション コードから取得するには、ロケーション コードの終了を示すフラグ ビットが必要です。このようなフラグがないと、たとえば 001 と 000 001 を区別することはできません。1 ビットを使用してシーケンスの終わりをマークすることにより、1 001 を 1 000 001 と簡単に区別できます。このようなフラグを使用することは、 Octree ルートの位置コードを 1 にします。

ロケーション コードは 32 ビット ワードです。つまり、最初の例に続くすべてのビットが2番目の例のビット... 001と等しい場合... 000 001、著者が言うように等しいかもしれません。

シーケンスの終わりをマークすることは、ツリー内のノードの深さを見つけるのにどのように役立ちますか?

著者は例... 1 001と を使用し... 1 000 001ます。最初のノードの深さは 1 で、2 番目のノードの深さは 2 ですか? もしそうなら、どうすればわかりますか？ロケーション コードは 32 ビット ワードであるため、「終了フラグ」に続くビットは、... 001 001どちらも有効なノードとして続くことができます。

したがって、私が本当に理解していないのは、ツリー内のノードの位置コードと深さの両方を 32 ビット ワードに格納する方法です。

WebGL を使用して巨大な 3D ボリュームをレンダリングしています。レイ キャスティング アルゴリズムはシェーダー (glsl) に実装されています。ボリュームはバイオ イメージ スタックから作成されます。私がやりたいことは、この 3D ボリュームをレンダリングするときにスムーズにズームインおよびズームアウトし続けることです。しかし、画像スタックは高解像度であるため、リアルタイムのパフォーマンスを得るには、Octree を使用する必要があります。実装方法について何か提案はありますか?

OGL シーン表現として octree を使用したいのですが、そこに移動オブジェクトがあります。また、この octree を使用して衝突検出を加速したいと考えています。移動するオブジェクトが貫通する octree (そのようなパスのすべてのセル/ノード) のパスを提供する優れたアルゴリズムはありますか?

速度がわかっている 1 つの移動オブジェクトがあるとします (つまり、2 つの位置、1 つのフレーム内の移動の開始と終了)。

私の考えは、単純にツリー全体を調べて、移動オブジェクトを含むセルと残りのセルの衝突検出を実行することです。それは私にそれらすべてを与えるでしょうが、それはやり過ぎではありませんか？ありがとう！

3D ボクセル データがあり、メモリ効率と高速アクセスのために再パッケージ化したいと考えています。データは、セルごとに 1 つの整数値の通常の octree で生成されます。残念ながらデータはまばらではありませんが、同じ値を持つセルは接続されているはずです。

私の現在の考えは、kD ツリーを使用することです。できれば左にバランスがとれていますが、これを生成するための効率的なアルゴリズムがあるかどうかはわかりません。私はいくつかのアイデアを持っていますが、これがすでにアルゴリズムを確立している問題の1つであるか、少なくともグーグルで検索できる名前であることを望んでいました.