問題タブ [octree]

私は最近、バイナリ スペース パーティショニング ツリーと、その 3D グラフィックスおよび衝突検出への応用について学びました。また、四分木と八分木に関連する資料を簡単に調べました。bsp ツリーではなくクワッドツリーを使用するのはいつですか、またはその逆ですか? それらは交換可能ですか？次のような表に記入するのに十分な情報があれば満足です。

A、B、Cとは？

私は、2005 年以来の 3D スクリプト言語である SceneMax の創設者です。最適化されたパフォーマンスのために、3ds max のような 3d パッケージで構築され、octree アルゴリズムによって分割される 1 つのメッシュ オブジェクトを使用してシーン レンダリングを追加したいと考えています。

メッシュ .X ファイルを受け取り、それをノード (octree) に分割し、それをレンダリングする方法を知っているアルゴリズムをどこで見つけることができるか知っていますか? エンジンに追加したい。エンジンはオープン ソースです (興味がある場合は、SceneMax を検索してください)。

スパースオクツリーを格納およびアクセスするための高速で効率的な方法を提案できる人はいますか?

HLSL で簡単に実装できるものが望ましいです。(レイキャスティング/ボクセル アプリを使用しています)

この例では、ツリーを事前に計算できるので、サイズと検索時間に主に関心があります。

アップデート

これを行おうとしている人にとって、より効率的な解決策は、Z 次曲線/モートン ツリーで生成された線形 octree としてノードを格納することです。そうすることで、内部ノードの格納が不要になりますが、線形ツリー配列と、個々のボクセルに関する情報を含む 2 番目の「データ テクスチャ」との相互参照が必要になる場合があります。

再帰なしでボクセル八分木に光線を当てる方法について、誰かが短くて甘い説明を提供できますか（または良いチュートリアルを提案できますか）？

複雑なモデルを八分木に焼き付けたので、光線と交差する最良/最も近い葉を見つける必要があります。標準のドリルダウン反復ツリーウォーク：

1. ルートノードを取得します
2. 交差点を確認してください
3. いいえ？出口
4. はい？光線の原点に最も近い光線と交差する子を検索します
5. 葉に到達するか、木を出るまでループします

常に葉を返しますが、たとえば地形がツリーに格納されている場合、光線の原点に最も近いノードに、必ずしも最適な葉が含まれているとは限りません。これは驚くべきことではありません。遠いノードにある背の高いオブジェクトは、このアプローチを使用してテストされません。

これを再帰的に行うには、ツリー内で交差するすべての葉を見つけ、距離で並べ替えて、光線の位置に最も近い葉を選択します。ただし、これは遅く、再帰が必要です。

ブレゼンハムの線アルゴリズムを使用してツリーをウォークする方法について少し読んだことがあります。これには、各ノードに隣接する隣接ノードへのポインターが含まれている必要があるようですが、これを便利な方法で実装する方法がわかりません。

助言がありますか？固定長配列または潜在的なスタックエントリごとに要素を持つ構造体を使用してHLSLでスタックを偽造することはできますが、そのためのメモリ要件は、十分に大きなツリーで機能しなくなる可能性があります。

ヘルプ。

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter37.htmlにあるGPUGems2の章から、Cgを使用してGPUで使用するためにOpenGLの3Dテクスチャに八分木を保存し​​ようとしています。しかし、私が得ている結果は正しくありません。これは私が八分木を作る方法のせいだと思います。

その章の付録には、「間接プールテクスチャ（八分木テクスチャ）を繰り返しモード（GL_REPEAT）でバインドすると...」と書かれています。

これは単にフィルターとラッピングを繰り返すように設定することを意味しますか、それとも何か他のことをする必要がありますか？これはこれまでの私のコードです

助けてくれてありがとう ：）

重複の可能性:
高速でテンプレート化された C++ オクトリー実装

C または C++ の CPU または GPU の octree 用に適切に調整された実装を提案できる人はいますか?

また、オクトリーはポインターの有無にかかわらず表現できるため、いずれかの手法の長所または短所を教えてください。

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

CPU で octree をレイ キャスティングしようとしています (GPU の方が優れていることはわかっていますが、現時点では動作しません。octree テクスチャが正しく作成されていないと思います)。

何をする必要があるかを理解しています。これまでのところ、各ピクセルにレイをキャストし、そのレイが octree 内のいずれかのノードと交差するかどうかを確認しています。存在し、ノードがリーフ ノードでない場合は、光線が子ノードと交差するかどうかを確認します。葉ノードがヒットするまでこれを続けます。リーフ ノードにヒットすると、そのノードの色が取得されます。

私の質問は、これを画面に描画する最良の方法は何ですか? 現在、色を配列に保存してglDrawPixelsで描画していますが、レンダリングにギャップがあり、投影が間違っているため、正しい結果が得られません(glRasterPos3fvを使用しています)。

編集：ここまでのコードはいくつかありますが、クリーンアップが必要です。申し訳ありません。octree レイ キャスティング コードは、必要かどうかわからないので省略しましたが、役立つ場合は投稿します :)

N体やSPHのような粒子アルゴリズムに興味があります。これらのアプリケーションでの重要な手順の1つは、クエリポイントを指定して、半径'h'の指定された球内にある粒子を見つけることです。

Octreesは、N体やSPHなどの問題に適した空間データ構造であると聞いています。

しかし、八分木を構築した後、「半径内に粒子を配置する」ステップがどのように実行されるのか理解できません。このステップを実行するための参考資料、論文、または記事を誰かに教えてもらえますか？

octree を作成し、そこからデータを追加および削除するコードを見てきましたが、実際に octree をどのように構築するのでしょうか? ある種の配列に保存してから octree に変換できる 3D ボクセル ソフトウェアはありますか? または、octree に直接保存できますか?

私はPythonでBlender用のこのパーティクルエンジンに取り組み始めています：http ：//www.youtube.com/watch？v = uoK4QV3jg58＆feature = channel_video_title

すべてのデータは私のスクリプトによって処理されます。Blenderはビジュアルのためだけにあります。今のところ、私の問題は、上のビデオで、すべてのパーティクルの各パーティクル間の距離を計算して、それらが互いに衝突しているかどうかを検出することです。

私はについて読み始めています：

• 八分木
• kdTree
• BVHTree
• AABBtree
• ...などなど

Kdtreeは、最も近いネイバーを検索するのに非常に効率的であるように見えますが、静的クラウドのみを検索します。私のパーティクルは常に移動するため、反復ごとにkdTreeを再生成する必要があり、多くのプロセスを消費すると思います。私は多くのゲームがAABBツリーを使用していることを読みました。少し迷ってしまいました…何を選べばいいのかわかりません。私が欲しいのは：

• 非常に大量の粒子（25万以上）間の衝突を検出します
• リアルタイムである必要はありません（とにかく250000個のパーティクルでは実際には不可能です）。200万個のパーティクルに対してフレームあたり20分は私にとって問題ではありません。
• 私の粒子は常に球です
• パーティクルとポリゴンオブジェクト間の衝突を検出します
• 必要な距離計算を減らすためのアルゴリズム（遠くにある場合でも、互いにすべてのパーティクルまたはポリゴンを計算するなどの回避）
• パーティクルは動的であり、ポリゴンオブジェクトは動的または静的にすることができます。

誰かが私に最良の推測が何であるか、そして私がPythonのドキュメントとその例をどこで見つけることができるかを教えてくれるなら。