常に動いている数百の粒子間で n 体シミュレーションを実行するために必要なアプリケーションをコーディングしています。アプリケーションにはリアルタイム要件があるため、シミュレーションを実行するアルゴリズムは高速である必要があります。
私はこの問題についてかなりの量の調査を行い、Barnes Hut アルゴリズムが私のニーズに最も適しているという結論に達しました。大きな粒子セットには非常に効率的であるようです。
http://arborjs.org/docs/barnes-hut は、アルゴリズムがどのように機能するかについて非常に明確な説明を提供しましたが、タイトルが示すように、反復ごとにツリーを再作成する必要があるかどうかを知りたいです。シミュレーションで使用されるパーティクルは、常に動的に動いています。また、ツリーを再作成する必要がある場合、(処理能力とメモリの点で) 最も効率的な方法でそれを行うにはどうすればよいでしょうか。
この質問への回答はかなり遅れています。当時、私はこの問題に取り組んだことがなかったと思います。しかし、私はしばらくの間それを調べてきたわけではありません。いくつかの洞察を共有することができます. @greedybuddhaが言っていることはほとんど正しいですが、それらはすべての時間ステップでツリーを完全に作成しないようにするためのトリックとテクニックです. いつものように、独自のオーバーヘッド (メモリ フットプリントなど) と必要なトレードオフを伴うこれらの手法を行う必要があります。また、すべての状況に適用できるとは限りません。
特定の深さの octree を処理するのに十分なメモリを前もって割り当てます。すべてのタイムステップが終了したときにのみ、メモリの割り当てを解除します。たとえば、使用するすべての n 体の入力データ セットについて、オクツリーがたとえば 10 の深さを超えることはないことがわかっているとします。その場合、オクツリーが持つ最大ノード数を簡単に把握できます(通常は等比数列の合計です)。すべての octree ノードに対して少しの簿記 (各ノードの有効な子インデックス) を行うことで、タイムステップごとに octree ノードを割り当て/割り当て解除する必要なく、このバッファーを簡単に再利用して octree ノードを埋めることができます。明らかに、ここで考えられるオーバーヘッドは、大量のメモリを浪費している可能性がありますが、タイムステップごとに割り当て/割り当て解除を行わないことでパフォーマンスが向上することです.octreeレベルの数を制限する通常の方法は、リーフノードごとに複数のボディを許可することです(最後のレベルのoctree または octree グリッドの最小セル サイズ)
必要な場合にのみ新しい Octree を作成する: ある一連のタイムステップ (バースト) で octree が変化せず、その後変化してパターンが繰り返される状況を考えることができます。これは、タイムステップ バースト中に物体の位置がわずかに変化し、そのバースト中に octree 構造が同じままである場合にのみ発生する可能性があります。そして、どのような状況で体がゆっくり動くか - 選択されたタイムステップサイズがかなり小さい場合、体に加えられる力 + 初期運動量は小さい. このようなバーストを動的に把握する方法は難しい問題です。これはよりトリッキーな手法であり、これを行う簡単な方法がわかりません。これには、タイムステップの粒度、ボディの初期速度/加速度、およびボディが扱う力の種類に関する洞察が必要です。