はじめに

この記事は Advent Calender 2017 の 11月10日 の記事です。
スマホで見ると図が見づらかったりするので、パソコンやタブレットでの閲覧を推奨します。

こんにちは、g2と申します。私は最近、コンピュータ上で行う物理シミュレーションにハマっています。複数の剛体の動きをシミュレートする上で重要なのが、「ある2つの剛体が衝突しているか？」という点です。そこで、この記事では特に矩形同士の衝突を判定する方法を解説します。

※任意の凸形状を持った剛体、３次元の剛体については扱いません。また、剛体の密度は一定とします。

まず、矩形（くけい）ってなに？

長方形ってありますよね? アレです。

衝突判定って言われても、ピンとこないんだけど?

例えば、円形同士の衝突判定を考えてみましょう。

ここで行っている判定方法は極めて単純です。

二つの円 $C_1$ と $C_2$ の中心同士を結ぶ線分の長さを $L$、各々の円の半径を $r_1$、$r_2$ とすると、円形剛体間の距離 $D$ は、 $D=L-(r_1+r_2)$ となります(図２の黄色線を参照)。

$D$ が正である限り $C_1$ と $C_2$ は接触はしないので、衝突する条件は

$$D=L-(r_1+r_2)\le 0$$

となります。

矩形同士の衝突判定

円形同士の衝突判定は比較的簡単でしたが、矩形となると同じようには行きません。なぜなら矩形は、円形とは違って回転した時のことを考えなければいけないからです。これによって、判定方法はもっと複雑になります。

矩形の持つ情報

2つの矩形に対する衝突判定が行えると、いくつも矩形が存在していたとしても、それらのうち任意のペアを選んで判定を行えば良いので、ここでは2つの矩形 $R_1$、 $R_2$ を考えます。
衝突判定に必要な矩形の持つ情報は、各々の矩形に対して以下の通りです。

• $\overrightarrow{r_1},\overrightarrow{r_2}$ : 矩形の位置ベクトル(2次元)
• ${\theta }_1,{\theta }_2$ : 矩形の角度
• $w_1,w_2$ : 矩形の幅
• $h_1,h_2$ : 矩形の高さ

衝突してるってどういうこと？

これは当たり前のことなのですが、矩形同士が衝突している時には

ことが言えます。実は、このことは非常に重要です。ここで、2つの矩形が衝突している例(図3)を見てください。衝突には様々なバリエーションがあり、全ての衝突における共通点は存在しないように思えるかもしれません。しかし、$x,y$ 軸が一方の矩形の各辺に並行であるようなローカル座標系 $(x^{\prime },y^{\prime })$ を考えてみると、ヒントが見えてきます。

ここではいくつかのパターンのうち、 $R_1,R_2$ の角が互いに少しめり込んでいる状態を考えます。そしてこの状況を $R_1$ のローカル座標系で考えると、図4のようになります。この図上で定義されている値 $d_0,d_1,d_2,d_3$ は、二つの矩形の位置ベクトル、幅、高さがわかっているため計算することができます。具体的には、

$$\begin{array}{rlc}{d}_0& =& \frac{1}{2}{w}_1\\ & & \\ d_1& =& \frac{1}{2}(|w_2(\overrightarrow{n_1}\cdot \overrightarrow{n_2})|+|h_2(\overrightarrow{n_1}\cdot \overrightarrow{t_2})|)\\ & & \\ d_2& =& |\overrightarrow{n_1}\cdot (\overrightarrow{r_2}-\overrightarrow{r_1})|\\ & & \\ d_3& =& d_0+d_1-d_2\end{array}$$

ただし、

$$\begin{array}{rlc}R(\theta )& =& \left(\begin{array}{rr}\mathrm{c}\mathrm{o}\mathrm{s}(\theta )& -\mathrm{s}\mathrm{i}\mathrm{n}(\theta )\\ \mathrm{s}\mathrm{i}\mathrm{n}(\theta )& \mathrm{c}\mathrm{o}\mathrm{s}(\theta )\end{array}\right)\\ & & \\ \overrightarrow{n_1}& =& R({\theta }_1)\left(\begin{array}{c}1\\ 0\end{array}\right)\\ & & \\ \overrightarrow{n_2}& =& R({\theta }_2)\left(\begin{array}{c}1\\ 0\end{array}\right)\\ & & \\ \overrightarrow{t_2}& =& R({\theta }_2+\frac{\pi }{2})\left(\begin{array}{c}1\\ 0\end{array}\right)\end{array}$$

となります。$d_1$ の計算については疑問を持たれるかもしれませんので説明しておきます。

$d_1$の値は、 $R_2$ の重心から各頂点へ向かう4ベクトル

$$\frac{1}{2}\left(\begin{array}{r}{w}_2\\ h_2\end{array}\right)R({\theta }_2),\frac{1}{2}\left(\begin{array}{r}{w}_2\\ -h_2\end{array}\right)R({\theta }_2),\frac{1}{2}\left(\begin{array}{r}-w_2\\ h_2\end{array}\right)R({\theta }_2),\frac{1}{2}\left(\begin{array}{r}-w_2\\ -h_2\end{array}\right)R({\theta }_2)$$

と $\overrightarrow{n_1}$ ($|\overrightarrow{n_1}|=1$)との内積をとることで、これらを $\overrightarrow{n_1}$ が定める直線(図4における $x^{\prime }$軸)上に射影し、これによって得られた4ベクトルの大きさのうち最も大きい値を求めることで得られます。$|\vec{a}|=|-\vec{a}|$を用いてこれを計算すると

$$\begin{array}{rl}{d}_1& =max\left(\left|\overrightarrow{n_1}\cdot \frac{1}{2}\left(\begin{array}{r}{w}_2\\ h_2\end{array}\right)R({\theta }_2)\right|,\left|\overrightarrow{n_1}\cdot \frac{1}{2}\left(\begin{array}{r}{w}_2\\ -h_2\end{array}\right)R({\theta }_2)\right|,\left|\overrightarrow{n_1}\cdot \frac{1}{2}\left(\begin{array}{r}-w_2\\ h_2\end{array}\right)R({\theta }_2)\right|,\left|\overrightarrow{n_1}\cdot \frac{1}{2}\left(\begin{array}{r}-w_2\\ -h_2\end{array}\right)R({\theta }_2)\right|\right)\\ & \\ & =max\left(\left|\overrightarrow{n_1}\cdot \frac{1}{2}\left(\begin{array}{r}{w}_2\\ h_2\end{array}\right)R({\theta }_2)\right|,\left|\overrightarrow{n_1}\cdot \frac{1}{2}\left(\begin{array}{r}{w}_2\\ -h_2\end{array}\right)R({\theta }_2)\right|\right)\\ & \end{array}$$

となりますが、ここで

$$\begin{array}{rl}\frac{1}{2}\left(\begin{array}{c}{w}_2\\ h_2\end{array}\right)R({\theta }_2)& =\frac{1}{2}\left(w_2\left(\begin{array}{c}1\\ 0\end{array}\right)R({\theta }_2)+\left(h_2\left(\begin{array}{c}0\\ 1\end{array}\right)R\left(-\frac{\pi }{2}\right)\right)R\left({\theta }_2+\frac{\pi }{2}\right)\right)\\ & \\ & =\frac{1}{2}\left(w_2\left(\begin{array}{c}1\\ 0\end{array}\right)R({\theta }_2)+h_2\left(\begin{array}{c}1\\ 0\end{array}\right)R\left({\theta }_2+\frac{\pi }{2}\right)\right)\\ & \\ & =\frac{1}{2}\left(w_2\overrightarrow{n_2}+h_2\overrightarrow{t_2}\right)\\ & \end{array}$$

が成り立つので、

$$\begin{array}{rl}{d}_1& =\frac{1}{2}max(|w_2(\overrightarrow{n_1}\cdot \overrightarrow{n_2})+h_2(\overrightarrow{n_1}\cdot \overrightarrow{t_2})|,|w_2(\overrightarrow{n_1}\cdot \overrightarrow{n_2})-h_2(\overrightarrow{n_1}\cdot \overrightarrow{t_2})|)\\ & \\ & =\frac{1}{2}(|w_2(\overrightarrow{n_1}\cdot \overrightarrow{n_2})|+|h_2(\overrightarrow{n_1}\cdot \overrightarrow{t_2})|)\\ & \end{array}$$

となることがわかります。

さて、本題に戻りますが、以上の計算で得られた $d_3$ が $0$ 以下であるということは何を意味するでしょうか？これは図4からも分かる通り、

ということを意味します。よって、 $R_1$ の $x^{\prime }$ 軸を用いた判定における条件式は $d_3\ge 0$ ということになります。逆に $d_3<0$ である時、これらは $x^{\prime }$ 軸の法線方向から見て離れているということになります。そして、「あらゆる向きから見ても2つの剛体が接触している」ことは「衝突している」ことの必要十分条件であるため、矩形に関しては 両矩形のローカル座標における各軸に対してこの判定を行い(計4回)、それらにAND演算をとることで、矩形同士の衝突判定を行うことができます。また、実際に衝突判定を行うと、図5のようになります。

※ところでこの $d_3$ の計算、見覚えがあると思います。実はこれは円形における衝突判定と同じイメージで、円形同士ではその重心に関する素晴らしい対称性のおかげで、2重心を通る直線のみを基準として判定を1回行うだけで衝突判定が行えたのですが、矩形同士では判定の基準となる直線が増えているだけなのです。

結局、何に役立つんですか？

この手法を用いると、2Dアクションゲームを作る際に自機の回転や坂に対して当たり判定を計算することができます。また、実際に物理シミュレーションをする場合は以上の方法に加えて、clipping という手法を用いてめり込み深度を計算する必要があります。趣旨に沿わないためここでは解説をしませんが、実際にシミュレーションを行ってみるとこんな感じになります。

さいごに

ここまで見て下さった方、ありがとうございました。初めて解説記事を書くので、わかりづらい点に関してはご了承ください。

明日は PS6Sさん, CulMenさん, nariさん の三人です。どんな記事か楽しみですね‪(˘ω˘)

参考文献

http://www.dyn4j.org/2011/11/contact-points-using-clipping/