剛体球衝突アルゴリズムが少し分かるようになる記事

【2020/8/6追記】「LS-DYNAのCPMの解明のため」とありますが、調べたところ、LS-DYNAではこの記事で紹介した前提(完全弾性衝突)が成立していませんでした。2物体の**Internal energyは保存**されるものの、**運動量及びTranslate kinetic energy(運動エネルギー)は保存されていません**。
つまり何が言いたいかというと、本記事はLS-DYNAのCPM法の説明にはなりません。純粋に剛体球衝突アルゴリズムとしてお読みいただければと思います。

----

LS-DYNAの[Corpuscular Particle Method (CPM)](http://public.beuth-hochschule.de/~kleinsch/Expl_FEM/2007_CPM_LSDyna.pdf)を使用しているのですが、複数種ガスの混合時の粒子数の比の影響(*TotalのInternal energyに対するTranslate energyの比が粒子数比で異なる→Part/Particle PressureやCMPsensorの値が粒子数比で変化する。(Airbag Pressureは粒子数比によらず一定)*)を考察をしたいと思い、かなり目標から手前の内容ですが、剛体球衝突について勉強しました。
何番煎じかわかりませんが(Qiitaでも@yotapoonさん、@NatsukiLabさんがそれぞれ記事を書かれています)、自分なりに理解したことをまとめたいと思い書いています。

# 1. 剛体球/円盤衝突アルゴリズムとは
**下図のようなシミュレーションを行う手法です。**(図は[WikipediaのKinetic theory of gases](https://en.wikipedia.org/wiki/Kinetic_theory_of_gases)より引用) 調べてみるとゲームプログラミング等でも使用されているようです。
気体分子運動論の解析でも使用されており、[wikipediaのBaltzmann distributionの記事](https://en.wikipedia.org/wiki/Maxwell%E2%80%93Boltzmann_distribution)では粒子の衝突の結果、粒子の速度分布がMaxwell-Boltzmann分布に収束してゆくことが確認できます。
自分のモチベーションとしては、気体分子の速度分布を算出し、ガスの混合時に各ガスの運動エネルギーがどう変化してゆくか理解したいということがあります。

![Translational_motion.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186356/f6198fc9-cd49-1235-02e8-110b1513e018.gif)

#2. 前提と数学的理解
まず、下記の2つが前提となります。特に大きさを持つというのがランダムな運動を実現するキモとなります。
1) 球/円盤は直径・速度・質量を持つ
2) 球/円盤は等速度直線運動をする=衝突以外で速度は変化しない

また、本記事は[thermosim](https://github.com/pierrethibault/thermosim)というgithubにアップされていたソースを対象に解説します。
このソースは、いわゆるTime-Step型のシミュレーションを採用しています。(こちらが詳しいです。https://qiita.com/NatsukiLab/items/476e00fea40b86ece31f)
なお、参考文献で示した記事でも同様/類似の手法が記載されていたため、一般的な手法と言えそうです。

###2.1.衝突判定
粒子*i*. *j*の時間$t$での座標を$r(t)$, 速度を$v(t)$,質量を$m$、直径を$d$とします。
まず、下記の式で、現時点で**既に**衝突している粒子の一覧を取得します。

```math
|r_i(t) - r_j(t)|\leq\frac{1}{2}(d_i+d_j)
```

既に衝突しているというのがキモで、現在のステップ(時間$t$)で接触した粒子を接触前まで"巻き戻し"、巻き戻された時点での速度と座標から、速度ベクトルを更新します。（前ステップでは接触していないことは保証されています）

衝突している粒子がわかったら、次はいつ衝突したのかを計算します。
まず、相対速度、相対位置ベクトルを下記のように定義します。なお、時間$t=0$を前回のステップの時間とします。

```math
v_{ij}=v_i-v_j\\
r_{ij}=r_i(0)-r_j(0)\\
```

粒子は等速直線運動をするので、前ステップから衝突までの時間を$t_c$として、衝突時の座標は下記のように示されます。

```math
r_i(t_c)=r_i(0)+v_i(t)・t_c\\
r_j(t_c)=r_j(0)+v_j(t)・t_c\\
```
以上から、$|r_i(t) - r_j(t)|=\frac{1}{2}(d_i+d_j)$となるときの時間$t_c$は下記のように示されます。(実際、前ステップの時間を0としているので、$tc$は前ステップから衝突までの時間差分と同じ意味です。)

```math
t_c=\frac{-r_{ij}・v_{ij}-\sqrt{(r_{ij}・v_{ij})^2-v_{ij}^2(r_{ij}^2-0.25(d_i+d_j)^2)}}{v_{ij}^2}
```
単純に上記は$|r_i(t) - r_j(t)|=\frac{1}{2}(d_i+d_j)$の両辺を2乗すると、$t_c$についての2次方程式となるので、解の方程式から導かれます。なお、解は2つあるのですが、+の方の解(大きい方の解)は粒子が貫通後に接触するまでの時間です。

### 2.2衝突後の速度の更新
衝突前後でも[物体の重心は等速直線運動をする](http://www.wakariyasui.sakura.ne.jp/p/mech/unndouryhzn/jyuusinnunn.html)性質を利用して、重心系の速度とi,jの相対速度を利用して、衝突後の速度を算出します。
(ここではプログラムに合わせて説明していますが、参考文献(特に[Wikipedia](https://en.wikipedia.org/wiki/Elastic_collision))の記事の方が直感的な理解がしやすいです）

衝突前後で運動量が保存されるので、

```math
m_iv_i+m_jv_j=m_iv_i'+m_jv_j'
```
となります。反発係数を$e$とすると、

```math
e=-\frac{v_i'-v_j'}{v_i-v_j}
```
となるので、これらより、

```math
v_i'=V-e\frac{m_j}{m_i+m_j}v_{ij}\\
v_j'=V+e\frac{m_i}{m_i+m_j}v_{ij}\\
```
ここで、

```math
V=\frac{m_iv_i+m_jv_j}{m_i+m_j}
```
で、重心の速度を意味します。

なお、完全弾性衝突時($e=1$)の関係の図は下記のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186356/c064ff41-b992-f68c-24f0-895713341507.png)

*`dvf`と`dv`は3章でのソースコード中の変数です。コードだとわかりにくい。。

#3. 実装 ([thermosim](https://github.com/pierrethibault/thermosim)のthermosim.py/def collideより)
## 3.1. 衝突判定
```python:thermosim.py
    from scipy.spatial.distance import squareform,pdist
    # Find colliding particles
    D = squareform(pdist(self.r))
    ind1, ind2 = np.where(D < .5*np.add.outer(self.d, self.d))
    unique = (ind1 < ind2)
    ind1 = ind1[unique]
    ind2 = ind2[unique]
```
self.rとself.dにはそれぞれ座標と直径を収めたnp.arrayで、`squareform(pdist(self.r))`で現時点での粒子間の距離を、`.5*np.add.outer(self.d, self.d)`で粒子が接するときの距離を算出します。それぞれ、粒子の数をnとするとnxnのarrayを返します。
`unique = (ind1 < ind2)`としているのは、上三角の成分(対角は除く)のみが必要な情報なためです。

## 3.2. 衝突時の座標の算出

```python:thermosim.py
            ru = np.dot(dv, dr)/ndv
            ds = ru + sqrt(ru**2 + .25*(d1+d2)**2 - np.dot(dr, dr))
            if np.isnan(ds):
                1/0

            # Time since collision
            dtc = ds/ndv

            # New collision parameter
            drc = dr - dv*dtc
```
`dtc`は2.1の$-t_c$と同じ意味かつ、同じ算出方法です。`drc`が衝突時の相対位置ベクトルのはず。


## 速度の更新

```python:thermosim.py
            # Center of mass velocity
            vcm = (m1*v1 + m2*v2)/(m1+m2)

            # Velocities after collision
            dvf = dv - 2.*drc * np.dot(dv, drc)/np.dot(drc, drc)
            v1f = vcm - dvf * m2/(m1+m2)
            v2f = vcm + dvf * m1/(m1+m2)
```
`dvf`が何を意味するかは2章の衝突時の図を参照。

## 座標の更新

```python:thermosim.py
            # Backtracked positions
            r1f = r1 + (v1f-v1)*dtc
            r2f = r2 + (v2f-v2)*dtc
```
これ、`dtc`でいいのか？ちょっと考え中です。

#参考文献
- https://github.com/pierrethibault/thermosim
- [剛体球の大規模数値計算をしたい人生だった](https://qiita.com/NatsukiLab/items/476e00fea40b86ece31f), @NatsukiLab
- [大規模剛体球系の高速シミュレーション](https://qiita.com/yotapoon/items/63e4bd6a0da40de97abc), @yotapoon
- [剛体円盤分子動力学シミュレーションにおける大規模計算と高速化の手法](https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/96587/1/KJ00004707458.pdf), 礒部 雅晴, 物性研究, 72(1), pp.21-41,1999-04
- [運動量保存の法則が成り立つ場合の重心の運動](http://www.wakariyasui.sakura.ne.jp/p/mech/unndouryhzn/jyuusinnunn.html)
- [２つのボールの衝突](http://www.asahi-net.or.jp/~uc3k-ymd/Sketch/Ball/ball02.html)
- [Wikipedia: Elastic collision](https://en.wikipedia.org/wiki/Elastic_collision)