이득우의 게임 수학 현재 절두체 컬링 구현에서는 카메라를 좌우로 많이 움직일 경우, 공포 영화의 한 장면처럼 아래와 같이 심각한 깨짐 현상이 발생한다. 문제의 원인을 알아보기 위해 아래와 같이, 삼각형 CBA 중 점 C가 카메라의 뒤쪽에 있는 경우를 가정해본다. 이를 투영하면 카메라 뒤쪽에 위치한 점 C는 원점을 중심으로 뒤집혀 투영 평면에 투영된다. 따라서 위 실행 화면처럼 엉뚱한 삼각형이 그려져 문제가 발생하는 것이다. 따라서 평면이 올바르게 보이려면 카메마 뒤쪽에 있는 점을 파악해 점이 거꾸로 투영되지 않도록 해야 한다. 원근 투영 행렬에 곱해 생성된 클립 좌표계의 w값은 뷰 공간에서의 깊이를 의미한다. 0 < w 카메라 앞에 점이 있다. w < 0 카메라 뒤에 점이 있다. w = 0 카메라 초점에..

Level 0. 문자 개수 세기 #include #include using namespace std; vector solution(string my_string) { vector answer(52, 0); for (char c : my_string) ++answer[c - (isupper(c) ? 'A' : 'G')]; return answer; }

이득우의 게임 수학 구 영역 대신 박스 영역을 사용하면 좀 더 정교한 절두체 컬링을 수행할 수 있다. 메시 데이터로부터 박스 영역을 생성하는 방법은 간단하다. 메시를 구성하는 점을 순회하면서 각 차원의 최댓값과 최솟값을 갱신해주면 된다. n개의 정점이 있을 때, O(n) 시간에 구할 수 있다. 이렇게 생성된 박스 영역을 기저 축이 정렬되어 있다는 의미에서 AABB 바운딩 볼륨이라고 한다. 구나 AABB 말고도 성능과 효율의 Trade-off에 따라 다양한 바운딩 볼륨이 존재한다. 책의 예제인 CK소프트렌더러에 정의된 AABB는 다음과 같다. // 책의 예제인 CK소프트렌더러에 정의된 AABB struct Box { public: FORCEINLINE constexpr Box() = default; FOR..

Level 2. 연속된 부분 수열의 합 가장 길이가 짧은 수열 중 가장 앞 쪽에 위치한 수열을 찾는 데에는 map 자료형을 사용했다. l - r로 계산한 수열의 길이를 map에 넣어 map의 첫 번째에 가장 길이가 짤은 수열들이 위치하게 하고, map의 각 원소는 vector를 원소로 갖는 set을 저장해 가장 앞 쪽에 위치한 원소가 첫 번째에 오도록 한다. vector는 비교 연산을 지원한다. 첫 번째 시도에서는 이중 for문을 통해 모든 경우의 수를 확인해서 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include using namespace std; vector solution(vector sequence, int k) { map..

이득우의 게임 수학 카메라 설정 값을 이용한 방법과 원근 투영 행렬을 이용한 방법에서 절두체 컬링이 잘 동작하는 것은 확인했지만, 가장자리에서 오브젝트가 갑자기 사라지거나 불쑥 생겨나는 현상이 있었다. 오브젝트의 위치를 이용해 절두체 내외부 판정을 하기 때문이다. 게임 오브젝트의 좌표가 절두체 외부에 있더라도, 메시가 차지하는 영역이 절두체와 겹친다면 그려줘야 한다. 게임 엔진은 메시가 차지하는 영역을 효과적으로 관리하기 위해 구(Sphere)나 박스(Box) 같은 원시 도형(Primitive shape)을 사용하는데, 이러한 원시 도형으로 설정한 공간 데이터를 바운딩 볼륨이라고 한다. 바운딩 볼륨에서 손쉽게 사용되는 원시 도형은 구다. 반지름을 통해 두 영역이 서로 겹치는지, 떨여져 있는지 가장 쉽게 ..

Level 0. 문자열 잘라서 정렬하기 굉장히 기초적인 파싱 문제인데 이 문제 때문에 하루를 꼬박 썼다.. 분명 알고리즘엔 문제가 없는데 도대체 왜 안 될까 생각하며 다른 파싱 기법도 써봤는데 계속 안 됐다. 결국은 set이 문제였다는 걸 깨달았다.. set이 중복을 허용하지 않는다는 걸 깜빡하고 있었다.. #include #include #include using namespace std; vector solution(string myString) { multiset mset; size_t last = 0; do { size_t first = myString.find_first_not_of('x', last); last = myString.find('x', first); if (first != stri..