トップ | puarts.com
メモ  |  制作記  |  開発記  |  日常の記録  |  デジタルコンテンツ制作  |  ファイアーエムブレム  |  ゲーム  |  C/C++  |  C#  |  PC/ソフトウェア  |  Web 開発  |  スクリプト言語  |  その他プログラミング  |  
「SPH」に関連する記事一覧

0  

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

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

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

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

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


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



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

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


Algorithm time (seconds)
All-pair search 31.03
Linked-list search 12.61

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

Algorithm time (seconds)
All-pair search 19.27
Linked-list search 2.88

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SPH法の2次元粒子シミュレーションプログラムを作ってみる

2011/07/27
C++ SPH 
前から粒子シミュレーションに興味があったのでSPH(Smoothed Particle Hydrodynamics)法という粒子法を使った2次元の粒子シミュレーションのプログラムをC++で作ってみました。


大雑把にやっていることは、それぞれ1つ1つのパーティクルに対してある距離内にいる周辺パーティクルとの距離から作用する力を計算して速度を求め、次のフレームの位置座標を計算していくという流れです。

GUIとかマウス操作とかにはQtを使っています。

ちょっとソースコードはごちゃごちゃしているので整理しないとアップできないですが、ネット上にすでにたくさんソースコードつきのプログラムがアップされているので検索すればすぐに見つかるかと思います。

こっから3次元に拡張してMayaのプラグインとかにしてパーティクルアニメーションに使えないかと考えています。3次元になると一気に大変になるという話は聞いていますが、頑張って3次元も自分で書いてみたいです。
0  

にほんブログ村 ゲームブログ ファイアーエムブレムへ にほんブログ村 デザインブログ コンピュータグラフィックスへ

0.0233 sec

Copyright(C)2006-2018 wsp All Rights Reserved