私は高性能クラスターで理論化学の仕事をしており、多くの場合、分子動力学シミュレーションが関係しています。私の研究が取り組む問題の 1 つは、テスト粒子が衝突する可能性のある N 次元 (通常は N = 2 ～ 5) の超球体の静的フィールドに関係しています。迅速な衝突検出を行えるように、球体のフィールドを表すために使用するデータ構造を最適化 (つまりオーバーホール) しようとしています。現在、N メンバーの構造体 (中心の座標ごとに double) へのポインターの単純な配列と最近傍リストを使用しています。oct-tree と quad-tree について聞いたことがありますが、それらがどのように機能するか、効率的に実装する方法、または 1 つを使用して高速な衝突検出を行う方法についての明確な説明は見つかりませんでした。私のシミュレーションのサイズを考えると、メモリは (ほとんど) オブジェクトではありませんが、サイクルはオブジェクトです。
1356 次
5 に答える
4
問題に対してこれにどのようにアプローチするのが最善かは、説明していないいくつかの要因によって異なります。 - 多くの粒子衝突計算に同じ超球配置が使用されるか? - 超球は均一なサイズですか? - 粒子の動きは何ですか (直線/曲線など)、その動きは球の影響を受けますか? - 粒子の体積はゼロだと思いますか?
線と点の間の最も近い点を見つける比較的高速な計算になるため、粒子には単純な直線の動きがないと仮定します。これは、どのボックスの線を見つけるのとほぼ同じ速度になる可能性があります。と交差します (n ツリーのどこを調べるかを決定するため)。
多くの粒子衝突に対して超球の位置が固定されている場合、ボロノイ分解/ディリクレ テッセレーションを計算すると、空間内の任意の点でどの球が粒子に最も近いかを後で正確に見つけるための高速な方法が得られます。
ただし、octrees/quadtrees/2^n-trees に関する元の質問に答えるには、n 次元で、関心のある空間領域を含む (ハイパー) キューブから始めます。これは 2^n ハイパーキューブに分割されます。内容が複雑すぎると思われる場合。これは、リーフ ノードに単純な要素 (たとえば、1 つの超球重心) だけが存在するまで再帰的に続きます。n ツリーが構築されたので、パーティクルのパスを取得し、それを外側のハイパーキューブと交差させることにより、衝突検出に使用します。交差点の位置は、ツリーの次のレベルの下にあるどのハイパーキューブを次に訪問するかを示し、そのレベルのすべての 2^n ハイパーキューブとの交差点の位置を決定し、リーフ ノードに到達するまで下に進みます。リーフに到達すると、パーティクル パスとそのリーフに保存されている超球との間の相互作用を調べることができます。衝突がある場合は完了です。それ以外の場合は、現在のハイパーキューブ リーフからパーティクル パスの出口点を見つけ、次にどのハイパーキューブに移動するかを決定する必要があります。衝突が見つかるか、全体的なバウンディング ハイパーキューブから完全に離れるまで続行します。
ハイパーキューブを終了するときに隣接するハイパーキューブを効率的に見つけることは、このアプローチの最も難しい部分の 1 つです。2^n ツリーの場合、サメットのアプローチ {1, 2} を適用できます。kd ツリー (バイナリ ツリー) については、{3} セクション 4.3.3 でアプローチが提案されています。
効率的な実装は、各ハイパーキューブからその子ハイパーキューブへの 8 つのポインターのリストを格納し、ハイパーキューブがリーフの場合は特別な方法でマークする (たとえば、すべてのポインターを NULL にする) だけの簡単なものです。
空間を分割して四分木 (n-木に一般化できます) を作成する方法の説明は、Klinger & Dyer {4} にあります。
他の人が言及しているように、任意の数の次元への拡張はより簡単であるため、kdツリーは2 ^ nツリーよりも適している可能性がありますが、より深いツリーになります。また、kd ツリーを使用して超球体のジオメトリと一致するように分割位置を調整することも簡単です。上記の 2^n ツリーでの衝突検出の説明は、kd ツリーにも同様に適用できます。
{3}集合論的に定義されたモデルの凸包の生成、連結成分のラベル付け、および最小距離の計算、Dan Pidcock、2000
{4}正規分解を使用した画像表現の実験、Klinger、A.、および Dyer、CR E、Comptr。グラフィックスと画像処理 5 (1976)、68-105。
于 2008-09-17T09:29:41.470 に答える
1
N次元空間をより迅速に検索できるkd-treeを実装したいようです。Stony Brook Algorithm Repositoryには、さらに詳しい情報と実装へのリンクがあります。
于 2008-09-16T22:50:00.947 に答える
1
あなたのフィールドは静的であるため（ハイパースフィアが動かないことを意味していると思います）、私が知っている最速のソリューションはKdtreeです。
自分で作成するか、次のように他の人のものを使用できます:
http://libkdtree.alioth.debian.org/
于 2008-09-16T22:53:03.153 に答える
0
クワッド ツリーは 2 次元ツリーで、各レベルでノードに 4 つの子があり、それぞれが親ノードの領域の 1/4 をカバーします。
Oct ツリーは 3 次元ツリーで、各レベルでノードに 8 つの子があり、それぞれが親ノードのボリュームの 1/8 を含んでいます。これを視覚化するのに役立つ画像を次に示します: http://en.wikipedia.org/wiki/Octree
N次元交差テストを行っている場合、これをNツリーに一般化できます。
交差アルゴリズムは、ツリーの最上部から開始し、テスト対象のオブジェクトと交差する子ノードに再帰的にトラバースすることで機能します。ある時点で、実際のオブジェクトを含むリーフ ノードに到達します。
于 2008-09-16T22:49:01.947 に答える
0
オクトリーは、球を中心で指定できる限り機能します。これは、ポイントを 8 つの子を持つ立方体領域に階層的にビンに入れます。八分木データ構造の近傍を計算するには、八分木のどの立方体領域が球内にあるかを計算するために、球と交差する立方体の計算を行う必要があります (見た目よりもある程度簡単です)。
最近隣を見つけるということは、複数の子が取り込まれ、周囲のすべてのノードが含まれるノードが得られるまで、ツリーを上に戻ることを意味します (これにより、クエリがすべての側面を取得することが保証されます)。
記憶から、これは球と立方体の交差の (やや単純な) 基本アルゴリズムです。
私。キューブ内の中心です (これは同名の状況になります)
ii. 立方体のいずれかの角が中心から半径 r 以内にあるか (球内の角)
iii. 立方体の各面 (面のどちら側に中心があるかを計算することで、面の一部を削除できます) について計算します (これはすべて 1 年目のベクトル演算です)。
を。球の中心に向かうサーフェスの法線
b. 球の中心から法線とサーフェスの平面との交点までの距離 (弦は立方体のサーフェスと交差します)
c. 平面の交点が立方体の側面内にある (立方体への弦交点の 1 つの条件)
iv。弦のサイズを計算します (通常の長さと球の半径の比の Cos^-1 の正弦)
v. 線上の最も近い点が弦の距離よりも短く、点が線の両端の間にある場合、弦は立方体のエッジの 1 つと交差します (弦は、エッジの 1 つに沿ってどこかで立方体の表面と交差します)。
少し記憶が曖昧ですが、これは octee データ構造を使用した球状領域を含む状況で私が行ったことです (何年も前)。他のポスターの一部が示唆しているように、KD-trees もチェックしたいかもしれませんが、最初の質問は私がしたことと非常に似ています。
于 2008-09-17T09:42:03.483 に答える