## Basic Pathfinding

경로 찾기 알고리즘을 평가하는 요소는 다음과 같습니다.

- 해가 존재하는 문제에 대해 해를 구할 수 있는가? (Complete)
- 최적해를 보장할 수 있는가? (Optimal)
- 시간, 공간 복잡도가 복잡한가? (Time, Space)

여러 알고리즘을 알아보며 평가해봅시다.

### Greedy

당장의 이득이 큰 선택을 이어가는 방식입니다.
예로 들어 현재 위치에서 목적지 까지의 거리가 최소화되는 방향으로 이동하는 방식이 그리디 정책입니다.

하지만, 최적해를 보장하지 못한다는 문제가 있습니다.

### BFS

그리디 방식보다는 Graph를 탐색하는 기법을 활용하는 것이 최적해를 찾을 수 있습니다.
그 중 Breadth First Search 방식은 최적해를 보장할 수 있습니다.

하지만, BFS는 모든 경로를 기록해야 하기 때문에 공간 복잡도가 높으며 시간 복잡도 또한 높게 측정됩니다.

<tip>
 **vs. DFS**
 Depth First Search 방식은 일반적으로 BFS보다 시간, 공간 복잡도 측면에서 효율적입니다.
 하지만, 이 역시 Greedy만큼 심각하지는 않지만, 역시 최적해를 보장할 수 없습니다.
 또한, graph에 cycle이 존재하는 경우에는 해를 구하지 못하는 경우도 생깁니다.

 | Algorithm | Complete | Optimal | Time | Space |
 |---|---|---|---|---|
 | BFS | Y | Y | $O(min(N, B^L))$ | $O(min(N,B^L))$ |
 | DFS | Y | N | $O(B^{L_{MAX}})$ | $O(L_{MAX})$ |
</tip>

<tip>
 **vs. Greedy**
 그리디와 BFS는 사실 비슷합니다.
 ![231211-215115](/posts/final_03/231211-215115.png)
</tip>

### A*

위에서 BFS와 Greedy 방식이 비슷하다 했었는데, 다른 부분은 priority queue를 사용하는 것이 차이입니다.

그렇다면, BFS에서 먼저 pop되는 노드의 기준은 무엇일까요?
처음부터 현재까지의 탐색 거리 중 가장 짧은 거리를 **g**라고 했을 때, g가 가장 작은 노드가 선택되게 됩니다.

Greedy에서 먼저 pop되는 노드의 기준은 무엇일까요?
현재 지점부터 목표 거리까지 거리가 최소가 될 거 같은 휴리스틱한 거리를 **h**라고 했을 때, h가 가장 작은 노드가 선택되게 됩니다.

A*는 BFS와 Greedy의 장점만을 모은 알고리즘으로, **f = g + h** 라 했을 때, f가 가장 작은 노드를 선택하여 경로를 탐색합니다.
즉, 빠르게 탐색하면서도 최적해를 보장할 수 있게 됩니다.
하지만, 메모리를 너무 많이 사용한다는 단점도 있습니다.

의사 코드는 아래와 같습니다.

```java:A*
INIT priority-queue Q
INSERT start node N to Q
while (Q is not empty) {
 REMOVE best N from Q that has lowest f(N)
 if (N is goal) break
 for (next node N' in Succ(N)) {
 if (N' is visited first ||
 previously expanded with f(N') > f(N) ||
 currently in Q with f(N') > f(N)
 ) {
 INSERT N' into Q or UPDATE N' within Q
 }
 } 
}
```

즉, 특이하게도 A* 목표 노드를 발견해도 종료하지 않습니다.
Goal state가 priority-queue에서 pop되었을 때만 종료하게 됩니다.

---

## Modified Pathfinding

지금까지는 정적인 장애물만 피해갔지만, 이런 경우에는 어떡해야 할까요?

- 동적인 장애물이 있을 경우
- 이동 경로를 부드럽게 움직이게 하고 싶을 경우

![231211-221920](/posts/final_03/231211-221920.png)

이동 경로를 부드럽게 하고싶은 경우에는 선형 보간을 사용하는 방식으로 해결할 수 있습니다.

동적인 장애물이 있는 경우에는 장애물이 움직인다고 A* 알고리즘을 다시 돌리는 행위는 너무 비효율적입니다.
따라서 A*에 약간의 Greedy 함이 추가되면 좋을 거 같습니다... 만, 어떻게 해야할까요?

### Inadmissible

A*가 최적해를 구할 수 있는 조건은 휴리스탁한 길이 h가 실제 길이보다 같거나 짧아야한다는 admissible이 지켜졌기 때문입니다.
그렇다면 h가 inadmissible 하다면?

기존 휴리스틱 h에 $\alpha$를 곱하여 inadmissible 하게 만들어봅시다.

$$
h'(n) = \alpha \cdot h(n)
$$

휴리스틱한 거리가 실제 거리보다 길어질만큼 $\alpha$를 곱하여 inadmissible하게 만들었습니다.
하지만, 효율성을 챙길 수 있습니다.
왜냐하면, f가 동일하다고 했을 때, $\alpha$를 곱한다면 f'의 값은 원래의 h가 작았던 경로가 더 작게 나올 것입니다.

즉, $\alpha$값을 높임으로서 효율적인 탐색을 지향하지만, 그리디의 특성을 일부 챙길 수 있게 되었습니다.
(물론 이 과정에서 최적해는 구하지 못할 수 있습니다)

### Hierarchical Planning

처음부터 전체적으로 세부적인 경로를 구하는 것이 아닌, 초기에는 듬성듬성한 탐색 경로를 설정하고, 나중에 세부적인 탐색 경로를 2차적으로 설정하는 방법입니다.

![231211-221544](/posts/final_03/231211-221544.png)

위에 소개된 두 방법은 일반적으로 비용이 저렴하며, 실제 필요한 영역만 탐색하기 때문에 효율적이고, 동적인 환경에 더 적응성이 강하다는 장점이 있습니다.
하지만, 최적해를 보장하지 못한다는 단점이 있습니다.

### Dynamic Planning

전체 경로를 planning 하는 것이 아니라, 일부 경로만 planning하고, planning 한 경로의 끝에 다다를 때 쯤, 다음 경로를 planning 하는 방식입니다.

동적인 환경에 대한 적응성이 더욱 뛰어납니다.
하지만, 극단적인 경우에 한 스탭만 planning 하는 경우에는 그리디 방식과 동일해집니다.

---

## Reactive Planning

위에서 언급한 Dynamic Planning의 극단적인 경우입니다.
즉, 최적성을 보장하지는 않지만, 빠르고, 자연스러운 움직임을 추구해야 하는 경우 사용하는 알고리즘 입니다.

### Potential Field Planning

잠재적인 힘의 공간을 이용한 planning 방식입니다.
경로 탐색 공간을 두 가지 힘에 의해 좌우되는 공간으로 변형해봅시다.

F는 장애물에서 멀어지려는 힘을 가하는 공간이고, G는 목표지점으로 향하는 힘을 가하는 공간이라고 가정해봅시다.
이 떄, F+G인 공간에서 물리 시뮬레이션을 한다면?
매 순간마다 위치와 속도를 얻을 수 있고, 그 방향으로 움직인다면 자연스러운 선택을 유도할 수 있습니다.

![231211-222259](/posts/final_03/231211-222259.png)

하지만 문제가 많습니다.

- 파라미터가 너무 많음
 힘, 가파르기, 속도, 질량 등 물리 시뮬레이션을 위한 파라미터가 너무 많이 필요합니다.

- 목표의 충돌

 ![231211-222520](/posts/final_03/231211-222520.png)

 장애물을 피하려는 목표와 부드럽게 움직이려는 목표의 충돌로 부자연스러운 움직임을 보일 수 있습니다.

- 국소 최적해

 ![231211-222543](/posts/final_03/231211-222543.png)

 목적지로 이동하지 못하고 갇힐 수도 있습니다.

### Flocking Models

경로를 파악해야 하는 객체, 즉 이동하는 객체가 집단일 경우에는 어떨까요?
집단 내부에서 규칙을 정해서 따르도록 하는 힘의 함수를 만드는 것이 도움이 됩니다.

![231211-222714](/posts/final_03/231211-222714.png)

- Separation
 일종의 personal space 개념으로 남들과 약간의 거리를 두고 싶은 정도의 힘 입니다.
- Alignment
 남들과 같은 방향으로 같이 가려는 힘 입니다.
- Cohesion
 집단에 속하려고 서로 응집하려는 힘 입니다.
- Avoidance
 장애물을 회피하려는 방향으로 가려는 힘 입니다.

이런 4가지 힘의 행동 규칙에 가중치를 부여하여 집단의 이동을 결정하면 간단한 규칙들의 합으로 군중의 복잡한 움직임을 모방할 수 있습니다.
가중치를 부여하는 방식에 따라 우선순위가 낮은 규칙은 적용되지 않을 수도 있고, 모든 규칙이 고루 영향을 미치도록 할 수도 있습니다.

정리하자면, 복잡한 군중 행동을 단순하게 표현할 수 있고, 여러 행동양식을 만들어 낼 수 있다는 장점이 있지만,
가중치 조절이 쉽지 않으며, 앞서 봤던 Potential Field의 영향도 받을 수 있다는 단점이 있습니다.

게임에서의 AI, 그 중 pathfinding 방식에 대해 알아봅니다.

## Kinematics

관절(Joints)와 뼈대(Links)의 트리구조의 계층적 모델로 표현 가능하며, 힘에 대한건 고려하지 않고, 관절의 각도만 고려하게 됩니다.

연산 순서에 따라 Forward, Inverse Kinematics로 구분되는데, 어떤식으로 다른지 알아봅시다.

- Forward

 ![231211-180201](/posts/final_02/231211-180201.gif)

 local coordinate 관점

- Inverse

 ![231211-180202](/posts/final_02/231211-180202.gif)

 global coordinate 관점

사실상 동일합니다.

3차원의 경우 회전은 각 축을 중심으로 하는 3개의 회전으로 분리(Eular angles)하여 계산합니다.

![231211-180643](/posts/final_02/231211-180643.png)

각 관절과 뼈대는 트리구조로 표현된다고 했었는데, 각 관절의 회전과 뼈대의 길이를 DFS 방식으로 탐색하며 계산한다면 원하는 부분의 움직임을 계산할 수 있습니다.

---

## Rotation

![231211-180857](/posts/final_02/231211-180857.png)

지금까지 3차원에서의 회전은 Eular angles를 연산하여 계산했었습니다.
하지만, 이 방식에는 치명적인 단점이 존재합니다.

- 연산 순서에 따라 결과가 달라진다.
- Gimbal lock 현상이 발생한다.

<tip>
 `Gimbal lock`
 
 가장 안쪽에 있는 축(Gimbal)과 가장 밖에있는 축이 평행하게 되어버리면 회전의 자유도의 손실이 발생하는 현상.
 [예시 영상](https://youtu.be/zc8b2Jo7mno?si=c-oq07BEsga7V98i&t=58)
</tip>

따라서 이를 해결할 두 가지 3차원 회전방법을 알아보겠습니다.

### Quaternion

4개의 파라미터로 4차원 공간의 구의 좌표(4원수)를 사용합니다.

$$
q = (w, x, y, z) \\
{}\\
w^2 + x^2 + y^2 + z^2 = 1
$$

쿼터니언은 복소수의 확장판으로 엄밀한 정의는 다음과 같습니다.

$$
w + ix + jy + kz = (w,x,y,z) = (w,v) \\
{}\\
i^2 = j^2 = k^2 = ijk = -1
$$

![231211-183507](/posts/final_02/231211-183507.png)

즉, 교환법칙이 성립되지 않으며, 허수부의 연산을 표로 그려보면 다음과 같습니다.

| x | 1 | i | j | k |
|---|---|---|---|---|
| **1** | 1 | i | j | k |
| **i** | i | -1 | k | -j |
| **j** | j | -k | -1 | i |
| **k** | k | j | -i | -1 |

이제 쿼터니언의 여러 연산을 알아봅시다.

- Add, Sub
 ![231211-184240](/posts/final_02/231211-184240.png)

- Mul
 ![231211-184321](/posts/final_02/231211-184321.png)

- Conjugate (켤레 복소수)
 ![231211-184501](/posts/final_02/231211-184501.png)

- Norm (크기)
 ![231211-184516](/posts/final_02/231211-184516.png)

- Mul Identity (곱셈 항등원)
 ![231211-184538](/posts/final_02/231211-184538.png)

- Mul Inverse (곱셈 항등원의 역)
 ![231211-184559](/posts/final_02/231211-184559.png)

근데 쿼터니언이 왜 회전과 관련이 있는걸까요?
다음을 보며 이해해봅시다.

![231211-185645](/posts/final_02/231211-185645.png)

오일러 공식에 의한 회전은 가장 아름다운 수식으로 알려진 만큼 유명해서 익숙할 겁니다.

![231211-185900](/posts/final_02/231211-185900.png)

실제로 전에 다뤄본대로 변환 행렬의 원소가 실수부와 허수부의 변환된 좌표로 나오게 됩니다.

![231211-190100](/posts/final_02/231211-190100.png)

위 개념을 확장하면 쿼터니언을 사용하면 3차원의 회전을 다룰 수 있다는 사실을 알 수 있습니다.

![231211-190242](/posts/final_02/231211-190242.png)

즉, 회전하고자 하는 좌표를 순허수 쿼터니언으로 변환하고,
특정 축(**유닛 벡터**)을 기준으로 회전각을 곱해주면 회전된 좌표가 순허수 쿼터니언의 형태로 나오게 됩니다.

### Rotation Matrix

9개의 파라미터로 3차원 회전을 달성하는 3by3 행렬입니다.

$$
R = \begin{bmatrix}
u_1 & v_1 & w_1 \\
u_2 & v_2 & w_2 \\
u_3 & v_3 & w_3 \\
\end{bmatrix} = \begin{bmatrix}
u & v & w \\
\end{bmatrix}
$$

여기서 u, v, w는 단위벡터이고, det(R) = 1 인 회전 행렬입니다.

파라미터가 9개나 되는데 굳이 rotation matrix를 사용하는 이유는 무엇일까요?
쿼터니언은 부호가 반대가 되는 경우가 있기 때문입니다.

$$
R_q(p) = R_{-q}(p)
$$

즉, 하나의 회전을 2개의 방법으로 표현할 수 있기 때문입니다.
반면에 rotation matrix는 하나의 회전이 유니크한 matrix 하나로 정의되기에 사용합니다.

물론, 쿼터니언-회전행렬간 변환 연산도 있습니다.

---

## Splines

애니메이션의 움직임을 부드럽게 하려면 어떻게 해야할까요?
수학적인 함수를 사용해서 시간 분할(간격)에 관계없이 애니메이션(위치)를 얻거나, 아주 잘게 쪼갠 미리 계산된 값(위치)를 사용하는 방법이 있을 것입니다.

다항식으로 이루어진 curve를 polynomial curve 라고 하는데 단순히 다항식을 사용하면 문제가 있습니다.
특정 점(위치)를 지나는 다항식을 계산하기가 어렵고, 차수가 높아질수록 불가능에 가까워집니다.

따라서 다음과 같은 방식을 사용해볼 수 있겠습니다.

### Lagrange Polynomial

라그랑주 다항식은 아래와 같이 생겼습니다.

$$
x(t) = L_0(t)x_0 + L_1(t)x_1 + ... + L_n(t)x_n \\
{}\\
L_k(t_i) = \left\{\begin{matrix}
1 \; if \; k=i \\
0 \; if \; k \neq i
\end{matrix}\right.
$$

![231211-201931](/posts/final_02/231211-201931.png)

즉, $x(t_0) = x_0$, $x(t_1) = x_1$ 과 같이 값이 나오기 때문에 원하는 함수 모양을 잡기 쉽습니다.
그러나, 차수가 높아질수록 L이 출렁이는, 일명 Oscillation 현상이 발생하기 때문에 keyframe particle motion에 적용하기에는 부적절합니다.

### Spline Interpolation

그렇다면 아래와 같이 해결해볼 수 있을 거 같습니다.

![231211-202159](/posts/final_02/231211-202159.png)

여기서 3차를 사용하는 이유는 2차는 평면상의 곡선만 표현할 수 있기에 공간의 움직임을 표현하기에는 부적절하고, 4차는 Oscillation 현상이 발생하기 때문에 부적절하기 때문입니다.
하지만 이 역시 문제가 있습니다.

우선 연걸지점이 미분 불가능할 수 있기에 움직임이 부자연스러울 수 있습니다.
또한, 일반적인 다항함수의 기저($t^3$ ~ $t^0$)로는 직관적으로 다항식이 어떤 모양인지 알 수 없습니다.

### Bezier Curve

우선 기저만 봤을 때 함수의 모양을 직관적으로 확인할 수 있도록 Bernstein 기저 함수를 사용할 수 있겠습니다.

$$
B_i^n = (_nC_i)(1-t)^{n-i}t^i
$$

Bernstein 기저 함수의 특징은 아래와 같습니다.

![231211-203158](/posts/final_02/231211-203158.png)

이 기저를 이용한 3차 다항식은 아래와 같습니다.

$$
p(t) = B_0^3(t)b_0 + B_1^3(t)b_1 + B_2^3(t)b_2 + B_3^3(t)b_3 \\
{}\\
= (1-t)^3b_0 + 3t(1-t)^2b_1 + 3t^2(1-t)b_2 + t^3b_3
$$

여기서 b의 값을 알면 함수의 모양을 예측할 수 있는데, 함수 p가 Bezier curve 입니다.

![231211-203320](/posts/final_02/231211-203320.png)

이 때의 $b_i$를 control point라고 부릅니다.

베지어 곡선의 특징은 다음과 같습니다.

- **End point interpolation**

 항상 $p(0) = b_0$, $p(1) = b_3$ 입니다.
 즉, 시점과 종점을 바로 알 수 있습니다.

- **Convex hull**

 항상 control points가 만드는 가장 작은 다각형(볼록한 모양) 내부에 베지어 곡선이 위치합니다.

 ![231211-203617](/posts/final_02/231211-203617.png)

 이 특성은 곡선이 교차되는 지점을 구할 때, 계산 범위를 한정지어 효과적으로 계산할 수 있도록 도와줍니다.

- **Affine inveriance**

 동일한 control points는 반드시 1개의 베지어 곡선만 생성합니다.
 즉, control points를 transform 하는 경우에는 동일한 transform이 베지어 곡선에 적용되는 효과를 갖습니다.

- **Tangent vectors**

 시점, 종점의 탄젠트 벡터는 각 시/종점과 인접한 control point의 차이의 3배로 표현됩니다.

 ![231211-203942](/posts/final_02/231211-203942.png)

 여기서 Spline Interpolation의 또 다른 문제였던 연결지점이 부자연스러울 경우를 예방할 수 있겠죠?

 ![231211-204538](/posts/final_02/231211-204538.png)

 끝 점의 탄젠트 벡터의 방향을 일치하도록 설정하면 됩니다.
 다르게 표현하면, 각 곡선 조각의 끝에 탄젠트 벡터가 있다면, 이를 이용해서 조각에 해당하는 베지어 커브를 그릴 수 있습니다.

- **Subdivision**

 베지어 곡선위의 임의의 점으로 곡선을 분할하면 분할된 곡선 역시 베지어 곡선이 됩니다.

- **De Casteljau's algorithm**

 시점 $t_k=u$ 일 때의 위치는 u:1-u로 내분하는 방식으로 구할 수 있습니다.

 ![231211-204228](/posts/final_02/231211-204228.png)

애니메이션이 처리되는 과정을 알아봅니다.

Animation

![231210-002735](/posts/final_01/231210-002735.png)

랜더링은 3D 세상의 정보를 2D의 영상으로 변환하는 과정을 의미합니다.
그 변환 과정을 세밀하게 알아봅시다.

## Geometry processing

공간상의 좌표를 모니터의 좌표로 변환하기 위해서 좌표를 변환하는 과정이 필요한데, 그 순서와 변환법을 알아보겠습니다.

### Viewing-transform

![231209-233923](/posts/final_01/231209-233923.png)

공간상의 좌표를 View plane 상에서 바라보는 곳의 좌표로 우선 변환합니다.

![231209-234611](/posts/final_01/231209-234611.png)

여기서 P는 카메라의 위치, N은 바라본 위치상의 평면(View plane)의 normal vector 입니다.
이 때, 사각 뿔 도형의 $P_{ref}$ 지점을 바라본다고 한다면, 법선 벡터 N은 $P_0 - P_{ref}$로 구할 수 있습니다.

여기서 View plane의 법선 벡터를 구했다고 View plane을 확정할 수는 없습니다.
왜냐하면 N을 축으로 회전이 가능하기 때문이죠.
따라서 View-up vector V를 정의합니다.

![231209-234059](/posts/final_01/231209-234059.png)

위에서 N, V를 구했다면, view space의 세 축을 정의할 수 있습니다.

$$
n = \frac{N}{||N||} \\
{}\\
u = \frac{V \times n}{||V||} \\
{}\\
v = n \times u
$$

이제 view space의 축의 벡터를 구했으니, world space의 물체를 view space로 좌표 변환이 가능합니다.
2차원을 예시로 들어보겠습니다.

![231209-235335](/posts/final_01/231209-235335.png)

2차원의 물제의 좌표를 우선 homogeneous coordinate로 표현합니다.

![231209-235404](/posts/final_01/231209-235404.png)

그리고 view coordinate를 word coordinate의 원점으로 이동시킵니다.

![231209-235416](/posts/final_01/231209-235416.png)

그리고 view coordinate를 rotation 하여 축을 일치시킵니다.

위 과정은 하나의 행렬로 표현 가능합니다.

$$
B' = \begin{bmatrix}
u_x & u_y & 0 \\
v_x & v_y & 0 \\
0 & 0 & 1 \\
\end{bmatrix} \cdot \begin{bmatrix}
1 & 0 & -x_o \\
0 & 1 & -y_o \\
0 & 0 & 1 \\
\end{bmatrix} \cdot B
$$

여기서 회전 방향이 시계방향이기 때문에 회전 백터가 Row 벡터로 이루어짐을 알아둡시다.

### Projection

좌표를 이동했다면, 3차원 물체를 2차원 View plane에 투영(projection)해야 합니다.
투영하는 방법에는 소실점이 있는 Perspective projection과 소실점이 없는(무한한 거리에 있는) Orthographic projection 2가지 방법이 있습니다.

- **Perspective projection**

 ![231210-000508](/posts/final_01/231210-000508.png)

 이 투영법은 닮음의 성질을 이용해서 투영합니다.
 즉, 아래와 같이 좌표가 view space에서 view plane으로 변환됩니다.

 $$
 (x,y,z) \Rightarrow (-d\frac{x}{z}, -d\frac{y}{z})
 $$

 하지만, 이는 선형 변환이 아니므로, 계산의 효율을 위해 homogeneous coordinate로 변환하여 선형 변환으로 만들어줍시다.

 $$
 \begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & -1/d & 0
 \end{bmatrix} 
 \begin{bmatrix}
 x \\
 y \\
 z \\
 1
 \end{bmatrix} = 
 \begin{bmatrix}
 x \\
 y \\
 -z/d
 \end{bmatrix}
 $$

 여기서 결과로 나온 벡터의 모든 원소를 $-z/d$로 나눠주면 $(-d\frac{x}{z}, -d\frac{y}{z})$를 얻을 수 있습니다.
 (homogeneous coordinate의 사용 안하는 좌표를 1로 바꿔주는 연산과 동일합니다)

 컴퓨팅 능력을 끌어올리기 위해 정사각행렬로 변환하면 식을 아래와 같이 표현할 수도 있습니다.

 $$
 \begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 \\
 0 & 0 & -1/d & 0
 \end{bmatrix} 
 \begin{bmatrix}
 x \\
 y \\
 z \\
 1
 \end{bmatrix} = 
 \begin{bmatrix}
 x \\
 y \\
 z \\
 -z/d
 \end{bmatrix} \Rightarrow (-d\frac{x}{z}, -d\frac{y}{z})
 $$

- **Orthographic projection**

 ![231210-001519](/posts/final_01/231210-001519.png)

 이 방식은 그저 z축의 정보을 사용하지 않으면 알아서 투영될 것입니다.

 $$
 \begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 1 \\
 \end{bmatrix} 
 \begin{bmatrix}
 x \\
 y \\
 z \\
 1
 \end{bmatrix} = 
 \begin{bmatrix}
 x \\
 y \\
 1
 \end{bmatrix} \Rightarrow (x, y)
 $$

### Clipping & Normalize

<tip>
 `View Frustum`
 
 ![231210-001840](/posts/final_01/231210-001840.png)
 공간상에서 화면에 실질적으로 보여지는 영역을 의미하며, 절두체 형식으로 공간이 잘리게 됩니다.
 최소로 카메라에 인식되는 평면을 near clipping plane, 최대는 far clipping plane 이라고 합니다.
</tip>

![231210-002108](/posts/final_01/231210-002108.png)

화면에서 보이지 않는 영역은 랜더링하지 않기 위해 clipping 하는 과정이 필요합니다.

![231210-002343](/posts/final_01/231210-002343.png)

하지만, 절두체는 계산하기가 힘들기 때문에 near clipping plane을 확장시켜 정사각형으로 만들어준 뒤 clipping 과정이 들어가게 됩니다.

이후에는 모니터의 해상도에 맞게 변환을 편리하게 하기 위해 좌표를 [-1, 1] 사이로 normalize 하는 과정이 추가됩니다.

아래는 위의 모든 과정을 요약한 Geometry processing 과정입니다.

![231210-002534](/posts/final_01/231210-002534.png)

---

## Lighting and shading

이 단계 역시 **Geometry processing 단계에서 수행**되지만, 분량이 많으므로 별도로 다뤄보겠습니다.

빛을 인식한다는 것은 광원으로부터 나온 빛이 물체와 부딪혀 흡수되지 않은 반사된 빛을 눈이 감지하는 과정을 의미합니다.
하지만 빛의 진행과 반사를 모두 추적하는 것은 연산량이 매우 많이 필요하기 때문에 이를 단순화 하기 위해 광원의 종류와 반사의 종류를 나누어 연산합니다.

### Light sources

광원의 종류에 따라 광원을 수식으로 표현해보겠습니다.

<notice>
 색상을 표현하기 위해 RGB값을 모두 연산해야 하지만, 수식으로 나타낼 때는 벡터 I로 한 번에 표현합니다.
 $$
 I = \begin{bmatrix}
 I_R \\
 I_G \\
 I_B \\
 \end{bmatrix} 
 $$
</notice>

- **Point lights**

 ![231210-003440](/posts/final_01/231210-003440.png)
 
 점광원으로 일반 적인 광원입니다.
 빛의 강도는 거리의 제곱에 반비례하며, 수식적으로는 아래와 같이 표현됩니다.

 $$
 I(p, p_0) = \frac{1}{|p-p_0|^2}I(p_0)
 $$

 하지만, 이렇게 처리하는 경우 실제로 거리에 따른 표현이 잘 되지는 않습니다.
 따라서 제곱항만 넣는 것이 아닌, 다항식으로 처리됩니다.

 $$
 I(p, p_0) = \frac{1}{k_c + k_ld + k_qd^2}I(p_0)
 $$

- **Distant lights**

 ![231211-162941](/posts/final_01/231211-162941.png)

 방향성 광원(무한히 멀리있는 광원)으로, 점광원과 차이점은 위치를 고려하지 않는다는 점입니다.
 점광원은 위치에 따라 입사각이 달라졌다면, 방향성 광원은 방향에 따라서만 입사각이 달라지게 됩니다.
 위 식에서 $p_0$ = [x y z 1]$^T$ 였다면, 방향성 광원에서는 $p_0$ = [x y z 0]$^T$ 입니다.

- **Spotlights**

 ![231211-163031](/posts/final_01/231211-163031.png)

 점광원 + 원뿔로, 점광원과 비슷하지만, 원뿔 영역에 해당하는 부분에만 빛이 비춰집니다.
 수식적으로 아래와 같습니다.

 $$
 I = cos^e \phi = (s\cdot I_s)^e
 $$

 여기서 $\phi$는 0과 $\theta$ 사이의 값이고, e값이 커질수록 중심부가 강하게 스포트라이트 됩니다.

 ![231211-164403](/posts/final_01/231211-164403.png)

- **Ambient lights**

 배경 광원으로 공간 전체에 은은하게 퍼져있는 빛입니다.
 즉, Intensity만 전체적으로 더해주면 됩니다.

### Interaction with Materials

빛과 상호작용하는 물질에 따라 흡수, 투과, 반사되는 정도가 달라지는데 여기선 반사에 대해서만 다뤄보도록 합니다.
(반사를 해야 물체가 눈에 보이겠죠?)

반사는 Phong reflection model로 표현되는데 이는 정반사(Specular) + 난반사(Diffuse) + 배경 의 3요소로 표현됩니다.
하나하나 알아봅시다.

- **Ambient reflection**

 배경 반사는 물리적 실체가 있는 구성요소는 아니고, 랜더링시 전체적으로 퍼진 빛을 시뮬레이션하기 위해 계산하며 아래와 같습니다.

 $$
 I_a = k_aL_a
 $$

 여기서 $k_a$는 반사 계수로 0과 1 사이의 값을 가지며, 1이면 배경 빛을 모두 반사합니다.

- **Diffuse reflection**

 난반사는 빛의 입사각과 관계 없이 모든 방향으로 반사한다고 가정하기 때문에 입사하는 빛의 양만 알면 반사량을 계산할 수 있습니다.

 $$
 I_d = k_d(N\cdot L)L_d
 $$

 여기서 N은 표면의 수직 단위벡터, L은 빛 소스($L_d$) 로의 방향 단위벡터 입니다.
 즉, 사이각을 계산하는 항이 추가된 것입니다. (**Position dependent**)

- **Specular reflection**

 정반사는 입사각과 동일한 반사각으로 빛을 반사합니다.
 즉, 관찰자가 어디있는지에 따라 반사된 빛의 밝기가 다르게 느껴지게 됩니다. (**View, Position dependent**)

 $$
 I_s = k_s(cos\alpha)^nL_s = k_s(V\cdot R)^nL_s
 $$

 여기서 R은 반사되는 방향 단위벡터, V는 view 방향 단위벡터 입니다.
 또한 $\alpha$는 R, V 사이의 각도입니다.

 ![231211-170153](/posts/final_01/231211-170153.png)

 또한 n은 일종의 상수인데, 거울의 경우에는 n이 거의 무한한 값이고, 금속은 100~500 사이 정도로 표현됩니다.

### Polygonal Shading

![231211-170419](/posts/final_01/231211-170419.png)

지금까지 위 그림과 같이 빛을 반사까지 했습니다.
그렇다면 이제 폴리곤 덩어리에 색칠을 해야 하는데, 그 방식도 여럿 존재합니다.
각 방식과 장단점을 알아봅시다.

- **Flat shading**

 ![231211-170816](/posts/final_01/231211-170816.png)

 면 단위로 색칠하는 방식으로 특정 면의 법선 벡터 n을 구하면 해당 면을 하나의 색상으로 칠하는 방식입니다.
 계산량은 가장 적지만, 다른 면과 매끄럽게 연결되지 않는다는 단점이 있습니다.

- **Gouraud shading**

 vertex 단위로 색칠하는 방식으로 면의 꼭짓점의 법선 벡터들을 구하고, 꼭짓점들의 색상을 칠합니다.
 면의 내부는 꼭짓점의 색상을 선형 보간하는 방식으로 계산합니다.

 이 때, 꼭짓점은 점이기 때문에 법선 벡터를 바로 구할 수는 없습니다.

 ![231211-171148](/posts/final_01/231211-171148.png)

 따라서 개발자가 임의로 지정해주거나, 주변 면의 법선 벡터의 평균을 사용해서 구하는 방식을 사용합니다.

 계산량은 보통이지만, 면과 면이 부드럽게 연결됩니다.
 하지만, vertex의 보간으로 계산하기 때문에 면 중앙에만 하이라이트로 비춰지는 빛을 표현할 수는 없습니다.

- **Phone shading**

 픽셀 단위로 색칠하는 방법으로 꼭짓점의 법선 벡터를 구하는 것 까지는 동일합니다.
 하지만, 색칠을 할 때는 픽셀별로 법선 벡터를 선형 보간하는 방식으로 구한 후, 픽셀의 법선 벡터를 이용해서 색상을 칠합니다.

 따라서 계산량은 가장 많지만, 가장 사실적으로 빛을 묘사할 수 있습니다.

 ![231211-171436](/posts/final_01/231211-171436.png)

 물론, 반사되는 빛 표현만 사실적으로 하는 것이지, 실루엣까지 부드럽게 할 수는 없습니다.
 실루엣을 부드럽게 하려면 vertex 개수 자체를 늘리는 방법을 사용해야 합니다.

---

## Rasterization

모든 객체는 아래의 세가지의 조합으로 표현할 수 있습니다.

- Points
- Line segments
- Triangles

예로 들어 곡선은 짧은 직선을 어려개로 근사할 수 있고, 폴리곤 덩어리와 곡면 역시 여러 삼각형으로 근사할 수 있습니다.

하지만, 위 세 요소를 수학적으로 기술했다고 해도, 화면에 띄우는 과정에서 Aliasing 현상이 나타나게 됩니다.

선을 기준으로 여러 근사 알고리즘과 Aliasing 현상을 알아보도록 합시다.

- **Point Sampling**

 ![231211-172416](/posts/final_01/231211-172416.png)

 각 픽셀의 중심부가 직선 범위 내부이면 1, 아니면 0으로 처리합니다.
 연산량이 가장 적이만 문제가 많습니다.

- **Bresenhan Line**

 ![231211-172343](/posts/final_01/231211-172343.png)

 인접한 픽셀이 둘 다 켜지는 방식을 방지하는 알고리즘으로, row, column 별로 1개만 1이 되도록 강제합니다.

- **Box Filtering - Antialiasing**

 ![231211-172713](/posts/final_01/231211-172713.png)

 각 픽셀이 직선에 얼마나 포함되는지에 대한 정보를 바탕으로 \[0, 1\] 사이로 찰하게 합니다.
 Antialiasing이 아닌 방식에 비해서는 느리지만, 그래도 빠른 편이며, 나름 정확하게 표현할 수 있습니다.

- **Weighted Filtering - Antialiasing**

 ![231211-172915](/posts/final_01/231211-172915.png)

 가우시안 필터링 기법을 사용하여 가중치를 부여(중심부의 weight가 큼)한 평균을 계산하여 칠합니다.
 가장 느리지만, 가장 묘사가 잘 됩니다.

### Hidden Surface Elimination

시각에 따라 보이지 않는 폴리곤 덩어리를 랜더링하면 성능이 떨어질 것입니다.
따라서 보이지 않는 부분은 랜더링 대상에서 제외시키는 방법들을 알아봅시다.

- **Back-face Culling**

 ![231211-173323](/posts/final_01/231211-173323.png)

 간단하게 설명하면 뒤를 바라보는 면은 랜더링 대상에서 제외시키는 방법입니다.
 view 방향 단위벡터(v)와 면의 법선 단위벡터(n)를 이용해서 $n \cdot v$로 계산하여 양수라면 랜더링, 음수면 제외하는 방식으로 동작합니다.

 주의할 점은 법선 벡터를 계산할 때, 꼭짓점의 좌표를 이용해서 $(p_1-p_0) \times (p_2-p_0)$ 와 같이 계산해야 하는데, 시계방향, 반시계방향으로 죄표를 넣으면 법선 벡터의 방향이 달라지게 됨을 주의합시다.

- **Depth Buffer (Z-Buffer)**

 ![231211-173721](/posts/final_01/231211-173721.png)

 진짜 무식한 방법이지만, Back-face culling보다 성능 좋은 방법입니다.

 1. 우선, Z-buffer를 무한대로, Frame buffer를 배경색으로 초기화 합니다.

 $$
 Z(x,y) = \infty \\
 C(x,y) = c_0
 $$

 2. depth가 작아지면, 즉 더욱 view plane에 가깝다면 (**z(x, y) \< Z(x, y)**) Z, Frame buffer를 업데이트 합니다.

 $$
 Z(x,y) = z(x,y) \\
 C(x,y) = c(x,y)
 $$
 
 심지어 속도도 빠릅니다.
 하지만, 메모리를 많이 쓴다는 단점은 있습니다.

 ![231211-174248](/posts/final_01/231211-174248.png)

 하지만 오늘날은 메모리 용량도 많기 때문에 Z-Buffer 방식을 사용합니다.

---

## Texture mapping

간단하게 텍스쳐를 폴리건 표면에 붙이는 방법만 알아봅시다.

1. 폴리건에 붙이고자 하는 텍스쳐 이미지를 \[0, 1\]로 normalize 합니다.
2. world coordinate(폴리건)과 texture coordinate(텍스쳐)의 대응관계를 찾습니다.
3. 대응관계에 따라 normalize된 텍스쳐의 좌표를 변환하여 폴리건 위에 씌웁니다.

일부 수학적 3차원 도형의 경우 2개의 좌표로도 표현이 가능한데, 이를 텍스쳐 좌표에서 활용하면 됩니다.

이 과정에서 샘플링이 누적되며 오류가 중첩되어 Aliasing 현상이 발생할 수 있습니다.

또한, 텍스쳐를 이용해서 세부 음영 묘사를 할 수 있는 트릭을 사용할 수 있습니다.
즉, 폴리건은 간단히 만들고, 세부 음영 묘사는 텍스쳐로 수행하여 성능을 높이는 최적화 방법입니다.

![231211-174923](/posts/final_01/231211-174923.png)

하지만, 가장자리 실루엣은 세부적으로 묘사가 안됩니다.
(vertex를 늘리는 방법 외엔...)

마지막으로, 배경을 텍스쳐로 입혀서 반사를 구현하는 최적화 방식 또한 있습니다.

랜더링 과정에 대해 알아봅니다.

Rendering Pipeline

## Matrix

$$
\begin{pmatrix}
a_{11} & a_{12} & ... & a_{1n} \\
a_{21} & a_{22} & ... & a_{2n} \\
... & ... & ... & ... \\
a_{m1} & a_{m2} & ... & a_{mn} \\
\end{pmatrix}
$$

m-by-n matrix, 또는 **m행(Row) n열(Column)** 의 행렬이라고 부른다.

여기서 하나의 **행** 만으로 이루어진 행렬을 `Row vectors`, 
한 **열**로만 이루어진 행렬을 `Column vectors` 라고 부른다.

### Transpose

$$
(A^T)_{ij} = A_{ji}
$$

각 행과 열을 뒤집은 행렬을 전치행렬 이라고 부른다.

### Square Matrix

행과 열의 개수가 같은 행렬을 의미한다.

### Identity Matrix

$$
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix}
, \;
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}
$$

위와 같이 Square Matrix인데 대각선만 1이고, 나머지는 0으로 채워진 행렬을 의미한다.

> AI = IA = A

이 행렬의 가장 큰 특징은 행렬 A에 Identity Matrix를 곱하면 다시 행렬 A가 나온다는 것이다.

### Scalar Multiplication & Addition

백터에 스칼라 곱을 하거나, 백터간 합이나 차를 구할 때는 [**이전 포스트**](https://wjlee611.github.io/blog/univ_virtual-worlds/mid_03)에서 벡터의 연산을 했을 때와 동일하게 **각 원소에 대해 연산**을 진행하면 된다.

### Matrix Multiplication

![231023-222141](/posts/mid_04/231023-222141.png)

행렬간 곱 연산은 위의 이미지와 같이 계산된다.
여기서 주의할 점은 **앞의 행렬의 `열`** 의 개수와 **뒤의 행렬의 `행`** 의 개수가 일치해야 한다는 점이다.

---

## Transformations

### Basis

변환에 앞서 기저에 대해 알 필요가 있다.
선형 독립인 벡터들이 공간을 생성(span)할 때, 그 벡터의 집합을 기저(basis)라고 한다.

<tip>
`선형 독립 (Linear Independent)`
 
N차원에서 어떤 하나의 벡터가 나머지 N-1개의 벡터의 **선형 결합으로 표현할 수 없는 경우**, N개의 벡터들이 선형 독립이라고 한다.
즉, 벡터간 의존성이 없어야 한다.
</tip>

벡터가 공간을 생성한다는 의미를 잘 모를 수 있는데, 예로 들어보자.

![231023-230449](/posts/mid_04/231023-230449.png)

v는 한 평면위의 벡터이다.
이 상태에서 $v_1, \; v_2$의 값을 [-$\infty$, $\infty$] 범위로 임의 조정한다고 가정해보자.
그럼 v는 어떤 범위의 종점 좌표를 가질 수 있을까?
바로 벡터 a, b가 속한 평면의 모든 좌표를 가질 수 있을 것이다.

즉, **평행하지 않은 벡터의 선형 결합으로 공간을 생성**할 수 있는 것이다.

그렇다면 두 벡터가 평행하지 않는다는 조건도 이해가 될 것이다.
만약 두 벡터가 **평행**하다, 즉, **하나의 벡터로 다른 벡터를 표현**할 수 있다, 다른 말로 두 벡터가 **선형 의존**이라면, v는 직선상에만 존재할 수 있기 때문이다.

그럼 다시 basis 얘기로 돌아와서, basis의 선형 결합으로 basis가 span하는 공간의 모든 벡터를 표현할 수 있다는 것을 이해했다.
이 때 성립하는 증명이 있다.

> 같은 basis의 선형결합으로 표현되는 벡터는 표현 방법이 1개로 유일하다.

위의 증명된 내용 덕분에, basis의 선형 결합 시 사용하는 weight를 좌표로써 활용할 수 있는 것이다.
그렇기에 basis를 바꾼다는 건 좌표값을 바꾸는 것일 뿐, 벡터 그 자체를 바꾸는게 아니다.

### Linear Map

선형 사상이란 벡터의 기저를 바꿀 때, 즉 **벡터 공간이 바뀔 때 변형시에 선형성이 유지되는 변환 함수($F$)** 를 말한다.

예로 들어 아래는 선형 사상이다.
![231023-232038](/posts/mid_04/231023-232038.png)

하지만, 이 경우는 선형 사상이 아니다.
![231023-232104](/posts/mid_04/231023-232104.png)

음? 그런데 이게 기저가 바뀌는거랑 무슨 상관이냐고?
이제 기저를 선형 사상(변환 함수)에 대입해보며 알아보자.

$$
\widehat{\textrm{v}} = F\textrm{v} \\
{} \\
\begin{pmatrix}
\widehat{v_1} \\
\widehat{v_2} \\
\widehat{v_3}
\end{pmatrix} =
\begin{bmatrix}
f_{11} & f_{12} & f_{13} \\
f_{21} & f_{22} & f_{23} \\
f_{31} & f_{32} & f_{33} \\
\end{bmatrix}
\begin{pmatrix}
v_1 \\
v_2 \\
v_3
\end{pmatrix} 
$$

이해를 돕기 위해 $v_1$, $v_2$, $v_3$을 $x$, $y$, $z$ 라고 생각해보자.

이제 ($v_1$, $v_2$, $v_3$) 대신에 (1, 0, 0) 을 대입해보자.
이 때, (1, 0, 0)은 x축을 가리키는 기저의 원소이다.


$$
\begin{pmatrix}
\widehat{v_1} \\
\widehat{v_2} \\
\widehat{v_3}
\end{pmatrix} =
\begin{bmatrix}
f_{11} & f_{12} & f_{13} \\
f_{21} & f_{22} & f_{23} \\
f_{31} & f_{32} & f_{33} \\
\end{bmatrix}
\begin{pmatrix}
1 \\
0 \\
0
\end{pmatrix} =
\begin{pmatrix}
f_{11} \\
f_{21} \\
f_{31}
\end{pmatrix} 
$$

즉, 선형 사상($F$) 로 인해 기저 x(1, 0, 0)는 $(f_{11}, \; f_{21}, \; f_{31})^T$로 변환되었다.

여기서 알 수 있는 것은 선형 사상, **Linear Function $F$의 i번째 열 벡터는 i번째 축의 기저벡터가 어디로 대응**되는가를 알려준다.
또한, 위의 변환 과정은 선형성이 유지된다.

참고로 선형성이 유지되는 특성 덕분에 여러 선형 사상을 한 번에 처리하는 것 또한 가능해진다.

> A(B(C(D(x)))) = ABCDx = $\textrm{x}^TD^TC^TB^TA^T$

### 2D Linear Transformations

우선 회전을 살펴보자.

![231023-234010](/posts/mid_04/231023-234010.png)

선형 사상을 이용한 기저의 변환을 어느정도 이해했다면 이제 변형식이 왜 이렇게 생겼는지도 이해할 수 있을 것이다.

예로 들어 (1,0) 즉 x축의 기저벡터를 $\theta$ 만큼 회전시킨 좌표는 ($cos \theta$, $sin \theta$)가 되는데, 이는 위에서 언급한 "선형 사상, **Linear Function $F$의 i번째 열 벡터는 i번째 축의 기저벡터가 어디로 대응**되는가를 알려준다" 와 완벽히 일치한다.

<tip>
 즉, 앞으로의 변환은 각 축의 기저 벡터가 어떻게 변하는지를 파악하고, 해당 **변화 후의 값을 이용**해서 선형 사상 함수를 작성하면 된다.
</tip>

이런 내용을 염두하고 다른 변환들도 살펴보자.

![231023-235906](/posts/mid_04/231023-235906.png)

![231024-000043](/posts/mid_04/231024-000043.png)

![231024-000102](/posts/mid_04/231024-000102.png)

### Affine Maps

2D Translation을 가능케하는 Transformations 이 있을까?

![231024-000319](/posts/mid_04/231024-000319.png)

없다.
그 이유는 **이동은 선형 변환이 아니**라서 이를 표현할 선형 사상 함수가 없기 때문이다.

즉, Affine Map은 Linear map + Translation 으로 표현할 수 밖에 없다.
왜냐면 Affine은 Linear하지 않기 때문이다.

### Homogeneous Coordinates

그렇다면 Transform과 Translate를 동시에 처리할 수 있는 방법이 없을까?
바로 Homogeneous Coordinates를 이용하면 된다.

이게 뭐냐면, 2차원의 Homogeneous Coordinates는 3차원의 벡터가 된다는 건데, 예시를 들어보자.

$$
\begin{pmatrix}
wx' \\
wy' \\
w
\end{pmatrix} =
\begin{bmatrix}
1 & 0 & t_x \\
0 & 1 & t_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{pmatrix}
wx \\
wy \\
w
\end{pmatrix}
$$

적당하게 w 기저를 하나 더 만들어서 차원을 높였다.
이 때, ($wx$, $wy$, $w$)를 Homogeneous Coordinates 라고 하는데, 이제 여기에 계산의 편의를 위해 $w$에 1을 대입해보자.

$$
\begin{pmatrix}
x' \\
y' \\
1
\end{pmatrix} =
\begin{bmatrix}
1 & 0 & t_x \\
0 & 1 & t_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1
\end{pmatrix} = 
\begin{pmatrix}
x + t_x \\
y + t_y \\
1
\end{pmatrix}
$$

결과는?
놀랍게도 Transformations 한 방식과 동일하게 진행되었는데 결과는 Translate 한 결과가 나왔다.
이를 이용하면 2D 에서의 모든 변형은 다음과 같은 4개의 행렬의 곱으로 표현이 가능해진다.

![231024-002119](/posts/mid_04/231024-002119.png)

즉, 좌상단의 2x2 행렬은 Transform을 위한 부분이고, 우상단의 2x1 행렬은 Translate를 위한 부분이다.

참고용으로 3D에 대한 Homogeneous Coordinates도 남겨놓겠다.
![231024-002347](/posts/mid_04/231024-002347.png)

### Compound Transformations

Linear Map의 마지막에 언급한 사실에 근거해 이제 모든 변환은 합성 변환으로 치환할 수 있다.

> A(B(C(D(x)))) = ABCDx = $\textrm{x}^TD^TC^TB^TA^T$

그렇게 하면 ABCDx 이 행렬곱을 정리하기만 하면 A~D 까지의 모든 변환을 한 번에 수행하는 결과를 얻을 수 있으니 연산량이 매우 감소하게 된다.

<notice>
 단, 연산 순서에 주의해야 한다.
 
 ![231024-002828](/posts/mid_04/231024-002828.png)
</notice>

이제 연산량이 어떻게 변하는지 예시를 살펴보자.

![231024-003050](/posts/mid_04/231024-003050.png)

이를 응용하면 특정 방향으로만 스케일링 하는 것도 구현할 수 있다.

![231024-003225](/posts/mid_04/231024-003225.png)

행렬에 대한 기본적인 내용과 이를 이용한 공간상에서의 변환에 대해 다뤄봅니다.

Matrix and Transformations

<notice>
 Vector와 Points는 (1, 2, 3) 과 같이 숫자로된 좌표로 표현된다는 점에서는 비슷하다.
 
 하지만, `Points`는 **공간의 위치**를 나타내지만, `Vector`은 **방향과 크기**를 나타낸다는 점이서 다르다.
 (벡터는 위치 개념이 없음. 상대적인 방향과 크기만을 가질 뿐) 
</notice>

## Vector Algebra

### Scalar Multiplication

![231023-204033](/posts/mid_03/231023-204033.png)

해당 방향으로 크기만 증가하는 연산이다.
**벡터의 각 성분에 크기 c만큼 각각 곱해주면** 된다.

### Addition

![231023-204232](/posts/mid_03/231023-204232.png)

A 벡터의 종점에 B 벡터의 시점을 이어붙이는 연산으로, 그 값은 A 벡터의 시점 &rarr; B 벡터의 종점이 된다.
평행 사변형법으로도 계산할 수 있으며, **벡터의 각 성분끼리 더하면** 된다.

### Substraction

![231023-204432](/posts/mid_03/231023-204432.png)

벡터에 -1을 스칼라 곱을 한 후, Addition을 한 결과와 같은 연산이다.
**벡터의 각 성분을 빼주면** 된다.

### Length & Direction

![231023-204636](/posts/mid_03/231023-204636.png)

벡터의 크기($L$)와 x축에 대한 방향($\theta$)는 다음과 같다.

> $L = \sqrt{x^2 + y^2}$
>
> $\theta = tan^{-1}\frac{y}{x}$

<tip>
 크기가 1인 벡터를 `단위벡터` 라고 하며, 벡터를 단위벡터로 변환하는 것을 **Normalization** 이라고 한다.
 백터를 Normalization 하는 법은 **벡터의 각 성분을 $L$로 나눠주면** 된다.
</tip>

### Linear Combination

벡터들을 선형결합 하는 것을 의미한다.

> $b = c_1v_1 + c_2v_2 + ... + c_kv_k$

이는 $v_1$, $v_2$, ..., $v_k$의 선형 결합이며, 상수 c를 weight라고 부른다.

이 weight 값에 따라 다른 명칭으로 불리기도 한다.

- `Affine Combination`
 weight의 합이 반드시 1이 되는 선형결합.

- `Convex Combination`
 weight이 모두 양수이고, 합이 반드시 1이 되는 선형결합.

### Dot product (내적)

![231023-211310](/posts/mid_03/231023-211310.png)

내적의 연산 결과는 스칼라가 되는데 우선 식부터 살펴보자.

> $\overrightarrow{a} \cdot \overrightarrow{b} = a_1b_1 + a_2b_2 = \begin{Vmatrix} \overrightarrow{a} \end{Vmatrix} \begin{Vmatrix} \overrightarrow{b} \end{Vmatrix} cos \theta$

내적은 사잇각을 알아내는데 사용할 수 있는데, 그런데 내적 그 자체는 무슨 의미를 가질까?
유닛벡터에 대해 다음과 같은 내적값은 다음과 같은 의미를 갖는다.

- `1`
 두 벡터가 **같은 방향으로 평행**하다

- `-1`
 두 벡터가 **정 반대 방향으로 평행**하다

- `0`
 두 벡터가 **수직**한다

- `>0`
 두 벡터가 **같은 방향**이다

- `<0`
 두 벡터가 **다른 방향**이다

### Projection

내적을 응용하면 한 벡터를 다른 벡터에 사상한 벡터를 얻을 수 있다.

![231023-212348](/posts/mid_03/231023-212348.png)

$\overrightarrow{a'}$ 벡터의 길이는 **$\begin{Vmatrix} \overrightarrow{a} \end{Vmatrix} cos \theta$** 와 같다.
또한 $\overrightarrow{a'}$ 벡터의 단위벡터는 **$\frac{1}{||\overrightarrow{b}||} \overrightarrow{b}$** 이다.

따라서 둘을 곱한 다음의 식이 벡터 a를 벡터 b에 사상한 벡터가 된다.

![231023-213605](/posts/mid_03/231023-213605.png)

### Cross produce (외적)

![231023-213718](/posts/mid_03/231023-213718.png)

> $\overrightarrow{a} \times \overrightarrow{b} = \begin{Vmatrix} \overrightarrow{a} \end{Vmatrix} \begin{Vmatrix} \overrightarrow{b} \end{Vmatrix} sin \theta \cdot \overrightarrow{n}$
>
> 여기서 $\overrightarrow{n}$은 벡터 a, b에 수직한 유닛 벡터

외적 두 벡터의 수직인 벡터로, 그 크기는 두 벡터가 이루는 평행사변형의 넓이이다.

계산은 아래와 같이 하면 된다.

$$
\begin{pmatrix}
a_1 \\
a_2 \\
a_3
\end{pmatrix} \times
\begin{pmatrix}
b_1 \\
b_2 \\
b_3
\end{pmatrix} =
\begin{pmatrix}
a_2b_3 - a_3b_2 \\
a_3b_1 - a_1b_3 \\
a_1b_2 - a_2b_1
\end{pmatrix}
$$

### Normal Vector

한 평면에 대한 수직 단위벡터로 외적을 이용하면 구할 수 있다.

![231023-214703](/posts/mid_03/231023-214703.png)

---

## Points Algebra

Points 는 더하거나, 스칼라곱에 대한 정의가 없다.
하지만, 특수 상황에서는 의미를 갖는데, 그것들에 대해 알아보자.

### Point - Point

![231023-210346](/posts/mid_03/231023-210346.png)

Point B에서 Point A를 뺴면, 그 결과는 A&rarr;B `Vector`가 된다.

### Point + Vector

![231023-210527](/posts/mid_03/231023-210527.png)

Point에 Vector를 더하거나 빼면 다른 `Point`가 된다.

### Affine Combination

위에서 언급했 듯, Points 는 더하거나, 스칼라곱에 대한 정의가 없다.
하지만, 스칼라 곱 중에서 그 weight의 합이 1이 되는 경우 내분, 또는 외분의 의미를 갖게된다.

벡터에 대한 기본적인 내용에 대해 다뤄봅니다.

Vector

## Coordinate Systems

어떤 데이터든 간에 3D 공간상에 표현하기 위해서는 좌표 시스템을 먼저 구현해야 한다.
그래야 공간상의 좌표의 조합으로 모델을 생성할 수 있기 때문이다.

![231023-195004](/posts/mid_02/231023-195004.png)

개발 환경에 따라 왼손 좌표계를 쓰거나 오른손 좌표계를 쓰는데, 참고로 유니티는 왼손 좌표계를 사용한다.
따라서 유니티 관련 포스트는 모두 왼손 좌표계 기준으로 기술될 예정이다.

---

## Polygonal Meshes

![231023-195154](/posts/mid_02/231023-195154.png)

모든 3D 오브젝트를 삼각형 평면을 이어붙힌 형태로 표현하는 기법으로, 가장 많이 사용되는 방식이다.
이런 데이터를 저장하는 방식에는 크게 3가지로 나뉘는데 각각 어떤식으로 데이터를 관리하는지 살펴보자.

<tip>
 mesh들은 OBJ, 3DS, POV 등의 확장자로 관리되는데,
 OBJ의 경우 아래와 같은 정보를 저장한다.
 - vertex의 좌표
 - 각 vertex의 택스쳐 좌표
 - 각 vertex의 수직 vertex
 - 위의 vertex들로 표현돤 face
</tip>

### Vertex-Vertex

![231023-195357](/posts/mid_02/231023-195357.png)

오직 점들만 데이터로 관리하는 자료구조를 사용한다.
각 vertex의 **좌표**와 인접한(연결된) **vertex**를 저장한다.

면에 대한 정보는 저장하지 않기에 추가적인 연산을 통해 얻어낼 수 밖에 없다.
그렇기에 용량은 가장 작지만, 연산에 대한 부담이 있는 모델이다.

### Face-Vertex

![231023-195627](/posts/mid_02/231023-195627.png)

점과 면을 데이터로 관리하는 자료구조를 사용하며, 가장 많이 사용되는 방식이다.
`face`는 face를 구성하고 있는 **vertex**들의 집합으로 관리되고,
`vertex`는 vertex의 **좌표**와 인접한 **faces**들의 집합으로 관리된다.

### Winged Edge

![231023-195936](/posts/mid_02/231023-195936.png)

점과 면, 추가로 모서리의 데이터로 관리하는 자료구조를 사용하며, mesh를 변화시켜야 할 상황에 유용하게 사용할 수 있다.
`face`는 face를 구성하고 있는 **edge**들의 집합으로 관리되고,
`vertex`는 vertex에 연결된 **edge**들의 집합으로 관리된다.
마지막으로 `edge`는 **시점, 종점의 좌표**와 **분할하는 면**, 그리고 연결된 edge 중 4개의 edge로 관리되는데,
4개의 edge는 **시점에 연결된 back CCW, back CW, 종점에 연결된 front CCW, front CW** 순으로 관리된다. (그림 참고)

모델을 저장하는 방법에 대해 알아봅나디.

Modeling


## Engine Architecture

정말 말도안되게 깊고 넓은 레이어가 있는데, 간략하게 무슨 역할만을 하는지 살펴보자.
~~(괜히 게임이 종합 예술이 아닌...)~~

- Platform Independence Layer
  디바이스에 상관없이 구동시키기 위한 레이어

- Core systems
  각종 코어 유틸리티들의 집합.
  메모리 관리, 수학 라이브러리, 자체 자료구조 알고리즘 등.

- Resource Manager
  각종 에셋글의 생성과 관리, 배치 등의 총괄적인 관리를 담당.
  **생성은 개발단계**에서, **배치는 런타임**에 관리된다.

- Rendering Engine
  에셋 등 데이터를 픽셀로 랜더링.
  Projection, Shading, Texture sampling 등이 여기서 처리됨.

- Scene Graph/Culling Optimization
  시야에 안보이는 부분을 잘라내여 보이는 부분만 랜더링하도록 최적화.

- Visual Effects
  광원, 명암 등, 이미지(비주얼) 향상을 위한 후처리 과정.

- Collision and Physics
  충돌 및 물리 계산.

- Animation
  에셋들의 물리법칙을 에외한 움직임.

- Human Interface Devices (HID)
  사용자 입력, 움직임 등의 장치 관리.

- Gameplay Foundation systems
  게임 개발 환경 제공.

---

## Resource Management

리소스에는 Meshes, audio, animation 등등 여러 raw resources 가 존재하는데, 각 리소스가 어떻게 처리되어야 하는지는 각 리소스의 Metadata를 참고하면 알 수 있다.

리소스 생성과정은 다음과 같다.
1. Maya, Photoshop 등과 같은 서드파티 앱에서 Export 한다.
2. 이후 유니티가 game-ready 에셋인 `prefeb`으로 변환하기 위해 리소스 컴파일러가 구동된다.
3. 추가로 여러 리소스를 하나의 패키지로 합치기 위해 링커도 제공한다.

### Runtime

유니티가 런타임에 어떻게 리소스를 관리하는지 개념적으로 알아보자.

우선 유니티는 동일한 리소스는 특정 시각에 반드시 **1개**만 메모리에 올라오도록 보장한다.
무슨 말이냐면 원할 때 리소스가 불러와지고, 이게 중복되어 불러와져 메모리 낭비를 하지 않게끔 해준다는 뜻인데, 이는 유니티의 **로딩 정책** 덕분에 가능해졌다.

![231023-181333](/posts/mid_01/231023-181333.png)

유니티는 리소스를 `비동기 로드`하기 때문에 로드해야 할 시점보다 미리 로딩한다.
예로 들어 Level 1 에서는 A, B, C 리소스가 필요한데, 레벨 실행 전에 먼저 필요한 리소스의 목록을 파악해서 로딩하고, 로딩이 완료된 후에 레벨을 진행하는 방식으로 진행된다.

이 때, 각 리소스별로 `Reference count`를 둬서 쓸데없는 중복 로딩이나, 필요 없는 리소스를 메모리에서 제거하기도 한다.
ref count가 0보다 큰데 로딩되지 않은 리소스는 로딩하고, ref count가 0인데 로딩된 리소스는 언로드 하도록 하는 것이다.

메모리에서 제거하는 원리는, GC(Garbage Collector)가 일정 주기로 ref count가 0인 리소스를 제거한다.
`System.GC.Collect()` 를 이용하면 수동적으로 GC를 호출할 수 있지만, 가능하면 그러지 말자.

정리하면 런타임에 리소스 매니저는 아래의 역할을 수행할 수 있어야 한다.
1. 동일한 리소스는 특정 시각에 메모리에 1개만 올라오도록 보장
2. 각 리소스의 생명주기를 관리
3. prefeb과 같은 여러군데 흩어진 리소스의 묶음을 관리할 수 있어야 한다
4. 리소스간 참조의 무결성을 보장해야 한다
5. 이미 로드된 리소스의 메모리 사용량도 관리해야 한다

### Location

리소스가 어디에 존재하는지에 따라 런타임시 로드 방식이 달라진다.

- AssetBundles
  유니티 플레이어 외부의 리소스로, 보통 웹서버 상에 존재하는 리소스이다.
  `AssetBundle.LoadAsset()` 으로 불러올 수 있다.

- Resource folders
  유니티 플레이어 내부의 리소스로, Project view의 Resources 폴더에 존재하는 리소스이다.
  `Resources.Load()` 로 불러올 수 있다.

---

## Game Loop

매 프레임 상태 변경을 하거나, 사용자 입력을 받거나, 화면 랜더링을 위한 무한 루프를 의미한다.
1초에 얼마나 루프가 돌아가는지를 나타내는 척도가 FPS인데, 엄밀히 말하면 화면이 그려지는 횟수지만, 한 루프에 한 번 화면이 업데이트되니 거의 같이 사용할 수 있다.

유니티에선 거의 대부분의 클래스가 `MonoBehavior`를 상속하여 정의하는데, 여기에서 `Update()` 함수가 프레임당 한 번 호출이 이루어진다.

그 외에도 override할 수 있는 다른 함수 몇 개 더 알아보자.

- `Start()`
  첫 프레임 업데이트시 호출되는 함수.

- `LateUpdate()`
  Update() 함수가 종료되고나서 호출되는 함수.

- `OnDestory()`
  소멸자 비스무리한 함수.
  마지막 프레임의 업데이트가 완료되고 나서 호출되는 함수.

### Delta Time

두 인접한 프레임 사이의 시간이 얼마나 흘렀는가를 나타내는 값으로, 보통 그 값은 FPS의 역수이다.
즉, 30FPS 게임에서의 $\Delta t$는 1/30 seconds, 즉, 3.33ms이다.

두 프레임 사이의 시간이므로 물리 시뮬레이션시 시간 변화율로서 동작하게 되는데, 물리량을 수식화 하면 다음과 같다.

| 의미 | 수식 |
|---|---|
| Position | $p_{t+\Delta t} = p_t + v_t \cdot \Delta t$ |
| Velocity | $v_{t+\Delta t} = v_t + a_t \cdot \Delta t$ |
| Acceleration | $a_{t+\Delta t} = f_{ext}/m$ |

즉, $\Delta t$가 너무 크거나 일정하지 않으면 물리량에 오차가 커질 수 밖에 없다.
만약 델타값을 고정시키고, 이를 게임 루프에 의존해서 증가시킨다면 컴퓨터 사양에 따라 다르게 동작하는 현상이 발생할 수 있다.

따라서, 유니티는 **CPU**의 `high-resolution timer`를 이용해서 델타값을 구하기 때문에 현실세계와 유사한 플레이 경험을 얻을 수 있도록 합니다.

유니티 게임 엔진에 대한 기초적인 이론을 알아봅니다.

Unity Engine

3학년 2학기 가상세계 수업 아카이브