Frustum Culling ( 절두체 선별 ) 에 앞서서
해당 범위에 오브젝트들이 포함되어있는지 어떻게 판별할까 ??
그 방법에 대해서 몇 가지 알아보고 넘어가자.
*AABB ( Axis - Aligned Bounding Box )
=> 축 정렬 경계 상자 라고 한다.
=> 큰 특징은 사각 Box 영역이 좌표축에 평행.
AABB 를 적용할 오브젝트의 최솟점 / 최댓점 을 구해 정의 가능하다.
최솟점(Vmin) / 최댓점(Vmax) 을 이용해서 AABB 의 중점(c) 과 거리(e) 를 구할 수 있다.
c = 0.5 ( Vmin - Vmax )
e = 0.5 ( Vmax - Vmin )
*AABB 와 회전의 문제
=> 좌표계 축을 기준으로 물체의 최솟점, 최댓점을 이용해 AABB 를 적용하는데,
월드 공간으로 변환되어질 때, 회전이 되어지면 어떻게 될까 ??
=> 해당 좌표계 ( 월드 공간 ) 와 평행하지 않게 된다.
따라서, 정확한 Collision 계산을 위해선
월드 공간으로 변환할 때 회전된 데이터를 가지고 있어야 한다.
이렇게 회전된 경계 상자 를 'OBB ( Oriented Bounding Box )' 라고 한다.
참고로 그림의 OriendtedBox 구조체에서,
Orientation (회전) 을 사원수로 사용했는데 회전행렬을 받는 것보다 데이터가 훨씬 적기 때문이다.
=> 월드 공간에서 'AABB' 를 계산해도 되지만 범위가 많이 커질 수 있다. ( 아래 그림 참조. )
=> AABB 를 포기하고 OBB 를 사용하는 것도 방법이다.
*OBB ( Oriented Bounding Box ) 충돌 처리
SAT ( Separating Axis Theorem )
=> oriented 란 Box 의 축이 표준 좌표축에 정렬되지 않아도 됨을 의미.
들어가기 앞서,
convex polygon (볼록 다각형) / concave polygon (오목 다각형) 차이점,
분리축 개념에 대해서 알아보자.
* convex polygon ( 볼록 다각형 )
1. 다각형의 내각이 항상 180° 보다 작아야 한다.
2. 다각형의 꼭지점을 이은 선들은 항상 다각형 있다.
* concave polygon ( 오목 다각형 )
1. 적어도 하나의 다각형의 내각이 180° 보다 크다.
2. 다각형의 꼭지점을 이은 선들 중 적어도 하나는 다각형 안에 없다.
polygon collision algorithm 에는 대표적으로 두가지 방법이 존재하는데
SAT Algorithm / GJK Algorithm 이다.
우리가 알아볼 SAT 알고리즘은 convex polygon 에서만 유효한 알고리즘이다.
SAT Algorithm 에서는 분리축 ( Separating Axis ) 개념을 이용한다.
*분리축이란 ??
=> 두 물체를 나눌 수 있는 평행한 선.
어떤 변의 N (Normal vector) 의 수직은 두 물체의 분리축이 될 수 있다.
따라서,
어떤 변의 N 에 물체들의 최소, 최대 정점을 투영시켜
투영시킨 곳의 영역이 서로 겹쳐져있는지 판별해 분리축을 만들 수 있는지 판단한다.
'분리축의 생성 여부' 가 해당 두 물체의 충돌 의 결과이다.
* SAT 를 이용한 충돌 확인 과정
그림을 예시로 설명하겠다.
우선 A, B 도형이 충돌한다고 가정하고 일부 과정을 살펴보면,
충돌 판별할 도형 중 한 변의 수직인 법선 벡터 ( Normal Vector ) 를 구한다.
( 그림에서는 B 도형의 보라색 화살표가 되겠다. )
이 후,
각 도형에서 해당 법선 벡터 기준으로 투영될 수 있는 최대, 최소인 점을 구한다.
그리고 해당 점들을 법선 벡터에 투영시킨 벡터를 구한다.
( 그림에서는 a1,a2 / b1,b2 )
만약,
각각의 도형의 점들이 투영된 벡터가 겹치지 않는다면 분리축이 들어갈 공간이 있다는 의미가 된다.
( 그림에서 Blank 표시 )
반대로,
투영된 벡터가 겹쳐진다면 분리축이 들어갈 공간이 존재하지 않으므로 두 도형은 충돌되었다고 볼 수 있다.
( 그림에서 Overlap 표시 )
위 과정을 비교하려는 각 도형의 변마다 수행해야한다.
Overlap 되어진다는 사실을 확인해 분리축이 들어갈 수 없음을 확인해야하기 때문이다.
이제 코드로 구현해보자.
해당 과정을 코드로는 어떻게 구현할 수 있을까 ??
* [2D] OBB 충돌의 SAT ( Separating Axis Theorem ) 활용
//의사코드
for (va : a_vertices)
{
normal = perpendicular(va);
for (vb : b_vertices)
{
projection = dot(vb - va, normal);
minSep = min(minSep, projection); //내적 계산의 최소를 구한다.
}
int result = MAX_MIN;
result = max(separation, minSep); //구한 내적의 최솟값의 최대를 구한다.
/* 하나라도 분리축이 생기는 공간이 있다면 충돌이 아니기 때문. */
}마찬가지로 위 그림을 예시로 A 도형 ( 삼각형 ), B 도형 ( 사각형 ) 이라 생각하자.
1. A 물체의 정점들을 모두 돈다. ( for 문 )
2. A 정점들의 법선 벡터를 구한다. ( normal )
의사코드 a_vertices 는 정점들을 담은 리스트이고
선택된 정점의 다음 정점을 가져와 벡터를 만들 수 있다.
3. B 물체의 정점들을 모두 돈다. ( for 문 )
va 정점에서 normal 벡터를 구한 구문 안에서 다시 B 물체의 정점을 돈다.
4. vb 를 가지는 for 문 안에서 normal vec 와 내적을 계산.
이론에선 투영되는 최대,최소를 구하는 것으로 나오지만,
실제 구현에는 적용하기가 힘들다.
하지만 우리는 간단하게 구할 수 있다.
B 도형의 정점들이 법선 벡터와 수직인 변의 정점인 va 의 뒤쪽에 존재하는지 확인하는 것이다.
A 도형 정점 중에서 선택된 va 와 vb 를 잇는 벡터
즉,
vb - va ( vb 로 향하는 ) 벡터가 normal 벡터와 같은 방향을 가리키는지 확인하면 된다.
만약 음수라면 뒤쪽에 존재한다는 의미로 해당 변보다 뒤에 있다.
따라서, 분리축이 생길 수 없다고 볼 수 있다.
5. 각 A 정점마다 minSep 의 최댓값을 구한다.
최댓값을 구하는 이유는 음수일 때 분리축이 생길 수 없기 때문이다.
만약,
최댓값이 양수라면 분리축이 생김으로 충돌되지 않음을 의미한다.
6. 해당 과정을 B 도형에 다시 수행해준다.
=> 충돌할 물체들의 모든 변을 확인해야하므로 다시 B 도형 기준으로 수행해준다.
* 왜 A, B 오브젝트 모두 변을 확인해주어야 하는걸까 ??
=> 그림에서 보듯이,
만약 B 에 기준에서만 변의 법선 벡터를 확인하게 되면
B 의 변에 해당 하는 축 모두 A 오브젝트와 겹치게 된다. 하지만 충돌되지 않았다.
A 기준의 녹색으로 표시된 Normal vector 에 대해서도 확인해야지만
충돌 검사를 재대로 할 수 있다.
* [3D] OBB 충돌의 SAT ( Separating Axis Theorem ) 활용
3차원에서는 어떻게 구현해야할까 ??
두 육면체 A, B 오브젝트가 있다고 가정할 때,
총 평면 각각 6개 씩 12개
A 변들 12개 * B 변들 12 개 = 144개
도합 156 가지의 분리축이 생길 수 있는 경우의 수가 존재한다.
하지만,
같은 법선 벡터를 가지는 평면 / 같은 방향을 가리키는 변들의 중복된 부분을 빼면
A, B 오브젝트들의 분리축이 생기는 경우의 수는 '15가지' 이다.
A 오브젝트의 평면 총 3개.
B 오브젝트의 평면 총 3개.
A 의 오브젝트 좌표축 (Cross) B 의 오브젝트 좌표축
각각의 좌표축들을 외적한 경우의 수 총 9개.
3D 에서는 분리축이 '평면' 이다.
여기서 나는 왜 3D OBB 에서는 각각 변들을 외적해야하는지 이해할 수 없었는데,
아래 예시로 이해할 수 있었다.
위 링크를 토대로 간단하게 설명하자면,
총 4장의 사진 ( 위 링크 참조 ) 으로 설명 가능한데,
편의상 순서대로 1,2,3,4 번 사진, Normal vector 도 N 으로 부르려한다.
3D 에서 OBB 물체들은 각각 회전할 수 있다.
그에 따라, 각각의 오브젝트가 가지는 축들이 변하게 되는데
이 때, 1번 사진은 특정한 상황에서의 예이다.
1번 사진에서 두 물체 사이의 간격이 아주 얇게 떨어져있다고 생각해보자.
해당 상황을 어떤 분리축의 N 에 투영시켜 판별해야할까 ??
2, 3 번 사진에서는
해당 오브젝트의 평면의 N 따라 투영 시, 모두 겹친다.
따라서, 그림에 나오는 분리축을 판별할 수 없다.
이 때, 두 오브젝트 변들의 외적한 축을 사용해 판별 가능하다.
4번 사진의 빨간색 부분의 벡터가 분리축의 N 이 되겠다.
3,4 번 사진에서 녹색으로 표시한 벡터들을 외적한 벡터이다.
이렇듯
해당 오브젝트 좌표축에 해당하는 벡터들의 외적을 이용해
이러한 상황을 모두 판별함으로써 정확한 분리축 생김 여부를 판별할 수 있다.
결국,
3D 에서 외적을 사용하는 이유는 평면이 분리축이 되기 때문이다.
* 결론
AABB : 축과 정렬된 경계 축
OBB : 축과 정렬되지 않는 경계 축
=> AABB 를 회전시켰을 때, 발생.
이 때, AABB 를 다시 설정하게 되면 추가 비용, 크기가 커질 가능성 존재.
* OBB 의 충돌처리
분리축 : 두 물체 사이에 존재하는 선. 두 물체를 분리하는 선
SAT ( Separating Axis Theorem )
=> 두 물체 사이에 분리축이 생기는지 아닌지 확인해 충돌 확인
분리축이 생길 수 있는 공간을 판별하기 위해
분리축과 수직이 되는 벡터 필요.
수직이 되는 벡터에 두 물체를 투영시켜
투영시킨 범위가 겹친다면 분리축이 생길 공간이 없음.
즉, 두 물체가 겹쳐진 상태.
해당 작업을 A, B 물체에 분리축이 생길 수 있는 모든 곳에 수행.
* 3D 에서의 SAT
물체의 변이 분리축이 되는 2D 와는 다르게,
3D 에서는 평면이 분리축이 되기 때문에 고려해야할 경우의 수가 많음.
만약 큐브 모양의 경계 상자를 충돌 확인한다고 가정할 때,
총 15가지 경우의 수 존재.
A,B 각각의 평면의 벡터 : 3 + 3 = 6개
A 의 변 벡터 (좌표축) (Cross) B 변 벡터(좌표축) : 3 * 3 = 9개
해당 경우의 수 모두 분리축이 생기지 않았다면
충돌되어졌다는 의미가 된다.
* 22/11/04 수정사항
1. 노말 벡터 -> 해당 변의 수직인 벡터 = 법선 벡터
=> 용어의 혼동 여지가 있어 바꿈.
2. SAT 관련 예시 그림 추가 및 설명 추가.
참고 자료
'DirectX > 개념' 카테고리의 다른 글
| [DX] ##8. FRUSTUM CULLING ( 절두체 선별 ) (0) | 2022.08.25 |
|---|---|
| [DX] ##7. GJK ( GILBERT-JOHNSON-KEERTHI ) Algorithm (0) | 2022.08.15 |
| [DX] ##5. 직교투영, Screen Space ( Window Space ) (0) | 2022.08.02 |
| [DX] ##4. Z-Fighting (0) | 2022.07.31 |
| [DX] ##2. Local, World, View Space (0) | 2022.07.29 |