今回は趣旨が少し違う。複数の物体がぶつかるか否かの真偽を取る判定を当たり判定と呼ぶ。
ゲームとかでよく使うのだが、コンピュータの物体移動は時間が離散的で物体は飛び飛びに移動する*1。
故にそのフレームと前のフレームで当たり判定ではぶつかっていないが、フレーム間で交差が発生していることもある。
しかし、交差が発生しているからと言ってぶつかっているとも限らない。
そこで、ベクトルを使って二つの物体がぶつかってるか判別してみよう。
なお、今回は簡単のため各フレーム間の移動は等速直線運動であるとしている*2。
導出を丸々乗っけてるので至極長い。
Notation
物体A,Bのあるフレームでの位置ベクトルをそれぞれ\(A_0,B_0\)とし、その次のフレームでの位置ベクトルを\(A_1,B_1\)とする。
また、物体A,Bの大きさ(半径)はそれぞれ\(r_A,r_B\)とする。
さらに、表記法として次のようなものを使う。
- \(C_0=B_0-A_0.\)
- \(C_1=B_1-A_1.\)
- \(X\in\{A,B,C\}\)
- \(X_{mid}=\frac{X_0+X_1}{2}.\)
- \(v_X=\frac{X_1-X_0}{2}.\)
定式化
時刻\(t\)における位置
さて、まずは時間変数を用意しよう。時刻\(t\)を\(t\in[-1,1]\)としよう*3*4。
このとき、時刻\(t\)における物体A,Bの位置\(A_t,B_t\)はそれぞれ
- \(A_t=A_{mid}+t\cdot v_A.\)
- \(B_t=B_{mid}+t\cdot v_B.\)
となる。
AB間の距離
位置ベクトルが表す位置間の距離は、差ベクトル自身の内積の平方根を取ればよい。
しかしルートの計算は重たい*5ので、距離の平方を用いて話を進めるが、分数を消すためによくわからない定数倍をする。
唐突に距離の平方の4倍が出てくるが、了承願いたい。
ある時刻\(t\)におけるAB間の距離を\(d_t\)とすると、
\(B_t-A_t=(B_{mid}+t\cdot v_B)-(A_{mid}+t\cdot v_A)=C_{mid}+t\cdot v_C\)より、
\(\begin{eqnarray}d_t^2
&=&(C_{mid}+t\cdot v_C,C_{mid}+t\cdot v_C)\\
&=&(C_{mid},C_{mid})+2(C_{mid},v_C)t+(v_c,v_c)t^2.\\
4d_t^2&=&4(C_{mid},C_{mid})+2\cdot4(C_{mid},v_C)t+4(v_c,v_c)t^2.\end{eqnarray}\)
ここで\(\alpha=4(v_c,v_c),\beta=4(C_{mid},v_C),\gamma=4(C_{mid},C_{mid})\)と置くと、
\(4d_t^2=\alpha t^2+2\beta t+\gamma\)となる。
この式を\(g(t)\)と置いておこう。
\(g(t)=4d_t^2=\alpha t^2+2\beta t+\gamma\)である。
個別計算
\(\alpha,\beta\gamma\)をそれぞれ計算する。目標は\(C_0,C_1\)による表示だ。
\(\begin{eqnarray}\alpha
&=&4\left(\frac{C_1-C_0}{2},\frac{C_1-C_0}{2}\right)\\
&=&(C_1-C_0,C_1-C_0)\\
&=&(C_0,C_0)+(C_1,C_1)-2(C_0,C_1).\end{eqnarray}\)
\(\begin{eqnarray}\beta
&=&4\left(\frac{C_0+C_1}{2},\frac{C_1-C_0}{2}\right)\\
&=&(C_0+C_1,C_1-C_0)\\
&=&(C_1,C_1)-(C_0,C_0).\end{eqnarray}\)
\(\begin{eqnarray}\gamma
&=&4\left(\frac{C_0+C_1}{2},\frac{C_0+C_1}{2}\right)\\
&=&(C_0+C_1,C_0+C_1)\\
&=&(C_0,C_0)+(C_1,C_1)+2(C_0,C_1).\end{eqnarray}\)
当たり判定
ある時刻\(t\)でABが当たるとは、\(d_t\leq r_A+r_B\)を満たすことである。
ここで、\(d_t\)は距離であり、\(r_A,r_B\)は大きさ(半径)なので、それぞれ正の値を取る。
よって\(d_t\leq r_A+r_B\Leftrightarrow d_t^2\leq (r_A+r_B)^2\Leftrightarrow 4d_t^2=g(t)\leq 4(r_A+r_B)^2\)が言える。
\(4(r_A+r_B)^2\)を\(R\)と置いておこう。
物体が当たっているか否かを判定するには、\(g(t)\leq R\)、言い換えると\(g(t)-R\leq 0\)が満たされるかを見ればよい。
\(f(t)=g(t)-R\)としておこう*6。
ただし、\(t\)は区間\([-1,1]\)の間しか動かないという条件付きである。
不等式を満たすか否かの判定
ある区間\(x\in[a,b]\)において、\(f(x)\)が非正値を取るか同課の判定について述べておく。
ただし、\(y=f(x)\)のグラフは下に凸であるとする*7。
\(y=f(x)\)が\((x_{top},y_{top})\)を頂点に取るとしよう。
このとき、\(x_{top}\in[a,b]\)ならば、\(f(x)\)の最小値が区間内に存在するため、\(y_{top}\leq 0\)か否かを調べればよい。
また\(x_{top}\in[a,b]\)でないとき、\(f(x)\)は区間内で単調な関数となる。
つまり、その時非正値を取るならば、\(f(a),f(b)\)の少なくともどちらか一方が非正値を取っている。
条件をまとめると次の通りである。
bool hitting(){ if(a <= x_top && x_top <= b){ return y_top <= 0; }else{ return (f(a)<=0 || f(b)<=0); } }
必要な値の算出
頂点座標
\(y=ax^2+bx+c\)の頂点\((x_{top},y_{top})\)は\((-\frac{b}{2a},c-\frac{b^2}{4a})\)である。
\(y=f(t)=g(t)-R=\alpha t^2+2\beta t+\gamma-R\)についても頂点を計算すると、
\(x_{top} = -\frac{2\beta}{2\alpha} = -\frac{\beta}{\alpha},\)
\(y_{top} = (\gamma-R)-\frac{(2\beta)^2}{4\alpha} = (\gamma-R)-\frac{\beta^2}{\alpha}\)
となる。
それぞれを\(C_0,C_1\)による表記に落とし込もう。
\(x_{top}\)について
\(\begin{eqnarray}x_{top}
&=& -\frac{\beta}{\alpha}\\
&=& -\frac{(C_1,C_1)-(C_0,C_0)}{(C_0,C_0)+(C_1,C_1)-2(C_0,C_1)}\\
&=& \frac{(C_0,C_0)-(C_1,C_1)}{(C_0,C_0)+(C_1,C_1)-2(C_0,C_1)}.\end{eqnarray}\)
\(x_{top}\)は区間\([-1,1]\)の間に入るかの判定を取るのだった。
つまり\(-1\leq x_{top}\leq 1\)の不等式を満たすかどうかを見る。
\(-1\leq x_{top}\)と\(x_{top}\leq 1\)に分けて変形する。
\(\alpha > 0\)なので、分母を払った後から計算を進めると、
\(\begin{eqnarray}
2(C_0,C_1)-(C_0,C_0)-(C_1,C_1) & \leq& (C_0,C_0)-(C_1,C_1)\\
(C_0,C_1) & \leq& (C_0,C_0)
.\end{eqnarray}\)
\(\begin{eqnarray}
(C_0,C_0)-(C_1,C_1) & \leq& (C_0,C_0)+(C_1,C_1)-2(C_0,C_1)\\
-2(C_1,C_1) & \leq& -2(C_0,C_1)\\
(C_1,C_1) & \geq& (C_0,C_1)
.\end{eqnarray}\)
\(y_{top}\)について
長たらしくなるので、途中、\(c_0=(C_0,C_0),c_1=(C_1,C_1),i=(c_0,c_1)\)とする。
\(\begin{eqnarray}y_{top}
&=&(\gamma-R)-\frac{\beta^2}{\alpha}\\
&=&c_0+c_1+2i-R-\frac{(c_1-c_0)^2}{c_0+c_1-2i}\\
&=&\frac{(c_0+c_1+2i)(c_0+c_1-2i)}{c_0+c_1-2i}-\frac{(c_0-c_1)^2}{c_0+c_1-2i}-R\\
&=&\frac{(c_0+c_1)^2-4i^2}{c_0+c_1-2i}-\frac{(c_0-c_1)^2}{c_0+c_1-2i}-R\\
&=&\frac{-4i^2}{c_0+c_1-2i}-R\\
&=&-\frac{4\{(C_0,C_1)\}^2}{(C_0,C_0)+(C_1,C_1)-2(C_0,C_1)}-R
.\end{eqnarray}\)
\(y_{top}\)は非正値を取るのかを見るのだった。
つまり、\(y_{top}\leq 0\)の不等式を満たすかどうかを見る。
\(\alpha > 0\)なので、分母を払った後から計算を進める。
\(r=r_A+r_B\)とすると\(R=4(r_A+r_B)^2\)なので、
\(\begin{eqnarray}
-4\{(C_0,C_1)\}^2 &\leq& R\{(C_0,C_0)+(C_1,C_1)-2(C_0,C_1)\}\\
-\{(C_0,C_1)\}^2 &\leq& r^2\{(C_0,C_0)+(C_1,C_1)-2(C_0,C_1)\}
.\end{eqnarray}\)
となる*8。
\(f(-1),f(1)\)について
区間の両端を代入したものも手続きでは使うことになる。
今回の区間は\([-1,1]\)なので、\(f(-1),f(1)\)を計算する。
\(f(\pm 1)\)
\(e\in\{-1,1\}\)なる\(e\)を考える。\(e^2=1\)である。
\(\begin{eqnarray}f(\pm 1)
&=&\alpha (\pm 1)^2+2\beta(\pm 1)+\gamma-R\\
&=&\alpha+\gamma \pm 2\beta -R\\
&=&\{(C_0,C_0)+(C_1,C_1)-2(C_0,C_1)\}\\
&&+\{(C_0,C_0)+(C_1,C_1)+2(C_0,C_1)\}\\
&&\pm 2\{(C_1,C_1)-(C_0,C_0)\} -R\\
&=&2(C_0,C_0)+2(C_1,C_1) \pm 2\{(C_1,C_1)-(C_0,C_0)\} -R
.\end{eqnarray}\)
よって\(f(1)=2(C_0,C_0)+2(C_1,C_1) + 2\{(C_1,C_1)-(C_0,C_0)\} -R = 4(C_1,C_1)-R\),
\(f(-1)=2(C_0,C_0)+2(C_1,C_1) - 2\{(C_1,C_1)-(C_0,C_0)\} -R = 4(C_0,C_0)-R\)となる。
\(f(\mp 1)\)は非正値を取るかどうか判定を取るのだった。
\(f( 1)\leq 0\)より\(4(C_1,C_1)\leq R \Rightarrow (C_1,C_1)\leq r^2\)
\(f(-1)\leq 0\)より\(4(C_0,C_0)\leq R \Rightarrow (C_0,C_0)\leq r^2\)
Conclusion
まとめである*9。
物体A,Bがぶつかるかどうかの判定を取る手続きを作った。
完成版の手続きをc++当たりでクラス化しておく。
...継承したら使えるんじゃないかな。確証はない。
struct vec{ double x,y; vec():x(0.0),y(0.0){} vec(double x, double y):x(x),y(y){} /* 内積 */ double operator *(const vec& v){ return x*v.x + y*v.y; } }; class Hitting{ private: vec pos[2]; double r; public: Hitting(double size):r(size){} void Set(vec p){ pos[0] = pos[1]; pos[1] = p; } const vec& operator[](int i){return pos[i];} static bool isHit(const Hitting& A, const Hitting& B){ vec C0(B[0]-A[0]); vec C1(B[1]-A[1]); double r_sq = (A.r + B.r); r_sq *= r_sq;// rの平方 double c0 = C0*C0; // (C0,C0)の内積 double c1 = C1*C1; // (C1,C1)の内積 double i = C0*C1; // (C0,C1)の内積 if(i <= c0 && i <= c1) return (-i*i <= r_sq * (c0+c1-2*i)); return (c0 <= r_sq || c1 <= r_sq); } };
