Zenn
🔳

【vvvv】VL.FuseのNeighborGridで近傍探索の高速化

2025/03/07に公開
vvvv
tech

image.png

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

要件

  • vvvv gamma 6.6
  • VL.Fuse 1.0.3 beta6

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

file

近傍探索とは

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

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

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

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

image.png

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

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

という流れになります。

実際に探索するときには、パーティクルがあるグリッド番号から、同じグリッドにあるパーティクルを読んできたり、近くのグリッドを探すだけでよくなり、計算効率がとても良くなります。

以下、より詳細な解説と資料になります。

NeighborGridの使い方

VL.FuseにはFuse.Compute.NeighborGrid に近傍探索アルゴリズムの機能が置いてあります。

Helpも無くノードも最低限しか無いので、一見すると使い方が分かりづらいのですが、基本的にはFor(fuse)と似たような感覚で使っていくことができます。

Grid内のIndexノードはIndex (Neighbor)で、SpatialHashによって最適化されたIndexにアクセスすることができます。

image.png

image.png

シンプルにパーティクル間の距離を測るノードを組んでみました。

まずはFor (Fuse) を使った例です。

全数検索になるので_、各コアで1000回のループが走ってしまい_、処理が重くなる原因になります。

image.png

こちらはNeighborGridを使った例です。

  • GridCellに現在いるGridのHashが入っています
  • 今いるグリッドに近いパーティクルだけを集めた配列でForループを回しているイメージです。
  • Indexノードが近くにあるパーティクルの番号を返してくれるので、計算量が少なく済みます。

image.png

実装例

近いパーティクル同士を線で繋ぐビジュアル（通称Plexus）を実装してみました。

image.png

3万パーティクルほどの近傍探索を120FPSほどで処理できている様子がわかります。グリッドは16分割四方で行っているので、各グリッドごとのパーティクル数は抑えられて、安定したフレームレートが実現できています。

実装のコアはこんな感じです。

  • 距離計算をして、検索範囲内のパーティクルに線分を追加するコードになります。
  • AppendBufferにて、線の分のBufferを追加していく実装になっています。

image.png

注意点

4分割四方で区切ると見るからにパフォーマンスが下がります。

これはグリッドごとのパーティクルの数が多いため、各パーティクルごとの探索するパーティクル数が多くなるためです。

image.png

また、パーティクルの分布に偏りが出ると、グリッド分割の効率が悪くなり、パフォーマンスが下がります。

image.png

また、範囲外については無視されます。

image.png

また、分割グリッド数が多くても、CPU側に負荷がかかりハッシュ化に時間がかかったり、正常に探索できなくなるので、これもよくありません。

image.png

まとめ

この近傍探索はコンピューターグラフィックスによく出てくるアルゴリズムで、高速な近傍探索が実現できれば、表現の幅が大きく広がります。ボロノイ、Boidsシュミレーション、粒子法の流体シュミレーションなど、近傍探索を使う例は挙げればキリがないです。

しかし、vvvv界隈に近傍探索の資料が乏しく、実装に苦労した思い出があります。特にVL.Fuseにはドキュメントが無く、Example等を探して使い方を探っていくほかなく、下のVL.Fuseリポジトリ内のR&DフォルダにあるExampleを見つけるまでは、使い方が全くわかりませんでした（汗

しかし、大量のパーティクルを効率よく捌いていければ、圧巻の表現（頂点数の暴力）をリアルタイムで生み出すことも可能なので、引き続き勉強していこうかと思います。

GitHubで編集を提案

Discussion