[3D Programming with DirectX12] Chapter 17 : Picking
클릭으로 오브젝트를 선택하는 Picking System을 설명합니다.
이번 장에서는 Picking에 대해 알아보자.
유니티 에디터 화면에서 오브젝트를 클릭하면 딱 선택이 된다. 분명 2D 스크린의 좌표를 클릭했을 뿐인데 어떻게 알고 3D 공간안에 오브젝트가 선택이 되는걸까? 우리가 살면서 보통 어떤 것을 가리킬때, 손가락을 이용한다. 그 이유는 방향을 알려주기 위함인데, 컴퓨터에서도 역시 화면안의 한 점에서부터 공간으로 선을 발사하여 닿는 물체를 선택하는 것이다.
Screen to Projection Window Transform
이것이 스크린 좌표를 3D로 옮기는 전체적인 플로우이다. 하나씩 수식을 통해 설명해보겠다.
Screen to NDC
NDC(Normalized Device Coordinate)에서 Screen space 변환 Matrix는 다음과 같다. \(\mathbf{M} = \begin{bmatrix} \dfrac{Width}{2} & 0 & 0 & 0 \\[4pt] 0 & -\dfrac{Height}{2} & 0 & 0 \\[4pt] 0 & 0 & MaxDepth - MinDepth & 0 \\[4pt] TopLeftX + \dfrac{Width}{2} & TopLeftY + \dfrac{Height}{2} & MinDepth & 1 \end{bmatrix}\)
여기서 depth buffer range는 0에서 1이고, TopLeftX = TopLeftY = 0 으로 둘 수 있으므로 식은
\[\mathbf{M} = \begin{bmatrix} \dfrac{w}{2} & 0 & 0 & 0 \\[2pt] 0 & -\dfrac{h}{2} & 0 & 0 \\[2pt] 0 & 0 & 1 & 0 \\[2pt] \dfrac{w}{2} & \dfrac{h}{2} & 0 & 1 \end{bmatrix}\]로 단순화 가능하다. 이제 NDC위의 점 \(\mathbf{p}_{ndc} = (x_{ndc},\ y_{ndc},\ z_{ndc},\ 1)\)를 통해 계산을 하면
\[[x_{ndc},\ y_{ndc},\ z_{ndc},\ 1] \begin{bmatrix} w/2 & 0 & 0 & 0 \\[2pt] 0 & -h/2 & 0 & 0 \\[2pt] 0 & 0 & 1 & 0 \\[2pt] w/2 & h/2 & 0 & 1 \end{bmatrix} = \left[\frac{x_{ndc}w+w}{2},\ \frac{-y_{ndc}h+h}{2},\ z_{ndc},\ 1\right]\] \[\mathbf{x_s} = \frac{\mathbf{x_ndc}w + w}{2}, \mathbf{x_ndc} = \frac{2x_s}{w} - 1\] \[\mathbf{y_s} = \frac{-\mathbf{y_ndc}h + h}{2}, \mathbf{y_ndc} = -\frac{2y_s}{h} + 1\]이렇게 ndc내의 x,y좌표를 구할 수 있다.
NDC to View
이제 NDC위의 점을 Projection Window로 변환할 차례이다. NDC는 Viewport를 길이가 1인 정육면체로 만들어놓은 것이이므로 실제 Viewport의 화면비 \(\mathbf{r}\)을 적용시키면
\[r = \frac{w}{h}\] \[\mathbf{x_v} = r(\frac{\mathbf{x_ndc}w + w}{2})\] \[\mathbf{y_v} = \frac{-\mathbf{y_ndc}h + h}{2}\]
\(\mathbf{x_v , y_v}\)는 Projection Window 위에 있으므로 상황에 따라 다른 distance에 위치하므로 추가 계산을 통해 카메라로부터 z거리가 1인 점으로 변환이 필요하다. y시야각의 1/2인 \(\mathbf{\alpha}\)를 이용하면
\[x'_v = \frac{x_v}{d} = \frac{x_v}{\cot\left(\frac{\alpha}{2}\right)} = x_v \cdot \tan\left(\frac{\alpha}{2}\right) = \left(\frac{2s_x}{w} - 1\right)r\tan\left(\frac{\alpha}{2}\right)\] \[y'_v = \frac{y_v}{d} = \frac{y_v}{\cot\left(\frac{\alpha}{2}\right)} = y_v \cdot \tan\left(\frac{\alpha}{2}\right) = \left(-\frac{2s_y}{h} + 1\right)\tan\left(\frac{\alpha}{2}\right)\]이것이 View위의 z좌표가 1인 점이다.
View to Ray
이제 카메라 위치좌표와 방금 구한 \(\mathbf{x'_v , y'_v}\)를 이용하면
\[\mathbf{r_v(t)} = \mathbf{q + tu}\]를 구할 수 있고, View Matrix 역행렬을 곱하면
\[\mathbf{r_w(t)} = \mathbf{qV^{-1} + tuV^{-1}} = \mathbf{q_w + tu_w}\]최종적으로 World space의 ray 공식을 얻을 수 있다.
Ray/Mesh Intersection
이제 ray와 교차하는 오브젝트를 찾아야 한다. 오브젝트의 모든 폴리곤에 대해서 검사를 진행하는 것은 비효율적이기 때문에 전 장에서 배웠던 Bounding과 교차하는 지 검사하는 것이 더 좋은 방법이다.
Ray/AABB Intersection
box에는 각 x,y,z축에 평행한 6개의 평면이 있고 ray가 해당 평면을 지나는 지점을 찾는다. 그렇게 되면 그림과 같이 각각 \(\mathbf{x_min, x_max, y_min, y_max, z_min, z_max}\)를 구할 수 있고,
\[\mathbf{p_enter = max(x_min , y_min, z_min)}\] \[\mathbf{p_exit = min(x_max , y_max, z_max)}\]로 진입점과 탈출점을 구할 수 있다. 이때
\(\mathbf{ p_exit > p_enter}\) 이면 선이 box를 교차하는 것으로 볼 수 있다.
Ray/Sphere Intersection
구와 선이 닿는지 판정하는 방법은 이미 고등학교에서 배웠던 개념이라 간단한 설명으로 대체하겠다. 선과 구 중심의 거리가 반지름보다 작으면 교차하는 것인데 선과 구 중심의 거리를 미지수로 놓는 이차방정식을 세우면 판별식을 통해 해가 있는지 알 수가 있다.
Ray/Triangle Intersection
삼각형 위의 점은 꼭짓점 $\mathbf{v}_0$을 origin으로, 두 edge를 축으로 하는 skewed coordinate system으로 표현한다.
\[\mathbf{p}(u, v) = \mathbf{v}_0 + u(\mathbf{v}_1 - \mathbf{v}_0) + v(\mathbf{v}_2 - \mathbf{v}_0)\]연립방정식 세우기
교차점에서 $\mathbf{r}(t) = \mathbf{p}(u, v)$ 이므로:
\[\mathbf{q} + t\mathbf{u} = \mathbf{v}_0 + u(\mathbf{v}_1 - \mathbf{v}_0) + v(\mathbf{v}_2 - \mathbf{v}_0)\]표기 편의를 위해 다음과 같이 치환한다.
\[\mathbf{e}_1 = \mathbf{v}_1 - \mathbf{v}_0, \quad \mathbf{e}_2 = \mathbf{v}_2 - \mathbf{v}_0, \quad \mathbf{m} = \mathbf{q} - \mathbf{v}_0\]정리하면
\[-t\mathbf{u} + u\mathbf{e}_1 + v\mathbf{e}_2 = \mathbf{m}\]이걸 행렬 방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 형태로 쓰면:
\[\begin{bmatrix} | & | & | \\ -\mathbf{u} & \mathbf{e}_1 & \mathbf{e}_2 \\ | & | & | \end{bmatrix} \begin{bmatrix} t \\ u \\ v \end{bmatrix} = \begin{bmatrix} | \\ \mathbf{m} \\ | \end{bmatrix}\]$\mathbf{A}$가 invertible하면 Cramer’s Rule에 의해
\[x_i = \frac{\det \mathbf{A}_i}{\det \mathbf{A}}\]여기서 $\mathbf{A}_i$는 $\mathbf{A}$의 $i$번째 열을 $\mathbf{b}$로 교체한 행렬이다.
각 미지수를 풀면
\[t = \frac{\det[\mathbf{m},\ \mathbf{e}_1,\ \mathbf{e}_2]}{\det[-\mathbf{u},\ \mathbf{e}_1,\ \mathbf{e}_2]}\] \[u = \frac{\det[-\mathbf{u},\ \mathbf{m},\ \mathbf{e}_2]}{\det[-\mathbf{u},\ \mathbf{e}_1,\ \mathbf{e}_2]}\] \[v = \frac{\det[-\mathbf{u},\ \mathbf{e}_1,\ \mathbf{m}]}{\det[-\mathbf{u},\ \mathbf{e}_1,\ \mathbf{e}_2]}\]3×3 행렬식은 스칼라 삼중적(scalar triple product) 으로 계산한다.
\[\det[\mathbf{a},\ \mathbf{b},\ \mathbf{c}] = \mathbf{a} \cdot (\mathbf{b} \times \mathbf{c})\]$t$, $u$, $v$를 구한 뒤 아래 조건을 모두 만족해야 Hit이다.
\[t \geq 0\] \[0 \leq u \leq 1\] \[0 \leq v \leq 1\] \[u + v \leq 1\]$t < 0$이면 교차점이 ray 뒤쪽이고, $u$, $v$ 범위를 벗어나면 삼각형 외부다.
Intersection Test의 추가 정보 & Demo
어쨋든 이렇게 Picking을 구현할 수 있다. 다만 한 가지 고려할 점이 있다. GPU는 렌더링 시 각 오브젝트에 World Matrix를 곱해 월드 공간으로 변환하지만, CPU는 그 변환 결과를 직접 알지 못한다. 그렇다면 교차테스트를 CPU에서 하려면 모든 오브젝트를 월드 공간으로 직접 변환해야 할까?
더 나은 방법이 있다. Ray에 World Matrix의 역행렬을 곱하면, Ray가 오브젝트의 로컬 좌표계로 변환된다. 이 상태에서 교차테스트를 수행하면 수학적으로 월드 공간에서 테스트하는 것과 동일한 결과를 얻는다.
오브젝트를 월드 공간으로 옮기는 대신 Ray를 로컬 공간으로 내리는 것이다. 버텍스 수가 많은 메시일수록 이 차이는 커진다.
우클릭으로 폴리곤을 Picking 할 수 있는 모습이다.
연습문제
- 수 천개의 오브젝트가 씬안에 위치한다고 하면 여전히 ray/bounding 테스트를 수 천번 진행해야 한다. Octree라는 방법을 조사해서 어떻게 효율적으로 테스트를 수행하는지 설명하라.
Octree 방법은 3D 공간을 8등분해서 ray가 지나가지 않는 공간은 제외하고 계산하는 방법이다. 만약 A라는 공간을 지나가는데 A안의 오브젝트 개수가 기준보다 많을 시 A를 다시 8개의 공간으로 나눠서 계산한다.
지나지 않는 공간의 오브젝트는 소거하기 때문에 많은 오브젝트가 있을 때 성능을 유지할 수 있다.
이번 장은 수학이 꽤 많아서 좀 힘든 감이 있었다. 그래도 이제 5~6장 밖에 남지 않았다. 1장을 업로드한지 1년이 조금 안된거 같은데 벌써 17장까지 왔다니 참 신기하다 내가 꾸준히 뭔가를 하고 있다니 참… 어쨋든 계속 가보자고~