AABB 와 삼각형 충돌 (Intersecting AABB and triangle)

AABB와 삼각형 충돌에 SAT방법이 적용된다.

먼저 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개 점

계산을 간단히 하기 위해 AABB의 중심이 원점이 되도록 이동 한다.
그 결과 삼각형의 점도 같이 이동 된다.
(AABB에 적용되는 월드 행렬의 역행렬을 사용하면 가능하다.)

OBB의 경우에는 반대로 회전 시켜 AABB로 만들어 계산 하면 된다.
(OBB의 월드행렬을 사용하여 원점으로 이동 후 AABB를 만들기 위해 회전시킨다.)

그리고 삼각형의 각 변은 다음과 같이 찾을 수 있다.

AABB를 원점, 축 형식으로 다시 표현한다.

AABB의 3개의 축

삼각형의 3개의 변

위의 각 3개의 축 과 3개의 변을 외적 하여 축 9개의 만들어 낸다.
그리고 이 9개의 축에 대해 투영을 시도 한다.

AABB의 반지름은 다음과 같이 나타낼 수 있다.
n: 반지름을 만들어 내는 축
e_i: AABB 3개의 축 길이
u_i: AABB 각 축
r: AABB의 반지름
(0 <= i <= 2)

예시로 9개의 축 중에 a₀₀경우를 살펴 본다.AABB 반지름은 위의 식에 의해 만들어 진다.
이 식에서 축 n 대신에 a₀₀을 사용한다.

이런 방법으로 9개 축에 AABB를 투영하여 반지름을 얻는다.

이제 삼각형을 9개 축에 투영해 보자.
a₀₀경우

이런 방법으로 9개 축에 삼각형을 투영하면

지금까지 결과를 보면 아래와 같은 패턴이 반복되는 것이 확인 된다.
p₀, p₂
p₀, p₁
p₀, p₁

그리고 삼각형의 경우는 각 축의 경우에서 투영된 값의 최소값과 최대값을 구하여 사용한다.

그런데 위에서 나왔던 패턴에 따라 최소, 최대 값을 구하면 2개의 항목만 사용하면 된다.

9개 축에 대해서 모두 정리하면
(각 축의 경우 마다 p₀, p_1, p₂ 값이 다르므로 주의)

이제까지 9개 축에 투영된 AABB와 삼각형에 대해서 교차 여부를 확인할 차례이다.

위에서 AABB를 투영하여 얻은 값은 반지름 값이므로 지름은 아래 범위 값이 된다.
[-r, r]

그래서 9개 축에 대해 아래 식을 모두 만족하면 교차하지 않는 상태가 된다.

1번 과정>
1. AABB의 법선 벡터 (3개)

앞의 3번 과정에서 AABB는 중심을 (0, 0, 0)으로 가진 상태로 변환된 상태 이다.
교차 검사는 AABB와 AABB의 교차 검사 방법과 유사하게 진행 된다.

AABB 각 축 거리의 절반
(e₀, e₁, e₂)

그리고 아래 식을 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판