목록전체 글 (135)
센로그
정렬 문제의 계산 복잡도는 O(n lg n)이라는 걸 7장에서 증명했었다. 이번에는 검색 문제에 대해서 알아보자! ◆ 키를 비교함으로만 검색을 수행하는 경우의 하한 검색 문제란, n개의 키를 가진 배열 S와 어떤 키 x가 주어졌을 때, x = S[i]가 되는 인덱스 i를 찾는 것. 만약 x가 배열 S에 없을 때는 오류(F)로 처리한다. 이분 검색의 경우, 시간복잡도가 W(n) = floor(lg n) + 1이 되는데, (floor은 바닥 함수를 의미함) 정렬되어있을 때 키를 비교함으로만 검색을 수행하는 경우 이분 검색보다 더 좋은 알고리즘은 없다! 이진 검색과 순차 검색의 결정 트리를 비교하면서 이를 살펴보자. ■ 이진 검색의 결정 트리. 큰 마디(내부마디) – 키와 각 아이템을 비교하는 마디 작은마디(..
◆ Motion Capture란? Motion Capture는 물체나 사람들의 움직임을 기록하는 것을 의미함. 초당 몇번씩 움직임을 샘플링해서, 디지털 데이터로 바꾼다. 이 기록 데이터는 2D 또는 3D 캐릭터 애니메이션을 만드는 데 쓰임! 만약 얼굴이나 손가락, 또는 미묘한 표정이 포함되면 performance capture라고도 불림. (구분하는 이유는, 얘네는 캡쳐하기 까다롭기 때문. 세밀하고 정교한 캡쳐가 필요함.) 보다 진짜같고 자연스러운 애니메이션을 만드는 것을 목표로 Motion Capture을 사용한다. ◆ Character Animation을 만드는 몇가지 방법들 캐릭터 애니메이션을 생성하는 방법들로는 몇가지가 있다. key frame animation procedural animatio..
◆ Skeleton bone들이 개별적으로 움직이는 걸 관절체(articulated body)라고 함. 관절체를 중심으로 움직이는 구조를 skeleton이라고 함. 캐릭터에 애니메이션을 적용하기 위해서, 보통 skeleton 구조를 사용한다. (skeletal animation) mesh가 skeleton 뼈대를 기준으로, 뼈대와 '함께' 움직이도록 구현하는 것임. ■ Rigging (a)의 경우 default pose의 mesh이고, (b)는 3ds Max에서 제공하는, biped라고 하는 기본 skeleton이다. 이 둘이 안 맞으니까, 잘 조정해서 skeleton과 mesh를 맞춰줘야 할 것이다! 이 과정을 리깅(Rigging)이라고 함. (c) skeleton이 너무 복잡하면 수정을 통해 조정해준..
◆ Bumpy surface 벽돌 벽이나, 포장 도로는 우둘투둘한 표면(Bumpy surface)임. == 우둘투둘한 곳에 vertex가 존재한다는 의미. 당연히 전부 고해상도로 렌더링하면, 현실과 비슷해 보일것임 ㅇㅇ 그러나, 너무 비쌈. 렌더링을 위해, data bus를 통해 CPU => GPU로 데이터 전송을 하고, GPU 파이프라인 내에서 처리를 하게 됨. 이때 vertex 개수가 많을수록 한번에 넘어가야 하는 데이터 개수와, Gpu내에서 처리해야 하는 데이터 양이 많아짐 => 우둘투둘한 표면에 대한 고해상도 폴리곤 메쉬를 처리하기 어려워짐!! 더보기 ※ GPU에 올려놓고 연산 처리하는 과정 : 사실 이 과정은 GPU 성능에 따라 빠르게 할라면 빠르게 할 수 있으니까 괜찮다 치자. 반면 CPU =..
◆ 계산 복잡도 문제가 갖고있는 본연의 계산량. 최소한 얼마나 많은 계산을 해야 그 문제가 풀리는지 문제풀이 접근하는 2가지 방법 (1) 문제를 푸는 더 효율적인 알고리즘을 개발 (2) 더 효율적인 알고리즘 개발이 불가능함을 증명 (예) 정렬문제인 경우 Θ(n log n) 보다 좋은 알고리즘은 불가능함이 입증 되었음. 일반적으로 “계산 복잡도 분석”이란 “문제의 분석”을 지칭 (not "알고리즘의 분석") 어떤 문제에 대해서 그 문제를 풀 수 있는 모든 알고리즘의 효율의 하한(lower-bound)을 결정한다. (최소한 이것보다는 오래걸리거나 비슷하게 걸린다.) ex) 예를들어 행렬 곱셈 문제를 보자. - 알고리즘의 분석 ✓ 일반알고리즘: Θ(n³) ✓ Strassen의 알고리즘: Θ(n^2.81) ✓ ..
대충 잘~ 그럴듯하게 IK를 푸는 법에 관한 이야기. 뉴턴 방법은 느리고 풀기 어려우나, 정확성을 요구하는 로보틱스 분야에서 많이 사용한다. FABRIK과 같은 Heuristic Algorithm은 실시간 속도가 중요하고 그럴듯하게 보여야 하는 게임 분야에서 많이 사용한다. 다음의 휴리스틱 IK 알고리즘들을 살펴볼 것임 CCD Triangulation IK SIK FABRIK FABRIK 확장 ◆ Cyclic Coordinate Descent (CCD) Inward: end effector ~> root joint까지 joint 단위로 시행하며, 임계점까지 반복. 각 step마다 end effector가 target position에 최대한 가깝게 하는 방향으로 각 joint를 돌림. CCD는 휴리스틱 ..