algorithm - 最近傍探索のための Octree のアルゴリズム

Question

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

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

Answer 1

ここで octree を使用する必要はありません。オクトリーは逆の問題 (グリッド ポイントが与えられ、最も近い粒子を見つける) には役立ちますが、ここではまったく役に立ちません。

グリッド セルのサイズが であると仮定すると(a, b, c)、そこから最も近いグリッド ポイント(x, y, z)は です(a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5))。