問題タブ [octree]

問題文: 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 をすべてチェックするため、パーティクルが外に出ているか境界線に近い場合、最後の反復ですべての速度が消費されます。

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

これは、ここでのスタックオーバーフローに関する最初の質問です。すべてが正しいことを願っています。Java プロジェクトでは、レイトレーシングに octree を使用する必要があります。私はすでに単純な八分木を作成し (隣接情報などを含まない)、オブジェクト メッシュの三角形を八分木の AABB に分類しました。ここで、すべての光線に対してツリーを簡単に横断したいと思います。(このプロジェクトを完了する時間は非常に短いため、非常に簡単なはずです)。基本的なアルゴリズムは次のとおりです。

1. 最初のノードから開始
2. このノードがヒットした場合、ソートされたリストで交点の場所を記憶します
3. このノードに子がある場合は、子ボックスがヒットしているかどうかを確認し、すべての交点をソートされたリストに書き込みます
4. 最も近い交点を持つ子ボックスから始めます
5. このボックスにも子がある場合は、4) を参照してください。
6. ノードに子がない場合は、このボックス内のすべての三角形を光線に対してチェックします
7. 三角形がヒットした場合、三角形の色を取得し（シェーディングとすべてを含む）、画面に描画します

残念ながら、私の現在の実装では、交点の計算 (ray と ABBB) に「バグ」があるようです。AABB のいずれかの側がヒットしたかどうかを確認し、最も近い IP (光線の原点からの最小距離) を記憶します。

私の BoundingBox クラスのこの関数のコードは次のとおりです。

これは最善の方法ではないと思います。私の最初の実装では、t 値を使用してそれらを比較しました (次にアクセスしたいボックスを見つけるため)。しかし、問題は同じでした。一部の交差点が見つかりませんでした。

ここで交差メソッドもチェックアウトしました: https://code.google.com/p/3d-workspace/source/browse/trunk/MathLibrary/Bounding/BoundingBox.cpp?r=17しかし、方法 がわかりませんこのコード (または任意の t 値) との交点を取得します。さらに、ここで説明されているようなスラブ メソッドをテストしまし た 。

たぶん、私はレイトレーシングを行うにはあまりにも愚かです。

しかし、私の実際の質問は次のとおりです。

t値を使用して、どのボックスが最も近い交差点を持っているかを比較することは可能ですか? はいの場合、どうすればこのt値を取得できますか? または、最初に切り取ったコードを機能させるにはどうすればよいですか? （これまでのところ、このソリューションが非常に遅い場合でも、機能するソリューションに満足しています）

前もって感謝します。

私は、3D オブジェクトの高レベルの記述から (たとえば、配列に配置され、Morton エンコーディングによって並べ替えられたリーフを使用して) 線形 octree を構築するトップダウン プロシージャを使用しています。問題は、私の意図したアプリケーションでは、結果の octree が 2:1 でバランスが取れている必要があることです。つまり、一方が他方のサイズの 2 倍を超える隣接ブロックのペアがあってはなりません。

私が見つけた唯一のものは、記事「Bottom Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel」です (複数の情報源から見つけることができますが、著作権は明確ではありません。このサイト) で、そのためのアルゴリズムが説明されています。問題は、提示されたアルゴリズムが並列メッセージ パッシング アーキテクチャで動作することであり、私のアプリケーションにとってはやり過ぎです。もう 1 つの問題は、(ボトムアップの) 構築アルゴリズムとバランス アルゴリズムが結びついているように見え、独自の方法でツリーを構築した後でのみバランスをとる方法が一目でわからないことです。

それでは、線形オクツリーを 2:1 でバランスさせるための (できれば単純で) 効率的な方法は何でしょうか? 並列アルゴリズムも優れていますが、リンクされたアルゴリズムのようなメッセージ パッシング モデルではなく、共有メモリ モデルを使用します。

非常に大きなシーンの表示に適した 3D エンジンに取り組んでいます。レンダリング自体の一部 (フラスタム カリング、オクルージョン カリングなど)、シーン管理に最適なソリューションは何かを考えています。

データは 3D メッシュの巨大なリストとして与えられ、それらの間に関係はありません。そのため、ポータルを生成できないと思います...

主な目標は、RAM の少ないシステム (500MB ～ 1GB) でこのエンジンを実行できるようにすることです。このエンジンにロードされるシーンは非常に大きく、何百万ものトライアングルを含むことができるため、メモリの使用量が非常に集中します。私は実際に現在、ロード時に構築された緩やかな octree を使用しています。これは小規模および中規模のシーンでうまく機能しますが、多くのシーンは大きすぎて完全にメモリに収まらないため、ここに私の質問があります:

チャンクを動的に (そして理想的にはシームレスに) ロードおよびアンロードするシーンをどのように処理しますか? また、チャンクをロード/アンロードする必要があるかどうかを判断するために何に基づいていますか? シーンは既知の 3D オーサリング ツールでカスタム エクスポーターを使用してエクスポートされるため、必要に応じてカスタム ファイル形式を作成できます。

重要な情報: 多くのシーンは、構造上、効果的に遮ることができません。例: 非常に巨大なパイプ ネットワークのため、オクルージョンはそれほど多くありませんが、要素の数が非常に多くなっています。

衝突検出のみに FCL ライブラリを使用したい。

私の最初のオブジェクトは、球体の形状を使用して指定したいロボットであり、2 つ目は octree を使用して世界の障害物です。

この検出コードを作成するために、指示に従ってみました。

ROS wiki の API から次の情報を入力するにはどうすればよいですか?

この API では三角形を使用していますが、私が知る限り、三角形は 3D メッシュにのみ使用されます。私はメッシュを使いたくありません。オブジェクトとして octree と sphere が必要です。

1. では、どうすればそれを変更できますか？
2. あと、衝突したことを真偽で返すには、どの関数を使えばいいでしょうか？
3. データが更新された場合はどうなりますか? ロボットが動いていて、ロボットと octree の位置を更新し続けたいということですか? どうすればそれを実行できますか?
4. BVH モデルの意味は何ですか?

例を探したところ、次のことがわかりました。

出力は「res1」でした

「1」とはどういう意味ですか? 衝突ということですか？そして、ここでの物理的な衝突の意味は何ですか? オブジェクトの位置はどこですか?なぜこれが ROS wiki の API に従っていないのですか?

長い質問で申し訳ありませんが、私は初めて FCL を使用し、それについて何も知りません。

私は2つのオブジェクトを持っています。最初のオブジェクトは、球として表現したい私のロボットで、2 番目のオブジェクトは、形状が不明な障害物です。障害物の形状を八分木で表現したい。

ROS wiki の api を使用して fcl ライブラリを使用して、これら 2 つのオブジェクト間の衝突 (true または false) をチェックするために fcl の api を使用するにはどうすればよいですか? ロボットが動いているとします。

また、レーザースキャンデータを使って障害物を検知?? octreeオブジェクトにそれを埋める方法??

次のようなシェアオブジェクトを作成した場合

この球体の中心がロボットの中心であることをどのように特定できますか?

編集：

次のコードを書きましたが、octree を埋める方法がわかりません

それで、何か提案はありますか???

独自のバージョンの octree を作成しようとしていますが、異なるサイズのポイントを追加しようとすると問題が発生します。深度レベルを下げるとすべてが上書きされるため、大きなブロックの情報が削除されます。

これを修正する最善の方法は、最後のポイントを逆方向にチェックし、新しいポイントの深さまでリストを再構築することだと思いました。しかし、私が求めている出力を考えるのは本当に簡単であるという事実にもかかわらず、実際にリストを作成する方法を理解することはできません.

開始リストと終了リストの例を使用してリストを作成するために必要なデータは次のとおりです["Nodes",(coordinate),"Nodes",(coordinate)...]。各座標がstructureリスト内のすべての項目を最後に到達するまでカバーする形式でデータが必要です。

これは極端な例 (深度 4 から 0 への移行) であり、4096 の異なる値を生成しますが、99% の確率でこれほど大きな値にはならないため、パフォーマンスはそれほど重要ではありません。

開始値と終了値の例の場合、各長さの値は必要ありません。次のように、すべて最大長にする必要があります-

私は試みましたが、実際には再帰的ではないことに気付きました。とにかくここにあります-

私が本当に必要とするのは実行時の各リストだけなので、ループ内からすべての組み合わせを出力できる段階に到達できれば、それらすべてを保存するためにメモリが無駄にならないので、それは素晴らしいことです:)

練習用に LWJGL を使用して Java でボクセル エンジンを作成していますが、チャンク管理システムで行き詰まっています。より具体的には、最適なレンダリングのために、ブロック ID の整数の 3D 配列であるチャンクをオクツリーに変換しようとしています。

これまでのところ、システムは機能していますが、非常に非効率的です。

これは 16*16*16 チャンクのスクリーンショットで、y=8 より下のすべての位置が 1 に設定されています (赤いブロック)。

https://raw.githubusercontent.com/ninthworld/Octree/master/screenshot0.png

OctNode ジェネレーター コードにデバッガーを追加して、チャンク配列へのアクセスに必要な回数を調べたところ、8392704が返されました。

8 つの子ノードを生成するためだけに、チャンク配列に 800 万回以上アクセスしました。

y=4 未満のブロックのみを持つようにチャンク配列を設定すると、プログラムはほぼ 30 秒間黒い画面になり、デバッガーは1623199744の配列アクセスを返します。

68 個の子ノードを生成するためだけに、16 億回を超える配列呼び出し。

明らかに、配列呼び出しの数を減らす必要がありますが、それは確かですが、どうやってそれを行うのかわかりません。ソース コード全体を見たい場合は、プロジェクトの github ページを次に示します。

私のコードの重要な部分は次のとおりです。

Main.java

OctNode.java

残念ながら、それが私が説明できる最善の方法です。同じことをより簡単かつ迅速に行う方法を指摘できれば、それはすばらしいことです。

主に C++ で記述された iOS および Android 用の 3D マップ レンダラーに取り組んでいます。オクツリーを使用して、ファイルからデータを読み込んで保存します。

これまでのところすべて問題なく、数平方キロメートルの小規模から中規模のマップのレンダリングはすべてクールで、スムーズに動作します。しかし今、国全体や大陸のサイズなど、マップのサイズを大きくしたいと考えています。

Octree の実装とチュートリアルはたくさんありますが、これまでのところ、大規模なデータ セットの遅延読み込みとツリー構築を効率的に処理する方法を説明するチュートリアルは 1 つも見つかりませんでした。

最適なのは、すでにそれを行っている無料の利用可能な Octree ライブラリが存在することです。あなたはそのようなことを知っていますか？それ以外の場合、一般的にオクツリーへの遅延読み込みを実装するにはどうすればよいですか?

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

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

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

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

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