長方形と円の当たり判定


2010/08/18 追記
2.外積を用いた円と線分の当たり判定 
 参考サイト様リンク追加(外部サイト) 


・はじめに

長方形と円の当たり判定は主にシューティングで、
レーザーとの当たり判定をとりたい時に使います。
いろいろな方法があると思いますが、ここではその一例を紹介します。
ベクトルの知識を使います。わからなければググりながら少しずつ見ていってください。

・円と円の当たり判定

その前にまず「円と円の当たり判定」のとり方を解説します。(わかっている人は次へ)
座標を表すクラスを次のようにします。

//座標クラス class
Point{
	public: float
	x,y;//座標
	Point(){x=y=0.0;}
};
・・・いろいろつっこみ所は満載だと思いますが(構造体でも良くね?とかfloat使うなとか)
とりあえず説明の便宜上、こうします。
あと適当にコピーコンストラクタとか作っとくとコードを簡略化できます。

んで、移動物体のクラスを次のようにします。
//移動物体クラス
class Mover : public Point{
public:
	float r;//当たり半径
	Mover(){r=0.0;}
};
これまたつっこみ所満(ry
新たに追加したメンバ r は当たり判定の円の半径です。

さて、もう知っている人もいるかもしれませんが、
「円と円の当たり判定」は三平方の定理を使います。



A(ax,ay)、B(bx,by) として各半径を ar , br とすると、
三平方の定理より

これより ar + br の方が大きかった場合、接触しています。
C++で平方根を返す関数sqrt()を使うと、処理速度が低下するので、長さの2乗を比較します。
では、Mover同士の当たり判定をとる関数を作りましょう。
//円と円の接触判定
bool MoverCollision(const Mover &m1,const Mover &m2){
	float dx,dy,r;
	dx=m2.x-m1.x;//水平方向の距離
	dy=m2.y-m1.y;//鉛直方向の距離
	r =m2.r+m1.r;//半径の和
    
	//三平方の定理
	return ((dx*dx)+(dy*dy)<(r*r));//当たっていたらtrue
}
はい、これで「円と円の当たり判定」がとれました。

・長方形と円の当たり判定

では、本題です。
レーザーは長方形です。
4点で制御するので、そのクラスを次のようにします。
//レーザークラス
class Lazer{
public:
	Point p[4];
};
イメージはこちら

「長方形と円の当たり判定」をとるのは一筋縄にはいきません。
次の3ステップを踏みます。
  1. 円の中にレーザーの端点があるかどうか
  2. 円がレーザーの線分に触れてないがどうか
  3. 円がレーザーの内部に入り込んでないかどうか
それぞれ次のような場合です
1.円の中にレーザーの端点があるかどうか
2.円がレーザーの線分に触れてないがどうか
3.円がレーザーの内部に入り込んでないかどうか
それぞれのパターンに分けて考えていきます。

1.円の中にレーザーの端点があるかどうか

これは各端点とMoverとの当たり判定をとれば簡単です。
//レーザーの端点との接触判定
bool LazerCollision1(const Lazer &laz,const Mover &m){
	Mover t;
	
	for(int i=0;i<4;i++){
		t.x=laz.p[i].x;	t.y=laz.p[i].y;
		if(MoverCollision(t,m)){
			return true;
		}
	}
	
	return false;
}
上記MoverCollision()を使ってます。
端点は半径0のMoverとみなすことができるので、前作った関数を流用します。

2.円がレーザーの線分に触れてないがどうか

次にレーザーの各辺(線分)と円の当たり判定をとります。

円の中心mから線分pqへ垂線を下ろし、線分pqとの交点をhとすると、
垂線mhとmの半径との長さを比べればよい。
(ここからベクトルを使います。)



引数として参照できるのはp,q,mの座標です。
そこからベクトルを2つ作成します。
2点からベクトルを作る関数を次のようにします。
//typedef宣言
typedef Point Vector;

//ベクトル生成関数
Vector CreateVector(const Point &p,const Point &q){
	return Vector(q.x-p.x,q.y-p.y);//p->qベクトル
}
ベクトルを表すクラスはPointと同じメンバ(意味合いは違うが)を持つのでtypedefで同一視しましょう。
ついでに後で使うのでベクトルに関する関数を先に作っちゃいましょう。
ベクトルの内積、外積、大きさの2乗を返す関数です。
//ベクトルの内積
float InnerProduct(const Vector &a,const Vector &b){
	return (a.x*b.x+a.y*b.y);//a・b
}

//ベクトルの外積
float OuterProduct(const Vector &a,const Vector &b){
	return (a.x*b.y-a.y*b.x);//a×b
}

//ベクトルの長さの2乗
float VectorLength2(const Vector &v){
	return InnerProduct(v,v);//v・v=|v|^2
}

再掲図

まず、2ベクトル を取得します。
とすると点 h は直線 pq 上にあるので、
(kは実数)
と表せます。
より

mh と直線 pq は垂直なので





ここでなので
k<0の時 の逆側に があり、
線分 pq 上に h が存在しない。


k>1の時 を超えて があり、
線分 pq 上に h が存在しない。


よって、0<k<1の時に線分 pq 上に h が存在する。

mh の長さの2乗は

ここでなので

これとMoverの半径の2乗とを比較します。
//レーザーの各辺(線分)と円の接触判定
bool LazerCollision2(const Lazer &laz,const Mover &m){
	Vector pq,pm;
	float inner,k,pqd2,pmd2,phd2,d2;

	const int n[][4]={{0,1,3,2},{1,3,2,0}};
	for(int i=0;i<4;i++){
		pq=CreateVector(laz.p[n[0][i]],laz.p[n[1][i]]);//0.1.3.2:1.3.2.0
		pm=CreateVector(laz.p[n[0][i]],(Point)m);

		inner=InnerProduct(pq,pm);//内積
		pqd2 =VectorLength2(pq);  //大きさの2乗
		pmd2 =VectorLength2(pm);  //大きさの2乗

		k=inner/pqd2;
       
		if(k<0 || 1<k)continue;//hが線分 pq 上にあるかどうか

		phd2=(inner*inner)/pqd2;  //phの大きさの2乗

		d2=pmd2-phd2;  //垂線の大きさの2乗

		if(d2<m.r*m.r)return true;//比較
	}
	
	return false;
}

3.円がレーザーの内部に入り込んでないかどうか


図において、円がレーザーの内部に入り込んでいるときはθ0,θ1ともに0°〜90°となる。
θはやはりベクトルを使って導きます。
θ0に着目すると、θ0はp[0],p[1],mの3点から成っています。
そこで、2ベクトル, を取得して、
内積が || || cosθという性質をもっていることから、
内積を各ベクトルの大きさで割ってcosθから導くという方法がありますが、これには問題があります。

純粋なベクトルの大きさをだすにはどうしてもsqrt()関数を使う必要がでてきます。
前述した通り、sqrt()関数は実行速度を低下させる原因になります。
なんとかsqrt()関数を使わないような単純な演算だけですましたいのです。

ベクトルには内積のほかに外積というものがあります。
(外積は平面ではあまり使われないようですが・・・)
その定義と利用法は次の通りです。


よって、外積を内積で割ると2ベクトルがなす角θのtanが取得できます。
tanθからθをだすにはatan2()関数を使います。
atan()はtanの逆関数のことで、アークタンジェントです。
atan()関数でtanがはずせると考えてください。

さて、導かれるθはラジアン単位です。
「θが0°〜90°の時」なので単位が合ってません。
どちらかにそろえて比較しますが、どちらかというと度(°)に合わせた方がわかりやすいかと思います。
そこで、こんなマクロを作っておきます。
#define PI 3.141592
#define RTOD(RAD) ((RAD)*(180/PI))
#define DTOR(DEG) ((DEG)*(PI/180))
使うのはRTODです。radian to degree を意図しています。
これで度(°)に変換してから比較します。
//レーザー内部に入り込んでいないかの判定
bool LazerCollision3(const Lazer &laz,const Mover &m){
	Vector pp,pm;
	float inner,outer,theta[2];

	for(int i=0;i<2;i++){
		pp=CreateVector(laz.p[i*3],laz.p[1+i]);//0.1:3.2
		pm=CreateVector(laz.p[i*3],(Point)m);

		inner=InnerProduct(pp,pm);
		outer=OuterProduct(pp,pm);

		theta[i]=RTOD(atan2(outer,inner));
	}

	if(0<=theta[0] && theta[0]<=90 &&
	   0<=theta[1] && theta[1]<=90){
			return true;
	}

	return false;

さて、これで「長方形と円の当たり判定」をとる関数が全てそろいました。
まとめて一つの関数にしましょう。関数ポインタを使います。
//レーザー(長方形)と円の接触判定
bool LazerCollision(const Lazer &laz,const Mover &m){
	bool(*lazer_collision[])(const Lazer &laz,const Mover &m)={
		LazerCollision1,
		LazerCollision2,
		LazerCollision3,
	};

	for(int i=0;i<3;i++){
		if((*lazer_collision[i])(laz,m)){
			return true;
		}
	}
	return false;
}

今回の全体ソースコードはこちら
Collision.cpp

・追記

2.外積を用いた円と線分の当たり判定

上記の2ステップ目「円と線分の当たり判定」は内積だけしか使ってませんでした。
外積を用いるとより簡単に書けますが、仕組みは理解しづらいかと思います。
まず、内積と外積の定義を再掲します。

そしてまず距離 d を求めます。

上の図の直角三角形pmhにおいて、

であり、2ベクトル の外積が

なので、距離 d は

と表せられます。
で、やはりベクトルの長さを直にだすにはsqrt()なんちゃら〜 で遅いので、
dの2乗と円の半径の2乗同士を比較します。
そして、円の半径の方が大きかったらそこから 線分 pq 上に h があるかを調べます。
つまり上記の方法とは比較の順番が違います。

線分 pq 上に h があるかを調べる方法ですが、
結論から言うと内積同士を乗算して0以下になれば h は線分 pq 上にあります。

このときはなす角が(鋭角・鈍角)、(鈍角・鋭角)にしかならないためです。
詳しくは参考サイト様を参照してください(←丸投げ
以下ソースです。
//レーザーの各辺(線分)と円の接触判定
bool LazerCollision2(const Lazer &laz,const Mover &m){
	Vector pq,pm,qm;
	float d2,cross;
	const int n[][4]={{0,1,3,2},{1,3,2,0}};
	
	for(int i=0;i<4;i++){
		pq=CreateVector(laz.p[n[0][i]],laz.p[n[1][i]]);
		pm=CreateVector(laz.p[n[0][i]],m);
		qm=CreateVector(laz.p[n[1][i]],m);

		cross=OuterProduct(pm,pq);
		d2=cross*cross/VectorLength2(pq);//距離の2乗

		if(d2<m.r*m.r){//当たる可能性がある
			if(InnerProduct(pm,pq)*InnerProduct(qm,pq)<0){//内側にある
				return true;
			}
		}
	}
	return false;
}
だいぶ簡単になりましたね。内容は難しいですが(^^
参考サイト様の方がはるかにわかりやすいです。

2010/08/18 ここまで追記

・感想

シューティングゲームを作る時に、つまずくのはこのレーザーの実装だと思います。
なので、少しでも助けになればと思いこのページを書きました。
「円と円の当たり判定」は簡単だけれど「長方形と円の当たり判定」になると途端に難しくなります。
ベクトルについての深い知識が必要になります。
わからないところはググりながら見ていってください。

・参考サイト様

龍神録プログラミングの館(34章 レーザーを作ってみよう)
このページ(現在ページ)の内容はこちら(リンク先)に準拠しています。わかりやすく解説されてます。

C言語〜ゲームプログラミングの館〜(s11. 当たり判定。)
「円と円の当たり判定」についてです。

ロベールのC++教室 - 第9章 関数ポインタ -
関数ポインタについてです。忘れた時に見てます。
関数ポインタは使いこなせれば強い武器になります。

2D衝突編その5 円と線分から多角形と円へ
いろいろな衝突判定を書かれています。
正直こちらのページにあることはこちらに全てありますorz

このページ(現在ページ)で示したのはあくまでも一例です。
「当たり判定」や「接触判定」といった語でググれば、別の手法を紹介しているサイト様にも巡り会えるでしょう。