Typing diary

다익스트라 DP에 기반한 최단 경로 탐색 알고리즘 알고리즘 수행 결과로 최단 경로트리를 반환한다. 아이디어 힙 자료구조를 이용하여 출발 노드에서 부터 해당 노드까지 비용이 적은 순으로 경로를 탐색한다. 다음과 같은 그래프가 있다고 하자. 다익스트라 알고리즘으로 해당 그래프를 탐색하게 되면 출발 노드부터 해당 노드까지 비용이 적은순 (1 → 4 → 2 → 5 → 3 → 6)으로 탐색을 하게 된다. 해당 과정을 구현하기 위해선 현재 탐색 가능한 노드 중 비용이 가장 적은 노드가 무엇인지 알아야 한다. (이때, 현재 탐색 가능한 노드란, 방문 했던 노드와 인접한 노드를 뜻한다.) 이를 위해 힙 자료구조를 사용하게 된다. . 이게 무슨 소리냐... 1번 노드를 시작 노드로, 6번 노드를 도착 노드로 정하자. 1..

각각의 픽셀에 대응하는 광선의 경로를 역추적 하여 렌더링하는 기법이다.​실제 사람의 눈으로 물체를 인식하는 방법과 유사하기 때문에 사실적인 렌더링이 가능하지만 연산량이 매우 많다.때문에 실시간 렌더링이 아닌 영화 CG같은 곳에 많이 쓰였지만, 엔비디아의 RTX 그래픽 카드가 RT코어와 머신러닝을 이용한 최적화를 통해 실시간 레이트레이싱을 지원하면서 게임에도 적용할 수 있게 되었다.​다음 그림 같이 카메라로 부터 광선을 발사하여 광선이 물체와 부딪히면 광선과 대응하는 픽셀에 RGB값을 변경하게 된다.빛을 광원이 아닌 카메라에서 부터 역추적 하는 이유는 광원에서 나온 빛 중 일부만 카메라에 비치게 되는데 카메라에 비치지 않은 빛은 렌더링 결과에 영향을 미치지 못한다. 때문에 불필요한 연산을 줄이기 위해 카메..

후면 추리기(Backface Culling) 컴퓨터 그래픽스에서 카메라의 반대 방향을 보고 있는 폴리곤을 판별해 렌더링에서 제외하는 것이다. 불필요한 연산을 줄여 최적화에 도움이 되고 반투명 물체를 구현하는데 필요하다. ​ CW(Clock wise), CCW(count clock wise) 폴리곤 정점의 배열이 시계방향인지, 반시계방향인지를 판단하여 면이 앞을 보고 있는지, 뒤를 보고 있는지 판단한다. ​ ​ ​ 카메라 위치를 c, 폴리곤 정점의 위치를 각각 p0,p1,p2라고 하자 ​ 정점 하나를 기준으로 잡고 나머지 정점을 향하는 벡터 v0,v1을 다음과 같이 구할 수 있다. ​ 두 벡터를 외적하면 폴리곤의 법선벡터인 n을 구할 수 있다. ​ 카메라에서 폴리곤의 기준점을 향하는 벡터 r을 다음과 같이..

2020. 12. 7 선형대수학에서, 행렬식(行列式, 영어: determinant 디터미넌트[*])은 정사각 행렬에 스칼라를 대응시키는 함수의 하나이다.(출처: 위키백과) 라고 한다. 정방행렬 A에 대한 행렬식 det(A)는 스칼라 값이라는 소리이다. ​ 이 행렬식이라는 스칼라 값이 무엇을 의미하는지 살펴보자. ​ 1) 행렬식의 의미 기하학적으론 선형변환에 의한 면적의 증가량을 의미한다. 즉 행렬A가 행렬B에 의해 선형변환 되었을 때, 행렬 BA의 열벡터 공간에서의 면적은 A의 열벡터 공간에서의 면적을 det(B)배 한것과 같다. ​ 행력식이 0이라는 의미는 선형변환이 한 차원을 짓뭉갠다는 것을 의미한다. 이는 곧 행렬의 열벡터가 선형종속라는 것과 같다. ​ ​ 행렬식은 판별식이라고도 하는데 행렬A의 행..