OpenGL ES를 이용한 3차원 컴퓨터 그래픽스 입문 Chapter 12 스크린 물체 조작

12.1 물체 선택  

마우스를 클릭해 주전자 선택

피킹(picking)

• 터치스크린에서는 물체를 손가락으로 선택, PC 스크린에서는 마우스를 클릭하여 물체를 선택하는 것

스크린에 렌더링된 영상은 픽셀의 2차원 배열이다. 피킹 시에 얻을 수 있는 정보는 스크린 상에서 손가락 또는 마우스로 선택한 점의 2차원 좌표 $\left(x_s, y_s \right)$ 뿐이다. 즉, 물체에 대한 정보는 없다.

 

12.1.1 스크린 공간 광선

3차원 뷰포트는 왼쪽 아래 모퉁이 좌표 (minX, minY), 해상도 w x h, $z$범위 [minZ, maxZ]로 정의된다.

위 사진의 뷰포트는  (minX, minY) = (0, 0), [minZ, maxZ] = [0, 1]

 

마우스 커서의 위치 $\left(x_s, x_y \right)$가 주어졌을 때, 시작점은 $\left( x_s, y_s, 0 \right) $이고 방향 벡터는 $\left(0, 0, 0 \right)$인 스크린 공간 광선(ray)을 정의할 수 있다. 이 광선에 의해 처음 부딪히는 물체가 선택될 것이다.

즉, 광선-물체 교차 검사를 수행해야 한다.

물체에 대한 정보를 스크린 공간에서는 얻을 수 없다.

따라서 광선을 오브젝트 공간까지 변환하여 그 공간에서 광선-물체 교차 검사를 수행해야 한다.

 

12.1.2 카메라 공간 광선

스크린 공간 광선을 오브젝트 공간으로 변환하기 위해서는 우선 카메라 공간으로 변환해야 한다.

카메라 공간 광선도 그 자신의 시작점과 방향 벡터로 정의된다.

위 사진을 보면, 뷰포트의 앞면은 뷰 프러스텀의 전방 평면(near plane)에 해당되므로, 뷰포트 앞면에 놓인 시작점은 카메라 공간의 전방 평면으로 변환된다.

전방 평면의 $z$좌표가 $-n$이므로, 카메라 공간 광선의 시작점은 $\left( x_c, y_c, -n \right)$으로 나타낼 수 있다.

즉 시작점의 $z$좌표는 $-n$으로 고정되므로, $x_c$와 $y_c$만 계산하면 된다.

 

투영 행렬을 $\left) x_c, y_c, -n \right)$에 적용하면 다음과 같다.

참고로 $m_{11} = \frac{\cot{\frac{fovy}{2}}}{aspect} $, $m_{22} = \cot{\frac{fovy}{2}}$이다. $\to$는 원근 나눗셈

위 식의 결과는 아래의 뷰포트 행렬에 의해 스크린 공간으로 변환된다.

위 식의 결과에서 $x$좌표는 $x_s$와 같고, $y$좌표는 $y_s$와 같다는 사실을 이용해 $x_c$와 $y_c$를 계산할 수 있다.

카메라 공간 광선의 시작점은 아래와 같다.

 

뷰 프러스텀은 카메라 공간의 원점으로 수렴하는 투영선들의 집합이다.

따라서 카메라 공간 광선을 뒤로 늘이면 원점에닿게 된다. 원점과 광선의 시작점을 연결한 벡터는 다음과 같다.

벡터는 $x$, $y$, $z$좌표 모두 $n$을 포함하고 있으므로, 모든 좌표를 $n$으로 나눠서 단순화된 벡터를 얻으면, 스크린 공간 광선의 방향 벡터이다.

 

12.1.3 오브젝트 공간 광선

카메라 공간 광선을 월드 공간으로, 그 다음에 오브젝트 공간으로 변환해야 한다.

월드 공간으로의 변환을 위해서는 뷰 변환의 역(inverse)이 필요하다.

뷰 변환 $M_{view}$는 이동($T$)에 이은 회전($R$), 즉 $RT$로 정의된다.

따라서 역변환 $M^{-1}_{view}$은 $T^{-1}R$이 된다. 회전 행렬의 역은 그 전치행렬과 같다.

즉 $R^{-1}$은 $R^T$와 같다.

$T$는 -EYE만큼의 이동을 표현하므로 $T^{-1}$은 EYE만큼의 이동을 표현한다. (Chapter5의 뷰 변환 참고)

따라서 $M^{-1}_{view}$은 아래와 같이 정의된다.

카메라 공간 -> 월드 공간 -> 오브젝트 공간

위 그림에서 구와 주전자는 각자 고유의 오브젝트 공간과 월드 변환을 가지고 있다. (그림을 보면 구는 조금 커졌음)

이러한 월드 변환의 역이 월드 공간 광선에 적용되므로, 오브젝트들은 각기 다른 오브젝트 공간 광선을 가진다.

 

광선을 매개변수 방정식(parametric equation)으로 다음과 같이 표현 가능하다.

 

$p(t) = s +td$

 

$s$는 시작점, $d$는 방향 벡터이고, 매개변수 $t$는 [0, $\infty$] 범위에 있다.

3차원 광선을 매개변수 방정식으로 표현

각가의 오브젝트는 다른 오브젝트 공간을 갖는다. 이 오브젝트 공간에서 $s$의 좌표는 서로 다르다. $d$도 마찬가지다.

 

12.1.4 광선과 바운딩 볼륨 간 교차 검사

폴리곤 메시로 표현된 물체와 광선 간 교차 검사를 수행하기 위해서는 원칙적으로 물체의 모든 삼각형에 대해 광선-삼각형에 대해 광선-삼각형 교차 검사를 실시해야 한다.

광선과 부딪히는 삼각형이 하나 이상 존재할 때, 그 물체는 광선과 교차한다고 판정할 수 있다.

삼각형 마다 이 교차 검사를 수행하는 것은 때로 많은 시간을 필요로 한다.

따라서 부정확하지만 훨씬 빠른 방법인, 각 메시를 완벽히 감싸는 바운딩 볼륨(bounding volume)을 구한 뒤 이를 광선과의 교차 검사에 사용하는 것이다.

(좌) AABB, (우) 바운딩 구

대표적인 바운딩 볼륨 두 가지

• AABB(axis-aligned bounding box)
  • 좌표축과 나란한 직육면체
  • 세 축별 범위 $\left[ x_{min}, x_{max} \right]$, $ \left[ y_{min}, y_{max} \right] $, $\left[ z_{min}, z_{max} \right]$로 정의
• 바운딩 구(bounding sphere)
  
  • 중심 좌표와 반지름 길이로 정의

 

AABB와 바운딩 구 계산법

AABB 계산

1. 초기화를 위해 임의로 한 정점 선택해 이 정점의 $x$좌표를 $x_{min}$과 $x_{max}$에, $y$좌표를 $y_{min}$과 $y_{max}$에 할당한다.
2. 나머지 정점 하나하나 방문하면서, 그 정점의 $x$좌표가 현재 $x_{min}$보다 작으면 $x_{min}$에 할당, $x_{max}$보다 크면 $x_{max}$에 할당한다. $y_{min}$과 $y_{max}$도 이러한 식으로 할당한다.

바운딩 구 계산

• 가장 단순한 방법은 AABB를 이용하는 것
• AABB의 중점을 바운딩 구의 중심으로 취하고, AABB의 대각선 길이의 반을 바운딩 구의 반지름으로 취한다.

종종 필요 이상으로 바운딩 구가 클 수 있으므로 최적화된 바운딩 구를 계산하는 좋은 알고리즘을 이용한다.

 

광선과 바운딩 볼륨 간의 교차

광선과 폴리곤 메시 간 교차 검사는 정확한 결과를 보장하지만, 때로 시간이 많이 소요된다.

광선과 바운딩 볼륨 간 교차 검사는 수행 속도는 빠르지만, 부정확한 결과가 나올 수 있다.

 

3차원 광선을 표현하는 매개변수 방정식의 $x(t)$, $y(t)$, $z(t)$를 중심이 $\left( C_x, C_y, C_z \right)$이고, 반지름이 $r$인 바운딩 구를 정의하는 함수의 $x$, $y$, $z$에 대입하면 2차 방정식을 얻을 수 있다.

또, 근의 공식을 이용해 매개변수 $t$를 얻을 수 있다. 이 $t$가 광선과 바운딩 구 간 교차점에서의 매개변수가 된다. 

 

판별식 $b^2 - 4ac$가 양수라면 서로 다른 두 실근을 얻게 된다. 두 실근을 $t_1$과 $t_2$라 하자.

이 두 실근을 매개변수 3차원 광선을 표현하는 매개변수 방정식에 대입하면 교차점의 3차원 좌표를 얻을 수 있다.

판별식이 0이면 중근을 갖는데, 광선이 바운딩 구와 접한다는 뜻이다.

판별식이 음수라면 실근을 갖지 않고, 광선은 바운딩 구와 교차하지 않는다는 것이다.

 

오브젝트 공간에서의 광선-물체 교차 검사

위 사진에서 두 개의 바운딩 볼륨이 따로 처리되는데, 광선은 두 바운딩 볼륨과 모두 부딪힌다.(참고로 구의 경우, 월드 변환의 역을 취하니 크기가 작아졌다. 따라서 오브젝트 광선도 작아지게 된다.)

주전자의 바운딩 볼륨과 부딪히는 점에서의 매개변수 $t_a$가 구의 바운딩 볼륨과 교차하는 점에서의 매개변수 $t_b$보다 작다. 따라서 주전자가 광선과 처음으로 교차하는 물체로 선택된다.

 

광선과 바운딩 볼륨 간 교차 검사는 종종 부정확한 결과를 산출한다.

위 사진의 (a)를 보면, 광선이 바운딩 구와 교차하더라도 실제 폴리곤 메시와는 교차하지 않을 숫 있다.

따라서 정확한 계산이 필요할 때는 반드시 폴리곤 메시의 모든 삼각형과 광선 간 교차 검사를 수행해야 한다.

이렇게 광선-삼각형 교차 검사를 하더라도 전처리 단계에서는 광선과 바운딩 볼륨 간 교차 검사를 수행한다.

그 이유는 (b)를 보면, 광선과 바운딩 볼륨이 교차하지 않는다면 폴리곤 메시는 광선과 교차하지 않는다고  보장할 수 있기 때문이다. 바운딩 볼륨을 이용한 간단한 검사를 통해, 광선-삼각형 교차 검사를 여러 번 수행하는 헛수고를 피할 수 있다.

반면, (c)를 보면, 광선이 폴리곤 메시와 교차한다면 광선은 이 메시의 바운딩 볼륨과도 반드시 교차하므로, 필요한 광선-삼각형 교차 검사를 놓치게 되는 경우는 없다.

 

12.1.5 광선과 삼각형 간 교차 검사

정확한 광선-물체 교체 검사를 위해서는 그 물체의 폴리곤 메시의 모든 삼각형과 광선 간 교차 검사를 수행해야 한다.

광선과 삼각형 $<a,b,c>$는 $p$점에서 교차하는데, 이 삼각형은 $p$에 의해 세 개의 작은 삼각형 $<p,a,b>, <p,b,c>,<p,c,a>$로 나눠진다고 볼 수 있다.

삼각형 $<p,b,c>$, $<p,c,a>$, $<p,a,b>$ 각각이 원래의 삼각형 $<a,b,c>$에서 차지하는 면적의 비중을  $u$, $v$, $w$라 하자. 그러면 $p$는 세 정점의 가중치 합으로 정의될 수 있다.

---

참고

삼가형 면적 비율 계산

3차원 삼각형 $<v_0, v_1, v_2>$에서 $v_i$의 좌표를 $\left( x_i, y_i, z_i \right)$라 하면, 각 정점을 $xy$, $yz$, $zx$ 평면 중 하나에 투영할 수 있다.

투영된 삼각형의 면적이 0이 아니라는 조건만 만족하는 평면을 고르면 된다.

예를 들어, $xy$평면이 선택되었으면 투영 후 $v_i$의 좌표는 $\left( x_i, y_i \right)$가 되고, 투영된 삼각형의 면적은 다음과 같이 계산된다.

---

$\left( u, v, w \right)$를 삼각형 $<a,b,c>$에 대한 $p$의 무게중심 좌표(barycentric coordinates)라고 부른다.

한편, $u$, $v$, $w$는 모두 [0, 1] 범위에 있으며 $u+v+w=1$이 된다. 따라서 $w$는 $1-u-v$로 대체될 수 있다.

 

광선은 매개변수 방정식 $s+td$로 표현되는데, 광선과 삼각형 $<a,b,c>$ 간 교차점 계산은 다음과 같은 방정식을 푸는 것이다.

 

여기서 $c-a$, $c-b$, $c-s$를 각각 $A$, $B$, $C$로 표기하면 다음과 같이 쓸 수 있다.

$d$, $A$, $B$, $S$ 모두 3차원 좌표이므로 다음과 같은 선형 시스템으로 정리된다.

이를 크레이머 법칙(Cramer's rule)로 풀 수 있다. 크라메르 법칙 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

이렇게 얻은 $u$와 $v$를 $p$의 식에 대입하면 교차점을 얻을 수 있다.

하지만, 이는 삼각형이 광선과 교차하는 점이 아니라, '삼각형이 놓인 무한한 넓이의 평면'이 광선과 교차하는 점이다.

따라서, 교차점이 삼각형 안에 놓인다는 보장은 없다. 일부 교차점은 삼각형 밖에 놓일 수 있다.

교차점이 삼각형 안에 있으려면, $u \geq 0, v\geq 0, w \geq 0$ 조건을 만족해야 한다.

한편, $w=1-u-v$이므로 마지막 조건 $w \geq 0$는 $u + v \leq 1 $로 대체된다.

 

폴리곤 메시의 모든 삼각형에 대해 광선-삼각형 교차 검사를 수행했을 때, 광선과 부딪히는 삼각형이 여러 개 발견될 수 있다. 가장 작은 양수 $t$를 가지는 교차점을 선택한다.

 

12.2 물체 회전

손가락 끝의 궤적을 추적해서 얻은 터치스크린 위의 2차원 점들을 $\left\{p_1,p_2,\cdots,p_n\right\}$이라고 하자.

위 사진에서의 손가락 움직임을 이웃한 두 점 $p_i$와 $p_{i+1}$으로 표현할 수 있다.

물체 회전을 효율적으로 구현하기 위해서, 해상도 $w \times h$의 터치스크린을 2 x 2 크기의 정사각형으로 변환한다.

이 변환을 $p_i$와 $p_{i+1}$에 적용해 $q_i$와 $q_{i+1}$을 얻는다.

 

터치스크린 위의 점 $p$와 정사각형 스크린 위의 점 $q$의 좌표를 각각 $\left(x, y\right)$와 $\left( x', y' \right)$로 표기하자.

터치스크린의 원점은 왼쪽 아래 귀퉁이에 있고, 정사각형 스크린의 원점은 중앙에 있으므로 $\left(x, y \right)$와 $\left( x', y' \right)$의 관계는 다음과 같다.

여기서 $x$는 [0, w], $y$는 [0, h], $x'$와 $y'$는 [-1, 1] 범위에 있다.

 

아크볼(arcball)

• 정사각형 스크린 뒤에 놓인 가상의 구
• 2 x 2 x 2 크기의 정육면체 안에 놓여 있고, 중심 좌표는 (0, 0, 0), 반지름 1
• 스크린 위에서 움직이는 손가락이 아크볼을 정육면체 안에서 돌려서 오브젝트를 회전시킴

 

정사각형 스크린의 $q$를 $-z$축을 따라 아크볼 표면에 투영하고, 좌표계 원점과 이 투영점을 이은 벡터를 $v$라 하자.

$q$와 $v$의 $xy$ 좌표는 같다. 즉, $v_x = q_x$, $v_y = q_y$이다.

한편, 아크볼 반지름은 1이고 $v$는 단위 벡터이므로, $v_z = \sqrt{1-v_{x}^2-v_{y}^2}$이 된다.

 

$v$의 좌표를 계산할 수 없는 경우가 존재한다. 즉 $q_{x}^2 + q_{y}^2$이 1보다 크다면, $q$는 아크볼 표면으로 투영되지 않는다. 이 경우, $q$를 먼저 3차원 좌표계의 $xy$평면으로 1차 투영한다. 이 투영점의 좌표는 $\left( q_x, q_y, 0 \right)$이다.

위 그림은 $xy$평면에서의 아크볼 단면과 투영점을 보여준다. 이 투영점을 정규화 하면, 즉 $\left( q_{x}^2, q_{y}^2, 0 \right)$을 자기 자신의 길이 $\sqrt{q_{x}^2 + q_{y}^2}$으로 나눈다. 이는 $\left( q_x, q_y, 0 \right)$을 아크볼 표면으로 2차 투영하는 결과다. 원점과 이 2차원 투영점을 이은 벡터를 $v$로 취한다.

결론적으로, $q_i$와 $q_{i+1}$으로부터 각각 $v_i$와 $v_{i+1}$을 계산할 수 있다. 

처음에 하려던 회전은 $v_i$를 $v_{i+1}$로 옮기는 것이 되었다.

이러한 회전은 $v_i$와 $v_{i+1}$ 에 모두 수직인 회전축 그리고 $v_i$와 $v_{i+1}$ 사이의 회전각 $\theta$에 의해 정의된다.

회전축은 $v_i$와 $v_{i+1}$의 벡터곱과 같다. $v_i$와 $v_{i+1}$은 단위 벡터이므로 $v_i\cdot v_{i+1} = \left\| v_i \right\| \left\| v_{i+1} \right\| \cos\theta = \cos\theta$이다.

따라서, $\theta = \arccos{\left(v_i \cdot v_{i+1}\right)}$가 된다.

 

이러한 회전축과 회전각을 이용한 회전된 물체는 GPU 파이프라인을 통해 즉각 스크린에 렌더링되어야 한다.

따라서, 실제 회전은 GPU 파이프라인의 첫 연산인 월드 변환보다 앞서 적용되어야 한다.

즉, 물체를 회전시킨 후 월드 변환, 뷰 변환 등을 거쳐 최종 스크린에 출력해야 한다.

따라서, 앞서 구한 회전축은 오브젝트 공간으로 변환되어야 한다. (회전각 $\theta$는 스칼라이므로 그대로 사용)

 

아크볼 공간은 GPU 파이프라인에 존재하는 것이 아니라, 임시로 만든 것이다. 따라서 이를 벗어나야 한다.

아크볼 공간의 회전축을 카메라 공간을 그대로 옮기면 된다.

'벡터'로서의 회전축은 카메라 공간에 놓인 주전자의 중심에 꽂혀 있는 것으로 간주할 수 있다.

카메라 공간의 벡터가 주어지면, 오브젝트 공간으로 변환할 수 있다.

 

현재 월드 변환 행렬을 $M$이라고 하자. 터치 스크린에서 손가락이 $p_1$에서 $p_2$로 이동하면, 회전축과 회전각이 계산되고, 위 사진과 같은 변환 과정을 거친다.

이 과정의 마지막 단계인 월드 공간에서 오브젝트 공간으로의 변환은 $M^{-1}$에 의해 이뤄진다.

오브젝트 공간으로 변환된 회전축을 이용해 계산한 회전 행렬을 $R_1$이라고 하자.

그러면 $MR_1$이 정점 쉐이더에게 새로운 월드 변환 행렬로 주어지고, $p_1$에서 $p_2$로 이동한 손가락에 의해 회전된 물체가 GPU 파이프라인을 거쳐 렌더링된다.

$MR_1$을 $M'$으로 약칭하자. 그 다음 $p_2$에서 $p_3$으로 이동하면, 위 사진의 마지막 단계에서 회전축은 $\left(M' \right)^{-1}$에 의해 월드 공간에서 오브젝트 공간으로 변환된다.

오브젝트 공간으로 변환된 회전축을 이용해 계산한 회전 행령르 $R_2$라고 하자.

그러면 $M'R_2$가 정점 쉐이더에게 새로운 월드 변환 행렬로 주어진다. 

이처럼 모든 손가락 움직임에 대해 이와 같은 연산이 반복된다.

 

 

출처
[OpenGL ES를 이용한 3차원 컴퓨터 그래픽스 입문]을 보고 공부하고 정리한 내용