[3D] 픽킹 (Picking)

픽킹이란 2D 스크린 좌표를 3D 좌표로 변경한 후 동일한 공간 내에서 교차 판정 하는 것이다.

여기서 중요한 것은 2D 좌표를 3D 좌표로 변경한다는 것이고, 동일한 공간! 내에서 교차판정한다는 것이다.

동일한 공간이 중요하다.

지형의 좌표가 존재하는 공간이 월드 공간이기 때문에 반드시 월드 공간으로 바꿔줘야한다.

과정을 간단히 말하자면,

1. 윈도우 좌표를 3D 좌표로 변경시킨다.

2. 폴리곤과 충돌체크를 한다. (IntersectTriangle)

이다.

픽킹이 처음에 어렵게 느껴지는 이유는 이 IntersectTriangle 함수가 프로그램을 위해 최적화된 함수로 몇몇 과정들이 축소되어있기 때문이다.

( Picking에 관한 코드는 Dx SampleBrowser에도 존재 하니 그걸 참고하세용 ~ 저도 그걸 참고해서 했어용>,<! )

먼저 2D 좌표에서 3D 공간 Ray를 뽑아내는 것을 보겠다.

<코드>

// 마우스 클릭 시 윈도우 좌표의 포인터를 구한다. POINT ptMouse; GetCursorPos(&ptMouse); ScreenToClient(g_hWnd,&ptMouse); // Ray 광선을 계산한다. // 2D 를 3D 좌표로 변경시킨다. D3DXVECTOR3 vRay; int nX = ptMouse.x; int nY = ptMouse.y; vRay.x = (((2.0f * nX)/WINSIZE_X) - 1.0f)/m_pCamera->GetProj()._11; vRay.y = (((-2.0f * nY)/WINSIZE_Y) + 1.0f)/m_pCamera->GetProj()._22; vRay.z = 1.0f; // Ray의 원점과 방향을 결정한다. m_vOrig = D3DXVECTOR3(0.0f, 0.0f, 0.0f); m_vDir = D3DXVECTOR3(vRay.x,vRay.y,vRay.z); // Ray를 뷰 행렬의 역행렬을 통해 월드 스페이스로 변환함 D3DXMATRIXA16 matView; matView = m_pCamera->GetView(); D3DXMATRIXA16 matInverse; // 뷰 행렬의 역행렬 D3DXMatrixInverse(&matInverse,NULL,&matView); // Ray에 뷰 행렬의 역행렬을 곱해서 월드 좌표로 변환한다. D3DXVec3TransformCoord(&m_vOrig,&m_vOrig,&matInverse); D3DXVec3TransformNormal(&m_vDir,&m_vDir,&matInverse); // 정규화 한다. D3DXVec3Normalize(&m_vDir,&m_vDir);

<설명>

1) 윈도우 좌표를 알아낸 후

2) 공식을 통해 3D 좌표로 변경시킨다.

3) m_vOrig 는 카메라의 위치이고, m_vDir은 Ray의 방향이다. 

m_vDir에 3D 벡터 Ray를 설정한다.

4) 카메라 공간 좌표를 월드 공간 좌표로 변경하기 위해 뷰행렬의 역행렬을 곱한다.

여기서 주의해야 할 점은 m_vOrig는 D3DXVec3TransformCoord이고, m_vDir은 D3DXVec3TransformNormal라는 점이다.

왜냐하면 Coord는 위치를 변환하는 것이고, Normal은 벡터를 변환하는 것이다.

5) m_vDir 을 정규화하면 Ray가 완성된다.

이제 폴리곤과 충돌체크를 하는 IntersectTriangle 함수를 알아보겠다.

앞서 말했듯 이 함수는 몇몇 식이 축약됬기 때문에 이해하기가 어렵다.

BOOL IntersectTriangle

(D3DXVECTOR3& v0,D3DXVECTOR3& v1,D3DXVECTOR3& v2, FLOAT* t,FLOAT* u,FLOAT* v);

m_vOrig는 월드 공간 상의 카메라의 원점이고, m_vDir은 Ray의 방향이다.

v0, v1, v2 는 삼각형 정점의 위치이다. 

t는 vOrig에서 v0까지의 거리이다.

u는 v0에서 v1의 비율이고, v는 v0에서 v2의 비율이다

점 p(벡터 p)가 v0,v1,v2내에 있는지 판단하는 방법은 벡터로 한다. 

만약, 삼각형을 △OAB라고 할 때, 벡터 P가 삼각형 내에 있을 조건은

1) u ≥ 0

2) v ≥ 0

3) u + v ≤ 1 

이다. 때문에 u와 v를 구해 점 p가 폴리곤 내에 있는지 판단한다. 

위 그림을 보면

v = ｜Ob｜/｜OB｜ 이다. (왜냐하면, ｜OB｜= ｜Ob｜ * v 니까.)

nA라는 A의 법선벡터를 구한다.

v = ｜Ob｜/｜OB｜

이 식의 분모와 분자에 nAcosΘ 를 곱한다.

v = ｜Ob｜ nAcosΘ /｜OB｜ nAcosΘ 

이것은 내적을 풀어쓴 것으로 

v = Ob · nA / OB · nA 

라고 할 수 있다.

그런데 nA에 투영했을 때, OP와 Ob의 정사영이 같으므로 

v = OP · nA / OB · nA

라고 할 수 있다. 이와 마찬가지로 

u = OP · nB / OA · nB

라고 할 수 있다.

N을  v0와 v2의 평면의 법선벡터라고 하자.

여기서 (vOrig – v0) · N = (P – v0) · N 의 정사영이 같음을 볼 수 있다.

따라서 N = vDir × (v2 – v0) 이다. 

t는 거리라고 했다.

tvec = vOrig – v0

e1 = v1 – v0

e2 = v2 – v0

라고 하자.

u = OP · nB / OA · nB

에서 OP는 거리이므로 tvec으로 고칠 수 있다. 그리고 nB는 위에서 법선벡터 N을 구했으므로 vDir x e2 라고 할 수 있다.

따라서, 

u = tvec · (vDir x e2) / e1 · (vDir x e2) 

v = tvec · (vDir x e1) / e2 · (vDir x e1) 

이렇게 구한 u와 v를 통해 p가 삼각형 내에 있는지 판단하는 것이다.

IntersectTriangle은 이 식을 풀어서 쓴 것이다.

마지막으로 거리 t 를 구하기 위해서 분모를 fDet로 놓는다.

fDet = e1 · (vDir x e2) = vDir · (e1 x e2)

[ fDet 가 0이면, Ray가 같은 평면이고, 0보다 작으면 뒤에서 쏜 Ray, 0보다 크면 앞에서 쏜 Ray이다. ]

[평면의 방정식이 0보다 크면 Ray가 앞에 있는 것이다.]

위의 식에서

｜P - vOrig ｜ = t * ｜vDir ｜

이다. 따라서

t = ｜P - vOrig ｜/ ｜vDir ｜

분모, 분자에 ｜N｜cosΘ 를 곱하면

t = ｜P - vOrig ｜ ｜N｜cosΘ  / ｜vDir ｜ ｜N｜cosΘ 

이고, 이것은 내적을 풀어쓴 것이므로 정리하면

t = (P - vOrig) · N / vDir · N 

이다. 근데 (P - vOrig)과 –tvec의 법선벡터 N에 대한 정사영이 같으므로

t = -tvec · N / vDir · N 

이다.

<코드>

// 정점과 충돌 체크 // vOrig는 카메라 원점, vDir는 Ray 방향 // v0, v1, v2 는 삼각형의 정점 // t 는 vOrig에서 v0 까지의 거리 // u 는 v0에서 v1 이고, v 는 v0에서 v2 이다. BOOL JB_Picking::IntersectTriangle ( D3DXVECTOR3& v0,D3DXVECTOR3& v1,D3DXVECTOR3& v2,FLOAT* t,FLOAT* u,FLOAT* v) { // 변의 길이 계산 D3DXVECTOR3 e1 = v1 - v0; D3DXVECTOR3 e2 = v2 - v0; // u, v를 하기위해 계산을 한다. // 만약 u라면, // vDir과 e2를 외적한 것에 e1을 내적한다. 그 것을 역분하고, 거기에 // vDir과 e2를 외적한 것에 tVec을 내적한 것을 곱한다. D3DXVECTOR3 pVec; // 분모가 같은 놈이기 때문에 이렇게 판단한다. D3DXVec3Cross(&pVec,&m_vDir,&e2); FLOAT fDet = D3DXVec3Dot(&e1,&pVec); // fDet가지고 tVec을 구한다. // tVec은 카메라 원점까지의 거리이다. D3DXVECTOR3 tVec; // 만약 내적 값이 0 보다 크면 앞에서 쏜 Ray이고, 0이면 같은 평면이고, // 0 보다 작으면 뒤에서 쏜 Ray이다. if(fDet > 0) { tVec = m_vOrig - v0; } else if(fDet < 0) { tVec = v0 - m_vOrig; fDet = -fDet; } // 0 으로 나눠주는 일이 없게 하려고 if(fDet < 0.0001f) { return FALSE; } // u 구하기 *u = D3DXVec3Dot(&tVec,&pVec); if(*u < 0.0f || *u > fDet) { return FALSE; } // v 구하기 D3DXVECTOR3 qVec; D3DXVec3Cross(&qVec,&tVec,&e1); *v = D3DXVec3Dot(&m_vDir,&qVec); if(*v < 0.0f || *u + *v > fDet) { return FALSE; } *t = D3DXVec3Dot(&e2,&qVec); FLOAT fInvDet = 1.0f/fDet; *t *= fInvDet; *u *= fInvDet; *v *= fInvDet; return TRUE; }

아래는 픽킹된 폴리곤을 찾아서 다른 색으로 그린 동영상이다.

---

[참고] http://blog.daum.net/gamza-net/8