픽킹~ 수학 이론

별 헤는 밤 비는 내리고 | 긴타마
http://blog.naver.com/preknife/26108881

ㅡ_- 우훠훠 정리 했던걸 모르고 가볍게 삭제해버리는 센스...

 

www.gamza.net 에 이성수님이 자세히 설명을 해 주셨는데...

 제가 수학이 너무 딸려서 이해하기 어려워서 열심히 제 수준으로 재 정리를 해 보았습니다. 이해 못하고 얼버무린게 많지만 냐햐햐햐햐

 

 

일단... IntersectTriangle의 함수는 반직선과 삼각형의 교차판정을 하는 함수인데 정확히 이게 반직선과 삼각형 평면과의 교점이 삼각형에 포함되는지 검사 하는 거라고 합니다.

그런데 점포함 테스트를 하지않고 다른 방법을 쓴다고 하네요 -_-;;

 

그림을 보시면 벡터가 세개 나옵니다. OA,OB는 고정된 벡터이고 OP는 임의의 벡터입니다.
임의의 벡터 OP를 벡터 OA,OB를 가지고 표현해 봅시다.

OP = u * OA + v * OB ( u,v는 임의의 실수 )

 

여기서 보시면, 벡터 OA와 벡터 OB의 함성벡터가 OP라고 했을때, 점 P가 OAB로 된 삼각형 영역 안에 있는 조건으로 OA와 OB 각 각 u, v를 곱해 줍니다. ;;

 

즉 u,v에 어떤 조건을 붙여서 P가 삼각형 OAB영역을 표현하도록 하려는겁니다.
P가 OAB영역을 표현하기위한 조건은, 삼각형의 변(①②③)에대해 각각 하나씩 있습니다.
① : 0 ≤ u
② : 0 ≤ v
③ : u + v ≤ 1

 

-_-조건 증명은 잘 모르겠습니다. 웬지 그럴것 같아서 ㅎㅎㅎ;;

위조건을 만족하는 u,v에 대해 P가 표현하는 영역은 삼각형 OAB입니다.
점 P가 삼각형 OAB에 포함되는지를 검사하는것은 u,v가 위조건을 만족하는지를 검사하는것과 같다는 얘기.
IntersectTriangle이 출력하는 u,v가 지금껏 이야기해온 u,v입니다. 반직선과 삼각형 평면의 교점이 P, 삼각형의 각 꼭지점이 O,A,B인 셈이죠. 따라서 반직선과 삼각형의 교차판정은 코드중에 다음처럼 나타납니다

 

그럼 이제 u, v값을 어떻게 구하는지 보겠습니다.

아래 그림 보시면...  그림에 설명이 잘 되어 있네요 ;;

즉 위에 조건을 기본으로  v값 공식을 유도 하였습니다.

 

이때 벡터 OB와 Ob를 OA에 수직인 벡터 nA에 투영을 한것이 오른쪽 그림입니다.

 

v = |Ob|/|OB| = |Ob||nA|cosθ/|OB||nA|cosθ = Ob•nA/OB•nA  

여기서 위처럼 한게.. 내적을 유도하려고 한것 같습니다. -_-;

그래서 OA와 수직인 벡터 nA에 투영한 OP, Ob벡터의 정사영이 같으므로

 

Ob•nA = OP•nA
∴v = Ob•nA/OB•nA = OP•nA/OB•nA

같은 방법으로 u를 표현하면..

u = OP•nB/OA•nB  

추가로 넣은 그림은... -_-저처럼 내적에서 투영의 의미가 햇갈리실 까봐 넣어 봤습니다.

의미는 옆에 있는 글 의미 그대로...

 

이제는 실제 IntersectTriangle함수 인자들을 이용하여 교차판정을 어떤식으로 하는지 그 부분을 보겠습니다. 이 부분은 --; 아직 정확히 이해는 못하겠는데, 대략적인 이해 내용만 적겠습니다.

 

 

실제로 IntersectTriangle은 공간상의 반직선과 평면의 교점(P)을 구하지 않고 u,v값을 계산해 냅니다. 점이 없이도 OP•N 값을 알아내는 방법이 있기때문인데요, 바라보는 방향에 비책이 숨어 있습니다.

 

왼쪽그림은 IntersectTriangle의 입력들을 그려놓은것입니다. 오른쪽 그림은 이것을 dir과 평행한 방향으로 바라본 그림이고요.
그림에 표시된 법선(N)은 V0,V2를 포함하고 바라보는 방향과 평행한 평면의 법선벡터입니다.

 

이때, 점 P와 orig는 이 벡터(N)에대해 '같은 정사영'을 갖는 점들임을 알수 있습니다. 즉 다음이 성립한다는 말이죠.

 

-_-이 말이 아직도 햇갈립니다. 대충 생각해 본게... 일단 dir은 평면에 평행하다고 했습니다.

이 말은 즉 평면상에 P와 Orig가 있다는 예기가 되고, 이는 즉 V0-Orig와 V0-P또한 평면상에 있다는 예기일듯 합니다. 그러면 Orig와 P가 같은 정사영을 갖는지 그림으로 보면...;; 일단 N은 해당평면의 법선벡터라고 하였습니다.

 

 

그래서 이는

(orig-V0)•N == (P-V0)•N

 

라고 할 수 있겠습니다.

N을 법선으로 하는 평면은 V0,V2,(V0+dir)을 포함하는 평면이고(dir과 평행한 방향으로 바라봤으므로), 따라서 법선 N은 다음과같이 구해집니다.

--; 앞에서 추측한 대로라면... 이렇게 나올 것입니다. 즉 dir과 v2-v0의 외적으로 바라보는 방향과 평행인 평면을 얻고 그 법선벡터를 만드는 것이지요... 즉 결과적으로 보면, 바라보는 방향의 평면을 만드는 목적을 --;; 이건 아닌가...

N = dir ⅹ ( V2 - V0 )

 

이제 모든값을 알았으니 정리를 좀 해볼까요?

위에서 u = OP•nB/OA•nB 라고 했습죠...

그러면 일단 OP는 평면상의 벡터를 나타내므로 orig-V0으로 구할 수 있을듯 합니다.

그리고 nB는 아까 위에서 구한 N이 되겠지요...

N은 앞에서 V2-V0과 수직인 벡터이면서 dir과 이루어진 평면의 법선벡터이기도 하니까...

 nB가 여기서의 N이 되겠습니다.

 

OA는 V1-V0이 되겠고... 정리하면

e1 = V1 - V0
e2 = V2 - V0

 

여기서 OP가 orig-V0이라고 한게;;;

P가 평면상의 3점을 포함한 평면상의 교차점이라고 한다면, dir에 평행이고, V2-V0으로 된 평면의 법선벡터 N에 대해서 OP와 Orig-V0은 동일한 정사영을 가짐을 알 수 있으므로 tvec을 OP대신 Orig-V0으로 나타낼 수 있다... 라고 생각을...

tvec = orig - V0

 

u = tvec • ( dir ⅹ e2 ) / e1 • ( dir ⅹ e2 )

 

소스에 나와 있는 대로라면 아래와 같습니다. (위 공식 있는 그대로 입니다;;)

D3DXVec3Cross( &pvec, &dir, &edge2 );   

FLOAT det = D3DXVec3Dot( &edge1, &pvec );
*u = D3DXVec3Dot( &tvec, &pvec );

FLOAT fInvDet = 1.0f / det;

*u *= fInvDet;

//방금 전에 글 보고 웃겨서 지웠습니다 -_-;; det/1 * u 가  det/u죠.. 이제는 나눗셈까지 한계를...

 

 

 

다음부터는 -_- 안그래도 이해가 안되는데;;;더 이해가 안되서 대충~

 

u를 구한것과 같은 방법으로 v를 구해 봅시다.

v = tvec • ( e1 ⅹ dir ) / e2 • ( e1 ⅹ dir )

여기에 약간의 수학적성질을 적용해보면 재미있는 사실을 알게됩니다.

A•(BⅹC) = B•(CⅹA) = C•(AⅹB)

이것을 이용해서 v의 분모부분을 변형해볼까요?

e2 • ( e1 ⅹ dir ) = e1 • ( dir ⅹ e2 )  

오호...잘보니 v,u의 분모부분이 같은넘이었군요!
분자부분도 같은방법으로 변형시켜보면 소스코드가 이해가 되실겁니다.
(이것두 역시 최적화. 나중에 t 를 계산할때 외적결과를 또 써먹으려고 변형을 해 놓은거죠. )
이것으로 다음소스에 대한 설명이 끝났습니다.

 

-_- 두 번 계산할 것을 위에 계산결과와 같게 유추하셔서 최적화 시키셨네요~~~ 멋지심...!!!

 

D3DXVec3Cross( &qvec, &tvec, &edge1 );
*v = D3DXVec3Dot( &dir, &qvec );
*v *= fInvDet; u구할떄 구했던 det?의 역수? 값 그대로... det/1 * v가 되겠네요 -_-

 

이제 아래 부터는 죽 읽어 나가도 무리 없을듯.... (-_-.. 사실 아직 안봤습니다. 캬캬캬)

 

IntersectTriangle은 연산을 수행하는 도중 판정결과를 알 수 있다면 바로 리턴하는 방식으로, 필요없는 연산이 일어나지 않도록 구성되어있습니다.
그중 하나가 첫번째 나온 비교문입니다.

if( det < 0.0001f ) return FALSE;

 

이 비교문은 코딩 차원에서 본다면 0으로 나누는 에러방지와 det값과 u,v값의 비교를 쉽게해주는 역할을 합니다만, 수학적으로 보면 이코드의 또다른면을 볼 수 있게됩니다.
이 조건이 참이되는 경우를 생각해 보도록 합시다. det값은 법선벡터 N과 변벡터 e1의 내적값입니다.
이값이 0이면 삼각형은 dir과 평행한 평면에 존재하는것 입니다. 만약 이 값이 0보다 작으면 삼각형이 뒤집어져 있는경우죠.

 

느끼는건데;;; DIr즉 바라보는 방향으로 한 평면에서 그에 수직인 벡터에 영역의 벡터를 투영시킬때 그 투영 길이가 영역안에 있는지, 여기서 투영길이는;; u, v값이 되겠지요... 추측입니다.

 여기서 잠깐!
D3D8.1 버젼부터는 det에 절대값을 취함으로써 뒤집어진 면도 교차라고 판정하도록 되어있습니다.
사실 이전 버젼의 예제들은 det값을 그대로 사용해서, IntersectTriangle함수가 반직선과 삼각형의 교차판정뿐 아니라 뒤집어진 삼각형이 아닌지까지 검사하도록 만들어져 있었던겁니다.
이것을 함수의 목적에 맞도록 수정했다고나 할까요?
하지만 det에 절대값을 취하는 부분만 없애면 '별도의 연산없이' 뒤집어진 삼각형을 검사해낼 수 있다는것을 꼭 알아두시길...

 

인자를 보면 t값도 있는데 이건 Orig와 P(교차점)과의 거리라고 합니다.

 

  *t = D3DXVec3Dot( &edge2, &qvec );
    *t *= fInvDet;

우선 설명을 하기전에 t와 det를 적당히 변형하도록 하겠습니다.
( 각종 연산결과들을 최대한 재사용하려고 변형해 놓은거라서 변형하지 않고는 설명이 넘 어렵습니다. )

det = e1 • ( dir ⅹ e2 ) = dir • ( e2 ⅹ e1 )
t = e2 • ( tvec ⅹ e1 ) = tvec • ( e1 ⅹ e2 ) = -tvec • ( e2 ⅹ e1 )
( ∵ AⅹB = -BⅹA )

공식을 보고 있자니 원래 문제를 e1,e2를 포함하는 평면과 평행한 방향으로 다시 보고싶어집니다.
(삼각형을 옆에서 바라봤으니 삼각형은 선분으로 보입니다.)

 

∴ t = |P-orig|/|dir| = |P-orig||N|cosθ/|dir||N|cosθ = (P-orig)•N / dir•N
(여기서 N = e2 ⅹ e1 ) 근데 N에 대해서 벡터 P-orig 와 -tvec이 같은 정사영을 갖습니다. 따라서...

(P-orig)•N == (-tvec)•N
∴ t = (P-orig)•N / dir•N = (-tvec)•N / dir•N      

t도 대충 보면... -_-;; 다음 기회에...

 

출처 :  http://www.gamza.net/ez2000/ezboard.exe?db=Algorithm&action=read&dbf=15&page=0&depth=1