코달

개념 스패닝 트리 (간선의 수 최소. 사이클이 생기면 안됨). 를 만드는 알고리즘 그리디 알고리즘. 길이(가중치)가 가장 작은 간선부터 연결함. 근데 그러다 보면 사이클이 생길 수 있음. 사이클을 피하는 알고리즘 필요. 방법 : 사이클 피하기 간선이 연결된 노드들을 그룹으로 묶고 같은 그룹끼리 연결하는 간선은 피하는 것, Disjoint Set을 활용함. 우선 간선후보들을 가중치 순으로 정렬함 간선 후보목록을 순회하며 가중치가 가장 작은 간선후보부터 사이클 검사를 함(Disjoint Set을 사용해 간선에 연결된 두 정점이 같은 팀인지 확인함). 참고 DisjointSet: https://ddukddaksudal.tistory.com/54 같은 팀이면 다음 간선 후보로 넘기고 다른 팀이면 간선을 추가함(..

개념 Union Find 라고 하기도 한다. 트리 구조를 이용한 상호 배타적 집합의 표현 팀끼리 합쳐지는 상황. 어떤 팀(팀 1)이 다른 팀(팀 2) 밑으로 들어가는 상황. 두 팀원들의 팀 ID를 같게 만들어야 함. 보통은 유저 배열을 모두 돌면서 그 유저가 팀1 소속이면 팀 ID를 팀 2로 만들어주는 방법을 생각했을 것이다. 그러나 모든 유저 배열을 순회하는 것은 비효율 적이다. 이럴 경우 Disjoint Set을 사용하면 좋다. 우선 모든 유저의 팀 ID를 자신의 인덱스로 초기화한다. 어떤 유저(1) 가 다른 유저(2)의 밑으로 들어가면 유저 1의 팀 ID를 2로 만든다. 유저 1의 인덱스는 여전히 1이다. 팀 ID만 2가 된 것이다. 이 상태에서 유저 2 팀이 유저 4를 팀원으로 가진 유저 3팀의 ..

레드블랙트리 란? 레드블랙트리는 이진 탐색 트리의 노드가 편향적으로 배치되어 트리의 균형이 맞지 않을 수 있다는 단점을 보완한 균형 이진 트리이다. 즉 이진 탐색 트리에 데이터를 삽입하고 균형을 맞추는 알고리즘 가동시키는 자료구조라고 할 수 있다. 레드블랙트리는 아래와 같은 특성을 가진다. 이러한 특성을 만족하면 자동적으로 균형이 맞춰지게 된다. 노드는 레드 혹은 블랙 루트노드는 블랙 리프노드(NIL)는 블랙 레드노드의 자식은 모두 블랙. 블랙노드만이 레드노드의 부모가 될 수있음. 어떤 노드부터 리프노드에 도달하는 경로는 리프노드를 제외하고 모두 같은 블랙노드 수를 가진다. 이런 특성을 맞추기 위해서는 노드 삽입, 삭제 시 추가적인 알고리즘이 적용되어야 한다. 이 알고리즘을 따라 코드를 구현하는 작업은 ..

디퍼드(Deffered) 렌더링 : 포워드 렌더링. 셰이더에서 계산한 중간 과정 정보를 저장해두고 재사용함. 색상, 노말, 깊이 등 정보를 Render Target에 저장해놓고 최종적으로 FS(Lighting) 적용함. Render Target 은 사실상 텍스쳐와 같다. 화면에 그려질 내용이 텍스쳐에 담기는 것이다. 이 렌더 타겟들을 그룹으로 나누어 묶는다. Renter Target Group으로 만든다. SwapChain 그룹, 글로벌 그룹(포지션, 노말, 컬러) 등.

직교투영 이란 카메라가 물체를 찍을 때 원근법을 무시하고 멀리 있든 가까이 있든 같은 크기로 화면에 출력하도록 하는 방식이다. 일반 물체들을 촬용하는 원근 투영 방법과는 대비되는 방식이다. 이러한 특징때문에 UI 요소들을 촬용하는 용도로 주로 쓰인다. 일반 물체들은 원근투영 카메라로 촬영하고, UI는 직교투영 카메라로 촬영한 뒤, 한 화면에 두 카메라가 촬영한 영상을 합쳐서 출력하게 된다. 그런데 일반 물체와 UI를 어떻게 구분할까? 답은 '레이어' 다. 카메라마다 촬영할 레이어를 지정하고, 물체마다 자신이 어떤 레이어인지 지정해두는 식이다. 카메라에 int32 CullingMask를 지정해서 어떤 레이어를 찍을지 지정한다.

필요성 : 기존의 오일러 회전 방식의 문제점 짐벌락 현상 때문. 여러 회전축의 회전이 결합되면 생기는 문제이다. 설명하자면 어떤 축이 회전함에 따라 다른 축이 변화하게 되는데, 이 때문에 두 축의 방향이 겹치는 순간 하나의 축이 소실되어버리는 현상이 나타난다. 세 개의 축을 회전시킬 때 두 번쨰로 회전시키는 축이 이 문제를 일으킨다. 사원수 : 사원수는 놀랍게도 복소수를 이용해 회전을 한다. 두 복소수를 곱하면 복소수를 극좌표계로 표현했을 때 각도를 더한 벡터가 나온다. 삼차원 벡터 회전 공식 : 벡터 V를 a 축으로 Th 만큼 회전시킨 벡터 V' = v*cosTh + (v . a)*a*(1-cosTh) + (a x v)sinTh 쿼터니언 q는 xi + yj +zk + w의 형태 또는 Vect(x,y,z..

절두체 컬링. FRUSTUM, 절두체란 피라미드 모양에서 머리가 잘린 모양. 카메라가 보는 영역이 절두체의 모양이다. 절두체 밖에 있는 물체는 그릴 필요가 없으므로 CPU에서 그리지 않을 물체를 미리 걸러서 GPU에 넘겨주는 것이 FRUSTUM CULLING이다. 그렇다면 어떻게 물체가 절두체 안에 있는지 판별할 수 있을까? 절두체는 여섯 개의 면으로 둘러 싸인 공간이다. 어떤 점이 어떤 평면보다 앞에 있는지, 뒤에 있는지 판별할 수 있다면 절두체의 모든 면에 대해 안에 있는지 확인해서 최종적으로 어떤 점이 절두체 안에 존재하는지 판별할 수 있을 것이다. 그럼 어떻게 어떤 점이 어떤 평면의 앞에 있는지, 뒤에 있는지 판별할 수 있을까? ax+ by +cz +d = 0 는 3D공간에서 평면의 식이다. 즉 ..

Noraml Map을 사용해 각 픽셀마다 다른 Noraml 벡터를 전달해주는 것. Normal Mapping이 없으면 색상이 대체로 밋밋해 보이게 됨. 왜냐하면 하나의 면에 Noraml 벡터가 하나 뿐일 경우 한 면에 대해 한 가지 색상이 계산되어 입혀지기 때문. 그런데 Normal Mapping을 통해 각 픽셀마다 다른 Normal 벡터를 주게되면 각 픽셀마다 다른 색상으로 계산됨. Normal Map이 푸른색을 띄는 이유 : Normal map은 이름처럼 Noraml 벡터들을 모아놓은 정보임. 따라서 Z축 값이 1에 가까운데, 이는 RGB값에서 파란 색에 해당함. 그래서 대체로 푸른색임. 실제 물체의 평면은 여러 방향을 향하는데, Normal Map이 픽셀마다 Z축을 향하는 이유 : 물체가 애니메이션..

Diffuse : 난반사 Ambient : 환경광 Specualr : 정반사광 Normal 벡터 : 어떤 면에 수직인 벡터 빛을 받은 정도에 따라 물체의 색상에 어떤 값을 곱하는 과정. Diffuse 구하기 : 비스듬하게 올 수록 약해짐. 노말 벡터(N)와 빛의 각도(L)의 COS 값을 곱함. N , -L내적을 해주면 됨. Ambient : 기초생활광. 빛이 벽에 가로막혔더라도 기본적으로 주는 광량. Specular : 벽에 튕긴 빛에 의해 받는 광량. 빛이 튕겨나온 방향 벡터 R, 카메라와 빛이 튕긴 지점의 방향 벡터 C 사이의 각도의 COS 값에 따라 광량 결정. (마치 눈망울의 빛나는 하얀 점 같은 부분.) 참고로 R은 빛 벡터 L과 노말벡터 N의 내적을 L에서 두 번 빼줌.

좌표계 변환 행렬이란 어떤 좌표계의 벡터를 다른 좌표계의 벡터로 변환하는 행렬이다. 예를 들어 설명하겠다. 아래 그림을 보자. A가 원점인 좌표계를 A좌표계, B가 원점인 좌표계를 B좌표계 라고 하자. 그리고 A좌표계의 수직 단위벡터를 u1, 수평 단위벡터를 v1, B좌표계의 수직 단위벡터를 u2, 수평 단위벡터를 v2라고 한다. 이때 A좌표계의 위치벡터 AM(x, y)을 B좌표계의 위치벡터 BM(X, Y)로 변환하려고 한다. AM은 어떤 값 x1과 y1을 각각 u1과 v1에 곱한 AM = x1*u1 + y1*v1 로 표현할 수 있을 것이다. 마찬가지로 BM = x2*u2 + y2*v2로 표현할 수 있다. 그런데 마찬가지로 u1도 어떤 값 ux와 uy를 u2, v2에 곱한 u1 = ux*u2 + uy*v..