やりたいことは、色々なモデルを試すこと。プログラムは遅くたって最低限動けばよし！次はモデルをいじるぞ！
っと思っていたのですが、プログラムを眺めてると、さすがに全て粒子で、全ての粒子に対する当たり判定するのは、無駄だよな～っと気になりだし、何となくアルゴリズムを考えるようになったところに、下記の論文を見つけました。
GPUによる近接相互作用に基づく粒子計算の近傍探索手法
https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=107323&file_id=1&file_no=1
アルゴリズムの中身がけっこう丁寧に書いてある。これなら実装できそうだ。っと思ってしまったからには・・・やりますか。
書かれてる手法は、大きく2つ。
一つは領域を格子に分割して、格子内の粒子を登録しておき、自身がある格子とその周辺の格子内の粒子に対してのみに当たり判定を行う方法。上の論文では、セル分割法と名付けられている。オーソドックスな方法みたいで、他の文献では、格子判定法だとか色々なネーミングがありました。
もう一つは、一度は全粒子に対して当たり判定をして、その際、近くの粒子を登録しておき、一定期間は、登録した粒子に対してのみに当たり判定を行う方法。上の論文では、粒子登録法とネーミングされています。
どちらも一定条件の元、情報を更新しなくてはいけない。セル分割法は粒子の数だけの一回ループで情報更新できるのに対して、粒子登録法は粒子数の2乗ループが必要になるので時間がかかる。しかし、粒子登録法はセル分割法に比べ、登録する候補粒子を少なくすることができる。また、論文では書かれていないけど、わざわざ全体の情報を更新しなくても、動きのある粒子に対してのみ情報を更新させることもできるはず。
メモリ消費量の違いもあるけど、今のところメモリは問題ない（多分、2次元なら問題にならない）ので考えません。
論文を見る前に、自分で思いついたのは、粒子登録法の方です。通常、土の解析だと激しく動く箇所は一部だから、相対移動量とか拾って、上手いこと更新範囲と回数を抑えるアルゴリズムにすれば、いい感じになるんじゃね？っと思ったのだけど、その更新判定の部分を作るの大変そう。
論文では、セル分割法と粒子登録法の両方を組み合わせたハイブリッドなやり方が書かれてあり、考えるの面倒だから、その通りやってみることにしよう。
ってことで、まずセル分割法を導入してみました。とりあえず、登録情報は毎回更新する仕様。
よしよし、結果は同じだな。さて、計算速度は？