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판

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판

광선과 삼각형 교차 ( Intersecting ray and triangle )

먼저 무게 중심 좌표(barycentric coordinate)부터 생각해 보자.

무게 중심 좌표는 참조되는 점들의 무게를 조합하는 형식으로 공간을 표현한다.

예를 들어 선분 AB를 생각해 보자

임의의 점 P는  선분  AB 사이에 있는 하나의 점이라고 가정 한다.

그럼 점 P는 아래과 같은 식으로 표현할 수 있다.

P=A + t(B-A)

풀어서 정리하면 다음과 같이 되고

P = A + tB - tA

P = (1-t)A + tB

여기서 표현을 바꾸면

위 식에서 u, v를 무게 중심 좌표(barycentric coordinate)라고 말한다.

참고로 barycentric 이라는 단어에서 bary는 그리스 단어에서 '무게'라는 뜻을 가지고 있다.

삼각형의 경우로 다시 생각하면 삼각형 안의 임의의 점 P 와

동일 선상에 있지 않는 점 A, B, C에 대해서 아래와 같이 나타낼 수 있다.

세번째에 있는 식을 보면 v, w 2개의 변수만 있어도 u를 구할 수가 있다.

그러므로 위 식을 다음과 같이 정리하여 아래에서 계속 사용 한다.

무게 중심 좌표에 따라서 각 u, v, w의 값을 표시 하면 아래과 같은 형태를 생각 할 수 있다.

각 점에서의 u, v, w 값은 아래과 같이 된다.

(u, v, w)

A=(1, 0, 0)

B=(0, 1, 0)

C=(0, 0, 1)

그리고 u, v, w의 값을 확인 하여 임의의 점이 삼각형 안에 있는지 확인할 수 있다.

그럼 이제 삼각형과 교차하는 광선을 생각해 보자.

광선은 아래와 같이 나타낼 수 있다.

o는 광선의 시작점을 나타내고 t는 광선의 길이는 나타내는 스칼라 변수 이다.

그리고  d는 광선의 방향을 나타내는 단위 벡터가 된다.

광선과 삼각형의 교차점은 위에서 설명한 2개의 식을 생각해 본다.

삼각형 안의 임의의 점

광선의 임의의 점

결국 교차점은 삼각형 안의 임의의 점과 광선의 임의의 점이 같을 경우가 된다.

이제 여기서 필요한 t, v, w의 값을 위 식을 계산하여 구해 보자.

 

위 식을 행렬식으로 다시 표현 하면 아래와 같이 된다.

앞쪽에 있는 행렬의 역행렬을 양변에 곱하면 t, v, w의 값을 구할 수 있다.

여기서 역행렬을 구할때는 cramer's rule을 사용 한다.

예를 들어 아래와 같이 3개의 선형 방정식이 있고 원하는 x, y, z 값을 구해야 한다.

 
 

이때 caramer's rule을 적용하면 

,,

식을 간단히 만들기 위해 먼저 d의 determinant식 풀어 본다.

determinant에서는 매트릭스를 전치하여 풀어도 같은 값이 된다. 

위의 d를 아래와 같이 전치하고

d의 determinant 표현을 식으로 풀게 되면 다음과 같다.

위의 식을 정리하면 내적으로 표현할 수 있다.

여기서 각각의 변수를 아래와 같이 벡터로 생각하고

 
 

위 식을 벡터로 표현하면

이제 복잡하게 정리 되었던 x, y, z를 위의 정리를 통해 정리하고

마지막으로 행렬로 다시 표현하면 아래과 같이 표현할 수 있다.

이제 원래대로 돌아가서 t, v, w를 구할 식을 다시 살펴 보자.

식을 간단히 하기 위해 각각의 요소를 아래와 같이 다시 정의 한다.

위 값을 caramer's rule를 사용하여 정리한 식에 대입을 해보자.

여기서 d값이 0이 되면 역행렬은 존재하지 않게 된다. 

그리고 계산량을 줄이기 위해 d값을 먼저 계산하여 변수에 저장하고 다시 사용하도록 한다. 

먼저 - 부호를 제거 하자.

외적의 정의에 따라서 

스칼라 값 r, s이 주어진 경우와 -부호를 적용될 경우 다음과 같다.

또한, Scalar Triple Product 정의에 따라 다음과 같이 된다. 

위의 정의들을 이용하여 식을 정리하면 

계산량 감소 및 재사용을 하기 위해 다음과 같이 정의 한다.

필요에 따라서 t, v, w값을 전부 계산하거나 혹은 부분계산하여 사용하도록 소스를 구현하면 된다.

마지막으로 앞에서 설명하였듯이 t값은 광선을 나타내는 식에 대입하여 사용하고

v, w 값은 삼각형 안의 임의의 점을 나타내는 식에 대입하여 사용하면 된다. 

참고자료

Real-Time Rendering 2판

Real-Time Collision Detection