광선과 삼각형 교차 ( 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