DirectX
84_Intersection (수학)
devRiripong
2024. 3. 31. 10:34
반응형
여러 도형끼리 포개질 때 탐지해 내기 위해서 Intersection 이란 걸 하게 되는데 여러 타입에 대해 알아본다.
Sphere to sphere
Sphere to AABB
Sphere to OBB
Sphere to plane
AABB to AABB
AABB to OBB
AABB to plane
OBB to OBB
OBB to plane
plane to plane
물리 엔진을 직접 구현한다면 중요한 내용이다.
MathUtils클래스에 이어서 코드를 넣어준다.
Sparating axis theorem을 검색해서 친절하게 분석한 글을 읽어본다.
1. MathUtils.h에 Intersection 관련 코드 추가하기
Primitive3D.h에 가서
struct Interval3D
{
float min;
float max;
};
를 추가한다.
MathUtils.h
//-------------------
// Intersection
//-------------------
static bool SphereSphere(const Sphere3D& s1, const Sphere3D& s2);
static bool SphereAABB(const Sphere3D& sphere, const AABB3D& aabb);
static bool SphereOBB(const Sphere3D& sphere, const OBB3D& obb);
static bool SpherePlane(const Sphere3D& sphere, const Plane3D& plane);
static bool AABBAABB(const AABB3D& aabb1, const AABB3D& aabb2);
static Interval3D GetInterval(const AABB3D& aabb, const Vec3& axis);
static Interval3D GetInterval(const OBB3D& obb, const Vec3& axis);
static bool OverlapOnAxis(const AABB3D& aabb, const OBB3D& obb, const Vec3& axis);
static bool AABBOBB(const AABB3D& aabb, const OBB3D& obb);
static bool OverlapOnAxis(const OBB3D& obb1, const OBB3D& obb2, const Vec3& axis);
static bool AABBPlane(const AABB3D& aabb, const Plane3D& plane);
static bool OBBOBB(const OBB3D& obb1, const OBB3D& obb2);
static bool PlanePlane(const Plane3D& plane1, const Plane3D& plane2);
MathUtils.cpp
bool MathUtils::SphereSphere(const Sphere3D& s1, const Sphere3D& s2)
{
float sum = s1.radius + s2.radius;
float sqDistance = (s1.position - s2.position).LengthSquared();
return sqDistance <= sum * sum;
}
bool MathUtils::SphereAABB(const Sphere3D& sphere, const AABB3D& aabb)
{
Point3D closestPoint = ClosestPoint(aabb, sphere.position);
float distSq = (sphere.position - closestPoint).LengthSquared();
float radiusSq = sphere.radius * sphere.radius;
return distSq < radiusSq;
}
bool MathUtils::SphereOBB(const Sphere3D& sphere, const OBB3D& obb)
{
Point3D closestPoint = ClosestPoint(obb, sphere.position);
float distSq = (sphere.position - closestPoint).LengthSquared();
float radiusSq = sphere.radius * sphere.radius;
return distSq < radiusSq;
}
bool MathUtils::SpherePlane(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;
}
bool MathUtils::AABBAABB(const AABB3D& aabb1, const AABB3D& aabb2)
{
Point3D aMin = AABB3D::GetMin(aabb1);
Point3D aMax = AABB3D::GetMax(aabb1);
Point3D bMin = AABB3D::GetMin(aabb2);
Point3D bMax = AABB3D::GetMax(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);
}
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;
}
Interval3D MathUtils::GetInterval(const OBB3D& obb, const Vec3& axis)
{
Vec3 vertex[8];
Vec3 C = obb.position; // OBB Center
Vec3 E = obb.size; // OBB Extents
vector<Vec3> A; // OBB Axis
A.push_back(obb.orientation.Right());
A.push_back(obb.orientation.Up());
A.push_back(obb.orientation.Backward());
// 각 좌표를 구해준다
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;
// 최소/최대 구하기
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;
}
bool MathUtils::OverlapOnAxis(const AABB3D& aabb, const OBB3D& obb, const Vec3& axis)
{
Interval3D a = GetInterval(aabb, axis);
Interval3D b = GetInterval(obb, axis);
return ((b.min <= a.max) && (a.min <= b.max));
}
bool MathUtils::AABBOBB(const AABB3D& aabb, const OBB3D& obb)
{
Vec3 test[15] =
{
Vec3(1, 0, 0), // AABB axis 1
Vec3(0, 1, 0), // AABB axis 2
Vec3(0, 0, 1), // AABB axis 3
obb.orientation.Right(), // OBB axis 1
obb.orientation.Up(), // OBB axis 2
obb.orientation.Backward() // OBB axis 3
// We will fill out the remaining axis in the next step
};
for (int i = 0; i < 3; ++i)
{
// Fill out rest of axis
test[6 + i * 3 + 0] = test[i].Cross(test[0]);
test[6 + i * 3 + 1] = test[i].Cross(test[1]);
test[6 + i * 3 + 2] = test[i].Cross(test[2]);
}
for (int i = 0; i < 15; ++i)
{
if (OverlapOnAxis(aabb, obb, test[i]) == false)
return false; // Seperating axis found
}
return true; // Seperating axis not found
}
bool MathUtils::AABBPlane(const AABB3D& aabb, const Plane3D& plane)
{
float pLen = aabb.size.x * fabsf(plane.normal.x) +
aabb.size.y * fabsf(plane.normal.y) +
aabb.size.z * fabsf(plane.normal.z);
float dot = plane.normal.Dot(aabb.position);
float dist = dot - plane.distance;
return fabsf(dist) <= pLen;
}
bool MathUtils::OverlapOnAxis(const OBB3D& obb1, const OBB3D& obb2, const Vec3& axis)
{
Interval3D a = GetInterval(obb1, axis);
Interval3D b = GetInterval(obb1, axis);
return ((b.min <= a.max) && (a.min <= b.max));
}
bool MathUtils::OBBOBB(const OBB3D& obb1, const OBB3D& obb2)
{
Vec3 test[15] =
{
obb1.orientation.Right(),
obb1.orientation.Up(),
obb1.orientation.Backward(),
obb2.orientation.Right(),
obb2.orientation.Up(),
obb2.orientation.Backward(),
};
for (int i = 0; i < 3; ++i)
{
// Fill out rest of axis
test[6 + i * 3 + 0] = test[i].Cross(test[0]);
test[6 + i * 3 + 1] = test[i].Cross(test[1]);
test[6 + i * 3 + 2] = test[i].Cross(test[2]);
}
for (int i = 0; i < 15; ++i)
{
if (OverlapOnAxis(obb1, obb2, test[i]) == false)
return false; // Seperating axis found
}
return true; // Seperating axis not found
}
bool MathUtils::PlanePlane(const Plane3D& plane1, const Plane3D& plane2)
{
Vec3 d = plane1.normal.Cross(plane2.normal);
return d.Dot(d) != 0; // Consider using an epsilon!
}
2. 정리
당장 오늘 외우지 않으면 큰일난다는 마인드로 해야 한다.
Sphere랑 하는 건 구랑 구 원점이랑 제일 가까운 점을 찾아서 그걸 이용해서 거리 계산한 다음에 radius를 비교하는 방식을 이용했고,
AABB, OBB 들어간 부분이 핵심이었는데 이건 SAT(Separating Axis Theorem)이라 해서 축을 기반으로 프로젝션을 때린 다음에 그 프로젝션끼리 겹치는 영역이 있는지, 즉 말 그대로 separating 하는 영역, 갭이 있는지를 확인해서 테스트를 축에 걸쳐가지고 최대 15번씩 하는데 그중에서 하나라도 실패하면 실패하는 테스트를 진행하는 것이다.
크게 구분하면 2가지의 이슈들로 구분할 수 있다.
요약을 해보면서 어떻게 설명할지 잘 생각을 해보면 된다.
기본적인 물체끼리 포개지는 것에 대해 완료했다.
반응형