[DirectX11] 기본 게임 도형(Sphere,AABB,OBB등)과 Intersection

DirectX 11로 게임 엔진 아키텍처 만들기

게임 개발, 특히 3D 게임에서, 물리적 상호 작용과 환경 인식은 플레이어 경험을 풍부하게 만드는 핵심 요소입니다. 이러한 상호 작용을 정확하게 구현하기 위해, 개발자들은 기본적인 3D 도형들 간의 교차(Intersection) 검사 알고리즘을 활용합니다. 이 글에서는 3D 게임 개발에 사용되는 주요 기본 도형과 이들 간의 교차 판별 방법에 대해 소개하겠습니다.

참고강의 링크:

https://www.inflearn.com/course/directx11-%EA%B2%8C%EC%9E%84%EA%B0%9C%EB%B0%9C-%EB%8F%84%EC%95%BD%EB%B0%98/dashboard

[게임 프로그래머 도약반] DirectX11 입문 강의 - 인프런

수학 개념과 공식

3D 게임 개발에서 자주 사용되는 기본 도형에는 구(Sphere), 축에 정렬된 경계 상자(AABB), 방향이 있는 경계 상자(OBB), 평면(Plane) 등이 있습니다. 이들 도형 간의 교차 검사는 게임 내 충돌 감지, 가시성 판단, 경로 탐색 등 다양한 기능의 기반이 됩니다.

구와 구의 교차

두 구의 중심 사이의 거리가 두 구의 반지름 합보다 작거나 같으면 충돌한다고 판단합니다.

// 구와 구의 충돌 검사
bool MathUtils::SphereToSphere(const Sphere3D& s1, const Sphere3D& s2)
{
	float sum = s1.radius + s2.radius; // 두 구의 반지름 합
	float sqDistance = (s1.position - s2.position).LengthSquared(); // 중심 간 거리의 제곱
	return sqDistance <= sum * sum; // 중심 거리의 제곱이 반지름 합의 제곱보다 작거나 같으면 겹침
}

구와 AABB의 교차

구의 중심에서 AABB에 가장 가까운 점까지의 거리가 구의 반지름보다 작으면 충돌한다고 판단합니다.

// 구와 AABB의 충돌 검사
bool MathUtils::SphereToAABB(const Sphere3D& sphere, const AABB3D& aabb)
{
	Point3D closestPoint = ClosestPoint(aabb, sphere.position); // AABB 상에서 구의 중심에 가장 가까운 점
	float distSq = (sphere.position - closestPoint).LengthSquared(); // 중심에서 가장 가까운 점까지 거리의 제곱
	float radiusSq = sphere.radius * sphere.radius; // 구의 반지름 제곱
	return distSq < radiusSq; // 중심에서 가장 가까운 점까지의 거리가 반지름보다 작으면 겹침
}

구와 OBB의 교차

구와 OBB의 충돌 검사도 구와 AABB의 충돌 검사와 유사하게 수행되지만, OBB의 회전을 고려하여 계산합니다.

// 구와 OBB의 충돌 검사
bool MathUtils::SphereToOBB(const Sphere3D& sphere, const OBB3D& obb)
{
	Point3D closestPoint = ClosestPoint(obb, sphere.position); // OBB 상에서 구의 중심에 가장 가까운 점
	float distSq = (sphere.position - closestPoint).LengthSquared(); // 중심에서 가장 가까운 점까지 거리의 제곱
	float radiusSq = sphere.radius * sphere.radius; // 구의 반지름 제곱
	return distSq < radiusSq; // 조건 동일
}

구와 평면의 교차

구의 중심에서 평면에 가장 가까운 점까지의 거리가 구의 반지름보다 작거나 같으면 충돌한다고 판단합니다.

// 구와 평면의 충돌 검사
bool MathUtils::SphereToPlane(const Sphere3D& sphere, const Plane3D& plane)
{
	Point3D closestPoint = ClosestPoint(plane, sphere.position); // 평면 상에서 구의 중심에 가장 가까운 점
	float distSq = (sphere.position - closestPoint).LengthSquared(); // 중심에서 가장 가까운 점까지 거리의 제곱
	float radiusSq = sphere.radius * sphere.radius; // 구의 반지름 제곱
	return distSq < radiusSq; // 조건 동일
}

AABB와 AABB의 교차

두 AABB가 교차하는지 판별하기 위해선, 모든 축(가로, 세로, 높이)에 대해 두 AABB의 최소점과 최대점을 비교합니다. 모든 축에 대해 한 AABB의 최대점이 다른 AABB의 최소점보다 크고, 최소점이 최대점보다 작다면, 두 AABB는 교차합니다.

// AABB와 AABB의 충돌 검사
bool MathUtils::AABBToAABB(const AABB3D& aabb1, const AABB3D& aabb2)
{
	Point3D aMin = AABB3D::GetMin(aabb1); // aabb1의 최소 좌표
	Point3D aMax = AABB3D::GetMax(aabb1); // aabb1의 최대 좌표
	Point3D bMin = AABB3D::GetMin(aabb2); // aabb2의 최소 좌표
	Point3D bMax = AABB3D::GetMax(aabb2); // aabb2의 최대 좌표

	return (aMin.x <= bMax.x && aMax.x >= bMin.x) &&
		(aMin.y <= bMax.y && aMax.y >= bMin.y) &&
		(aMin.z <= bMax.z && aMax.z >= bMin.z); // 모든 축에 대해 겹치면 true
}

AABB와 OBB의 충돌 검사

충돌 검사는 분리 축 정리(Separating Axis Theorem, SAT)를 사용하여 수행됩니다. AABB의 모든 축과 OBB의 모든 축, 그리고 이들 축의 외적에 대해 분리 축을 테스트하여 겹치지 않는 축이 하나라도 존재하면 충돌하지 않는 것으로 판단합니다.

 

// AABB의 주어진 축에 대한 구간을 계산
Interval3D MathUtils::GetInterval(const AABB3D& aabb, const Vec3& axis)
{
	Vec3 i = AABB3D::GetMin(aabb); // 최소 좌표
	Vec3 a = AABB3D::GetMax(aabb); // 최대 좌표

	Vec3 vertex[8] =
	{
		Vec3(i.x, a.y, a.z), Vec3(i.x, a.y, i.z), Vec3(i.x, i.y, a.z), Vec3(i.x, i.y, i.z),
		Vec3(a.x, a.y, a.z), Vec3(a.x, a.y, i.z), Vec3(a.x, i.y, a.z), Vec3(a.x, i.y, i.z),
	};

	Interval3D result; // 구간 초기화
	result.min = result.max = axis.Dot(vertex[0]); // 첫 정점을 기준으로 초기화

	for (int i = 1; i < 8; ++i)
	{
		float projection = axis.Dot(vertex[i]);
		result.min = min(result.min, projection); // 최소값 갱신
		result.max = max(result.max, projection); // 최대값 갱신
	}
	return result; // 계산된 구간 반환
}

// OBB와 주어진 축에 대한 구간(Interval) 계산
Interval3D MathUtils::GetInterval(const OBB3D& obb, const Vec3& axis)
{
	Vec3 vertex[8]; // OBB의 꼭짓점을 저장할 배열

	Vec3 C = obb.position; // OBB의 중심 위치
	Vec3 E = obb.size; // OBB의 크기(각 축에 대한 반 길이)

	vector<Vec3> A; // OBB의 축
	A.push_back(obb.orientation.Right()); // OBB의 오른쪽 방향 축
	A.push_back(obb.orientation.Up()); // OBB의 위쪽 방향 축
	A.push_back(obb.orientation.Backward()); // OBB의 뒤쪽 방향 축

	// OBB의 8개 꼭짓점 계산
	vertex[0] = C + A[0] * E.x + A[1] * E.y + A[2] * E.z;
	vertex[1] = C - A[0] * E.x + A[1] * E.y + A[2] * E.z;
	vertex[2] = C + A[0] * E.x - A[1] * E.y + A[2] * E.z;
	vertex[3] = C + A[0] * E.x + A[1] * E.y - A[2] * E.z;
	vertex[4] = C - A[0] * E.x - A[1] * E.y - A[2] * E.z;
	vertex[5] = C + A[0] * E.x - A[1] * E.y - A[2] * E.z;
	vertex[6] = C - A[0] * E.x + A[1] * E.y - A[2] * E.z;
	vertex[7] = C - A[0] * E.x - A[1] * E.y + A[2] * E.z;

	// 주어진 축에 대해 OBB의 꼭짓점들을 투영하여 최소/최대 값 계산
	Interval3D result;
	result.min = result.max = axis.Dot(vertex[0]); // 첫 꼭짓점으로 초기화

	for (int i = 1; i < 8; ++i)
	{
		float projection = axis.Dot(vertex[i]); // 꼭짓점을 축에 투영
		result.min = min(result.min, projection); // 최소값 갱신
		result.max = max(result.max, projection); // 최대값 갱신
	}
	return result; // 계산된 구간 반환
}

// AABB와 OBB가 주어진 축에 대해 겹치는지 검사
bool MathUtils::OverlapOnAxis(const AABB3D& aabb, const OBB3D& obb, const Vec3& axis)
{
	Interval3D a = GetInterval(aabb, axis); // AABB의 구간 계산
	Interval3D b = GetInterval(obb, axis); // OBB의 구간 계산
	return ((b.min <= a.max) && (a.min <= b.max)); // 구간이 겹치면 true 반환
}

// 두 OBB가 주어진 축에 대해 겹치는지 검사
bool MathUtils::OverlapOnAxis(const OBB3D& obb1, const OBB3D& obb2, const Vec3& axis)
{
	Interval3D a = GetInterval(obb1, axis); // obb1의 구간 계산
	Interval3D b = GetInterval(obb2, axis); // obb2의 구간 계산
	return ((b.min <= a.max) && (a.min <= b.max)); // 구간이 겹치면 true 반환
}

// AABB와 OBB의 충돌 검사
bool MathUtils::AABBToOBB(const AABB3D& aabb, const OBB3D& obb)
{
	Vec3 test[15] = // 충돌 검사에 사용될 축
	{
		Vec3(1,0,0), // AABB 축 1
		Vec3(0,1,0), // AABB 축 2
		Vec3(0,0,1), // AABB 축 3
		obb.orientation.Right(), // OBB 축 1
		obb.orientation.Up(), // OBB 축 2
		obb.orientation.Backward(), // OBB 축 3
		// 외적으로 생성된 추가 축은 여기에서 계산됨
	};

	// 추가 축 계산 (AABB 축과 OBB 축의 외적)
	for (int i = 0; i < 3; ++i)
	{
		test[6 + i * 3 + 0] = test[i].Cross(test[3]);
		test[6 + i * 3 + 1] = test[i].Cross(test[4]);
		test[6 + i * 3 + 2] = test[i].Cross(test[5]);
	}

	// 모든 축에 대해 겹치는지 검사
	for (int i = 0; i < 15; ++i)
	{
		if (!OverlapOnAxis(aabb, obb, test[i])) // 하나라도 겹치지 않으면 false 반환
			return false;
	}

	return true; // 모두 겹치면 true 반환
}

AABB와 평면 충돌 검사

AABB와 평면의 충돌 검사는 평면의 법선과 AABB의 크기를 기반으로 계산된 반응성(pLen)을 평가하여 수행됩니다. AABB 중심에서 평면까지의 거리를 평가하여, 이 거리가 계산된 반응성 내에 위치한다면 AABB가 평면과 충돌하고 있다고 판단합니다.

 

// AABB와 평면의 충돌 검사
bool MathUtils::AABBToPlane(const AABB3D& aabb, const Plane3D& plane)
{
	float pLen = aabb.size.x * fabsf(plane.normal.x) + // AABB의 각 축에 대한 반응성 계산
		aabb.size.y * fabsf(plane.normal.y) +
		aabb.size.z * fabsf(plane.normal.z);

	float dot = plane.normal.Dot(aabb.position); // 평면의 법선과 AABB 중심의 내적
	float dist = dot - plane.distance; // 평면 상수와의 차이 계산

	return fabsf(dist) <= pLen; // 겹치는지 여부 반환
}

OBB와 OBB의 충돌 검사

OBB와 OBB 사이의 충돌 검사 역시 SAT를 사용합니다. 두 OBB의 모든 축과 이들 축의 외적을 이용한 축을 테스트합니다.

// 두 OBB의 충돌 검사
bool MathUtils::OBBToOBB(const OBB3D& obb1, const OBB3D& obb2)
{
	Vec3 test[15] = // 충돌 검사에 사용될 축
	{
		obb1.orientation.Right(), // OBB1 축 1
		obb1.orientation.Up(), // OBB1 축 2
		obb1.orientation.Backward(), // OBB1 축 3
		obb2.orientation.Right(), // OBB2 축 1
		obb2.orientation.Up(), // OBB2 축 2
		obb2.orientation.Backward(), // OBB2 축 3
		// 외적으로 생성된 추가 축은 여기에서 계산됨
	};

	// 추가 축 계산 (OBB1 축과 OBB2 축의 외적)
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j) {
			test[6 + i * 3 + j] = test[i].Cross(test[3 + j]);
		}
	}

	// 모든 축에 대해 겹치는지 검사
	for (int i = 0; i < 15; ++i)
	{
		if (!OverlapOnAxis(obb1, obb2, test[i])) // 하나라도 겹치지 않으면 false 반환
			return false;
	}

	return true; // 모두 겹치면 true 반환
}

평면과 평면의 충돌 검사

두 평면의 노멀 벡터의 외적이 0이 아니면, 즉 두 평면이 평행하지 않으면 두 평면은 충돌한다고 판단할 수 있습니다.

// 두 평면의 충돌 검사
bool MathUtils::PlaneToPlane(const Plane3D& plane1, const Plane3D& plane2)
{
	Vec3 d = plane1.normal.Cross(plane2.normal); // 두 평면의 법선 벡터의 외적
	return d.Dot(d) != 0; // 외적의 결과가 0이 아니면 두 평면은 평행하지 않은 것으로 간주
}

결론

3D 게임 개발에서 도형 간의 교차 검사는 물리적 상호 작용의 기반이며, 다양한 상황에서 객체 간의 충돌 감지, 가시성 판단, 경로 탐색 등에 활용됩니다. 정확한 교차 판별 알고리즘을 구현함으로써, 개발자는 보다 현실적이고 반응적인 게임 환경을 제공할 수 있습니다. 이러한 기본적인 수학 개념과 알고리즘의 이해는 게임 개발의 복잡성을 관리하고, 사용자에게 몰입감 있는 게임 플레이 경험을 제공하는 데 중요한 역할을 합니다.