2차원 직선과 직선 교차 (Intersecting line and line)

직선을 다음과 같이 표현 한다.

두개의 직선이 만나므로 아래 식으로 시작하여 풀이 된다.

같은 벡터에 대해서 내적을 하면 0이 되는 관계를 이용한다.

먼저 s에 대해서 정리하고

다음 t에 대해서 정리한다.

d₁^⊥: d₁의 수직 성분
d₂^⊥: d₂의 수직 성분

그리고 s, t에 대해 정리된 식을 모아보면 다음과 같다.

아래의 경우 두 직선은 평행한 상태가 된다.

그리고 아래 3가지 경우에 따라서 s, t값의 범위를 확인하여
교차 검사를 진행하면 된다.

1. 직선의 경우(시작과 끝이 무한대)
    s, t는 무한대

2. 선분의 경우
    d가 단위 벡터의 경우
    0 <= s <= l₁, 0 <= t <= l₂
     (l_1,l₂:각 선분의 길이)

    d가 단위 벡터가 아닐 경우 (P_end - P_start)
    0 <= s <= 1, 0 <= t <= 1
    (P_start, P_end:선분의 시작점과 끝점)

3. 광선의 경우
    0 <= s, 0 <= t

두 번째 방법으로는 선분의 s, t범위를 이용하여 구하는 방법이 된다.

첫번째 교차 방법에서 사용했던 식을 가져와서 사용한다.

먼저 2개의 직선 r₁, r₂에 대해서 다음과 같이 나타낸다.

그리고 d를 단위 벡터가 아닌 직선의 끝점과 시작점의 차이로 나타낸다.

이렇게 해서 s, t에 대한 식을 다시 정리하면

식을 간략히 하기 위해 아래과 같이 정의하고 다시 식을 정리하면

s식의 분모를 t식의 분모와 동일하게 만들기 위해 아래 정의를 이용한다.

최종적으로 아래 식과 같이 정리 된다.

이제 교차 여부를 검사 하면 한다.

f의 값이 0이 되면 두 직선은 평행 상태가 된다.

평행이 아닐 경우에는 s, t값의 범위를 검사한다.

이 방법에서는 방향 벡터 d를 직선의 끝점과 시작점의 차를 이용하므로
선분의 경우 s, t는 아래를 만족 해야 한다.
0 <= s <= 1, 0 <= t <= 1

그러므로 아래 조건을 통과 하면 교차 상태가 된다.

s의 경우
if f > 0 then
   if d < 0 or d > f then no_intersect
else
   if d > 0 or d < f then no_intersect

t의 경우
if f > 0 then
   if e < 0 or e > f then no_intersect
else
   if e > 0 or e < f then no_intersect

참고자료
Real-Time Rendering 2판

직교 투영 (Orthographic Projection)

이 투영 방법은 z값에 상관없이 변환 후에도 x, y값이 그대로 보존 된다.

원근 투영과 달리 투영 평면에 수직한 평행선을 따라
양의 z값, 음의 z값 모두 같은 평면으로 투영하게 된다.

그래서 특정 구간으로 z값을 제한 하여 사용한다.

투영은 뷰 변환 후에 (l, r, b, t, n, f)의 AABB 공간을 변환하게 된다.
l: 왼쪽 좌표
r: 오른쪽 좌표
b: 아래쪽 좌표
t: 위쪽 좌표
n: 가까운 평면
f: 먼 평면

위 4개 항목(l, r, b, t)는 현재 화면 크기에 맞추어 사용하게 된다.

예를 들어 1024x768의 화면을 가진 프로그램의 경우
(0, 1024, 0, 768)이 된다.

혹은 특별한 상황에 따라 값을 다르게 사용할 수 있다.

투영 변환 후에 생성 되는 공간을 정규화된 장치 좌표.
NDC(Normalized Device Coordinates)라고 한다.

NDC는
최소값으로 (-1, -1, -1), 최대값으로 (1, 1, 1)을 가진
축에 정렬된 정육면체 공간이 된다.

위의 경우는 OpenGL의 경우이며,

DirectX의 경우는
최소값으로 (-1, -1, 0), 최대값으로 (1, 1, 1)을 가지는
정육면체 공간을 사용한다.

즉, 직교 투영은 (l, r, b, t, n, f)의 AABB를
(-1, -1, -1), (1, 1, 1)의 AABB로 변환하는 결과가 된다.

먼저 y값의 변환을 생각해 보자.

z값은 y값에 영향을 주지 않으니 y의 변환만 신경쓰면 된다.

첫번째로 y값을 뷰 윈도우(l, r, b, t) 기준으로 되도록
값을 조정(이동) 한다.
아래 점이 원점이 되도록 y값을 수정 하면 다음 같이 된다.

 

두번째로 y값을 NDC영역인 [-1, 1]의 범위가 되도록 조정(스케일) 한다.

[b, t]에서 [-1, 1]으로 변환이 되므로
(t-b)의 크기에서 2의 크기로 스케일 된다.
그래서 다음 크기 만큼 곱해준다.

 

x값도 위와 같은 방법으로 [l, r]범위에서 [-1, 1]범위로 변환하게 된다.

z값의 경우는 추가 작업이 필요하다.

상식적으로 z값은 가까운 평면(n) < 먼 평면(f) 으로 생각 된다.

하지만 OpenGL의 경우 z축은 화면에서 밖으로 튀어나오는 방향이다.

그러므로 실제 계산에서는 z값에 음수를 곱하여 사용해야 한다.

지금까지의 결과로 직교 투영 변환은 이동 변환, 크기 변환이 차례대로
이루어지는 것을 확인할 수 있다.

행렬을 사용하여 차례대로 정리하면

DirectX의 경우 NDC의 z값은 [0, 1]범위가 된다.
[n, f]에서 [0, 1]으로 변환이 되므로 (f-n)의 크기에서 1의 크기로 스케일 한다.
n의 값이 ndc로 변환했을때 원점이 되므로 이동 변환할때는
현재 z값에서 n값 만큼만 빼주면 된다.

그리고 z축은 화면 밖에서 안쪽으로 들어가는 방향이 되므로 z값에 음수를 곱하지 않아도 된다.

그 결과 위의 행렬은 조금 수정되어 아래와 같이 된다.

참고자료
Essential Mathematics For Games And Interactive Applications
Real-Time Rendering 2판

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판

박스(AABB, OBB)의 반지름 구하기 (Radius of AABB and OBB)

벡터 n에 투영한 박스(AABB, OBB)의 반지름 구하기

먼저 박스의 각 축을 다음과 표시한다.


각 축의 길이는 다음과 같이 표시한다.

그래서 박스의 포함된 점R은 다음식으로 나타낼 수 있다.






c: center of a box

따라서 박스의 외곽을 구성하는 8개의 점은 아래와 같이 된다.

박스의 반지름을 구하기 위해서는 반지름을 만들어낼 벡터n을 선택한 후
벡터n에 투영하여 구하면 된다.

이렇게 박스의 8개 점을 모두 투영하고 하나를 선택하여 사용한다.
투영된 길이 중에서 최대 값을 사용하여야 박스의 모든 점을 포함하는
최대 반지름값을 얻을 수 있게 된다.

그럼 위 식에서 최대 반지름을 만족 시키기 위해서
먼저 각 축의 길이는 모두 양의 값을 가지게 된다.
그래서 위 식을 아래와 같이 정리할 수 있다.

만약 벡터n이 단위 벡터가 아닌 경우 n의 크기로 나누어 주면 된다.

참고자료
Essential Mathematics For Games And Interactive Applications
3D 게임 프로그래밍 & 컴퓨터 그래픽을 위한 수학 제2판
Real-Time Rendering 2판