wasm で簡単な物理シミュレーションを書いてみた話 - 衝突判定

Wasm で載せた簡単な粒子のシミュレーションの覚え書きの続き。前の記事はこちら。

出来たものはこちら。

ゲームとかでもでボトルネックになるという衝突判定。wasm でやるからには、性能が大事になるものがいいと思って選んだので、ちょっと力を入れた部分。

描画については自分でどうなるものでもないので、簡単に「点」としての描画で済ませてしまいました。SDL_RenderPoints()という関数があり、これに全粒子のx,y の位置を渡して一度に描画させる。なので、描画自体には処理能力は取られない。数値の方で半径を1px 以上にすれば隙間が出来るので見た目も変わる。

衝突判定を素直にやると、粒子数が５万なら 50k x 50k の、2500m 回、つまり毎度25億回判定を行わなければいけないので、どうしてもここが問題になります。それを回避するのがグリッド化。

4分木法とか色々あるのでしょうけど、今回使ったのはBlazing Fast Neighbor Search with Spatial Hashingに紹介されていた方法。

要は、グリッドに分けて、x, y の値を使ってグリッドの所属を判定し、粒子の x, y の値自身もメモリ上にグリッドに沿って並ぶように並び替えて処理を回す方法。途中、並び替えで使っているのは計数ソートですよね、これ。

最初はグリッドだけを採用して確認し、その後でメモリの並び替えをやりました。

グリッドを使う前は1万粒子以下でしか 60fps は出ませんでしたけど、これで数倍速くなりました。

その後は、SoA 化。最初は粒子１つを表す構造体に位置情報とかを詰めていましたけど、float x[20000]; と全部の粒子の位置情報をまとめて持つように変更。でもこれはそんなには利かなかった気が。

で、スレッド化。
スレッド化は、スレッドプールを作って作業を割り当て。
スレッド化では、作業間でのロックを作りたくなかったので、インターレース方式と言いますか、一度に流す作業は数グリッド行置きに回して、ロックフリーにしました。グリッドの判定は、右と下の段の3セルに自身を合わせた5セル分の粒子を処理すればいいので、次の行を同時に処理しなければロックは考えなくて良いはずということで。
で、上から下までやり終えるまで一応全スレッド待って、次の仕事を振る。

スレッドは、書き込みバッファと読み込みバッファを別々に用意して、影響を排除する方法もありますけど、wasm だともしかしたらスレッドを使えない環境もあるんじゃないかと思って、それは止めました。スレッドが使えない時にバッファを用意して処理すると、相互書き込みより遅くなってしまうので。
なので、A粒子とB粒子の互いで相互書き込み、重複処理なし、インターレース方式のスレッド処理。

なるべく二乗根とかの計算を避けるようにしましたけど、その辺は今のライブラリは効率がいいのかあまり影響なかった気がします。一番効いたのはやっぱりグリッド化だったかなぁと。計算させないのが一番。

SIMD はコンパイラにお任せして深入りなし。

後、粒子半径やグリッドの大きさ、重力の強さとサブステップの回数などは、速度と動きの両方にかなり影響があった。

パフォーマンスの計測は、gprof と perf を使用。