2017年11月10日 | ブログ記事

しかく と しかく が ごっつんこ

g2

はじめに

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

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

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

まず、矩形くけいってなに?

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

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

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

図1は、二つの円が重なる様子を表したものです。重なった時に円の色が濃くなっていると思います。

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

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

DD が正である限り C1C_1C2C_2 は接触はしないので、衝突する条件は

D=L(r1+r2)0 D = L - (r_1 + r_2) \leq 0

となります。

矩形同士の衝突判定

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

矩形の持つ情報

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

img0

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

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

重なった部分が存在する

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

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

d0=12w1d1=12(w2(n1n2)+h2(n1t2))d2=n1(r2r1)d3=d0+d1d2\begin{array}{rl} d_0 & = & \displaystyle\frac{1}{2}w_1 \\\\ d_1 & = & \displaystyle\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}

ただし、

R(θ)=(cos(θ)sin(θ)sin(θ)cos(θ))n1=R(θ1)(10)n2=R(θ2)(10)t2=R(θ2+π2)(10)\begin{array}{rl} R(\theta) &=& \left( \begin{array}{rr} \rm{cos}(\theta) & \rm{-sin}(\theta) \\ \rm{sin}(\theta) & \rm{cos}(\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}

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

d1d_1の値は、 R2R_2 の重心から各頂点へ向かう4ベクトル

12(w2h2)R(θ2),12(w2h2)R(θ2),12(w2h2)R(θ2),12(w2h2)R(θ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), \frac{1}{2} \left( \begin{array}{r} -w_2 \\ -h_2 \\ \end{array} \right) R(\theta_2)

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

d1=max(n112(w2h2)R(θ2),n112(w2h2)R(θ2),n112(w2h2)R(θ2),n112(w2h2)R(θ2))=max(n112(w2h2)R(θ2),n112(w2h2)R(θ2))\begin{array}{rl} d_1 &= max \left(\displaystyle \left|\overrightarrow{n_1}\cdot\frac{1}{2}\left( \begin{array}{r} \it{w_{\rm 2}} \\ \it{h_{\rm 2}} \\ \end{array} \right) R(\theta_2)\right|, \left|\overrightarrow{n_1}\cdot\frac{1}{2}\left( \begin{array}{r} \it{w_{\rm 2}} \\ \it{-h_{\rm 2}} \\ \end{array} \right) R(\theta_2)\right|, \left|\overrightarrow{n_1}\cdot\frac{1}{2}\left( \begin{array}{r} \it{-w_{\rm 2}} \\ \it{h_{\rm 2}} \\ \end{array} \right) R(\theta_2)\right|, \left|\overrightarrow{n_1}\cdot\frac{1}{2}\left( \begin{array}{r} \it{-w_{\rm 2}} \\ \it{-h_{\rm 2}} \\ \end{array} \right) R(\theta_2)\right|\right)\\\\ &= \displaystyle max \left( \left|\overrightarrow{n_1}\cdot\frac{1}{2} \left( \begin{array}{r} \it{w_{\rm 2}} \\ \it{h_{\rm 2}} \\ \end{array} \right)R(\theta_2)\right| , \left|\displaystyle\overrightarrow{n_1}\cdot\frac{1}{2} \left( \begin{array}{r} \it{w_{\rm 2}} \\ \it{-h_{\rm 2}} \\ \end{array} \right)R(\theta_2)\right| \right) \\\\ \end{array}

となりますが、ここで

12(w2h2)R(θ2)=12(w2(10)R(θ2)+(h2(01)R(π2))R(θ2+π2))=12(w2(10)R(θ2)+h2(10)R(θ2+π2))=12(w2n2+h2t2)\begin{array}{rl} \displaystyle\frac{1}{2}\left(\begin{array}{c} w_2 \\ h_2 \\ \end{array}\right)R(\theta_2) &= \displaystyle\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)\\\\ &= \displaystyle\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)\\\\ &= \displaystyle\frac{1}{2}\left(w_2\overrightarrow{n_2} + h_2\overrightarrow{t_2}\right)\\\\ \end{array}

が成り立つので、

d1=12max(w2(n1n2)+h2(n1t2),w2(n1n2)h2(n1t2))=12(w2(n1n2)+h2(n1t2))\begin{array}{rl} d_1 & = \displaystyle\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})|)\\\\ & = \displaystyle\frac{1}{2}( |w_2(\overrightarrow{n_1}\cdot\overrightarrow{n_2})| + |h_2(\overrightarrow{n_1}\cdot\overrightarrow{t_2})|)\\\\ \end{array}

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

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

x'軸の法線方向から R₁, R₂ を見た時に、重なっている箇所が存在する

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

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

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

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

さいごに

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

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

参考文献

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

この記事を書いた人
g2

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2017年11月17日
そばやのワク☆ワク流体シミュレーション~MPS編~
sobaya007
2017年11月14日
IBIS2017参加報告
Keijan
2017年12月27日
Splatoon2~ボムの使い方~
shigurure
2017年12月26日
RustでMCMC(Metropolis-Hasting)
David
2017年12月26日
NinjaFlickerが完成しました
gotoh
2017年12月25日
Project Obelisk [traP Advent Calendar 2017]
nari

活動の紹介

カテゴリ

タグ