먼저 SAT를 알아보자.
SAT(Separating Axis Theorem)는
임의의 떨어져 있는 두 볼록 다면체 A, B에 대해 어떤 축이 존재하고
그 축으로 각 다면체를 투영하여 투영된 구간들이 겹쳐지지 않는다는 이론
A, B가 겹치지 않을 경우 다음 축들 중 하나에 대한 평행한 축에 의해 분리 된다.
1. A의 면 중 하나의 법선 벡터
2. B의 면 중 하나의 법선 벡터
3. A의 변과 B의 변에 동시에 수직인 축 (외적)
SAT 이용하여 총 13개 축을 TEST 한다.
1. AABB의 법선 벡터 (3개)
2. 삼각형의 법선 벡터 (1개)
3. AABB의 축과 삼각형 각 변과의 외적 (9개)
separating axis을 찾으면 바로 exit 그리고 교차 하지 않는다.
모든 separating axis 검사 후 축을 찾지 못하면 반드시 교차 한다.
효율적인 검사 순서는 3-> 1-> 2으로 진행한다.
3번 과정>
3. AABB의 축과 삼각형 각 변과의 외적 (9개)
삼각형의 3개 점
.png)
계산을 간단히 하기 위해 AABB의 중심이 원점이 되도록 이동 한다.
그 결과 삼각형의 점도 같이 이동 된다.
(AABB에 적용되는 월드 행렬의 역행렬을 사용하면 가능하다.)
OBB의 경우에는 반대로 회전 시켜 AABB로 만들어 계산 하면 된다.
(OBB의 월드행렬을 사용하여 원점으로 이동 후 AABB를 만들기 위해 회전시킨다.)
그리고 삼각형의 각 변은 다음과 같이 찾을 수 있다.
AABB를 원점, 축 형식으로 다시 표현한다.
AABB의 3개의 축
삼각형의 3개의 변
위의 각 3개의 축 과 3개의 변을 외적 하여 축 9개의 만들어 낸다.
그리고 이 9개의 축에 대해 투영을 시도 한다.
AABB의 반지름은 다음과 같이 나타낼 수 있다.
n: 반지름을 만들어 내는 축
ei: AABB 3개의 축 길이
ui: AABB 각 축
r: AABB의 반지름
(0 <= i <= 2)
예시로 9개의 축 중에 a00경우를 살펴 본다.AABB 반지름은 위의 식에 의해 만들어 진다.
이 식에서 축 n 대신에 a00을 사용한다.
이런 방법으로 9개 축에 AABB를 투영하여 반지름을 얻는다.
이제 삼각형을 9개 축에 투영해 보자.
a00경우
이런 방법으로 9개 축에 삼각형을 투영하면
.png)
.png)
지금까지 결과를 보면 아래와 같은 패턴이 반복되는 것이 확인 된다.
p0, p2
p0, p1
p0, p1
그리고 삼각형의 경우는 각 축의 경우에서 투영된 값의 최소값과 최대값을 구하여 사용한다.
그런데 위에서 나왔던 패턴에 따라 최소, 최대 값을 구하면 2개의 항목만 사용하면 된다.
9개 축에 대해서 모두 정리하면
(각 축의 경우 마다 p0, p1, p2 값이 다르므로 주의)
이제까지 9개 축에 투영된 AABB와 삼각형에 대해서 교차 여부를 확인할 차례이다.
위에서 AABB를 투영하여 얻은 값은 반지름 값이므로 지름은 아래 범위 값이 된다.
[-r, r]
그래서 9개 축에 대해 아래 식을 모두 만족하면 교차하지 않는 상태가 된다.
1번 과정>
1. AABB의 법선 벡터 (3개)
앞의 3번 과정에서 AABB는 중심을 (0, 0, 0)으로 가진 상태로 변환된 상태 이다.
교차 검사는 AABB와 AABB의 교차 검사 방법과 유사하게 진행 된다.
AABB 각 축 거리의 절반
(e0, e1, e2)
그리고 아래 식을 x, y, z 축에 대해 모두 만족하면 교차 하지 않는 상태가 된다.
2번 과정>
2. 삼각형의 법선 벡터 (1개)
AABB와 평면 교차 검사 방법으로 확인 가능 하다.
삼각형의 법선 벡터를 사용하여 AABB의 반지름(r)을 구한다.
그리고 삼각형이 만드는 평면과 AABB의 거리(s)를 구해서 비교 한다.
s>r
위의 식이 만족하면 교차 하지 않는 상태가 된다.
여기 까지 총 3개의 과정을 거쳐 검사를 하며
이 과정을 모두 통과 하면 AABB와 삼각형은 교차 상태가 된다.
참고자료
Essential Mathematics For Games And Interactive Applications
3D 게임 프로그래밍 & 컴퓨터 그래픽을 위한 수학 제2판
Real-Time Rendering 2판
