센로그

◆ 계산 복잡도문제가 갖고있는 본연의 계산량. 최소한 얼마나 많은 계산을 해야 그 문제가 풀리는지문제풀이 접근하는 2가지 방법(1) 문제를 푸는 더 효율적인 알고리즘을 개발 (2) 더 효율적인 알고리즘 개발이 불가능함을 증명 (예) 정렬문제인 경우 Θ(n log n) 보다 좋은 알고리즘은 불가능함이 입증 되었음. 일반적으로  “계산 복잡도 분석”이란  “문제의  분석”을  지칭 (not "알고리즘의 분석")어떤  문제에  대해서  그  문제를  풀  수  있는  모든  알고리즘의  효율의  하한(lower-bound)을  결정한다.(최소한 이것보다는 오래걸리거나 비슷하게 걸린다.) ex) 예를들어 행렬 곱셈 문제를 보자.- 알고리즘의 분석✓ 일반알고리즘: Θ(n³)✓ Strassen의 알고리즘: Θ(n^..

대충 잘~ 그럴듯하게 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는 휴리스틱 ..

◆ Quasi-Newton Method Quasi-Newton method는 Hessian을 정확히 구하는 것이 아닌, Hessian의 근사를 구하는 방법이다. 2차 미분을 사용하는 Newton method의 경우 종종 수렴이 매우 빠르게 되지만, Hessian의 역함수를 구해야 하므로 큰 계산비용이 요구된다. 따라서, 많은 사람들이 Quasi-Newton Method를 선호한다. 초기 추측을 정하고, 그 지점에서의 gradient(1차 미분)을 구한다. gradient의 변화량을 통해 Hessian을 근사한다. 근사된 Hessian을 이용해 해를 업데이트한다. 종료 조건에 도달할 때까지 반복한다. ◆ Quasi-Newton VS Newton method - 계산 비용 ..

◆ Newton Method for IK Newton method는 IK 문제와 같은 비선형 방정식을 풀기위해 (자코비안과는 다르게) 반복적으로 접근하는 방법이다. root finding optimization 단변수 (uni-variate) 다변수 (multi-variate) ㆍ문제 정의 : IK 문제는 joint angle 등의 변수를 모르는 비선형 연립 방정식의 형태이다. 우리는 end effector가 최대한 target position에 가까이 가도록 하는 연립방정식의 해를 구해야 한다! ㆍ뉴턴 방법 특징 : Newton method는 비선형적인 문제를 선형적으로 접근한다.(Problem linearization) 매 st..

화면상 오브젝트 조작에 관한 이야기 ◆ Object Picking 우리는 손가락 터치이나, 마우스 클릭을 통해 해당 물체를 선택하기를 원함. 클릭된 위치의 좌표 (x_s, y_s)를 반환하고, 이로부터 물체를 선택해서 그 물체에 대한 조작을 할 수 있도록 ㅇㅇ 이를 위한 기본적인 아이디어는, Ray를 쏘자! 가 된다. 스크린의 점으로부터 z축에 ray를 쏘면, 충돌하는 물체들이 있을 수 있음 그중 가장 처음으로 충돌하는 물체를 선택하자~ 하는 아이디어 근데, 그럼 어디서 찾아줘야 하나? screen space에서 찾아주면 되나? ㄴㄴ. 결국 screen space는 렌더링 끝낸 결과물이라, 어떤 오브젝트와 충돌하는지 판단하고 처리를 해주기가 힘듦 따라서 screen space ray를 object spa..

◆ Euler Transform euler angle을 사용해 변환하는 과정 더보기 ※ 이거~ x,y,z축(주축)을 기준으로 회전 가능 => 임의의 축으로 회전하려면, 주축으로 맞춰서 회전하고 다시 원래대로 돌려줬었다 근데 이러면 불편하기도 하고, 문제도 발생함 회전할 때의 order(순서)가 굉장히 중요하다! 순서가 바뀌면 결과가 완전히 달라짐 ◆ Keyframe Animation in 2D keyframe을 사용하여 제작하는 Animation 전통적으로 애니메이션 제작에서는, 시니어 아티스트가 키 프레임을 그리고 주니어 아티스트가 이 사이를 채우는 방식. 근데 이런 방식은 너무 비용이 많이 든다! => 컴퓨터가 자동으로 채워주는 알고리즘이 등장 keyframe들만 정의해주고, keyframe 사이의 ..