2D 線分と動的円との衝突判定メモ

同人ゲームを作っていて、3Dの衝突判定・応答の部品はあるのだが、2D関連がどうも弱い。
現在マップ(2D)の線分との衝突判定が、線分と動的AABBだけだったので、
3Dで使用していた、線分と動的球体との衝突判定のやつを改良し、以下のようにしてみた。
ただ単に球体が3次元、それを2次元にしただけなので大して変わらないですが。


動的球体と線分の判定の時は、三角形、AABB,OBB,などの、辺と頂点の判定に使用してましたね。

紅!魔境村より線分と動的円との判定・応答
衝突パターン
上記のパターンは

 32パターン×左右反転×4回転=96種

で、マップ上で扱えるようにしてます。赤いところが外側に向かって法線のある線分です。
なんか、話が脱線してしまったな^^;



とりあえずメモ代わりに貼り付け!
//-----------------------------------------------------------------------------------
// [ 説明 ] 
//  二次方程式を解き、最小値を返す。
// [ 引数 ]
//  fA		:[in] a
//  fB		:[in] b
//  fC		:[in] c
//  pTime	:[in,out] 0~1の範囲の時間の値をセットする
// [ 戻り値 ]
//  falseの場合解なし trueの場合解あり
//-----------------------------------------------------------------------------------
bool FindLowestRootInInterval(float fA, float fB, float fC, float *pTime)
{
	// 判別式
	float fDeterminant = fB*fB - 4.0f*fA*fC;
	
	// これが負なら解は複素数.
	if(fDeterminant < 0.0f) return false;

	// これを基準化する方法はコンピュータに依存する
	//      -b ±√(-b^2-4ac)
	// x = -------------------
	//             2a
	// aが0近くである場合、上記の式は、安定しない。
	float fQ = -0.5f*(fB + (fB < 0.0f? -1.0f : 1.0f) * sqrtf(fDeterminant));
	// 下記の二つは+INF、-INFあるいはNANを返すことができる。
	float x1 = fQ / fA;
	float x2 = fC / fQ;
	//float sqrtD = sqrt(fDeterminant);
	//float fTA = 1.0f/(2.0f*fA);
	//float x1 = (-fB - sqrtD) * fTA;
	//float x2 = (-fB + sqrtD) * fTA;

	// 並び替えをするか?
	if(x1 &gt; x2)
	{
		float temp = x2;
		x2 = x1;
		x1 = temp;
	}

	// 値が範囲内か:[0 pTime]
	if(x1 &gt; 0.0f && x1 < *pTime)
	{
		*pTime = x1;
		return true;
	}

	// x2を使用することがある
	// if r1 < 0
	if(x2 &gt; 0.0f && x2 < *pTime)
	{
		*pTime = x2;
		return true;
	}
	// 解がない
	return false;
}

//-----------------------------------------------------------------------------------
// [ 説明 ] 
//  /| ̄ ̄ ̄ ̄ ̄|\       通常こんな感じの拡張されたエッジと判定する
// | ・rP0  rP1・ |
// \|_____|/
// [ 引数 ]
//  rCircle		:[in] 円
//  rVe			:[in] 速度ベクトル
//  rP0			:[in] 縁の頂点1
//  rP1			:[in] 縁の頂点2
//  *pTime		:[in, out] 0~1の範囲の時間の値をセットする
//  pvOut		:[out] 衝突した頂点をセットする
//  bVer0		:[in] rV0の円もチェックするか?trueでチェックする
//  bVer1		:[in] rV1の円もチェックするか?trueでチェックする
// [ 戻り値 ]
//  1の場合辺で衝突あり、2(rP0),3(rP1)で頂点部分で衝突あり、0で衝突無し
//-----------------------------------------------------------------------------------
int IntersectCircleEdgeLine(
	const SG_CIRCLE &rCircle,
	const SG_VECTOR2 &rVel,
	const SG_VECTOR2 &rP0, 
	const SG_VECTOR2 &rP1, 
	float *pTime, 
	SG_VECTOR2 *pvOut,
	bool bVer0, bool bVer1
)
{
	float fTmpT = *pTime;
	SG_VECTOR2 vKe = rP1 - rP0;
	SG_VECTOR2 vKg = rP0 - rCircle.c;
	float fK_ee = vKe.Dot();
	float fK_eg = vKe.Dot(vKg);
	float fK_es = vKe.Dot(rVel);
	float fK_gg = vKg.Dot();
	float fK_gs = vKg.Dot(rVel);
	float fK_ss = rVel.Dot();
	float fR2 = rCircle.r*rCircle.r;

	// fA*t^2 + fB*t + fC = 0 :より
	float fA = fK_ee * -fK_ss + (fK_es * fK_es);
	float fB = 2.0f * (fK_ee*fK_gs - fK_es*fK_eg);
	float fC = fK_ee * (fR2 - fK_gg ) + (fK_eg*fK_eg);

	if( FindLowestRootInInterval(fA, fB, fC, &fTmpT) )
	{
		if( fTmpT == 0.0f )
		{
			*pvOut = rCircle.c;
			*pTime = 0.0f;
			return 1;
		}

		// ヒットがrP0とrP1の間にある場合チェック
		float f = (fK_es*fTmpT - fK_eg) / fK_ee;
		if( (f >= 0.0f) && (f <= 1.0f) )
		{
			*pvOut = rP0 + vKe * f;
			*pTime = fTmpT;
			return 1;
		}
		fTmpT = *pTime;
	}

	//-----------------------------------------
	// 円と頂点(rP0)チェック
	//
	if( bVer0 )
	{
		fB = 2.0f*(rCircle.c-rP0).Dot(rVel);
		fC = fK_gg - fR2;
		if( FindLowestRootInInterval(fK_ss, fB, fC, &fTmpT) )
		{
			*pvOut = rP0;
			*pTime = fTmpT;
			return 2;
		}
		fTmpT = *pTime;
	}
	//-----------------------------------------
	// 円と頂点(rP1)チェック
	//
	if( bVer1 )
	{
		fB = 2.0f*(rCircle.c-rP1).Dot(rVel);
		fC = (rP1-rCircle.c).Dot() - fR2;

		if( FindLowestRootInInterval(fK_ss, fB, fC, &fTmpT) )
		{
			*pvOut = rP1;
			*pTime = fTmpT;
			return 3;
		}
		fTmpT = *pTime;
	}
	return 0;
}

今回の続き 2D 動的円と動的AABBの衝突判定メモ

コメント 

コメントを残す