SPH Linked-list searchの修正と速度比較実験

先日2次元SPHシミュレーションにLinked-list Searchという近傍探索法をC++で実装して、うまくいかなかったという記事を書きましたが、大学の教授に尋ねたら私の考え方が間違っていたということがわかりました。

セルごとにlinked-listを作るところまでは良かったのですが、どうやらその後に、ひとつのセルの周辺のセルを含めて近傍探索しなければならないのをひとつのセル内のみで近傍探索していたためにセルの境界線で粒子が重なる問題が起こっていたようでした。

１次元なら周辺セルを含める3個のセル, ２次元なら9個のセル, ３次元なら27個のセルを近傍探索するようにします。

２次元の場合はひとつのセルに属する粒子の近傍探索は下図のような赤い領域(セル9つ分)で行います。


これを実装してみたところ、無事、下図のように境界線でパーティクルが重なることはなくなりました。しかもAll-pair Searchに比べるとかなり高速です。



ついでに処理時間を計測して比較してみました。

まず、Visual Studioでの最適化オプションを最大にして3045個のパーティクルを1000ステップ計算させるのにかかった処理時間を比較しました。



次に最適化オプションなしでコンパイルして3045個のパーティクルを30ステップ計算させてみました。


最適化をしないと６倍以上速くなる結果になりました。最適化をすると処理速度差は縮まって2.5倍程度。

近傍探索をするセルが大分増えたので速度はどうなるかと心配でしたが、All-pair searchに比べれば十分速い結果になったので良かったです。

それと、コンパイラの最適化はすごいなぁと思いました。今回実験をしてみて粒子シミュレーションを行う時に最適化をしてコンパイルするときとしないときとでは速度が何倍も変わってくることをすごく実感できました。

普段、実行速度が速くなるように自分なりに工夫をしてコードを書いているつもりなのですが、コンパイラの最適化でこんなに実行速度が変わってしまうのです。下手に自分で速くしようとすると、逆にコンパイラの最適化の妨げになって結果的に遅くなることはあるので、良いコードを書くためにはもっとコンパイラの最適化を行う挙動を理解する必要があります。

MayaのMELやExpressionなんかはその場で命令を解釈して実行してゆくインタープリター言語なので、複数の命令を超えての最適化は行えません。
この大きな最適化の恩恵を受けることができないと考えると、Expressionで頑張って複雑なことをやろうとするのは頑張り損な気がします。

とは言ってもプラグイン開発は手続きを書くのが面倒。パーティクル用のMaya plug-inの開発テンプレートみたいのを作っておくと即座にシミュレーションなどの計算をMayaに反映させられるので、暇ができたら作っておきたいです。

関連記事