SPHの近傍探索法Linked-list algorithmを実装してみる

以前作ったSPH法の２Dシミュレーションプログラムの近傍探索アルゴリズムをもっと高速なものにしようとLinked-list algorithmという手法を使ったプログラムを作ってみました。

私が英語のSPHの参考書を解釈した限りだと、この手法は領域をパーティクルの影響範囲に適したサイズのセルに分割して、領域ごとにパーティクル同士のlinked-ilstを作成して高速化するという手法のようです。

総当りで調べるAll-pair search法がO(N^2)なのに対して、この手法はO(N)なのでパーティクルの数が増えるほど、その速度差は顕著になるはずです。

実際プログラムを作ってみて動かしてみるとめちゃくちゃ速い。Qtのペイント系のGUIライブラリを使ってリアルタイムで描画しようとした場合、All-pair searchは300くらいの粒子数でのろのろになってしまったのですが、Linked-list algorithmの方は3000超えてもまだ余裕がありました。

しかし、一つ問題が発生してしまいました。下図のように分割したセルの形がパーティクルに現れてしまいました。

考えてみれば、セル内のみで近傍探索をして力を計算しているのだから、セルの境界付近にいる粒子は隣のセルから近い位置にいたとしても影響を受けず、結果的にパーティクルが重なってしまう現象が起こるのは当然のことです。

参考書には分割したセルを場合により、くっつけたりしても良いと書いてあったので、そこに解決のヒントがあるのではないかと思いましたが、よく考えれば、例えどんな形の分割領域であろうと境界付近では、こういった問題は発生してしまうのは避けられないのではないでしょうか。

うーん、とりあえず考えても解決策が見つからなかったので、もっとよく調べるか誰かに聞くかする必要があります。

関連記事