이제 스크린에서 물체를 선택하는 방식과 회전하는 것에 대해 알아보고자 한다. 스크린을 조작하여 물체를 선택할 때 어떤 물체가 선택되는지, 손가락으로 물체를 슬라이드하면 어떻게 돌아가는지 등에 대한 내용이다.
Object Picking
2차원 스크린의 게임 상에서 마우스 커서로 유닛이나 물체를 클릭할 때, 스크린에서 z값이 가장 작은(카메라와 가장 가까운) 물체를 선택하게 된다. 이는 매우 간단한 작업처럼 보이지만 여기에는 생각보다 고려해야 할 부분이 많다.
가장 가까운 물체를 선택하는 방식은 레이저(Ray)를 쏴서 가장 먼저 맞는 물체를 선택하는 것과 동일하다.
우리가 Screen space의 x,y 좌표(start point)를 클릭한다면 Screen space에서는 (x, y, 0) 에서 (x, y, MAX(z)) 로 향하는 레이저(direction vector)를 쏘게 된다. 하지만 Screen space에는 개별 Object들의 정보나 구분이 없다. 왜냐면 World space를 거쳐서 단일화 되었기 때문이다. 물체에 대한 정보가 없으므로 이 레이저를 Object space까지 이전하여 레이저가 물체에 닿는지 검사해야 한다.
따라서 이 레이저의 Screen space에서 Camera space까지의 변환을 하고, Camera space에서 Object space까지로 거슬러 올라가야 한다. Camera space에서 Clip space까지 그리고 NDC에서 Screen space까지 변형을 다시 살펴보자.
Camera-space Ray
우리는 이 변환 과정의 역변환을 통해 레이저를 Camera space로 보내고자 한다. Screen space에서 (x,y)로 선택된 좌표로부터 출발한 레이저인 (x, y, -n)은 다음과 같은 변형을 거쳐 Camera space에서 정의된다.
View frustum이 projection transform에 의해 2x2x2 의 정육면체로 바뀌고, 그 정육면체가 3차원 Viewport 크기에 맞춰서 Scaling 되었고, 그 위치로 translation 돼서 Screen space로 만들어졌었다.
Camera space의 시작점(xc, yc, -n)에 projection transform을 적용하면 Clip space의 시작점을 알게 된다. w좌표가 1이 아니므로(n이므로) homogeneous coordinates를 Cartesian으로 바꾸기 위해서 n으로 나눈다(Perspective division). 이것이 Clip space의 시작점이다.
여기에 Viewport transform을 적용하면 Screen space의 시작점이 나온다.
Screen space의 방향벡터는 Camera space의 방향벡터를 통해서 알 수 있다. Camera space의 방향벡터는 원점과 시작점을 잇는 것이다. 시작점에서 원점을 빼기만 하면 방향벡터가 나온다.
이렇게 우리는 Camera space의 시작점과 방향벡터를 알게 되었다.
Object-space Ray
이렇게 Camera space에서 정의된 레이저를 이제 World space로, Object space로 이동시켜 물체와의 교차 여부를 판단하고 이때 n값을 이용해 가장 먼저 교차된 물체를 선택할 것이다.
Camera space에서 결정된 Ray를 역으로 World space의 Ray로 변환해야 한다. View trasform의 역변환을 사용하면 된다. World space에서 Camera space로 변환할 때 Translation 후 Rotation을 했으므로 역순으로 하면 된다. 그러면 Camera space에서 정의했던 Ray가 이제는 World space에서 정의가 된다. 이제 Object space의 Ray만 결정하면 된다.
Object space는 개별 Object마다 공간이 있고, 자기 나름의 World transform을 가지고 있었다. 역시나 개별마다 똑같이 역변환 해주면 된다. 그러면 우리는 하나의 World space에서 Ray의 수는 개별 Object의 수만큼 생긴다는 것을 알 수 있다.
Ray Intersection
지금까지 Screen space에서 선택된 (x, y) 좌표로 부터 minz to maxz 로 향하는 레이저를 정의하고, 이를 Camera space까지, 다시 Object space에서 정의하였다. 이제 이 Ray를 이어서 실제 Object space의 Object와 부딪히는지 테스트 해야 한다. 즉, 마우스를 클릭하는 순간마다 Object space Ray를 만들어서 개별 Object와 충돌 여부를 판정해주어야 한다.
하지만 연산이 매우 많아서 조금 정확하지 않더라도 빠른 방법을 생각해 봤을 때, 모든 polygon mesh의 삼각형에 대해서 테스트 하지 말고, polygon mesh를 감싸는 Bounding Volume을 만들어서 이것과 부딪히는지 안 부딪히는 지를 보는 방법을 생각해냈다.
Bounding Volumes
Ray와 polygon mesh의 충돌 테스트를 하기 싫어서, polygon mesh를 감싸는 Bounding volume과 Ray를 충돌 시키는 것이다.
가장 많이 쓰이는 Bounding volume은 박스랑 구이다. 박스는 x, y, z 값의 min max 값만 있으면 되고, 구는 중심점과 반지름만 있으면 된다. (a)에서 구한 점들의 min max 값을 찾아서 (b)에서 중심점을 찾아 박스를 정의해주고 (c) 는 너무 구가 크고 좀더 타이트하게 만들어서 (d) 처럼 Bounding volume을 만들 수 있다.
Ray-BV Intersection
다만 아래 그림처럼 Bounding volume 표면의 점은 polygon mesh의 표면의 점과 다른 부분이 있다. 어느정도 Trade off가 필요하다.
실제 어떻게 충돌하는지 수학적으로 정의해보자.
Ray를 시작점(s)과 방향 벡터(d)를 파라미터 t를 써서 Parametric equation으로 정의할 수 있다. 대입해서 판별식으로 해가 존재하는지 확인하면 된다.
판별식이 0보다 크면 근이 두개이기 때문에 물체를 지나가고, 판별식이 0이면 근이 한개(중근)이기 때문에 겹치는 것이고, 판별식이 0보다 작으면 근이 없기 때문에 지나가지 않는 것이다. 부딪히는 점은 t1과 t2 중 작은 것을 고르면 된다.
누가 먼저 부딪히는 지도 알 수 있다.
이제 충돌 테스트를 해보자.
(a)에서는 Ray와 BV와는 충돌하지만 polygon mesh 와는 충돌하지 않는다. 따라서 또 테스트를 해야한다. 또? 그럼 왜해? 사실 cost 차이가 어마어마 하다.
(b)에서 Ray와 BV와 충돌하지 않는다. 그러면 그 Ray는 절대로 polygon mesh와 충돌할 수 없다. 따라서 BV를 쓰는 것은 전체적으로 따져봤을 때 기대값이 정말 크다고 볼 수 있다. 굉장히 효율적인 알고리즘이다.
Ray-Triangle Intersection
더 정확하게 하고싶다? 그럼 Ray롸 모든 polygon mesh의 충돌 테스트를 해야 한다.
꼭지점을 a, b, c라고 표기하고 Ray와 하나의 삼각형이 이루는 평면이 만나는 점을 p라고 하자. p는 삼각형을 3개의 영역으로 분할을 한다.이때 새로운 면적 index u, v, w 라고 하자. 그리고 p와 a, b, c가 이루는 세개의 면적을 각각 u, v, w라고 하자. 여기서 p가 a에 가까울수록 u값은 더 커진다.
p = ua + vb + wc로 표현되고 (u, v, w)를 barycentric coordinate라고 하고 무게중심 좌표라고도 한다.
당연히 u+v+w = 1 이다. (합이 삼각형의 면적이므로) 우리가 알고 있는 레이저와 삼각형의 vertex 좌표를 이용해 위 u, v, n값을 구할 수 있다. 이때 w 는 1-u-v 이다. 이렇게 구한 u, v, w를 이용해 p점이 삼각형의 내부에 있는지 외부에 있는지 알 수 있게 된다.
삼각형의 외부에서 교차하게 된다면 u, v, w의 값중 하나의 값이 0보다 작은 값을 가지게 될 것이다.
반대로 모든 값이 양수라면 삼각형과 레이저가 교차한 것이다.
이렇게 물체의 모든 삼각형에 대해 검사를 하면 물체가 교차하는지 여부와 해당 교차삼각형을 알 수 있게 된다.
또한 t값을 알게되므로 어떤 물체가, 어떤 삼각형이 가장 먼저 교차하는지 알 수 있게 된다.
Object Rotating
이제 물체의 회전에 대해서 보도록 하자. 스크린을 슬라이드 했을때 물체가 돌아가는 경험을 한 적이 있을것이다.
2차원 좌표의 p1에서 p2까지 우리가 2차원에서 물체를 돌릴 때, 어떤 과정을 거쳐서 물체가 어떻게 회전하는지 보자.
Arcball
회전을 시킬 대상을 공이 하나 감싸고 있다고 하자. 그 다음 스크린에서 우리의 스크린은 그 공을 회전시키는 것이다. 물체와 공은 붙어있기 때문에 공이 돌아가면 같이 따라서 돌 것이다. 우리는 그 공을 Arcball이라고 한다. Arcball이라는 구체를 정의하고 이를 이용해 회전을 하는데, 먼저 스크린의 w x h 크기를 2 x 2의 정사각형으로 normalize 하자. 왜냐면 반지름이 1인 구를 만들기 위해서이다. 이 스크린을 2x2x2 공간으로 확장하고 여기에 가상의 구인 Arcball을 넣자.
p1을 선택하고, 그 점을 (x, y)라고 하자. 이 점을 [0, w] 구간에서 [-1, 1] 구간으로 옮기고 싶다(normalize). 먼저 w로 나누고, 2를 곱하면 구간은 [-1, 1]로 바뀐다. x' = 2x/w - 1
이렇게 정규화된 좌표를 q라고 하자.
q로부터 -z축을 따라서(Archball 표면으로) 쭉 projection 시키고 벡터 v를 정의하자. v의 좌표는 (q의 x좌표, q의 y좌표)가 된다.
v의 z좌표는 sqrt(1-qx^2-qy^2)이므로 v벡터를 구할 수 있다.
이제 두 점을 구했으므로 회전축과 회전 각도를 계산하면 위의 회전을 완벽하게 정의할 수 있다.
회전 축은 vi와 vi+1과 수직일 수밖에 없다. 그러면 회전 축은 vi와 vi+1의 외적으로 구할 수 있다.
회전 각은 p1과 p2의 구 위에서의 점을 v1, v2라고 하면 v1이 v2로 회전하기 위한 각도(회전각)를 계산한다. 회전각은 v1과 v2의 내적을 이용하면 구할 수 있다. 즉, 회전각 theta는 arccos(v1 dot v2)가 된다.
Object-space Rotation Axis
다만 물체의 회전은 Screen space에서 이루어질 수 없다. 이는 Object Picking에서 보았던 이유와 동일하다.
따라서 물체를 Object space로 이동시킨 후 회전을 구현해야 한다.
근데 다른점은 Arcball의 공간은 전혀 알 수가 없다. 그럼 랜더링 파이프라인과 어떻게 역으로 돌아가야 하는지 답이 좀 안나온다. 여기서 트릭을 쓴다. 회전축이 마치 Camera space에서 정의된 것처럼 취하는 것이다.
Ref.
Introduction to Computer Graphics with OpenGL ES (J. Han)
'☘️ Computer Graphics > Fundamental' 카테고리의 다른 글
| CG - Euler Transforms and Quaternion (0) | 2022.07.21 |
|---|---|
| CG - Output Merger (0) | 2022.07.20 |
| CG - Lighting (0) | 2022.07.19 |
| CG - Image Texturing (0) | 2022.07.18 |
| CG - Rasterizer (0) | 2022.07.16 |