問題タブ [octree]

私は現在、球体データセット用の CPU のみのラスタライザーを実装する必要がある課題に取り組んでいます。データセットは静的であるため、セット全体がカメラの前で回転できる場合でも、実行時に変更されません。

現在のアイデアは、オクルージョン カリング メソッドを実装して、カメラの視点から他の球体によってオクルージョンされた球体がラスタライザーの次の段階に進まないようにすることです (Z バッファーとピクセルのシェーディングに対するテスト)。 CPU 時間。

これを達成するための可能な方法を検討してきました。最初に、シーン モデルを octree で維持する階層型 Z バッファリングの実装について考えました。ただし、データセットが回転するため、フレームごとに octree を再計算する必要があり、かなりコストがかかる可能性があります。私は正しいですか？

このシナリオでは、球体データセットの階層構造を計算するための空間ハッシュまたは安価な方法がより有益であるかどうかはわかりません。これについて何か考えはありますか？これは CPU に完全に実装する必要があることに注意してください。

私は現在、Revelles、Urena、および Lastra の論文「An Efficient Parametric Algorithm for Octree Traversal」を実装しています。Ray - Octree 交差アルゴリズムでは、誰かがそれを実装して自分のコードを貼り付けました。私の実装は、計算にいくつかのベクトルを使用したことを除いて、同じである必要があります。ただし、このオクツリーを使用すると、画像の右上部分のみがレンダリングされ、画像の残りの部分についてはオクツリーがトラバースされません。トラバースするかどうかのチェックは、次のメソッドで行われます。

[編集]上記のメソッドは関数を実装します

紙から。C. Urena が指摘したように、トラバーサルが正しくない原因となるエラーが論文に含まれています。残念ながら、このエラーが発生する前にトラバーサルがスキップされます。C. Urena のリンクの後にある Google グループでは、octree ノードのサイズの計算方法が異なるようです。やった：

対

グーグルグループで。私はそれをテストし、別の更新を投稿します。[/編集]

[編集 2]カルロスが言及した修正を適用し、サイズを半分に縮小すると、ここまで来ました。

球体は完全にレンダリングする必要がありますが、少なくとも左上 4 分の 1 のすべての光線が拒否されるわけではありません。[/編集 2]

[編集 3]異なるデータ セットを使用すると、一見より良い結果が得られます。コードの他の部分を調査する必要があるようです。

[/編集 3]

ボクセルベースの流体を格納する octree があります。流体をシミュレートするとき、現在のノードの周囲の葉にアクセスする必要があります。そのような検索を実装するにはどうすればよいですか?

ノードがその親ノードへのポインターを格納していると仮定できます (おそらく他のデータが必要ですか?)

後でレンダリング用のメッシュを含める必要がある Octree を C++ で実装しています。しかし、現時点では、オクトリーの構築に苦労しています。より正確に言えば、問題を引き起こすのは addNode() 関数です。二分木に似た再帰的な実装を考えました: Binary Tree implementation C++

ただし、octree では、すべてのノードに 2 つだけでなく 8 つの子があります。さらに、ノードを追加する場所を決定するために、バイナリ ツリーのように単純なスイッチ (左/右) を使用することはできません。8 つの息子の 1 つが空 (ポインターが NULL) かどうかを確認する必要があり、ポインターが null でない場合は、息子の 1 つを引数として add 関数を呼び出す必要があります。ただし、これにより、常に最初の息子に後続のすべてのサブ octree が含まれる octree が生成されます。この追加機能は一般的にどのように実装され、この問題は回避されますか?

これまでの設計上の決定について少し背景を説明します... ポイントを格納できる octree 構造を開発しました。特定の基本ボクセル サイズに基づいて、「世代」の再帰を制限することにしました。子ノードは、そのノードにポイントが追加されたときにのみ作成されます。これは動的なグラフィックス アプリケーションではありません。この octree とその中のオブジェクトは静的であるため、パフォーマンスを向上させるための前処理は問題になりません。

ここで、オクツリーに「シェイプ」を追加したいと思います。具体的には、三角形で構成されるサーフェス メッシュです。これらの三角形の頂点は、八分木に格納されている点に対応していません。これらの形状を octree にどのように格納しますか? 2つのオプションが表示されます...

灰色のノードは、形状がないという点で「空」です。代替案 1 では、シェイプが交差するすべてのノードに保存されます。つまり、ノード 1a には shape1 が含まれ、4c と 4d は shape2 を共有します。別の方法 2 では、形状は交差する最小のノードにのみ格納されます。つまり、ノード 1a には形状 1 が含まれ、ノード 4 には形状 2 が含まれます。

私が見た octrees に関するほとんどの投稿は、Alt1 を前提としていますが、その理由は説明されていません。Alt2 は私にとってより理にかなっており、ノード境界に存在する形状に対してのみ余分な作業を作成します。Alt1 が望ましいのはなぜですか?

編集:明確にするために、使用する実装言語は C++ であるため、その言語でのサンプル実装を好みますが、質問は言語に依存しません。タグの使い方が間違っていたらごめんなさい。

Edit2:形状ストレージの問題とは直接関係ありませんが、このリンクには、質問の背後にあるオクツリートラバーサルに関する良い議論があります。この質問に取り組むことに興味のある人なら誰でも役立つかもしれないと思いました。

更新: 4 年後、Alt2 は実装が簡単になりましたが、より高い octree レベルに格納された大きな三角形が octree を走査するたびにテストされるため、非常に遅くなりました。私の場合、それは数百から数千の不要なテストを意味しました。代わりにR*-Tree バリアントを使用するようにコードを修正することになりました。これは実装が簡単で、大幅に高速でした。

Java でビットマップ イメージに使用される色を取得するのが難しいと感じています。octree色量子化アルゴリズムまたはその他のより優れたアルゴリズムを使用したJavaプログラミングで、最もよく使用される画像の色を取得するにはどうすればよいですか?

問題文: Octree を使用して各粒子の最も近い GRID ID を見つける。

図[1]:

図[2]:

どのグリッドポイント(リジッド;写真では)が最も近いかを確認する必要があるパーティクル(〜6k、可動)のシステムがあります。Octree は 3D グリッドでは高速 (est) であるため、誰かが私に Octree を勧めてきました。

これは、再帰的なオクトリーがグリッドの最も近いグリッド ポイントを取得するための正しいアルゴリズムですか?

1. 入力を点 P として取得 開始座標 C (最初は [0,0,0])
2. 開始サイズ = [Sx、Sy、Sz]
3. 8 つすべての中点を取得 Mi = {M1,..,M8} Mi と P の最小距離を取得

4. M が M の開始位置を Cn セット サイズ Sn = [Sx/8, Sy/8, Sz/8] として取得するとします。

5. M と P の距離が 2 * 未満の場合 (グリッド スペース G):

   5.1. Cn から Sn までのすべてのグリッド ポイントを反復します。

   5.2. 結果として最小に印刷

6. そうしないと

   6.1. 開始座標を Cn に設定

   6.2. サイズをSnに設定

   6.3. 後藤1

問題: A x B x C をすべてチェックするため、パーティクルが外に出ているか境界線に近い場合、最後の反復ですべての速度が消費されます。

この問題を解決するためのより良い方法があれば提案してください。