ボクセルベースの流体を格納する octree があります。流体をシミュレートするとき、現在のノードの周囲の葉にアクセスする必要があります。そのような検索を実装するにはどうすればよいですか?
ノードがその親ノードへのポインターを格納していると仮定できます (おそらく他のデータが必要ですか?)
2507 次
1 に答える
7
各 octree ノードも octree (およびその深さ) に 3D インデックス [1] を保持していると仮定します。
- クエリ ノードの隣接ノードの 3D インデックスを生成します (各次元でクエリ ノードの 3D インデックスを単純にインクリメント/デクリメントします)。
- 潜在的な各隣接ノードについて、生成された 3D インデックスを使用してルートから octree をトラバースし、各ノードで子を持つパスを選択します。
現在のノードがより深い深さでのみ近隣ノードを持っている場合 (octree が完全ではない)、2. で実行されたトラバーサルは、クエリ ノードの深さ以下の octree で到達可能な最大の深さで停止します。
ノードが親へのポインターを保持している場合、2. まず現在のノードとその各隣接ノードの最も低い共通の祖先を見つけ (これは、3D インデックスで最も長い共通のバイナリ プレフィックスを見つけることによって行われます)、開始することで改善できます。この先祖ノードからのみ隣人に到達するためのトラバーサル。
[1]: 3D インデックスは、単純に octree 内のノードの x/y/z 座標です。たとえば、ルートの 8 つの子には、2 進数 1 桁の 3D インデックスがあります (これらのノードは octree の深さ 1 にあります): 0/0/0、1/0/0、0/1/0、1/1 /0, ... ルートの 64 個の孫には、2 桁の 2 進数の 3D インデックスがあります (これらのノードは octree の深さ 2 にあります): 00/00/00, 01/00/00, 10/ 00/00、11/00/00、00/01/00、01/00/00...
于 2014-02-02T17:16:03.127 に答える