티스토리 뷰
개요
본 장에서는 이전에 포스팅한 SAT 이론 및 구현 스터디(1) 한 개념들을 SFML 환경의 코드로 구현한 내용들을 다룬다.
코드 구현전에 전반적인 흐름을 파악하기 위해서 플로우 차트를 작성해 보았다.
1. Convex Polygon의 Edge Vector 구하기
먼저 Edge Vector를 구하기 위해서는 두 개의 정점의 x, y 성분을 알아야 한다.
두 정점은 좌표가 아닌 벡터 성분이고 벡터 뺄셈을 통해서 Edge Vector를 구하게 된다.
연산은 존재하는 Convex Polygon의 정점의 갯수만큼 반복된다.
해당 코드는 다음과 같다.
sf::Vector2f Collision::DetermineEdgeVector(sf::Vector2f* vertices, uint32_t index, uint32_t count) const
{
uint32_t i0 = index + 1; // B
uint32_t i1 = index; // A
if (i0 == count)
{
i0 = 0;
i1 = count - 1;
}
// Vector AB is B - A
return vertices[i0] - vertices[i1];
}
2. 모서리 벡터의 Normal Vector(Axis)구하기
Convex Polygon에서 산출한 Edge Vector의 수직 벡터를 구한다.
수직벡터를 구하기 위해서는 회전행렬을 사용한다. 회전 행렬 방정식은 아래와 같다.
a &= \begin{bmatrix}
a_x \\
x_y \\
\end{bmatrix} \\
a^\perp &=\begin{bmatrix}
cos\frac{\pi}{2}& -sin\frac{\pi}{2} \\
sin\frac{\pi}{2}& cos\frac{\pi}{2} \\
\end{bmatrix}
\begin{bmatrix}
a_x\\
a_y\\
\end{bmatrix} \\
&= \begin{bmatrix}
0 & -1 \\
1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
a_x \\
a_y \\
\end{bmatrix} \\
&= \begin{bmatrix}
-a_y \\
a_x
\end{bmatrix}
\end{align}
sf::Vector2f Collision::DetermineNormalVector(sf::Vector2f* edgeVectors, int index) const
{
sf::Vector2f normalVector = sf::Vector2f{ -edgeVectors[index].y,edgeVectors[index].x };
//normalize
const float length = sqrtf(
(normalVector.x * normalVector.x) +
(normalVector.y * normalVector.y));
normalVector = normalVector / length;
return normalVector;
}
Normal Vector가 구해졌으면 해당 벡터를 별도의 배열에 저장한다.
여기서 중요한 점은 중복이 되는 벡터는 배열에 저장하지 않는다. 오버랩 체크를 할 때 똑같은 축에 투영을 한다면
연산 비용만 낭비되므로 Normal Vector 배열 저장전에 중복체크는 꼭 하도록 하자.
3. Axis Projection and Overlap Check(축 투영 및 겹침 체크)
도형이 겹쳐졌는지 체크하기 위해서는 하나의 Axis에 Convex Polygon의 정점들을 투영시키고 각 도형의 투영된 선분(투영 값의 최대, 최솟값)을 산출한 후, 두 개 이상의 투영값에서 겹쳐짐 여부를 체크한다.
Axis Projection
일반적으로 벡터 성분의 투영은 Dot Product(내적법) 을 사용한다.
투영한 결괏값은 각 Convex Polygon에 해당되는 배열에 별도로 저장하고 이들 배열에서 최솟값(min), 최댓값(max)
을 결정한다.
그럼 Convex Polygon 도형 하나에 min, max 값 두 개가 나오게 된다.
연산된 min, max 값은 Vector2f에 저장했다.
해당 로직을 코드로 표현하면 다음과 같다.
sf::Vector2f Collision::ProjectOnto(sf::Vector2f* vertices, uint32_t count, sf::Vector2f axis) const
{
// 초기 최대, 최소값 설정
float min = INF;
float max = -INF;
// 도형의 정점 갯수만큼 반복
for (uint32_t i = 0; i < count; i++)
{
float projection = DotProduct(vertices[i], axis);
if (projection < min)
min = projection;
if (projection > max)
max = projection;
}
// 최대, 최소값 반환
return
{
min,
max
};
}
Overlap Check
도형의 겹쳐짐 체크는 두 개의 Convex polygon의 투영된 값들을 비교하여 겹쳐진 길이를 연산하고 이에 따른 판단을 한다.
만약 두 투영값들이 서로 겹쳐지지 않을 경우, 두 도형은 서로 겹쳐진 상태가 아닌 것으로 그냥 로직에서 리턴 시킨다.
반대로 겹치는 구간이 있는 경우, 검사 축(Axis) 벡터에 겹쳐진 길이를 곱하여 MTV(Minimum Translation Vector)를 구한다. MTV는 검사한 Axis 중에서 겹쳐진 길이가 가장 큰 값으로 한다.
해당 로직은 아래와 같이 구현할 수 있겠다.
float Collision::Overlap(sf::Vector2f v0, sf::Vector2f v1) const
{
// 두 투영값이 서로 겹쳐지지 않은 경우 0을 반환
// 만약 겹치는 경우, 겹친 길이를 반환
return !(v0.x <= v1.y && v0.y >= v1.x) ? .0f : std::min(v0.y, v1.y) - std::max(v0.x, v1.x);
}
void Collision::CheckOverlap()
{
float overlap = Overlap(bodyProtection, otherProtection);
// 안겹치면 해당 로직 리턴
if (!overlap) // =>!0 이므로 true 즉 오버랩이 없다는 뜻
{
MTV = sf::Vector2f(.0f, .0f);
delete[] axis;
return false;
}
// 겹치면 검사 Axis에 겹친 길이만큼 곱셈
else
{
if (overlap < minOverlap)
{
minOverlap = overlap;
MTV = a * overlap;
}
}
}
4. MTV 연산
산출된 MTV를 토대로 도형을 회피시켜야 한다. 우선 MTV의 방향과 두 도형 중심 사이의 벡터의 방향이 서로 일치하는지 체크한다. 도형의 중심을 구하는 수식은 다음과 같다
$$ C_x = \frac{1}{6A}\sum_{i=0}^{n-1}(x_i+x_{i+1})(x_iy_{i+1}-x_{i+1}y_i)$$
$$ C_y = \frac{1}{6A}\sum_{i=0}^{n-1}(y_i+y_{i+1})(x_iy_{i+1}-x_{i+1}y_i)$$
$$ A = \frac{1}{2}\sum_{i=0}^{n-1}(x_iy_{i+1}-x_{i+1}y_i)$$
이를 코드로 구현하면 다음과 같다.
sf::Vector2f Collision::GetCenter(const Collider& body) const
{
sf::Vector2f center;
uint32_t count = body.m_verticesCount;
float A = 0.0f;
float area = 0.0f;
for (uint32_t i = 0; i < count; i++)
{
auto& v0 = body.m_vertices[i];
auto& v1 = body.m_vertices[i + 1 != count ? i + 1 : 0];
float b = CrossProduct(v0, v1);
A += b;
center += (v0 + v1) * b;
}
center *= 1.0f / (3.0f * A);
return center;
}
그리고 두 도형의 벡터와 MTV의 방향을 검사하는 로직은 다음과 같다.
만약 두 도형의 벡터와 MTV의 내적이 음수면 이는 두 벡터의 방향이 정반대이므로 MTV에
-1을 스칼라 곱 해준다.
if (DotProduct(GetCenter(body) - GetCenter(other), MTV) < 0.0f)
{
MTV *= -1.0f;
}
5. MTV만큼 도형 회피
이제 정말로 MTV가 결정됐으니 MTV만큼 도형을 이동시켜 준다.
해당 코드는 다음과 같다.
void CGameState::CheckCollision()
{
for (auto& c : m_Colliders) {
sf::Vector2f MTV;
Collision::Instance.SATCollision(m_box, *c, MTV);
m_box.Move(MTV);
}
}
위 과정은 하나의 주기에 레벨 내에 존재하는 모든 Collider를 검사한다.
참고한 사이트
- https://www.sevenson.com.au/programming/sat/
- https://www.youtube.com/watch?v=-EsWKT7Doww
- https://www.youtube.com/watch?v=dn0hUgsok9M&t=69s
- https://www.youtube.com/watch?v=gYZaiuz8pJU
- https://dyn4j.org/2010/01/sat/#sat-axes
- https://en.wikipedia.org/wiki/Centroid
'SFML' 카테고리의 다른 글
| SAT 이론 및 구현 스터디(1) (0) | 2025.02.28 |
|---|---|
| [SFML] 이벤트 다루어보기 (2) | 2025.01.10 |
| [SFML] SFML 창(window)을(를) 띄우고 관리까지 해보자. (0) | 2025.01.07 |
| [SFML] SFML 3.0 Visual Studio 개발 환경 구축하기 (2) | 2025.01.06 |
| SFML 알아보기 (2) | 2025.01.06 |