Table of Contents

ゲーム開発者の教科書：Game Programming in C++ を読んで理解したことについてを要約します（内容の転載を避け、詳しく説明しすぎないように配慮します）

ゲームプログラミング in C++

衝突検知

ここでは、ゲームオブジェクトの交差判定の実装を行う

幾何学図形の種類

線分、平面、ボックスなどの幾何学図形についてはCollision.hで宣言する

線分

Collision.h

線分（line segment）は、始点と終点で構成される

struct LineSegment {
	Vector3 mStart;
	Vector3 mEnd;
};

Collision.cpp

LineSegment::PointOnSegment()

線分上の任意の点は、パラメトリック方程式で計算できる

$$ L(t) = Start + (End - Start)t \quad \quad (0 \leq t \leq 1) $$

Vector3 LineSegment::PointOnSegment(float t)const {
	return mStart + (mEnd - mStart) * t;
}

半直線の場合は$(0 \leq t \leq \infty)$、直線の場合は$(\infty \leq t \leq \infty)$

線分は、着弾のテスト、標準レティクル、サウンドオクルージョンの判定、マウスによるピッキングなどに使う

LineSegment::MinDistSq()

線分$AB$と任意の点$C$を結ぶ最短距離を求めるとき、3つのケースを考える

ケース①：$AB$と$AC$の間の角度が$90$度よりも大きい
ケース②：$AB$と$BC$の間の角度が$90$度よりも大きい
ケース③：上記以外

これらの場合分けはドット積で判定する

ケース①の最短距離はベクトル$AC$の長さ
ケース②の最短距離はベクトル$BC$の長さ
ケース③の最短距離は$AB$に垂直な線分を$C$から$AB$まで引いたときの長さ
- $AB$上の$\vec{p}$の長さは、ドット積による正射影（scalar projection）で求める

$\vec{p}$の長さは、"$\vec{AC}$“と"正規化された$\vec{AB}$“とのドット積 $$ \lVert \vec{p} \rVert = \vec{AC} \cdot \frac{\vec{AB}}{\lVert \vec{AB} \rVert} $$

ベクトル$\vec{p}$は、$\lVert \vec{p} \rVert$と"正規化された$\vec{AB}$“とのスカラー積 $$ \vec{p} = \lVert \vec{p} \rVert \frac{\vec{AB}}{\lVert \vec{AB} \rVert} $$

ベクトルの長さの2乗は、それ自身とのドット積と同じであるため、 $$ \vec{p} = (\vec{AC} \cdot \frac{\vec{AB}}{\lVert \vec{AB} \rVert})\frac{\vec{AB}}{\lVert \vec{AB} \rVert} = \frac{\vec{AC} \cdot \vec{AB}}{\lVert \vec{AB} \rVert} \frac{\vec{AB}}{\lVert \vec{AB} \rVert} = \frac{\vec{AC} \cdot \vec{AB}}{{\lVert \vec{AB} \rVert}^2} \vec{AB} = \frac{\vec{AC} \cdot \vec{AB}}{\vec{AB} \cdot \vec{AB}} \vec{AB} $$

最短距離$d$は、 $$ d = \lVert \vec{AC} - \vec{p} \rVert $$

これにより、高価な平方根の演算を回避できる

float LineSegment::MinDistSq(const Vector3& point) const {
	// Construct vectors
	Vector3 ab = mEnd - mStart;
	Vector3 ba = -1.0f * ab;
	Vector3 ac = point - mStart;
	Vector3 bc = point - mEnd;

	// Case 1: C projects prior to A
	if (Vector3::Dot(ab, ac) < 0.0f) {
		return ac.LengthSq();
	}
	// Case 2: C projects after B
	else if (Vector3::Dot(ba, bc) < 0.0f) {
		return bc.LengthSq();
	}
	// Case 3: C projects onto line
	else {
		// Compute p
		float scalar = Vector3::Dot(ac, ab) / Vector3::Dot(ab, ab);
		Vector3 p = scalar * ab;
		// Compute length squared of ac - p
		return (ac - p).LengthSq();
	}
}

平面

平面（plane）は、無限に伸びている2次元のオブジェクトである

Collision.h

平面の方程式： $$ P \cdot \hat{n} + d = 0 $$ $P$：平面上の任意の位置座標
$n$：平面の法線
$d$：平面と原点との符号付き最短距離

struct Plane {
	Vector3 mNormal;
	float mD;
};

Collicion.cpp

Plane::Plane()

任意の三角形から、その平面の方程式を導ける（平面の法線はクロス積で求まる）

Plane::Plane(const Vector3& a, const Vector3& b, const Vector3& c) {
	// Compute vectors from a to b and a to c
	Vector3 ab = b - a;
	Vector3 ac = c - a;
	// Cross product and normalize to get normal
	mNormal = Vector3::Cross(ab, ac);
	mNormal.Normalize();
	// d = -P dot n
	mD = -Vector3::Dot(a, mNormal);
}

Plane::SignedDist()

任意の点$C$との最短距離を正射影を使って求める

法線$n$に対する$C$の正射影$s$は、 $$ s = C \cdot \hat{n} $$

$d$と正射影$s$の差が、求める最短距離となる $$ SignedDist = s - d = C \cdot \hat{n} - d $$

float Plane::SignedDist(const Vector3& point) const {
	return Vector3::Dot(point, mNormal) - mD;
}

バウンディングボリューム

現代の3Dゲームでは、バウンディングボリューム（bounding volume）を使う

2つのオブジェクトの交差（intersect）を判定する際は、コリジョン（collision）を行う

球

Collicion.h

中心位置（center）と半径（radius）で球を定義する

struct Sphere {
	Vector3 mCenter;
	float mRadius;
};

人型のオブジェクトなどに適用すると”バウンディングボリュームは交差しているが、オブジェクトは交差していない“といった偽陽性（false positive）が増えるデメリットもある

一方で、3Dオブジェクトの回転を気にする必要がないなどのメリットがある

軸平行バウンディングボックス（AABB）

Collision.h

軸平行バウンディングボックス（axis-aligned bounding box）は、すべての面と法線が基本ベクトルの$x,y,z$のどれかと平行している直方体を表す（回転しない箱のイメージ）

2次元の場合、左下の点$(x,y)$（最小点）と右上の点$(x,y)$（最大点）によって定義される

3次元の場合、最小点は最小の$(x,y,z)$の値を持ち、最大点は最大の$(x,y,z)$の値を持つ

struct AABB {
	Vector3 mMin;
	Vector3 mMax;
};

Collision.cpp

AABB::UpdateMinMax()

モデル（一連の点）をロードしてAABBを構築する

void AABB::UpdateMinMax(const Vector3& point) {
	// Update each component separately
	mMin.x = Math::Min(mMin.x, point.x);
	mMin.y = Math::Min(mMin.y, point.y);
	mMin.z = Math::Min(mMin.z, point.z);

	mMax.x = Math::Max(mMax.x, point.x);
	mMax.y = Math::Max(mMax.y, point.y);
	mMax.z = Math::Max(mMax.z, point.z);
}

以下のように呼び出す

AABB box(points[0], points[0]);	// pointsはstd::vector<Vector3>と想定
for (size_t i = 1; i < points.size(); i++) {
	box.UpdateMinMax(points[i]);
}

垂直軸周りの回転のみのオブジェクトなどは除き、基本的には回転後にはAABBを再計算する必要がある

AABB::Rotate()

回転後のAABBを計算する

void AABB::Rotate(const Quaternion& q) {
	// Construct the 8 points for the corners of the box
	std::array<Vector3, 8> points;
	// Min point is always a corner
	points[0] = mMin;
	// Permutations with 2 min and 1 max
	points[1] = Vector3(mMax.x, mMin.y, mMin.z);
	points[2] = Vector3(mMin.x, mMax.y, mMin.z);
	points[3] = Vector3(mMin.x, mMin.y, mMax.z);
	// Permutations with 2 max and 1 min
	points[4] = Vector3(mMin.x, mMax.y, mMax.z);
	points[5] = Vector3(mMax.x, mMin.y, mMax.z);
	points[6] = Vector3(mMax.x, mMax.y, mMin.z);
	// Max point corner
	points[7] = Vector3(mMax);

	// Rotate first point
	Vector3 p = Vector3::Transform(points[0], q);
	// Reset min/max to first point rotated
	mMin = p;
	mMax = p;
	// Update min/max based on remaining points, rotated
	for (size_t i = 1; i < points.size(); i++) {
		p = Vector3::Transform(points[i], q);
		UpdateMinMax(p);
	}
}

有向バウンディングボックス（OBB）

Collision.h

有向バウンディングボックス（oriented bounding box）は、AABBのような軸平行の制限を持たない

中心の位置（center）、回転クォータニオン（rotation）、ボックスの広がり（extent）を使って表現される

struct OBB {
	Vector3 mCenter;
	Quaternion mRotation;
	Vector3 mExtents;
};

計算コストはAABBよりもはるかに高い

カプセル

Collision.h

カプセル（capsule）は、半径を持つ線分である

ある時間に移動する球の直線移動も表現できる

struct Capsule {
	LineSegment mSegment;
	float mRadius;
};

凸ポリゴン

Collision.h

2Dゲームでは、オブジェクトのコリジョンが凸ポリゴンで表現される場合がある

凸ポリゴン（convex polygon）は、頂点の集合で表現できる

struct ConvexPolygon {
	// Vertices have a clockwise ordering
	std::vector<Vector2> mVertices;
};

頂点列には必ず順序を持たせる（ここでは時計回り）

交差判定

コリジョンが点を含むかの判定、バウンディングボリューム間での交差、線分と他のオブジェクトとの交差、動くオブジェクトの動的な判定について考える

点の包含判定

ここでは、点が形状の内側もしくは表面にある場合、含まれていると判定する

球の包含判定

Collision.cpp

Sphere::Contains()

球の中心と点の間の距離が、球の半径以下であれば、球は点を含む

不等号の両辺を2乗することで、高価な平方根の演算を避ける

bool Sphere::Contains(const Vector3& point) const {
	// Get distance squared between center and point
	float distSq = (mCenter - point).LengthSq();
	return distSq <= (mRadius * mRadius);
}

AABBのの包含判定

Collision.cpp

AABB::Contains()

6面に対してチェックし、どれも真でないのなら必ず点を含む

bool AABB::Contains(const Vector3& point) const {
	bool outside = point.x < mMin.x ||
		point.y < mMin.y ||
		point.z < mMin.z ||
		point.x > mMax.x ||
		point.y > mMax.y ||
		point.z > mMax.z;
	// If none of these are true, the point is inside the box
	return !outside;
}

カプセルの包含判定

Collision.cpp

Capsule::Contains()

点と線分との最短距離の2乗が、半径の2乗以下の場合に点を含む

bool Capsule::Contains(const Vector3& point) const {
	// Get minimal dist. sq. between point and line segment
	float distSq = mSegment.MinDistSq(point);
	return distSq <= (mRadius * mRadius);
}

凸ポリゴンの包含（2D）判定

Collision.cpp

ConvexPolygon::Contains()

点からポリゴンの頂点それぞれに向かうベクトルを作り、それぞれ隣接する2つのベクトルの成す角度の総和がほぼ$360$度であれば、ポリゴンは点を含む

bool ConvexPolygon::Contains(const Vector2& point) const {
	float sum = 0.0f;
	Vector2 a, b;
	for (size_t i = 0; i < mVertices.size() - 1; i++) {
		// From point to first vertex
		a = mVertices[i] - point;
		a.Normalize();
		// From point to second vertex
		b = mVertices[i + 1] - point;
		b.Normalize();
		// Add angle to sum
		sum += Math::Acos(Vector2::Dot(a, b));
	}
	// Have to add angle for last vertex and first vertex
	a = mVertices.back() - point;
	a.Normalize();
	b = mVertices.front() - point;
	b.Normalize();
	sum += Math::Acos(Vector2::Dot(a, b));
	// Return true if approximately 2pi
	return Math::NearZero(sum - Math::TwoPi);
}

acosや平方根を多用するため、効率の悪さがデメリットになる

別の方法として、点を始点とする半直線（ray）を引いて、その半直線が辺と何回交差するのかを数える方法がある（奇数回交差した場合、その点はポリゴンの内側にある）

バウンディングボリューム間の交差判定

あらゆる組み合わせの交差判定がある

球と球の判定

Collicion.cpp

Intersect()

双方の中心の間の距離が、球の半径の和以下の場合、交差する

bool Intersect(const Sphere& a, const Sphere& b) {
	float distSq = (a.mCenter - b.mCenter).LengthSq();
	float sumRadii = a.mRadius + b.mRadius;
	return distSq <= (sumRadii * sumRadii);
}

AABBとAABBの判定

Collicion.cpp

Intersect()

ボックスが交差しないケースをテストする

3つの座標軸をテストして、そのうちどれかがボックスを分離していないかを調べて交差判定する分離軸定理（separating axis theorem）の応用

bool Intersect(const AABB& a, const AABB& b) {
	bool no = a.mMax.x < b.mMin.x ||
		a.mMax.y < b.mMin.y ||
		a.mMax.z < b.mMin.z ||
		b.mMax.x < a.mMin.x ||
		b.mMax.y < a.mMin.y ||
		b.mMax.z < a.mMin.z;
	// If none of these are true, they must intersect
	return !no;
}

球とAABBの判定

Collicion.cpp

Intersect()

球の中心とボックスの間の最短距離の2乗が、半径の2乗以下であれば交差する

bool Intersect(const Sphere& s, const AABB& box) {
	float distSq = box.MinDistSq(s.mCenter);
	return distSq <= (s.mRadius * s.mRadius);
}

LineSegment::MinDistSq()

$x,y,z$各成分の最短距離を個別に求める

それぞれの成分において、$min$と$max$の間にあるかそれ以外かで判定し、前者の場合距離は$0$となる

float LineSegment::MinDistSq(const Vector3& point) const {
	// Construct vectors
	Vector3 ab = mEnd - mStart;
	Vector3 ba = -1.0f * ab;
	Vector3 ac = point - mStart;
	Vector3 bc = point - mEnd;

	// Case 1: C projects prior to A
	if (Vector3::Dot(ab, ac) < 0.0f) {
		return ac.LengthSq();
	}
	// Case 2: C projects after B
	else if (Vector3::Dot(ba, bc) < 0.0f) {
		return bc.LengthSq();
	}
	// Case 3: C projects onto line
	else {
		// Compute p
		float scalar = Vector3::Dot(ac, ab) / Vector3::Dot(ab, ab);
		Vector3 p = scalar * ab;
		// Compute length squared of ac - p
		return (ac - p).LengthSq();
	}
}

カプセルとカプセルの判定

Collicion.cpp

Intersect()

2本の線分の間の最短距離の2乗が、半径の和の2乗以下であれば交差する

bool Intersect(const Capsule& a, const Capsule& b) {
	float distSq = LineSegment::MinDistSq(a.mSegment, 
		b.mSegment);
	float sumRadii = a.mRadius + b.mRadius;
	return distSq <= (sumRadii * sumRadii);
}

線分の判定

弾丸とオブジェクトの衝突テストなどに線分を使う

ほとんどの線分交差テストで、無限の長さを持つ直線として最初に判定を行い、交差することがわかったら、$t$が$[0,1]$の範囲に含まれるかを調べる

線分と平面の判定

線分$L(t)$が平面上の点となる$t$が存在するかを調べる $$ L(t) \cdot \hat{n} + d = 0 $$

変形して$t$について解くと、 $$ (Start + (End - Start)t) \cdot \hat{n} + d = 0 $$ $$ Start \cdot \hat{n} + (End - Start) \cdot \hat{n}t + d = 0 $$ $$ (End - Start) \cdot \hat{n}t = -Start \cdot \hat{n} - d $$ $$ t = \frac{-Start \cdot \hat{n} - d}{(End - Start) \cdot \hat{n}} $$

Collicion.cpp

Intersect()

直線が平面の法線と直行する場合、分母のドット積が$0$となり、ゼロ除算を行う（この場合に交差となるのは、startとendが平面上の点であるとき）

参照を使って$t$の値を返す

bool Intersect(const LineSegment& l, const Plane& p, float& outT) {
	// First test if there's a solution for t
	float denom = Vector3::Dot(l.mEnd - l.mStart, p.mNormal);
	if (Math::NearZero(denom)) {
		// The only way they intersect is if start
		// is a point on the plane (P dot N) == d
		if (Math::NearZero(Vector3::Dot(l.mStart, p.mNormal) - p.mD)) {
			return true;
		}
		else {
			return false;
		}
	}
	else {
		float numer = -Vector3::Dot(l.mStart, p.mNormal) - p.mD;
		outT = numer / denom;
		// Validate t is within bounds of the line segment
		if (outT >= 0.0f && outT <= 1.0f) {
			return true;
		}
		else {
			return false;
		}
	}
}

線分と球の判定

Collicion.cpp

Intersect()

“直線から球の中心$C$までの距離"が"球の半径$r$“以下であれば交差する

これらの距離が等しくなるような$t$があるかを調べると、 $$ \lVert L(t) - C \rVert = r $$ $$ \lVert Start + (End - Start)t - C \rVert = r $$ $$ \lVert Start - C + (End - Start)t \rVert = r $$

両辺を2乗し、長さの2乗をドット積で置き換える $$ {\lVert Start - C + (End - Start)t \rVert}^2 = r^2 $$ $$ (Start - C + (End - Start)t) \cdot (Start - C + (End - Start)t) = r^2 $$

ベクトル加算に対するドット積は分配可能であるため、 $$ (Start - C) \cdot (Start - C) + 2(Start - C) \cdot (End - Start)t $$ $$ \quad \quad \quad \quad + (End - Start) \cdot (End - Start)t^2 = r^2 $$

これを$t$について求めると、 $$ t = \frac{-b\pm \sqrt{b^2 - 4ac}}{2a} $$ $a = (End - Start) \cdot (End - Start)$
$b = 2(Start - C) \cdot (End - Start)$
$c = (Start - C) \cdot (Start - C) - r^2$

この判別式（discriminant）：$b^2 - 4ac$から、解の個数と虚実を判別できる

判別式が負であれば、直線は球と交差しない
判別式が$0$であれば、1つの交点を持つ
判別式が$0%より大きければ、2つの交点を持つ

$t$の解を得たら、$t$が範囲$[0,1]$の中にあるかを確認する

bool Intersect(const LineSegment& l, const Sphere& s, float& outT) {
	// Compute X, Y, a, b, c as per equations
	Vector3 X = l.mStart - s.mCenter;
	Vector3 Y = l.mEnd - l.mStart;
	float a = Vector3::Dot(Y, Y);
	float b = 2.0f * Vector3::Dot(X, Y);
	float c = Vector3::Dot(X, X) - s.mRadius * s.mRadius;
	// Compute discriminant
	float disc = b * b - 4.0f * a * c;
	if (disc < 0.0f) {
		return false;
	}
	else {
		disc = Math::Sqrt(disc);
		// Compute min and max solutions of t
		float tMin = (-b - disc) / (2.0f * a);
		float tMax = (-b + disc) / (2.0f * a);
		// Check whether either t is within bounds of segment
		if (tMin >= 0.0f && tMin <= 1.0f) {
			outT = tMin;
			return true;
		}
		else if (tMax >= 0.0f && tMax <= 1.0f) {
			outT = tMax;
			return true;
		}
		else {
			return false;
		}
	}
}

線分とAABBの判定

Collicion.cpp

Intersect()

線分と面との交差テストには、“線分と平面の判定"で利用した等式を応用する $$ t = \frac{-Start \cdot \hat{n} - d}{(End - Start) \cdot \hat{n}} $$

AABBの各面は座標軸と平行なので、上記の式を最適化することができる（3次元では、テストするべき面が6面になる）

ボックスの6つの側面と線分との交差をテストする

6つの面との交点の$t$の値をtValues配列に格納する

この配列を小さい順にソートして、手前の交点から順にボックスに含まれているかを調べる

bool Intersect(const LineSegment& l, const AABB& b, float& outT, Vector3& outNorm) {
	// Vector to save all possible t values, and normals for those sides
	std::vector<std::pair<float, Vector3>> tValues;
	// Test the x planes
	TestSidePlane(l.mStart.x, l.mEnd.x, b.mMin.x, Vector3::NegUnitX, tValues);
	TestSidePlane(l.mStart.x, l.mEnd.x, b.mMax.x, Vector3::UnitX, tValues);
	// Test the y planes
	TestSidePlane(l.mStart.y, l.mEnd.y, b.mMin.y, Vector3::NegUnitY, tValues);
	TestSidePlane(l.mStart.y, l.mEnd.y, b.mMax.y, Vector3::UnitY, tValues);
	// Test the z planes
	TestSidePlane(l.mStart.z, l.mEnd.z, b.mMin.z, Vector3::NegUnitZ, tValues);
	TestSidePlane(l.mStart.z, l.mEnd.z, b.mMax.z, Vector3::UnitZ, tValues);
	
	// Sort the t values in ascending order
	std::sort(tValues.begin(), tValues.end(), [](
		const std::pair<float, Vector3>& a,
		const std::pair<float, Vector3>& b) {
		return a.first < b.first;
	});
	// Test if the box contains any of these points of intersection
	Vector3 point;
	for (auto& t : tValues) {
		point = l.PointOnSegment(t.first);
		if (b.Contains(point)) {
			outT = t.first;
			outNorm = t.second;
			return true;
		}
	}

	//None of the intersections are within bounds of box
	return false;
}

TestSidePlane()

側面をテストする機能をカプセル化したヘルパー関数

線分が交差する際に、$t$の値をstd::vectorに追加する

bool TestSidePlane(float start, float end, float negd, const Vector3& norm, std::vector<std::pair<float, Vector3>>& out) {
	float denom = end - start;
	if (Math::NearZero(denom)) {
		return false;
	}
	else {
		float numer = -start + negd;
		float t = numer / denom;
		// Test that t is within bounds
		if (t >= 0.0f && t <= 1.0f) {
			out.emplace_back(t, norm);
			return true;
		}
		else {
			return false;
		}
	}
}

ボックスの各側面を独立テストすれば、線分と交差した面を返すように修正できる（オブジェクトがボックスから跳ね返るときに利用できる）

その際は、TestSidePlane()の引数にボックスの側面を割り当て、その面（あるいは側面の法線）をIntersect()が書き込める参照引数として渡す

線分とAABBの交差は、スラブ（slab）を使って最適化することも可能（参考文献を参照）

動的オブジェクト

瞬間的な（instantaneous）テストでは交差を検出できない場合がある

弾丸と紙との交差判定を考えると、

弾丸を線分で表現すれば、線分の開始点を1つ前のフレームにおける弾丸の位置、終点を現在のフレームでの位置にして交差を検出できる

フレーム間の複数の時間で交差判定するサンプリングを行う方法もある

連続衝突検知（continuous collision detecton）は、交差時間を直接求める手法と、サンプリングする手法の両方に使われる

球スイープの交差（swept-sphere intersection）

Collision.cpp

SweptSphere()

動いている2つの球を考える

1つ前のフレームでの位置を$t=0$とし、現フレームでの位置を$t=1$とする

$P_0$は1つ前のフレームでの球$P$の位置、$P_1$は現フレームでの位置とする

$Q_0$は1つ前のフレームでの球$Q$の位置、$Q_1$は現フレームでの位置とする

$$ P(t) = P_0 + (P_1 - P_0)t $$ $$ Q(t) = Q_0 + (Q_1 - Q_0)t $$

球の間の距離が、2つの球の半径の合計と等しくなるような$t$を求める $$ \lVert P(t) - Q(t) \rVert = r_p + r_q $$

$$ {\lVert P(t) - Q(t) \rVert}^2 = (r_p + r_q)^2 $$ $$ (P(t) - Q(t)) \cdot (P(t) - Q(t)) = (r_p + r_q)^2 $$ $$ (P_0 + (P_1 - P_0)t - Q_0 - (Q_1 - Q_0)t) \cdot (P_0 + (P_1 - P_0)t - Q_0 - (Q_1 - Q_0)t) $$ $$ = (r_p + r_q)^2 $$ $$ (P_0 - Q_0 + ((P_1 - P_0) - (Q_1 - Q_0))t) \cdot (P_0 - Q_0 + ((P_1 - P_0)-(Q_1 - Q_0))t) $$ $$ = (r_p + r_q)^2 $$

$$ t = \frac{-b\pm \sqrt{b^2 - 4ac}}{2a} $$ $a = ((P_1 - P_0) - (Q_1 - Q_0)) \cdot ((P_1 - P_0) - (Q_1 - Q_0))$
$b = 2(P_0 - Q_0) \cdot ((P_1 - P_0) - (Q_1 - Q_0))$
$c = (P_0 - Q_0) \cdot (P_0 - Q_0) - (r_p + r_q)^2$

bool SweptSphere(const Sphere& P0, const Sphere& P1, const Sphere& Q0, const Sphere& Q1, float& outT) {
	// Compute X, Y, a, b, and c
	Vector3 X = P0.mCenter - Q0.mCenter;
	Vector3 Y = P1.mCenter - P0.mCenter - (Q1.mCenter - Q0.mCenter);
	float a = Vector3::Dot(Y, Y);
	float b = 2.0f * Vector3::Dot(X, Y);
	float sumRadii = P0.mRadius + Q0.mRadius;
	float c = Vector3::Dot(X, X) - sumRadii * sumRadii;
	// Solve discriminant
	float disc = b * b - 4.0f * a * c;
	if (disc < 0.0f) {
		return false;
	}
	else {
		disc = Math::Sqrt(disc);
		// We only care about the smaller solution
		outT = (-b - disc) / (2.0f * a);
		if (outT >= 0.0f && outT <= 0.0f) {
			return true;
		}
		else {
			return false;
		}
	}
}

コードに衝突検知を追加する

BoxComponentクラスでは、アクターにAABBを追加する

PhysWorldクラスでは、AABBを追跡し、必要なときに交差を検出する

BoxComponentクラス

BoxComponent.h

所有アクターがワールド変換を再計算するときに変化が起こるので、Update()ではなくOnUpdateWorldTransform()をオーバーライドする

オブジェクト空間のAABB構造体のインスタンスmObjectBox、ワールド空間のAABB構造体のインスタンスmWorldBoxをメンバ変数に持つ

オブジェクト空間のバウンディングボックスは、BoxComponentを初期化したら変化しない

ワールド空間のバウンディングボックスは、所有アクターのワールド変換に追従して変換する

ワールドの回転に従って回転するべきかを示すbool値mShouldRotateもメンバ変数に持つ

Mesh.h

オブジェクト空間のAABBをメッシュファイルから取得するため、AABBをメンバ変数mBoxとして追加する

Mesh.cpp

Mesh::Load()

gpmeshファイルを読み込むとき、個々の頂点でAABB::UpdateMinMax()を呼び出して、オブジェクト空間のAABBを作成する

~
for (rapidjson::SizeType i = 0; i < vertsJson.Size(); i++) {
		// For now, just assume we have 8 elements
		const rapidjson::Value& vert = vertsJson[i];
		if (!vert.IsArray() || vert.Size() != 8) {
			SDL_Log("Unexpected vertex format for %s", fileName.c_str());
			return false;
		}

		Vector3 pos(vert[0].GetDouble(), vert[1].GetDouble(), vert[2].GetDouble());
		mRadius = Math::Max(mRadius, pos.LengthSq());
		mBox.UpdateMinMax(pos);	// ※

		// Add the floats
		for (rapidjson::SizeType i = 0; i < vert.Size(); i++) {
			vertices.emplace_back(static_cast<float>(vert[i].GetDouble()));
		}
	}
~

PlaneActor.h

AABBを表すBoxComponentクラス型のメンバ変数mBoxを追加する

PlaneActor.cpp

メッシュのオブジェクト空間のAABBを受け取り、BoxComponentに設定する

Mesh* mesh = GetGame()->GetRenderer()->GetMesh("Assets/Plane.gpmesh");
mc->SetMesh(mesh);
// Add collision box
mBox = new BoxComponent(this);
mBox->SetObjectBox(mesh->GetBox());

BoxComponent.cpp

BoxComponent::OnUpdateWorldTransform()

オブジェクト境界をワールド空間に変換するには、スケーリングと回転と平行移動を適用する

スケーリングする際は、minとmaxに所有アクターのスケールを掛ける

回転する際は、AABB::Rotate()に所有アクターのクォータニオンを渡す（mShouldRotateがtrueのとき）

平行移動する際は、minとmaxの両方に所有アクターの位置を加算する

PhysWorldクラス

Game.h

物理の世界はPhysWorldクラスにまとめる

PhysWorldポインタmPhysWorldをGameに追加し、Game::Initialize()で初期化する

Game.cpp

Game::Initialize()

// Create the physics world
mPhysWorld = new PhysWorld(this);

PhysWorld.h

BoxComponentポインタの配列を持つ

std::vector<class BoxComponent*> mBoxes;

Rendererがすべてのスプライトコンポーネントの配列を持つのと同様に、PhysWorldはすべてのボックスコンポーネントの配列を持つ

PhysWorld.cpp

PhysWorld::AddBox()

BoxComponentを管理する（追加）

PhysWorld::RemoveBox()

BoxComponentを管理する（削除）

BoxComponent.cpp

BoxComponent::BoxComponent()

AddBox()を呼び出す

BoxComponent::~BoxComponent()

RemoveBox()を呼び出す

PhysWorld.h

ボックスへの衝突検知を追加するため、衝突した位置、衝突点の法線、交差したBoxComponentとActorの両方へのポインタを含むCollisionInfo構造体を定義する

struct CollisionInfo {
		// Point of collision
		Vector3 mPoint;
		// Normal at collision
		Vector3 mNormal;
		// Component collided with
		class BoxComponent* mBox;
		// Owning actor of component
		class Actor* mActor;
	};

PhysWorld.cpp

PhysWorld::SegmentCast()

最も近い交差を最重要と想定する

すべてのボックスをテストして、最も小さい$t$の値を持つ交差の結果を返す（線分の始点に最も近い交差であるため）

bool PhysWorld::SegmentCast(const LineSegment& l, CollisionInfo& outColl) {
	bool collided = false;
	// Initialize closestT to infinity, so first
	// intersection will always update closestT
	float closestT = Math::Infinity;
	Vector3 norm;
	// Test against all boxes
	for (auto box : mBoxes) {
		float t;
		// Does the segment intersect with the box?
		if (Intersect(l, box->GetWorldBox(), t, norm)) {
			// Is this closer than previous intersection?
			if (t < closestT) {
				closestT = t;
				outColl.mPoint = l.PointOnSegment(t);
				outColl.mNormal = norm;
				outColl.mBox = box;
				outColl.mActor = box->GetOwner();
				collided = true;
			}
		}
	}
	return collided;
}

ボールの衝突を線分キャストで判定する

このプロジェクトでは、SegmentCast()を使ってプレイヤーが撃つ銃弾（ball projectile）が何かに当たるか判定する

判定して当たっていたら、弾が表面の法線に沿って跳ね返るようにする

Actor.cpp

Actor::RotateToNewForward()

ドット積とクロス積とクォータニオンで、アクターの進行方向を新しい方向へと回転させる

void Actor::RotateToNewForward(const Vector3& forward) {
	// Figure out difference between original (unit x) and new
	float dot = Vector3::Dot(Vector3::UnitX, forward);
	float angle = Math::Acos(dot);
	// Facing down X
	if (dot > 0.9999f) {
		SetRotation(Quaternion::Identity);
	}
	// Facing down -X
	else if (dot < -0.9999f) {
		SetRotation(Quaternion(Vector3::UnitZ, Math::Pi));
	}
	else {
		// Rotate about axis from cross product
		Vector3 axis = Vector3::Cross(Vector3::UnitX, forward);
		axis.Normalize();
		SetRotation(Quaternion(axis, angle));
	}
}

BallActor.h

MoveComponentの新しい派生クラスであるBallMoveをメンバ変数に持たせる（BallActorに固有な動きを実装する）

BallMove.cpp

BallMove::Update()

ボールが飛んでいく方向に線分を構築する

その線分がワールドに置かれたコリジョンと交差したら、その表面でボールが跳ね返るようにする（Vector3::Reflect()で向きを反転させ、RotateToNewForward()で新しい方向に回転させる）

void BallMove::Update(float deltaTime) {
	// Construct segment in direction of travel
	const float segmentLength = 30.0f;
	Vector3 start = mOwner->GetPosition();
	Vector3 dir = mOwner->GetForward();
	Vector3 end = start + dir * segmentLength;

	// Create line segment
	LineSegment l(start, end);

	// Test segment vs world
	PhysWorld* phys = mOwner->GetGame()->GetPhysWorld();
	PhysWorld::CollisionInfo info;
	// (Don't collide vs player)
	if (phys->SegmentCast(l, info) && info.mActor != mPlayer) {
		// If we collided, reflect the ball about the normal
		dir = Vector3::Reflect(dir, info.mNormal);
		mOwner->RotateToNewForward(dir);
		// Did we hit a target?
		TargetActor* target = dynamic_cast<TargetActor*>(info.mActor);
		if (target) {
			static_cast<BallActor*>(mOwner)->HitTarget();
		}
	}

	// Base class update moves based on forward speed
	MoveComponent::Update(deltaTime);
}

PhysWorldでのボックス衝突判定

PhysWorld.cpp

PhysWorld::TestPairwise

ゲームの物理ワールドにあるすべてのボックスに関して衝突をテストする場合、素直に実装するとあらゆるペアの組み合わせで交差テストをすることになる（$O(n^2)$のアルゴリズム）

void PhysWorld::TestPairwise(std::function<void(Actor*, Actor*)> f) {
	// Naive implementation O(n^2)
	for (size_t i = 0; i < mBoxes.size(); i++) {
		// Don't need to test vs itself and any previous i values
		for (size_t j = i + 1; j < mBoxes.size(); j++) {
			BoxComponent* a = mBoxes[i];
			BoxComponent* b = mBoxes[j];
			if (Intersect(a->GetWorldBox(), b->GetWorldBox())) {
				// Call supplied function to handle intersection
				f(a->GetOwner(), b->GetOwner());
			}
		}
	}
}

不要なIntersect()の呼び出しが大量にある

PhysWorld::TestSweepAndPrune()

スイープ＆プルーン（sweep-and-prune）手法は、特定の軸に沿って区間が重なるボックスだけテストし、交差テストの回数を減らす

例えば、$x$軸に沿う区間でボックス同士が重なっているかを判定し、重なっていなければその時点でそのペアを除外する

最初にボックスの配列を$x$の最小値の昇順でソートする

すべてのボックスについて$x$の最大値を取り出し、それを$max$に保存する

$min.x$が$max$よりも小さいボックスだけを重なり判定する

$max$よりも$min.x$が大きいボックスに遭遇したら、$x$軸が重なるボックスはもう存在しないことになる

void PhysWorld::TestSweepAndPrune(std::function<void(Actor*, Actor*)> f) {
	// Sort by min.x
	std::sort(mBoxes.begin(), mBoxes.end(), [](BoxComponent* a, BoxComponent* b) {
			return a->GetWorldBox().mMin.x < b->GetWorldBox().mMin.x;
	});

	for (size_t i = 0; i < mBoxes.size(); i++) {
		// Get max.x for current box
		BoxComponent* a = mBoxes[i];
		float max = a->GetWorldBox().mMax.x;
		for (size_t j = i + 1; j < mBoxes.size(); j++) {
			BoxComponent* b = mBoxes[j];
			// If AABB[j] min is past the max bounds of AABB[i],
			// then there aren't any other possible intersections
			// against AABB[i]
			if (b->GetWorldBox().mMin.x > max) {
				break;
			}
			else if (Intersect(a->GetWorldBox(), b->GetWorldBox())) {
				f(a->GetOwner(), b->GetOwner());
			}
		}
	}
}

これにより、計算時間は半分に減らせる（$O(n log n)$アルゴリズム）

3軸すべてのプルーニングを行って残されたボックスは必ず交差することになる

スイープ＆プルーンは、ブロードフェーズ（broadphase）というカテゴリに属する技法であり、ナローフェーズ（narrowphase）に入る前に、可能な限り多くのコリジョンを除外する

プレイヤーと壁との衝突

プレイヤーが壁を突き抜けるのを許している実装を修正する

プレイヤーにBoxComponentを追加し、PlaneActorでカプセル化した個々の壁にもBoxComponentを追加する

Gameの中にPlaneActorポインタの配列を作り、その配列をプレイヤーのコードからアクセスする

もしAABBが交差すれば、壁と接触しないようにプレイヤーの位置を調整する

プレイヤーの位置を調整するには、最小の重なり（minimum overlap）がある軸で重なりを相殺する

2次元の場合は差の数は4個で、3次元の場合は差の数は6個になる

FPSActor.cpp

FPSActor::FixCollisions()

最小の重なりをテストする

プレイヤーの位置を変更するとプレイヤーのBoxComponentも変わるので、毎回の交差テストでBoxComponentのワールド境界を再計算する

FPSActor::UpdateActor()

FPSActor::FixCollisions()を呼び出す

ゲームプロジェクト

まとめ

参考文献

詳細に衝突検知のテーマを扱う：
Real-Time Collision Detection (The Morgan Kaufmann Series In Inteacive 3-D Technolagy)
無償で公開：リンク

物理エンジンの動きのコンテクストに衝突検知を組み込む方法の解説：
Game Physics Engine Development
無償で公開：リンク