当たり判定に使うミンコスキー差を可視化した

## はじめに
皆さん、**当たり判定** はご存知ですか？
主にゲームや物理シミュレーションで行われる、「二つのオブジェクトが衝突しているかどうか判定する」アルゴリズムのことです。

当たり判定には色々ありますが、有名なものに **GJKアルゴリズム** があります。
これは、凸型(簡単に言うと凹みがない)多角形(ポリゴン)なら何でも当たり判定が出来てしまうアルゴリズムです。

その **GJKアルゴリズム** の **コア** として、 **ミンコスキー差** が登場します。

## ミンコスキー差って？
ミンコスキー差は、まず言語で説明すると「二つのポリゴンの中身にある座標(位置ベクトル)を全部引き算した後の**図形** 」を言います。

例えば、ポリゴン0とポリゴン1のミンコスキー差を出すとします。
ポリゴン0の中に含まれる座標(位置ベクトル)がありますね。

ポリゴン1にも。

これらを **全ての組み合わせにおいて** 引き算します。

つまり、ポリゴン0に内包される位置ベクトル全てを
```math
P_0 \in \vec p_{0, i} (i=0, \cdots)
```

ポリゴン1に内包される位置ベクトル全てで
```math
P_1 \in \vec p_{1, j} (j=0, \cdots)
```

引き算
```python
p = []
for p0 in P0:
    for p1 in P1:
        p.append(p0-p1)

#p全てあわせてミンコスキー差の図形
```

した図形が、 **ミンコスキー差** (上記の`p`で構成される新たな図形)です。

ミンコスキー「差」ですが、扱っているのが位置ベクトルの集合なので、ミンコスキー差は図形を表現しているわけです。

### どうして当たり判定？
ミンコスキー差は当たり判定にとても有効に使えます。

というのも、
**ミンコスキー差の図形が原点を内包していれば、衝突している** という定理があります。

まあこれはちょっと考えればで、原点を含むということは
`p=[0,0,0]`
を含んでいる。
`p`は先ほどの通り`p = p0 - 01`なので
要するに、これが`p0 == p1`を指しているわけです。

これで、
**図形vs図形**
のお話を
**図形vs原点**
の問題にすり替えることが出来るのですね。

:::note warn
もちろん、愚直にミンコスキー差を算出するのは計算量がかなり大きすぎるので、GJKアルゴリズムではベクトルの内積を上手に利用することで、ミンコスキー差の輪郭をとっています。
これについて、後々の記事でご紹介します。
:::

## 可視化した
可視化しました。
![sasa_20231206_122823.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2602537/fe527f1b-9b84-a56b-b94a-7bbefea1e497.gif)

:::note
レポジトリ: https://github.com/konbraphat51/Minkowski_Difference
動作ページ: https://konbraphat51.github.io/Minkowski_Difference/
:::

PCならマウスを動かすだけ、スマホならタッチで、青の図形がその場に移動し、左側の画面で緑と青の間のミンコスキー差が可視化されています。

気づきにくいですが、Canvasの下にボタンがあり、これを押すと他のプリセットのポリコンに切り替わります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2602537/90bbfe20-cdd1-0e44-7d28-f2cc505d9f6c.png)


使用ライブラリは我が自作ライブラリHotSoupScriptです: [初心者向けゲームプログラミングJavaScriptライブラリを作り、講座をした](https://qiita.com/konbraphat51/items/b138683db352afd77714)

仕組みは単純で、単純にCanvas内の全点(10ピクセルごとの間隔で）を走査することで、両図形に内包されている位置ベクトルを算出。
それらを引き算して、出てきたベクトルで新たに赤い四角を書いただけです。

### 分かること
#### 衝突しているとき、原点を含む

![sasa_20231206_122904.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2602537/fbd436d5-7cff-1ac1-21c6-bea8efc01496.gif)

逆に、 **衝突していないとき、原点を含まない** ですね。

#### 凸図形同士のミンコスキー差は凸図形
凸図形同士ならミンコスキー差は凸図形
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2602537/bf27152e-dd89-aeca-849c-0a313dc7fcad.png)

（この組み合わせの）凹図形同士ならミンコスキー差は凹図形になっていますね。（この組み合わせ以外ならどうなるかは未調査です）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2602537/e122ed34-0008-198c-1988-3df7cf9c3bce.png)

「 **凸図形同士ならミンコスキー差は凸図形** 」はGJKアルゴリズムが前提とする定理になっています。
証明はそんなに難しくないのですが、検索すればすぐ出てくるので割愛。

#### 図形が平行移動だけならミンコスキー差も平行移動
![sasa_20231206_122823.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2602537/fe527f1b-9b84-a56b-b94a-7bbefea1e497.gif)

いつ使うか分かりませんが、図形が回転せず平行移動するだけなら、ミンコスキー差が変形せず、そのまま平行移動することがわかりますね。

## 最後に
弊HotSoupScriptライブラリは描画APIを単純化していてこういったビジュアルプログラミングに扱いやすいのでオススメです: https://github.com/konbraphat51/HotSoupScript

GJKアルゴリズムの記事、そのうち投稿します。

:::note
いいね頂けると泣いて喜びます><

この記事を読んでいる方は次の記事を読んでいるかもしれません:
* [初心者向けゲームプログラミングJavaScriptライブラリを作り、講座をした](https://qiita.com/konbraphat51/items/b138683db352afd77714)
* [【ゲーム物理】離散要素法DFMで簡単物理エンジン！①　基礎編](https://qiita.com/konbraphat51/items/157e5803c514c60264d2)
:::