Game Engineering 1

LeemHyungJun·2023년 6월 1일

Game Engineering

목록 보기

7/8

Introduction to Inverse Kinematics

1. Introduction

IK를 푸는 가장 일반적인 방법이 Jacobian 이다.

1-1. Jacobian

원래 matrix의 변수를 한번씩 편미분 하여 구성한 함수
ex) $f= \begin{bmatrix} x^2y\\ 5x+sin\ y\\ \end{bmatrix}$

J_f = \begin{bmatrix} 2xy & x^2\\ 5 & cos\ y \\ \end{bmatrix}

IK를 풀기 위해 쓰는 식 : $F = J\theta$ -> $J^{-1}F=\theta$
문제점
- high computational cost : 계산이 복잡하다
- singularity problems : 해를 구하지 못하는 경우가 있다
해결책
- inverse Jacobian 대신 feedback loop를 통한 방법
  - 성능 향상, singularity 문제 발생하지 않음
- Newton Method
  - itearation으로 local minimum 으로 다가가는 방법
  - optimization problem
- FABRIK

1-2. The Articulated Body Model

character is modeled as a chain composed of rigid links
DoF (Degrees of Freedom)
- 1 DoF
  - suture joint model : 갈라짐
  - hinge joint model
- 2 DoF
  - gliding joint model : 상하좌우 움직일 수 있는 면
  - saddle joint model
  - pivot joint model
- 3 DoF
  - ball and socket joint model
Motion
- FK : 하나의 해를 가지고 퀄리티가 좋지만 만들기 힘들다
- IK : 해가 하나가 아닐 수 있고, 없는 경우도 있다.

2. Geometric Algebra

2-1. Bivector

2차원의 object
magnitude of bivector = area
- bivector에 scalar배 하면 크기가 scalar배 된다.
두개의 bivector 더하면 새로운 방향의 bivector가 된다.

2-2. Inner product

denoted : $<u,v>$
내적이랑 계산이 같음 : $||u||*||v||*cos\theta$
결과가 scalar

2-3. Outer product

wedge product, exterior product 라고 부르기도 한다.
denoted : $u \wedge v$
특징
- Inner product의 문제점 해결
  - 기존 vector의 성질(정보)를 잃어버린다.
- Outer product는 기존 벡터의 방향을 유지하면서 계산한다.
  - $u \wedge v = -v \wedge u$
  - 계산 결과 앞에 있는 벡터에서 시작해서 끝나는 벡터 쪽으로 향하는 방향을 가진다.
- 평행한 벡터의 outer product의 결과는 0이다.
  -> 두 벡터의 사잇각을 sin으로 나타낼 수 있다.
example
- $v=(a,b), w = (c,d)$ , $e_1=(1,0), e_2=(0,1)$
- area = $|det[v,w]| = |ad-bc|$
- $v\wedge w = (ae_1+be_2)\wedge(ce_1+de_2)\\=(ad-bc)e1\wedge e2$
  -> e1, e2의 각도는 90도 이므로 결과값 1
  -> $e1\wedge e1=0$ -> ( $sin\theta = 0)$ 이기 때문에
$u\wedge v$
- 3차원 공간의 기저
- $\wedge^2(R^3)$
$u\wedge v \wedge w$
- 1차원 공간의 기저벡터
- $\wedge^3(R^3)$
Outer Product...
- outer product 또한 inner product의 문제와 같이 계산 전 벡터의 정보가 사라지는 문제가 존재한다.
- ex) v와 u의 사잇각이 세타이고, u와 w의 사잇각이 90+세타인 경우 둘의 outer product의 결과값이 같다.

2-4. Inner product + Outer product = Geometric Product

Geometric product : $uv = u \cdot v + u\wedge v$
inner product의 결과는 scalar, outer product의 결과는 bivector
- 서로 다른 타입의 결과를 통합해야함
  -> complex number를 통해 가능하게 함
연산 예시
- $uw = u\cdot w + u\wedge w$
- $wu = u\cdot w - u\wedge w$
- 기저 벡터 중 두개를 선택한 경우
  - $x\wedge y = xy$ -> ( $x\cdot y =0)$ 이므로

2D에서 GA의 기하학적 의미

$V = a+b\hat{x}+c\hat{y}+d\hat{x}\hat{y}$ -> 벡터 두개와 bivector 한개
회전 방향
- $\vec{u}i$ -> CCW 회전(positive 회전)
- $i\vec{u}$ -> CW 회전(negative 회전)
Pseudo Scalar example
- Pseudo scalar : $i=\hat{x}\hat{y}$
- $\vec{u}i=2\hat{x}\hat{x}\hat{y} + \hat{y}\hat{x}\hat{y}=2\hat{y}-\hat{x}$ -> $\hat{x}\hat{y} = -\hat{y}\hat{x}$ 이기 때문에
Complex Number를 이용한 Rotation
- CASE 1) 세타를 알고 있는 경우
  - $a+bi$ -> Cartesian form
  - $r(cos\theta + isin\theta)$ -> Polar form
  - $cos\theta + isin\theta = e^{i\theta}$ -> Euler's formula
- CASE 2) 이동한 만큼을 알고 있는 경우
  - $\vec{u}\vec{v} = ||\vec{u}||*||\vec{v}||cos\theta+\vec{u}||*||\vec{v}||sin\theta i = ||\vec{u}||*||\vec{v}||e^{i\theta}$
  - u와 v가 normalized 된 경우 $\vec{u}\vec{v}=e^{i\theta}$
  - Conjugate : i 의 부호를 바꾸기 -> 회전을 의미함
    - $\vec{u}\vec{v} = \vec{u}\cdot\vec{v}+\vec{u}\wedge\vec{v}$ -> $(\vec{u}\vec{v})^*=\vec{u}\cdot\vec{v}-\vec{u}\wedge{v}$

3D에서 GA의 기하학적 의미

$V = a+b\hat{x}+c\hat{y}+d\hat{z}+e\hat{x}\hat{y}+f\hat{y}\hat{z}+g\hat{x}\hat{z}+h\hat{x}\hat{y}\hat{z}$
Pseudo scalar example
- $\hat{x}\hat{y}\hat{z} = i$
- $\vec{v}i = \vec{U}$
- $-\vec{v} = \vec{U}i$
V를 간단히 하면..
- $a+\vec{u}+\vec{v}i+bi$
Outer product & Cross Product
- $\vec{u}=a_1\hat{x}+b_1\hat{y}+c_1\hat{z}$
- $\vec{v}=a_2\hat{x}+b_2\hat{y}+c_2\hat{z}$
  -> $\vec{u}\vec{v} =\vec{u}\cdot\vec{v} +\vec{u}\wedge\vec{v}$
- outer product
  - $\vec{u}\wedge\vec{v}=(a_1b_2-b_1a_2)\hat{x}\hat{y}+(b_1c_2-c_1b_2)\hat{y}\hat{z}+(a_1c_2-c_1a_2)\hat{x}\hat{z}$
  - 각 항들이 Rotor를 의미
- cross product
  - $\vec{u}\times \vec{v}=(a_1b_2-b_1a_2)\hat{z}+(b_1c_2-c_1b_2)\hat{x}+(a_1c_2-c_1a_2)\hat{y}$
  - 각 항들이 vector를 의미
- 결론
  - $\vec{u}\wedge\vec{v}=i\vec{u}\times\vec{v}$
Rotor 구하기
- vector $\vec{v}$ 를 z축 기준으로 90도(CCW) 회전한 결과 : $\vec{v}'$
- $\vec{v}=3\hat{x}+2\hat{y}+\hat{z}$ : 회전 이전의 결과
- $\vec{v}'=3\hat{y}-2\hat{x}+\hat{z}$ : 원하는 결과
- 시도 1 (pseudo scalar이용)
  - 2d rotation with bivector
  - $\vec{v}\hat{x}\hat{y} =(3\hat{x}+2\hat{y}+\hat{z})\hat{x}\hat{y}=3\hat{y}-2\hat{x}+\hat{x}\hat{y}\hat{z}$
    -> 원하는 결과 아님..(trivector 남아있음)
- 시도 2 (conjugate 이용)
  - $\vec{v}\hat{x}\hat{y}=(\hat{x}\hat{y})^*\vec{v}=\hat{y}\hat{x}\hat{v}$
    -> $3\hat{y}-2\hat{x}-\hat{x}\hat{y}\hat{z}$
    -> 원하는 결과 아님..(negative trivector 남아있음)
- 시도 3 (시도1+시도2)
  - $\hat{y}\hat{x}\vec{v}\hat{x}\hat{y}=-3\hat{x}-2\hat{y}+\hat{z}$
    -> 너무 많이 회전함..
- 시도 4 (rotate angle을 절반으로 줄이기)
  - $\hat{x}\hat{y}=e^{i\theta}$
  - $e^{-i\frac{\theta}{2}}\vec{v}e^{i\frac{\theta}{2}}=3\hat{y}-2\hat{x}+\hat{z}=\vec{v}'$
    -> 원하는 결과!
- 결론
  - Rotor : 평면 $\hat{I}$ 에서 $\vec{v}$ 를 $\theta$ 만큼 돌린 결과
  - $e^{\hat{I}\frac{\theta}{2}}$

3. Quaternion

Rotor와 비슷한 컨셉
쿼터니언은 3차원 공간에서만 가능하다! (Rotor는 확장 가능)
Rotor에 비해 편리함.. 단점은 직관적이지 않다는 것
unit vector $u$ 를 세타만큼 회전
- $q = e^{\frac{\theta}{2}(u_xi+u_yj+u_zk)} = cos\frac{\theta}{2}+(u_xi+u_yj+u_zk)sin\frac{\theta}{2}$
- ordinary rotation : $p=(p_x,p_y,p_z)$
  -> $p'=qpq^{-1}$ (Rotor와 유사한 형태..)
빠른 계산을 위해 matrix form을 많이 사용한다.