vvvvのVL.Fuseに近傍探索を高速化するSpatial Hash + NeighborGridという機能を見つけたのですが、使い方の資料があまり見当たらなかったので、ここに残したいと思います。

要件

• vvvv gamma 6.6
• VL.Fuse 1.0.3 beta6

今回サンプルとして使うプロジェクトデータはこちらになります。

Plexus With Spatial Hash.vl

近傍探索とは

近傍探索（パーティクルシステムの）とは、ある点とそれに近い距離の点を探すアルゴリズムのことです。

一番素直な実装は全数検索で、自分以外の点すべての距離を計算する方法です。例として10000パーティクルの近傍探索を行う場合は、10000x10000=1億回の距離計算を行わなければならず、PCのリソース的にも現実的ではありません。

それを解決するために、あらかじめデータを加工して最適化しておき、近くにある点を素早く見つけられるようにするのが、近傍探索アルゴリズムです。

VL.Fuseでは近傍探索アルゴリズムに**Spatial Hash（空間ハッシュ）**を用いているようです。GPUの並列処理に向いたアルゴリズムで、いくつかの制約はありますがとても高速に動作します。

SpatialHash（空間ハッシュ）アルゴリズムを手順に沿って簡単に説明すると、

• 空間をグリッド状に分割して、空間に番号を割り当てる。
• パーティクルに今いるグリッドの番号を登録しておく。
• パーティクルを整理して、グリッドの番号だけでパーティクルたちを呼び出せるようにしておく。