10장 Collision - ② 교차 테스트
게임에서 플레이어가 벽에 부딪히거나 총알이 표적에 맞거나 중력이 작용하는 세계에서 플레이어가 땅을 딛고 서있기 위해서 충돌 검사가 필요하다. 10장에서는 다양한 상황에서 사용할 수 있는 몇 가지 충돌 검사 기법을 다룬다. 그리고 충돌 검사를 위한 기본 기하 타입을 소개한다. 그런 다음 이런 기본 기하 타입 간의 교차 계산을 다룬다. 그리고 게임 메커니즘에 충돌을 포함하는 방법을 설명한다.
💡 10장의 목차
- 기하 타입
- 교차 테스트
- 게임에서 충돌처리
교차 테스트
게임에서 오브젝트 충돌을 표현하기 위해 여기서는 앞서 다룬 다양한 기하타입 오브젝트 간 교차 여부를 테스트하는 방법을 다룬다. 여기서는 아래의 교차 테스트만 다룬다.
- 점을 포함하는지 판정하는 테스트
- 구의 점 포함 판정 테스트
- AABB 점 포함 판정 테스트
- 캡슐의 점 포함 테스트
- (2D)볼록 다각형의 점 포함 테스트
- 바운딩 볼륨 테스트
- 구체와 구체 교차 테스트
- AABB와 AABB 교차 테스트
- 구와 AABB 교차 테스트
- 캡슐과 캡슐 교차 테스트
- 선분 테스트
- 선분과 평면 교차 테스트
- 선분과 구체의 교차 테스트
- 선분과 AABB 테스트
- 동적 오브젝트
점을 포함하는지 판정하는 테스트
물체가 특정한 점을 포함하는지 여부를 테스트하는 것은 그 자체로 매우 유용하다. 예를 들어 플레이어가 게임 세계의 특정 지역 내부에 있는지 여부를 판단하는 테스트에 이런 형태의 테스트를 사용할 수 있다. 여기에서는 점이 해당 물체의 가장자리에 있다 하더라도 물체에 포함된 것으로 판단한다.
구의 점 포함 판정 테스트
구가 점을 포함하는지를 알아내기 위해서는 우선 점과 구의 중심 사이의 거리를 구한다. 그리고 이 거리가 구의 반지름보다 같거나 작다면 구는 점을 포함한다. 비용이 비싼 제곱근 연산을 피하자.
bool Sphere::Contains(const Vector3& point) const
{
float distSq = (mCenter - point).LengthSq();
return distSq <= (mRadius * mRadius);
}AABB 점 포함 판정 테스트
아래의 경우중 하나라도 해당한다면 점은 2D AABB 박스의 밖에 존재한다.
- 점이 박스 왼쪽에 있다.
- 점이 박스 오른쪽에 있다.
- 점이 박스 위쪽에 있다.
- 점이 박스 아래쪽에 있다.
3D에서는 아래의 경우가 추가하면 된다.
- 점이 박스 앞에 있다.
- 점이 박스 뒤에 있다.
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;
// 하나라도 true 라면 점은 밖에 있다.
return !outside;
}캡슐의 점 포함 테스트
캡슐에서 점 포함 테스트는 구에서 진행한 것과 비슷하다. 선분과 점 사이의 거리가 반지름보다 같거나 작다면 캡슐은 점을 포함한다. 비용이 비싼 제곱근 연산을 피하자.
bool Capsule::Contains(const Vector3& point) const
{
// 점과 선분 사이의 최소 거리 제곱값 구하기
float distSq = mSegment.MinDistSq(point);
return distSq <= (mRadius * mRadius);
}볼록 다각형(2D)의 점 포함 테스트
볼록 다각형 내부에 임의점과 볼록 다각형의 각 정점을 잇는 벡터들을 만들자. 그렇다면 아래의 그림과 같이 인접한 정점 벡터 사이에서 만들어지는 모든 각의 합은 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++)
{
// 점과 첫 번째 버텍스로 벡터 구성
a = mVertices[i] - point;
a.Normalize();
// 점과 두 번째 버텍스로 벡터 구성
b = mVertices[i + 1] - point;
b.Normalize();
// sum에 구한 각을 더한다.
sum += Math::Acos(Vector2::Dot(a, b));
}
// 마지막 버텍스와 처음 버텍스가 이루는 각을 구한다.
a = mVertices.back() - point;
a.Normalize();
b = mVertices.front() - point;
b.Normalize();
sum += Math::Acos(Vector2::Dot(a, b));
// 값이 대략적으로 2pi에 가까우면 true 리턴
return Math::NearZero(sum - Math::TwoPi);
}이 각의 총합 접근법은 그렇게 효율적이지 못하다. 왜냐하면 이 접근법은 몇몇 제곱근과 아크코사인 계산을 요구하기 때문이다. 보다 복잡하기는 하지만 다른 접근법 중에는 각의 총합 접근법보다 효율적인 방식이 많다.
다각형의 점 포함 테스트
앞서 다룬 볼록 다각형의 점 포함 테스트를 개선하는 방법으로 점에서 시작하는 무한한 광선을 그리고, 광선이 모서리와 몇 개나 교차하는지를 세는 방법이 있다. 광선이 모서리와 홀수로 교차한다면 점은 폴리곤 내부에 있다. 그렇지 않다면 점은 바깥에 있다. 이 광선 접근법은 볼록 다각형뿐만 아니라 오목 다각형에서도 잘 동작한다.
바운딩 볼륨 테스트
여러 바운딩 볼륨 간 교차 테스트 계산은 매우 일반적이다. 예를 들어 플레이어와 벽의 충돌 검사를 위해서는 플레이어 바운딩 볼륨과 벽의 바운딩 볼륨 간의 교차 테스트를 해야 한다.
구체와 구체 교차 테스트
두 구체는 구체의 중심 사이의 거리가 각 구체의 반지름 합보다 작거나 같으면 교차한다. 비용이 비싼 제곱근 연산을 피하자.
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 교차 테스트
AABB 교차를 시험하는 로직은 AABB가 점을 포함하는지를 판단하는 로직과 같다. 두 오브젝트가 교차할 수 없는 몇 가지 경우에 대해서 테스트를 진행하고 하나라도 true라면 교차하지 않는 것이다. 모두 false라면 두 물체는 반드시 교차한다. AABB 오브젝트 a와 b에 대해서 아래의 테스트가 하나라도 참이라면 두 오브젝트는 교차하지 않는다.
a의x최댓값이b의x최솟값 보다 크다.a의y최댓값이b의y최솟값 보다 크다.a의z최댓값이b의z최솟값 보다 크다.b의x최댓값이a의x최솟값 보다 크다.b의y최댓값이a의y최솟값 보다 크다.b의z최댓값이a의z최솟값 보다 크다.
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;
// 모두 false라면 교차하는 것
// 하나라도 true라면 두 물체는 교차하지 않는다.
return !no;
}구와 AABB 교차 테스트
구와 AABB 교차 테스트를 하기 위해서는 구의 중심과 AABB 박스 사이의 최소 거리 제곱을 계산해야 한다. 구의 중심과 박스 사이의 거리는 곧 점과 AABB 박스 사이의 거리를 구하는 것과 같다. 점과 AABB 박스사이의 거리를 구하기 위해서는 먼저 점과 AABB 박스의 xyz 축 성분 별 거리를 구해야 한다.
하나의 축에서 점과 성분 간의 거리를 측정하기 위해서는 아래와 같이 3가지 경우로 나눠볼 수 있다.
- 점의 요소가 min 보다 작다.
- 점의 요소가 min, max 사이에 있다.
- 점의 요소가 max 보다 크다.
만약 점의 요소가 min, max 사이에 있다면 해당 성분의 값은 0이 된다. 그리고 각 성분을 Math::Max함수로 계산한 후 제곱하여 더하면 점과 AABB 박스의 거리를 구할 수 있다.
float AABB::MinDistSq(const Vector3& point) const
{
// 각각의 축과 점 사이의 거리를 계산한다.
float dx = Math::Max(mMin.x - point.x, 0.0f);
dx = Math::Max(dx, point.x - mMax.x);
float dy = Math::Max(mMin.y - point.y, 0.0f);
dy = Math::Max(dy, point.y - mMax.y);
float dz = Math::Max(mMin.z - point.z, 0.0f);
dz = Math::Max(dz, point.z - mMax.z);
// 거리의 제곱 식
return dx * dx + dy * dy + dz * dz;
}점과 AABB박스 사이의 거리를 계산하는 MinDistSq함수를 활용하여 구와 AABB 교차 테스트를 아래와 같이 정의할 수 있다.
bool Intersect(const Sphere& s, const AABB& box)
{
float distSq = box.MinDistSq(s.mCenter);
return distSq <= (s.mRadius * s.mRadius);
}캡슐과 캡슐 교차 테스트
캡슐은 반경이 있는 선분이므로 각 선분과 선분 사이 최소 거리 제곱값을 구한다. 그리고 각 반경들의 합의 제곱과 비교하여 구할 수 있다. 다만 선분과 선분사이 최소 거리는 이곳에서 다루기에 복잡하기에 생략한다. 구현되어 있는 선분의 MinDistSq함수를 활용한다.
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);
}선분 테스트
선분은 충돌 감지에서 다양하게 활용된다. 예를 들어 공 발사체가 오브젝트와 충돌 여부를 판정할 때도 사용될 수 있다. 그리고 선분 교차 테스트는 선분이 교차하는지 여부뿐만 아니라 최초로 교차되는 점을 알아내는 것도 포함한다. 앞서 선분의 매개변수 방정식을 다음과 같이 정의했었다.
\[L(t) = Start + (End-Start)t \qquad where\ 0 \le t \le 1\]
대부분 선분 교차 테스트 접근법은 선분을 무한히 긴 선으로 간주하여 충돌 여부를 판정한다. 무한히 긴 선분이 충돌한다면, \(t\)값이 [0, 1]영역에 속하는지 검증한다.
선분과 평면 교차 테스트
평면의 방정식은 다음과 같았다.
\[P \cdot \hat{n} + d = 0\]
선분과 평면이 교차한다면 아래의 식에서 선분과 평면이 교차하기 위한 \(t\)값을 찾아야 한다.
\[L(t) \cdot \hat{n} + d = 0\]
\[(Start + (End-Start)t) \cdot \hat{n} + d = 0\]
\[t = \frac{-Start \cdot \hat{n} - d}{(End - Start)\cdot \hat{n}}\]
분모의 내적이 0이 되는 경우를 주의하여 \(t\)값을 구하자. \(t\)값이 0이라면 선분이 법선에 수직이기 때문에 선분이 평면에 포함되어있을 경우에만 충돌한다. 그리고 무한히 긴 선분이 평면과 충돌한다면 \(t\)가 선분 범위 내의 값인지 검증하여 충돌 여부를 판정할 수 있다. 소스코드는 여기에서 bool Intersect(const LineSegment& l, const Plane& p, float& outT) 함수를 참고하자.
선분과 구체의 교차 테스트
선분과 구 사이의 교차점을 찾기 위해서는 선과 구체 \(C\) 사이의 거리가 구의 반지름 \(r\)과 같은 \(t\)가 있는지 찾는다.
\[\lVert L(t) - C \rVert = r \]
소스코드는 여기에서 bool Intersect(const LineSegment& l, const Sphere& s, float& outT) 함수를 참고하자.
선분과 AABB 박스 교차 테스트
선분과 AABB 박스 교차를 테스트하기 위해서 다음과 같은 방법을 활용할 수 있다.
- AABB 박스의 가장자리에 무한히 큰 평면을 만든다. 만약 2D AABB 박스 라면 4개의 평면이 만들어질 것이다.
- 각 평면들과 선분의 교차점을 구한다.
- 교차점이 AABB에 속하는지를 확인한다.
소스코드는 여기에서 bool Intersect(const LineSegment& l, const AABB& b, float& outT, Vector3& outNorm) 함수를 참고하자.
동적 오브젝트
지금까지 테스트는 현재 프레임에서 두 물체가 교차하는지 여부를 테스트한 것이다. 하지만 이러한 테스트는 간단한 게임에 한해서는 충분하지만 빠르게 움직이는 물체에서는 문제가 생길 수 있다.
위의 그림처럼 하나의 프레임 동안 오브젝트를 지나치는 경우 앞서 다룬 교차 테스트로는 충돌 여부를 테스트할 수 없다.
연속 충돌 감지
여러 유형의 이동 오브젝트에 대해 프레임 사이의 여러 지점에서 충돌 여부를 판별하는 과정을 연속 충돌 감지라고 한다.
동적 오브젝트의 충돌을 다루기 위한 하나의 방법으로는 탄환의 이동을 선분으로 표현하는 것이다. 하지만 이러한 방법은 탄환이 매우 작을 경우에만 동작한다. 커다란 물체는 선분으로 표현할 수 없기 때문이다.
연속 충돌 감지의 한 가지 예시인 구의 궤적 교차라 불리는 방법만을 여기서 다룬다. 구의 궤적 교차는 2개의 이동하는 구의 충돌을 검사하는 방법이다. 기본적인 접근법은 두 개의 구의 중심에 대한 매개변수 방정식의 차와 두 구의 반지름의 합을 비교하는 방법이다. 식은 다음과 같다.
\[P(t) = P_{0} + (P_{1}-P_{0})t\]
\[Q(t) = Q_{0} + (Q_{1}-Q_{0})t\]
\[\lVert P(t)-Q(t)\rVert = r_p + r_q\]
소스코드는 여기에서 bool SweptSphere 함수를 참고하자.
출처:
에이콘 출판 <Game Programming in C++>
