衝突判定：向きを持つ長方形と線と判定

アバター
GRAM
記事: 164
登録日時: 14年前
住所: 大阪

衝突判定：向きを持つ長方形と線と判定

投稿記事 by GRAM » 12年前

剛体の回転運動のプログラムに「向きのある長方形：有向境界ボックス（以下OBB）」を用いてしまったため、
このOBBと、床や壁にあたる線（別に線分でも半直線でも直線でもよいが）
との衝突判定について書きます。

要はこんな感じの一般的な状況を考えて、長方形と線が交差しているかを考えます。
hit.png
hit.png (7.93 KiB) 閲覧数: 1093 回
見つけるのは「当たってるかどうか？と、どこに交点があるか？」の2つにすることにします。
これら2つはいっぺんに出てきます。

①データの保持方法
取りあえず、OBBと直線をどうやって保持するかを考えることにします。
OBB（向きのある長方形）

CODE: 

class OBB
{
public:
	OBB(  const Vec& length, const Vec& s, const Vec& direction　)
		:length_(length / 2.0),s_(s),direction_(direction)
	{
		direction_.Normalize();//ベクトルの正規化
	};
public:
	Vec S() const{ return s_; }
	Vec Direction() const{ return direction_; }
	Vec Length()const{ return length_; }
private:
	Vec direction_; //向き(0度でx方向)　ただし正規化（つまり長さが１）されていることが保障されている
	Vec s_;//中心位置
	Vec length_; //各辺の長さの半分
};
まぁ上の通りですが、中心位置、方向、各辺の長さの半分を保存します。

つぎに線分

CODE: 

class Segment
{
public:
	Segment( Vec s, Vec d )
		:s_(s),d_(d)
	{
	}
public:
	Vec S() const{ return s_; };
	Vec D() const{ return d_; };

private:
	Vec s_;//始点
	Vec d_;//向き
};
線分の方は始点と方向ベクトルで保存します。方向ベクトルの長さが線分の長さになります。

②座標系の回転
さて実際に判定するわけですが、わざわざややこしいOBBを使う必要はありません。
このように座標系を移動⇒回転させて、向きのないしかも原点中心の長方形と判定させた方がいろいろと楽です。
rotation.png
rotation.png (14.41 KiB) 閲覧数: 1110 回
これは意外と簡単で、次のようにすることにより実現します。

CODE: 

bool OBBToSegment( OBB& obb, const Segment& seg, Vec& s)
{
	Vec obbDirectionX = obb.Direction();
	Vec obbCenter = obb.S();
	Vec obbLength = obb.Length();
	Vec segSP = seg.S();
	Vec segDirection = seg.D();

	//OBB基準の座標系へ変換
	segSP -= obbCenter;	//線分の始点をOBBの中心座標分ずらす
	segSP = Linear::VRotate2D( segSP, -obbDirectionX.y, obbDirectionX.x );	//OBBの角度分始点を回転
	segDirection = Linear::VRotate2D( segDirection, -obbDirectionX.y, obbDirectionX.x );	//OBBの角度分線分の方向ベクトルを回転
・・・
Vec Linear::VRotate2D( const Vec&, double sin, double cos )
► スポイラーを表示
この関数は、第一引数に与えられたベクトルを第2、第3引数で与えられるsin cosの値によって回転します。
今、obbの方向ベクトルは正規化されているつまり長さが1であることが保障されているので
そのx方向の長さがcosに、y方向の長さがsinになります。もちろんx軸と、OBBとの角度が30°なら-30°回転させるのでsinは符号が逆になります。

③スラブ
さて、平行四辺形は２組の平行な直線を用いて表すことができます。
この2組の平行な直線がそれぞれ90度に交わるときこれが長方形になる条件ということができます。
これらの直線のうち、1組の平行な2直線のことをスラブといいます。
とりあえず見てみましょう。
slub.png
slub.png (48.08 KiB) 閲覧数: 1075 回
AABBを2つのスラブであらわしたとき、
1つひとつのスラブと判定したい線分との交点を求めることは極めて容易です。

CODE: 

	double l = obbLength[i];
	double t1 = (-l - segSP[i]) / segDirection[i];
	double t2 = ( l - segSP[i]) / segDirection[i];
	if( t1 > t2 ) std::swap( t1, t2 );
Vec classはoperator[]を有しており、 i=1ならxをi=2ならyの参照を返します。
x方向のスラブも、y方向のスラブも↑の計算式で交点を求めることができ、
tの値は、それぞれ線分の長さのを何倍すれば交点までたどり着くかが代入され、
t1には、近い方の交点がt2には遠い方の交点が入ります。
これは三角形の相似を考えれば明らかなことです。

④判定
準備は整いました。
判定も極めて簡単です。
要は、当たっている場合はあるスラブの遠い方の交点があるスラブの近い方の交点よりも近い位置にあるということは起こりません。
一方当たっていない場合は、あるスラブの遠い方の交点（上の図ならty2）があるスラブの近い方の交点(同tx1)よりも近い距離にあります。
↑の図を見てください

つまりコードはこういうことになります。

CODE: 

double tmin = std::numeric_limits::min(); //線分、半直線なら0に
	double tmax = std::numeric_limits::max(); //線分なら1に
	for( int i = 1; i  1.0 )
			{
				return 0;
			}
		}
		else
		{
			double t1 = (-l - segSP[i]) / segDirection[i];
			double t2 = ( l - segSP[i]) / segDirection[i];

			if( t1 > t2 ) std::swap( t1, t2 );
			if( t1 > tmin ) tmin = t1;
			if( t2  tmax ) return false;
		}
	}
線分についていえばコードはこんな感じです

CODE: 

bool OBBToSegment( OBB& obb, const Segment& seg, Vec& s)
{
	Vec obbDirectionX = obb.Direction();
	Vec obbCenter = obb.S();
	Vec obbLength = obb.Length();
	Vec segSP = seg.S();
	Vec segDirection = seg.D();

	//OBB基準の座標系へ変換
	segSP -= obbCenter;	//線分の始点をOBBの中心座標分ずらす
	segSP = Linear::VRotate2D( segSP, -obbDirectionX.y, obbDirectionX.x );	//OBBの角度分始点を回転
	segDirection = Linear::VRotate2D( segDirection, -obbDirectionX.y, obbDirectionX.x );	//OBBの角度分線分の方向ベクトルを回転

	double tmin = 0.0;
	double tmax = 1.0;
	for( int i = 1; i  1.0 )
			{
				return 0;
			}
		}
		else
		{
			double t1 = (-l - segSP[i]) / segDirection[i];
			double t2 = ( l - segSP[i]) / segDirection[i];

			if( t1 > t2 ) std::swap( t1, t2 );
			if( t1 > tmin ) tmin = t1;
			if( t2  tmax ) return false;
		}
	}
	//交点
	s = seg.S() + seg.D()*tmin;
	return true;
}
OBBと判定するに当たり、直線の方程式を出してちまちま解いたりするのをよく見ますが、
こっちの方が一般性があるかなと思います。
ただし座標変換は厳密には必要なく、ベクトルに慣れていればOBBのままスラブと線分の交差判定をすることもできます。
またこのやり方は３Dへの応用も容易で、レイトレーシング法なんかにも使われたりするらしいです。
（具体的にはforループをi=1~2ではなく、i=1~3にすればそのまま3Dでつかえる）
・・・意外と説明むずい
最後に編集したユーザー GRAM on 2013年1月05日(土) 14:30 [ 編集 4 回目 ]
ページトップ
コメントはまだありません。