상후니의 개발 블로그

* 정렬 알고리즘 ( Sort Algorithm ) 정렬 알고리즘은 굉장히 다양하고 상황 마다 효율적인 알고리즘이 다를 수 있다. 우선 간단한 것부터 개념 정리를 할 것이고 정렬에 관한 내용을 갱신해가며 업데이트 할 예정이다. ( 아래에 구현된 코드는 검증되지 않은 코드이다. ) 알고리즘을 만족하지 못하는 케이스가 있을 수 있다. *선택 정렬 ( Selection Sort ) / O( N2 ) => 처음부터 끝까지 탐색 후 데이터를 첫 순서 놓기 -> 2번째 idx 부터 끝까지 찾고 옮기기... { 1, 5, 10, 7, 2 } { 1, 5, 10, 7, 2 } { 1, 2, 10, 7, 5 } { 1, 2, 5, 7, 10 } { 1, 2, 5, 7, 10 } void SelectSort(std::ve..

* GJK Alogrithm SAT ( 분리축 이론 ) 과 더불어 다각형 충돌 처리에 쓰이는 알고리즘이다. SAT 보다 상대적으로 비용이 저렴하고 빠르다. 우선 대략적인 개념을 알아보고 어떤 식으로 구현할지 알아보자. * Minkowski Sum => 두 다각형을 그리는 정점들의 합한 벡터들의 모양을 그린다. ( 원점 기준 표현 ) * Minkowski Difference => 두 다각형을 그리는 정점들의 차인 벡터들의 모양을 그린다. ( 원점 기준 표현 ) => 원점이 포함되어진다면 두 물체는 overlap 되어진 상황. 즉, 정점들의 벡터 차를 원점 기준으로 그렸을 때, 도형이 원점을 포함한다면 겹쳐져있다는 개념을 활용해 두 물체의 겹쳐짐 여부를 판별 가능. 하지만, 원점 기준으로 물체를 그리는 연산..

*상호 배타적 집합 (Disjoint Set) => 유니온-파인드 Union-Find (합치기-찾기) => 서로 다른 원소들이 같은 집합에 속해있는지, 속해있지 않은지 판별 가능. => 대표적으로 크루스칼 알고리즘 MST 를 찾는데 활용. ( 싸이클 방지 ) int Find(int u) { if (u == _parent[u]) return u; return Find(_parent[u]); } void Union(int u, int v) { u = Find(u); v = Find(v); if (u == v) return; _parent[u] = v; } *문제점 1. Find 함수는 Union 연산 시, 덧붙여지는 각 원소들이 새로운 parent 를 가리키도록 갱신해야하기 때문에 O(n) 시간 복잡도를 가..

Frustum Culling ( 절두체 선별 ) 에 앞서서 해당 범위에 오브젝트들이 포함되어있는지 어떻게 판별할까 ?? 그 방법에 대해서 몇 가지 알아보고 넘어가자. *AABB ( Axis - Aligned Bounding Box ) => 축 정렬 경계 상자 라고 한다. => 큰 특징은 사각 Box 영역이 좌표축에 평행. AABB 를 적용할 오브젝트의 최솟점 / 최댓점 을 구해 정의 가능하다. 최솟점(Vmin) / 최댓점(Vmax) 을 이용해서 AABB 의 중점(c) 과 거리(e) 를 구할 수 있다. c = 0.5 ( Vmin - Vmax ) e = 0.5 ( Vmax - Vmin ) *AABB 와 회전의 문제 => 좌표계 축을 기준으로 물체의 최솟점, 최댓점을 이용해 AABB 를 적용하는데, 월드 공간..

*Clip Space => 대표적인 투영 방법 원근 투영 / 직교 투영 *직교 투영 ( Orthogonal Projection ) => 평면상 수직으로 투영된다. => 원근감이 존재하지 않는다. => UI ( User Interface ) 를 랜더링할 때 많이 쓰임. @viewport width : w @viewport height : h @near plane : n @far plane : f * 직교 투영 행렬 => 직교 투영 행렬은 원근 투영 행렬보다 비교적 어렵지 않게 구할 수 있다. 몇 가지만 짚고 넘어가자. * 왜 2 / w , 2 / h 인가 ?? => 투영좌표계에선 x, y 가 (-1, 1) 이기 때문. 가운데 ( 0,0 ) 에서, x 기준 : 1,4 사분면 / 2,3 사분면 y 기준 : 1..

*TEXT 매크로 => 언리얼에서는 '문자열 리터럴' 을 TEXT 매크로 안에 넣어서 TEXT("Hello World") 로 넘겨주는 것이 좋음. https://docs.microsoft.com/ko-kr/cpp/c-language/c-string-literals?view=msvc-170 ( 문자열 리터럴 ) => 어떤 플랫폼에서든 동작 가능하도록 언리얼에서 인코딩. ( 크로스 플랫폼 환경 ) *FName => 콘텐츠 브라우저에서 새 애셋 이름을 만들 때, => 다이나믹 머터리얼 인스턴스의 파라미터를 변경할 때, => Skeletal Mesh Bone 에 접근할 때, => 문자열 사용에 있어서 초경량 시스템 제공 -> 주어진 문자열이 사용된다 해도 데이터 테이블에 한번만 저장됨. => 대소문자 구분 X,..

* 투영행렬 ( Perspective Matrix ) 결과 g(z) = A + B / z g(n) = 0 g(f) = 1 을 이용해서 A,B 를 구할 수 있었다. 하지만, 항상 또 다른 문제가 발생하기 마련이다. 우리가 near, far 에 따라서 z 값을 [ 0~1 ] 사이의 값으로 맞추기 위해 만든 g(z) 함수 와 z 값 사이에 문제가 발생한다. *Z-Fighting ( 정밀도 문제 ) z ( 깊이 ) 의 낮은 정밀도로 인해서 물체가 겹쳐보이는 현상이 발생. 무슨말인가 ?? 위에서 우리가 구한 g(z) 함수는 '비선형' 함수 이다. 즉, 일차방정식처럼 일정한 방향으로 늘어나지 않고 이차함수처럼 곡선이다. 그래프를 참고하면 'near' 값이 엄청난 영향을 끼친다 는 사실을 알 수 있다. near 의 ..

*하나의 점이 화면에 보여지기까지의 과정 *LocalSpace => 어떤 점들을 원점을 기준으로 어디에 위치해있는지 표현하는 공간. => 점이 시작되는 좌표가 있는 공간. 즉, 초기 물체가 그려지는 공간. *WorldSpace => Local space 에서 그려진 물체를 크기,회전,위치를 가진 정보를 더해 Worldspace 공간으로 넘긴다. => 물체가 크기, 회전, 위치를 가지는 공간. 흔히 ' SRT ' 라고 부른다. => 물체마다 독립적인 World 행렬 존재 *Translation 행렬 => 이동행렬의 이동 값들은 마지막 4x4 마지막 줄에 정의되어진다. *Scale 행렬 => 벡터의 스케일을 키워주는 행렬 => 위치를 원점에 놓고 계산해야 물체 자체만을 키울 수 있음. => 그렇지 않으면 커..

*3D 그래픽스를 처음 접했을 때의 궁금증 *행렬을 사용하는 목적 => 3차원을 표현하기에 적합하다. => 선형변환을 적용할 수 있다. *선형변환이란 ?? 간단하게 설명하자면, 어떤 값 : A 라고 할때, A + ( 어떤 연산 ) = B 즉, A 에 어떤 연산 을 적용했을 때, 모든 계산된 값은 B 이어야 한다. 이 때, 어떤 연산을 '선형' 이라고 한다. 또, 이 과정을 '선형변환' 이라고 한다. 벡터는 크기를 늘이고 줄일 수 있다. 또한, 방향도 가지고 있다. 어떤 벡터를 어떤 점에 적용했을 때, 이동한 점을 알 수 있고 반대로 적용한 벡터를 알고 있다면, 다시 원래대로 되돌아올 수 있다. 즉, 벡터는 명백히 '선형' 이다. 따라서, 벡터는 선형이고 어떤 벡터들을 어떤 점이나 다른 벡터에 적용하는 것..

*링킹 ( Linking ) *Linker 는 왜 필요한 것일까 ?? => 모든 obj 파일들을 하나로 합치는 역할. => 컴파일 단계에서, TU 는 독립적으로 실행되기 때문에 합쳐졌을 때의 최종적인 위치를 모른다. 모든 obj 파일을 하나로 합치는 과정과 동시에 심볼들의 정확한 위치를 확정시키는 역할을 링킹에서 수행한다. 간단히 말해서, printf("Hello World"); 에서 printf 는 stdio.h 안에 printf 가 구현되어있다. 즉, 컴파일 단계까지는 printf 의 구현부가 어디있는지 알 수 없다. printf 를 호출한 코드 ( obj ), printf 가 정의된 코드 ( library ) 이 둘을 합치는 과정이 필요. 또한, 데이터 영역의 전역변수도 마찬가지이다. 현재 각 ob..