# 電腦動畫與特效 # Introduction ## 什麼是動畫？ - 讓靜止物移動 - 賦予生命 - 藝術 - 歷史不久 - 發展快速 ### 動畫的歷史 #### 早期動畫裝置 - 視覺暫留 - 18世紀末期 相機出現 - 19世紀初期 第一部使用攝影機所拍攝之動畫 - ... ### Disney - 第一個將聲音加入影片 - 第一個使用故事版(storyboards) - 第一個將寫實風格應用於動畫 - 多層場景 - 場景重複利用 - 景深效果 - 鏡頭縮放效果 - Parrallax - 鏡頭與景物有相對運動時會有遮擋、不同視角的效果 ## 電腦動畫 - 使用電腦演算法、電腦技術製作動畫 - $\rightarrow$ 互動式媒體（Ex. 遊戲、VR...） - 結合真實場景（數位特效） ### 數位製作流程 1. 故事 2. 故事版（Storyboards） - 手稿、漫畫等（分鏡圖）加上聲音、音樂 3. 視覺發展 - 風格 4. 角色設計 5. 場景規劃 6. 建模 7. 動作生成 8. 上色／材質 9. 燈光設計 10. 渲染 - 模型變化繪製 11. 後製 ### 電腦動畫技術 - 關鍵影格 - 骨架動畫 - 動力學模擬 - 行為動畫 #### 關鍵影格（Keyframing） - 指定重要影格 - 資深者繪製 - 資淺者繪製其他影格（插植產生） ##### 控制參數 - 球體落地彈跳運動 - 3D位置 - 朝向 - 壓縮程度 - 角色 - 3D位置、朝向 - 骨架角度 - 臉部表情 - 毛髮、衣物 - 場景 - 攝影機位置、角度 - 燈光位置、角度 - 背景運動 ## 骨架動畫 - 運動學 - 單純描述運動狀態（位置、速度、加速度等資訊） - 不包含受力等外部資訊 ### 正向運動學（Forward Kinematics - F.K.） - 給定角色關節狀態（角度）$\rightarrow$算出位置 - $X=f(\theta)=\begin{bmatrix} l_1cos\theta_1+l_2cos(\theta_1+\theta_2) \\ l_1sin\theta_1+l_2sin(\theta_1+\theta_2) \end{bmatrix}$ ### 逆向運動學（Inverse Kinematics - I.K.） - 給定角色位置$\rightarrow$算出關節角度 - $\theta=f^{-1}(X)=\begin{bmatrix} \frac{-(l_2sin\theta_2)x+(l_1+l_2cos\theta_2)y}{(l_2sin\theta_2)y+(l_1+l_2cos\theta_2)x} \\ cos^{-1}\frac{(x^2+y^2-l_1^2-l_2^2)}{2l_1l_2} \end{bmatrix}$ ## 動作捕捉（Motion Capture） - 動作即時錄製 - 透過感測裝置追蹤被拍攝者的動作 - 紀錄座標／關節角度 - 3D重建模組 ## 動作編輯（Motion Editing） - 特定動作 - 特定演員、動作、形式 - 保留原動作的基礎上做編輯、修改 ### Motion Retargeting - 同動作換到不同人物（Ex.身材比例不同） ### Motion Graph - 將動作（不同狀態）用graph連接 - 動作與動作轉換之間有條件限制 ## 動力學模擬 - 以物理定律為基礎 - 模擬物理現象 - 重力 - 動量 - 碰撞 - 摩擦 - 流體 - 彈性 - 碎形 ### 粒子系統 - 狀態 - 位置 - 速度 - 生命週期 - 顯像性質（Rendering properties） #### 硬質物體 - 鋼體系統 - 碰撞 - 限制 #### 變形物體 - 彈性物體 - FFD - 彈性力學 - 皮膚 - 骨架驅動 #### 布料 - 布料模擬 - 不可延伸性 - 碰撞 偵測、處理 ## Dynamic＋Control ### 肌腱韌帶模擬 - 由肌肉、肌腱、韌帶帶動皮膚 ## 群體／行為動畫 - 定義行為模式 - 呈現群體行為 - 透過電腦產生大量個體行為 ## 深度學習 ## 總結 - Keyframing: interpolating between keyframes - Skeletal animation: human and animals - Kinematics: representing and posing a character - Motion capture - Motion editing - Motion synthesis - Dynamics and simulation: - passive objects - active objects with force/torque control - Behavior animation: group and crowd # ODE_Implicit ## Outline - 常微分方程的穩定度 - 傳遞誤差 - 剛性系統 - 隱性法解微分方程（剛性系統） ## 常微分方程的穩定度 ### 解析解 - 穩定： - Ex. $y'=-y$ - 差距隨時間變小（系統最終趨近於同值（收斂）） - 不穩定： - Ex. $y'=y$ - 差距隨時間變大 - 中性穩定： - Ex. $y'=1/2$ - 差距不隨時間改變 ### 數值解 - 系統發散可能原因： 1. 微分方程本身定義的系統不穩定 2. 系統穩定，但數值方法不對 ### 決定穩定度與精度 - 判斷常微分方程是否穩定：套用$x'=Ax$，其中$A$為常數 - 觀察數值方法解方程的**穩定度**、**精度** #### Ex. Euler's Method - 應用$x'=Ax$： - $x_{n+1}=x_n+hAx_n=(1+Ah)x_n$ - $\rightarrow x_n={(1+Ah)}^nx_0$ - 若$Re(A)$（$A$的實數部）$<0$，則此系統穩定 - 若$|1+Ah|<1$，則數值解穩定 ## 傳遞誤差 - 誤差在遞迴間的增減情況 ### Ex. Euler's method - Global error：propagated error + local error - $e_{n+1}\leq (1+hK)e_n+\frac{h^2}{2}x''(\xi_n)$ - $(1+hK)e_n$：propagated error - $\frac{h^2}{2}x''(\xi_n)$：local error - $h$：time step，$K$：與ODE特性相關 - 截斷錯誤（Truncation error - 忽略$\frac{h^2}{2}x''(\xi_n)$項） - $e_n\leq \frac{h^2}{2}[{(1+hK)}^{n-1}x''(\xi_n)+{(1+hK)}^{n-2}x''(\xi_1)+\cdots+x''(\xi_n)]$ - 若$|1+hK|<1$，則error不會增加 <br> - 推廣至高階微分方程 - $e_{n+1}\leq (I+hJ_f)e_n$+(local error at step $n+1$) - Jacobian of $f$：$J_f(i, j)=\frac{\partial f_i}{\partial x_i}$ - 若$(I+hJ_f)$的全部eigenvalues都小於1，則error不會增加 #### 穩定度分析 - Growth factor（公比：$(1+hK)$、$(I+hJ_f)$） - 數值方法 - Step size （h） - ODE #### Mean Value Theorem - $\frac{f(a)-f(b)}{a-b}=f'(s)$, $s=\frac{a+b}{2}$ ## 剛性方程式 - 以ODE：$x'=-kx$（stable）為例 - $k$：剛性係數（常數） - Ex. Spring-Damper System - Spring force: - 維持位置平衡性 - $F_s=-k_sx$ - Damping force: - 維持速度平衡性 - $F_d=-cv$ - $\rightarrow ma=-cv$ - $\rightarrow \dot{v}=-\frac{c}{m}v$ - $\rightarrow$ 阻尼系統（Damper System） - 補救： - Small step size $\rightarrow$ 沒有效率 - Implicit methods ### Ex. Euler's method - $x_{n+1}=x_n+hf(x_n, t_n)$ $=x_n+h(-kx_n)$ $=(1-hk)x_n$ - 若$|1-hK|<1$，則收斂 $\rightarrow h<\frac{2}{k}$ ## 隱性法／隱性函數（Implicit Method） - 上述的Euler's method 是顯性（explicit） - 根據所知系統狀態及時間算出結果 ### Euler Method - Explicit Euler Method - $x_{n+1}=x_n+hf(x_n, t_n)$ - Implicit (Backward) Euler Method - $x_{n+1}=x_n+hf(x_{n+1}, t_{n+1})$ - Ex. $x'=-kx$ - $x_{n+1}=x_n+h(-kx_{n+1})$ $\rightarrow x_{n+1}=\frac{1}{(1+hK)}x_n$ - $\forall h >0$, 此系統穩定 #### Implicit Euler Method - $x_{n+1}=x_n+hf(x_{n+1}, t_{n+1})$ - $\vec{x} =\begin{bmatrix} x_1 \\ \vdots \\ x_k \end{bmatrix}$ - $\dot{\vec{x}}=\vec{f}(\vec{x})$ - $\vec{f}\in (R^k \rightarrow R^k)$ - 解系統方程式 - Root finding - Approximate $f$ by $\frac{\partial f}{\partial x}$ ##### Ex. solving a $k$th-order ODE $\frac{d^{(k)}y}{dt}=f(y^{(k-1)},y^{(k-2)}, \cdots, y', y, t)$ - 轉換成一階微分方程構成之系統方程式 - $\dot{X}(t)=\vec{f}(X(t))$ - Implicit method <br> $\frac{d}{dt}X(t)=\dot{X}(t)=f(X(t))$ $X_{n+1}=X_n+hf(X_{n+1})$ One-term Tayler series: $f(X_{n+1})\approx f(X_n)+J_f(X_{n+1}-X_n)$ $X_{n+1}=X_n+h(f(X_n)+J_f(X_{n+1}-X_n))$ $X_{n+1}=X_n+{(I-hJ_f)}^{-1}hf(X_n)$ ## Jacobian - $\vec{f}(\vec{x})=\begin{bmatrix} f_1(x_1, x_2, \cdots, x_m) \\ f_2(x_1, x_2, \cdots, x_m) \\ \vdots \\ f_n(x_1, x_2, \cdots, x_m) \end{bmatrix}$ - $\vec{f}\in (R^m \rightarrow R^n)$ - $\frac{d\vec{f}(x)}{dx} \Rightarrow J_f=\begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_m} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_m} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \cdots & \frac{\partial f_n}{\partial x_m} \end{bmatrix}$ - $J_f\in R^{n\times m}$ - $\Delta f=J_f\cdot\Delta x$ - $v_f=J_f\cdot v_x$ # Particles ## 粒子 - 點質量物體，沒有體積，沒有朝向 - 特性 - 質量 - 位置 - 速度 - 外力 - 生命週期 - 顯像性質 - ... - 粒子資訊 - 位置、速度、外力、質量 - 2nd order ODE - $\ddot{x}=\frac{f}{m}$ - 1st order ODEs - $\dot{x}=v$ - $\dot{v}=\frac{f}{m}$ ### 粒子系統 - 多粒子集合 - 描述 - 氣體 - 火焰 - 水／流體 - 變形曲面（Ex. 布料） - 彈性物體 - 群體行為 <br> 1. Particle System $\rightarrow$ Solver（ODE Solver） - 狀態 - 微分 2. Solver $\rightarrow$ Particle System - $\Delta x$、$\Delta v$、$f$（Solver 計算） 3. Paricle System 更新粒子資訊 ## Force ### Spatial Forces - 與該粒子附近區域（local region）的粒子有關 - 空間資料結構能使計算變簡便 ### Unary Forces - 只與該粒子本身有關係 - Ex. - 重力：$f=mg$ - 黏滯力：$f=-k_dv$ - 風場：$f=kv_{wind}$ ### n-ary Forces - 與 n 個粒子有關係 - Ex. - binary forces - spring and damper - $f_a=-k_s(|x_a-x_b|-l_0)\frac{x_a-x_b}{|x_a-x_b|}-k_d(\frac{(v_a-v_b)\cdot()}{|x_a-x_b|})$ #### Spring Force（彈簧力） - 粒子位於比自然長度更**遠**的位置，彈簧力需要將它拉回 - $\Delta l=|\vec{x}_a-\vec{x}_b|-r>0$，$r$：rest length（自然長度） - $\vec{f}_a=-(k\Delta l)\vec{l}, k>0$ - $\vec{l}=\frac{\vec{x}_a-\vec{x}_b}{|\vec{x}_a-\vec{x}_b|}$ - 粒子位於比自然長度更**近**的位置，彈簧力需要將它推出 - $\Delta l=|\vec{x}_a-\vec{x}_b|-r<0$ - $\vec{f}_a=-(k\Delta l)\vec{l}$，$k>0$ - $\rightarrow \vec{f}_a=-k_s(|\vec{x}_a-\vec{x}_b|-r)\vec{l}$，$k_s>0$ $=\vec{f}_a=-k_s(|\vec{x}_a-\vec{x}_b|-r)\frac{\vec{x}_a-\vec{x}_b}{|\vec{x}_a-\vec{x}_b|}$ #### Damper Force（阻尼力） - 速度維持於平衡質的彈簧 - 兩粒子遠離，阻尼力須將其拉回 - $\Delta v=(\vec{v}_a-\vec{v}_b)\cdot\vec{l}>0$ - $\vec{f}_a=-(k\Delta v)\vec{l}$，$k>0$ - 兩粒子接近，阻尼力須將其推開 - $\Delta v=(\vec{v}_a-\vec{v}_b)\cdot\vec{l}<0$ - $\vec{f}_a=-(k\Delta v)\vec{l}$，$k>0$ - $\rightarrow \vec{f}_a=-k_d((\vec{v}_a-\vec{v}_b)\cdot\vec{l})\vec{l}$，$k_d>0$ $=-k_d\frac{(\vec{v}_a-\vec{v}_b)\cdot(\vec{x}_a-\vec{x}_b)}{|\vec{x}_a-\vec{x}_b|}\frac{(\vec{x}_a-\vec{x}_b)}{|\vec{x}_a-\vec{x}_b|}$ ##### Notes - 根據能量守恆定律，若粒子系統僅有質量與彈簧力，當系統受到外力時，即使外力已消失，系統會無限震盪（沒有能量消散） - 阻尼力／黏滯力：抵抗運動 - 外力消失後，讓粒子系統緩緩靜止 - 建議：至少要有一點阻尼力 - 也不要太多，以免粒子系統反應性不佳 ## 碰撞偵測與反應 ### 碰撞偵測 - 判斷粒子與平面是否有發生碰撞 - 靠近平面 - $N\cdot(x-p)<\varepsilon$ - $x$：粒子位置 - $p$：平面上任意點 - $N$：平面法向量，$|N|=1$ - 朝向平面前進 - $N\cdot v<0$ ### 碰撞反應 - 正確：倒退回碰撞發生的時間點 - continuous collision detection - 不太精確，但較簡單的替代方案 - discrete collision detection - 發生穿刺後再做 collision response <br> 假設沒有摩擦力 - 碰撞前 - $v=v_N+v_T$ - 碰撞後 - $v'=-k_rv_N+v_T$ - $k$：coefficient of restitution ## Contact - 碰到平面後沿著平面移動 - 靠近平面 - $|N\cdot (x-p)|<\varepsilon$ - 沿平面移動 - $|N\cdot v|<\varepsilon$ - 受力與平面法線反方向 - $N\cdot f<0$ ### 接觸力 - 外力往平面方向施壓 - $f^c=-(N\cdot f)N$，$N\cdot f<0$ - 外力遠離平面方向 - $f^c=0$，$N\cdot f>0$ - （動）摩擦力 - $f^f=-k_f(-N\cdot f)v_t$，$N\cdot f<0$ # ConstrainedParticles ## Outline - 限制力 - 單一限制條件 - 多重限制條件 - 參數化限制 ## 簡單例子 - 珠子在圓形軌道上運動 - 可以自由移動，但不能離開軌道 ### Penalty Constraints - 運用彈簧力 - 問題：（for $k$） - 太弱會導致珠子容易脫離軌道 - 太強會變成剛性系統 ## Constraint Force（限制力） - 合法加速度？ - 跟速度（$v$）、法向量（$n$）有關 - 計算出 $\hat{f}$ 使 $f+\hat{f}$ 只會產生合法加速度 - $\hat{f}$：抵銷會造成非法加速度的力 ### Single implicit constraint - 限制條件 - $C(x)=|x|-r=0$ - 參數限制 - $x=\begin{bmatrix} rcos\theta \\ rsin\theta \end{bmatrix}$ #### 合法加速度 - 合法位置（$r=1$） - $C(x)=\frac{1}{2}(x\cdot x-1)$ - 合法速度 - $\dot{C}(x)=x\cdot \dot{x}=0$ - 合法加速度 - $\ddot{C}(x)=\dot{x}\cdot \dot{x}+x\cdot \ddot{x}=0$ #### 合法條件 - 起始滿足合法位置、速度 - $C(x)=0$ - $\dot{C}(x)=0$ - 確定加速度合法 - $\ddot{C}(x)=0$ #### 限制力 - 合法加速度條件 - $\ddot{C}(x)=\dot{x}\cdot \dot{x}+x\cdot \ddot{x}=0$ - $\ddot{x}=\frac{f+\hat{f}}{m}$ - $\rightarrow \ddot{C}(x)=\dot{x}\cdot \dot{x}+x\cdot\frac{f+\hat{f}}{m}=0$ - $\rightarrow \hat{f}\cdot x=-f\cdot x-m\dot{x}\cdot\dot{x}$ <br> $\hat{f}\cdot x=-f\cdot x-m\dot{x}\cdot\dot{x}$ - 一個方程式，兩個未知數 - 還需要一個條件 ##### Virtual Work（虛功） - 加上限制力不改變系統總能量（被動） - 動能：$T=\frac{1}{2}m\dot{x}\cdot\dot{x}$ - $\dot{T}=\frac{1}{2}m(\ddot{x}\cdot\dot{x}+\dot{x}\cdot\ddot{x})=m\dot{x}\cdot\ddot{x}=\dot{x}(f+\hat{f})$ - $\dot{T}$：virtual work - $\hat{f}\cdot\dot{x}=0$，$\forall\dot{x}\in\begin{Bmatrix}\dot{x}|x\cdot\dot{x}=0\end{Bmatrix}$（合法速度的集合） - $\rightarrow \hat{f}=\lambda x$ - $\hat{f}\cdot x=-f\cdot x-m\dot{x}\cdot\dot{x}$ 代入 - $\rightarrow \lambda =\frac{-f\cdot x-m\dot{x}\cdot\dot{x}}{x\cdot x}$ ##### Geometric Interpretation - 限制力 - $\hat{f}=\lambda x=\frac{-f\cdot x-m\dot{x}\cdot\dot{x}}{x\cdot x}x$ - 若系統速度為0 - $\rightarrow \hat{f}=-\frac{f\cdot x}{x\cdot x}x$ - 只留下切線方向上的力 ## 推廣至粒子系統 - 推導粒子系統的限制力 ### 粒子限制 - Paritcle i： - $\vec{X}_i=\begin{bmatrix} \vec{x}_i \\ \vec{v}_i \end{bmatrix}$ - 外力 for particle i： - $\vec{f}_i$ - Particle system： - $Y=\begin{bmatrix} X_1 \\ X_2 \\ \vdots \\ X_n \end{bmatrix}$，$Y\in R^{6n}$ - $6$：$x$、$v$、$f$、$m$、$\Delta x$、$\Delta v$ - 限制條件 - 每個都是function：$C_i(x_1, x_2, \cdots)$ - $C_i(x_1, x_2, \cdots)=0$，$\forall i$ - $\frac{\partial C_i}{\partial x}$，$\forall i$ ### 運動方程 - n 個粒子的系統 - $\begin{bmatrix} \ddot{x}_1 \\ \ddot{x}_2 \\ \vdots \\ \ddot{x}_n \end{bmatrix}=\begin{bmatrix} \frac{1}{m_1} & 0 & \cdots & 0 \\ 0 & \frac{1}{m_2} & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \frac{1}{m_n} \end{bmatrix}\begin{bmatrix} f_1 \\ f_2 \\ \vdots \\ f_n \end{bmatrix}$ - $\rightarrow \ddot{q}=WQ$，$W\in R^{6n\times 6n}$，$Q\in R^{6n\times 1}$ #### 限制方程式 - 系統的限制方程 - $C(q)=0$，$C\in R^{3m}$ - $\dot{C}=\frac{\partial C}{\partial q}\frac{dq}{dt}=J\dot{q}=0$，$J$：Jacobian - $\ddot{C}=\dot{J}\dot{q}+J\ddot{q}=0$ - 計算合法加速度 - $\ddot{q}=W(Q+\hat{Q})$，$Q$：Constraint forces - $\rightarrow \ddot{C}=\dot{J}\dot{q}+JW(Q+\hat{Q})=0$ - $\rightarrow JW\hat{Q}=-\dot{J}\dot{q}-JWQ$ #### Principle of Virtual Work - 確保限制力不會增加功 - $\hat{Q}\dot{q}=0$，$\forall \dot{q}\in \begin{Bmatrix}\dot{q}|J\dot{q}=0\end{Bmatrix}$ - 向量須滿足 - $\hat{Q}=J^T\lambda$ ### 限制力的兩個條件 - 合法加速度 - $JW\hat{Q}=-\dot{J}\dot{q}-JWQ$ - 虛功的原則 - $\hat{Q}=J^T\lambda$ - $\rightarrow JWJ^T\lambda =-\dot{J}\dot{q}-JWQ$ #### Constraint Gradients - $\hat{Q}=J^T\lambda$ - Normal of $C_1$：$\frac{\partial C_1}{\partial q}$ - Normal of $C_m$：$\frac{\partial C_m}{\partial q}$ - $J=\begin{bmatrix} \frac{\partial C_1}{\partial q_1} & \frac{\partial C_1}{\partial q_2} & \cdots & \frac{\partial C_1}{\partial q_n} \\ \frac{\partial C_2}{\partial q_1} & \frac{\partial C_2}{\partial q_2} & \cdots & \frac{\partial C_2}{\partial q_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial C_m}{\partial q_1} & \frac{\partial C_m}{\partial q_2} & \cdots & \frac{\partial C_m}{\partial q_n} \end{bmatrix}$ - 每一列都是該平面的法向量 <br> - 合法狀態：平面相交 - $\hat{Q}=J^T\lambda \rightarrow \sum_{i=1}^{m}\lambda_i\frac{\partial C_i}{\partial q}$ - 限制力所作之功為 0 ##### Lagrange Multiplier [Wikipedia](https://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0) - Maximize $f(x, y)$ - Sub. to $g(x, y)=0$ ## 參數化限制 $x=\begin{bmatrix} rcos\theta \\ rsin\theta \end{bmatrix}$ - 限制 - $\dot{x}=\frac{\partial x}{\partial\theta}\frac{d\theta}{dt}=T\dot{\theta}$ - $T=\frac{\partial x}{\partial\theta}$ - $\ddot{x}=\dot{T}\dot{\theta}+T\ddot{\theta}=\frac{f+\hat{f}}{m}$ - Degree of freedom：$1$ - Solve for $\ddot{\theta}$ - 兩邊同乘$T$ - Virtual work principle：$\hat{f}\cdot T=0$ - $\rightarrow \ddot{\theta}=\frac{T\cdot \frac{f}{m}-T\cdot\dot{T}\dot{\theta}}{T\cdot T}$ ### Lagrangian Dynamics - 參數空間下描述物體運動狀態的動力學 - **並非**於不受限制的空間中建立運動方程 - **而是**受限制空間內用額外參數（$u$）描述系統運動狀態$\rightarrow$解參數空間加速度（$\ddot{u}$） ### 優劣 - 優點： - 運動自由度較少 - 限制條件一定會滿足 - 缺點： - 很難找到好的參數化函數 - 難以結合限制條件 # RigidBodyDynamics ## 剛體運動模擬 - 粒子系統：只有考慮到每個粒子單獨運動和互動間的關係 - 實心物體運動 - 粒子系統不足 ### 問題 - 無限制條件系統（free space） - 有限制條件系統 - 碰撞偵測、接觸 - 運算效率 - 剛體：passive object - 受到外力才會有運動 ## 剛體觀念 - 移動 $\rightarrow$ 轉動 - 位置 $\rightarrow$ 朝向 - 線性速度 $\rightarrow$ 角速度 - 質量 $\rightarrow$ 轉動慣量 - 線性動量 $\rightarrow$ 角動量 - 力 $\rightarrow$ 力矩 - 粒子系統：粒子狀態 - $Y(t)=\begin{bmatrix}x(t)\\ v(t) \end{bmatrix}$ - $\frac{d}{dt}Y(t)=\begin{bmatrix} v(t) \\ \frac{f(t)}{m} \end{bmatrix}$ - 剛體系統：剛體狀態 - $Y(t)=\begin{bmatrix}x(t) \\ ? \\ v(t) \\ ? \end{bmatrix}$ ### 位置 vs. 朝向 - $x(t)=\begin{bmatrix} x(t) \\ y(t) \\ z(t) \end{bmatrix}$ - $R(t)=\begin{bmatrix} r_{xx}(t) && r_{yx}(t) && r_{zx}(t) \\ r_{xy}(t) && r_{yy}(t) && r_{zy}(t) \\ r_{xz}(t) && r_{yz}(t) && r_{zz}(t) \end{bmatrix}$ - $x(t)$（位移）$\rightarrow$$R(t)$（朝向改變量：旋轉）：body space $\rightarrow$ world space - $r_i(t)=x(t)+R(t)r_{0i}$ - $x(t)$：world space 中 body space 的原點座標 - $r_{0i}$：body space 的座標 - 假設剛體為均勻密度：$x(t)$為質心 - 以$x$軸單位方向向量（$(1, 0, 0)$）為例 - $R(t) \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} =\begin{bmatrix} r_{xx}(t) && r_{yx}(t) && r_{zx}(t) \\ r_{xy}(t) && r_{yy}(t) && r_{zy}(t) \\ r_{xz}(t) && r_{yz}(t) && r_{zz}(t) \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} =\begin{bmatrix} r_{xx}(t) \\ r_{xy}(t) \\ r_{xz}(t) \end{bmatrix}$ - $R$的第一行 - $R(t)$代表在時間 t，world space 內$x, y, z$軸方向 - $x(t)$：位置，$R(t)$：朝向 #### Body Space vs. World Space - Body space：（= object space = local space） - 物體本身的座標系統 - 固定、不會改變的空間 - 剛體內部各點的相對位置是固定的 - 幾何中心＝body space 的原點 - World space： - 多物體的共同座標系統 - 全域性 ### 線性速度 vs. 角速度 - 線性速度 - 單位時間內的位移量 - $v(t)=\frac{dx(t)}{dt}$ - 角速度 - $x(t)$、$R(t)$兩者獨立 - 固定質心位置的情況下，任何移動都是轉動造成的 - 將線性速度與角速度分開來看 #### 角速度 - $\omega(t)$：三維向量，描述角速度 - $\left\{\begin{matrix} \dot{r}(t)\perp b \\ \dot{r}(t)\perp \omega(t) \\ |\dot{r}(t)|=|b||\omega(t)| \end{matrix}\right.$ - $\rightarrow \dot{r}(t)=\omega(t)\times b=\omega(t)\times b+\omega(t)\times a=\omega(t)\times r(t)$ - $\because \omega(t)\parallel a$ - $\therefore\omega(t)\times a=0$ - $R(t)$根據時間，行變換 - $\dot{R}(t)=\begin{bmatrix} \omega(t)\times\begin{pmatrix} r_{xx}(t) \\ r_{xy}(t) \\ r_{xz}(t) \end{pmatrix} && \omega(t)\times\begin{pmatrix} r_{yx}(t) \\ r_{yy}(t) \\ r_{yz}(t) \end{pmatrix} && \omega(t)\times\begin{pmatrix} r_{zx}(t) \\ r_{zy}(t) \\ r_{zz}(t) \end{pmatrix} \end{bmatrix}$ - 簡化 - $\dot{R}(t)=\omega(t)^{*}R(t)=\begin{pmatrix} 0 && -\omega_z && \omega_y \\ \omega_z && 0 && \omega_y \\ -\omega_y && \omega_x && 0 \end{pmatrix}\begin{pmatrix} r_{xx}(t) && r_{yx}(t) && r_{zx}(t) \\ r_{xy}(t) && r_{yy}(t) && r_{zy}(t) \\ r_{xz}(t) && r_{yz}(t) && r_{zz}(t) \end{pmatrix}$ ##### 簡化矩陣 - $a\times b =\begin{pmatrix} a_yb_z-b_ya_z \\ -a_xb_z+b_xa_z \\ a_xb_y-b_xa_y \end{pmatrix}$ - $a \times b=a^{*}b=\begin{pmatrix} 0 && -a_z && a_y \\ a_z && 0 && -a_x \\ a_y && a_x && 0 \end{pmatrix}\begin{pmatrix} b_x \\ b_y \\ b_z \end{pmatrix}$ ### Particles - 剛體：由大量小粒子組成 - 第 $i$ 個粒子在時間 $t$ 時在 world space 的位置： - $r_i(t)=x(t)+R(t)r_{0i}$ - $x(t)$：world space 中 body space 的原點座標 - $r_{0i}$：在 body space 內的座標 - $\frac{d}{dt}r_i(t)=\frac{d}{dt}x(t)+\frac{d}{dt}R(t)r_{0i}$ - $\rightarrow \dot{r}_i(t)=\dot{x}(t)+\omega(t)^{*}R(t)r_{0i}$ $=v(t)+\omega(t)^{*}(R(t)r_{0i}+x(t)-x(t))$ $=v(t)+\omega(t)^{*}(r_i(t)-x(t))$ - $v(t)$：線性速度 - $\omega(t)^{*}(r_i(t)-x(t))$：角速度 ### 質量 vs. 慣量 #### 質量 - 第 $i$ 個物體的質量：$m_i$ - $M=\sum_{i=1}^{N}m_i$ - 質心 - $COM=\frac{\sum_{i=1}^{N}m_ir_i(t)}{M}$ - $COM \in \mathbb{R}^3$ - $COM$ in body space：$(0, 0, 0)$ #### 轉動慣量 - 質量相對於質心的分布狀況 - $I(t)=\sum_{i=1}^{N}\begin{pmatrix} m_i({r^{'}}^2_{iy}+{r^{'}}^2_{iz}) && -m_ir^{'}_{ix}r^{'}_{iy} && -m_ir^{'}_{ix}r^{'}_{iz} \\ -m_ir^{'}_{iy}r^{'}_{ix} && m_i({r^{'}}^2_{ix}+{r^{'}}^2_{iz}) && -m_ir^{'}_{iy}r^{'}_{iz} \\ m_ir^{'}_{iz}r^{'}_{ix} && m_ir^{'}_{iz}r^{'}_{iy} && m_i({r^{'}}^2_{ix}+{r^{'}}^2_{iy}) \end{pmatrix}$ - $r^{'}_i=r_i(t)-x(t)$ - $I(t)$ 跟朝向有關，與絕對位置無關 - 累加 $\rightarrow$ 積分 - 會隨著物體轉動而改變 - 但在 body space 是定值 ##### 推導 - $I(t)=\sum_{i=1}^{N}m_ir^{'T}_ir^{'}_i\begin{pmatrix} 1 && 0 && 0 \\ 0 && 1 && 0 \\ 0 && 0 && 1 \end{pmatrix} - m_i\begin{pmatrix} {r^{'}}^2_{ix} && r^{'}_{ix}r^{'}_{iy} && r^{'}_{ix}r^{'}_{iz} \\ r^{'}_{iy}r^{'}_{ix} && {r^{'}}^2_{iy} && r^{'}_{iy}r^{'}_{iz} \\ r^{'}_{iz}r^{'}_{ix} && r^{'}_{iz}r^{'}_{iy} && {r^{'}}^2_{iz} \end{pmatrix}$ $=\sum_{i=1}^{N}m_i({r^{'}}^T_ir^{'}_i1-r^{'}_i{r^{'}}^T_i)$ ##### Body Space 內的轉動慣量 - $r^{'}_i(t)=r_i(t)-x(t)=R(t)r_{0i}$ - $R(t){R(t)}^T=1$ - $\rightarrow I(t) =\sum_{i=1}^{N}m_i({r^{'}}^T_ir^{'}_i1-r^{'}_i{r^{'}}^T_i)$ $=\sum^{N}m_i[{r_{0i}}^Tr_{0i}R(t){R(t)}^T-R(t)r_{0i}{r_{0i}}^T{R(t)}^T]$ $=R(t)\sum^{N}m_i[{r_{0i}}^Tr_{0i}1-r_{0i}{r_{0i}}^T]{R(t)}^T=R(t)I_{body}{R(t)}^T$ - $I_{body}$：body space 內的轉動慣量 ### 力 vs. 力矩 ### 力 - $F(t)=\sum f_i(t)$ ### 力矩 - $\tau(t)=\sum (p_i(t)-x(t))\times f_i(t)$ ## 剛體運動方程 :star: - $\frac{d}{dt}Y(t)=\frac{d}{dt}\begin{pmatrix} x(t) \\ R(t) \\ Mv(t) \\ I(t)\omega(t) \end{pmatrix}=\begin{pmatrix} v(t) \\ \omega(t)\times R(t) \\ F(t) \\ \tau(t) \end{pmatrix}=\begin{pmatrix} v(t) \\ \omega(t)^{*}R(t) \\ F(t) \\ \tau(t) \end{pmatrix}$ - $Mv(t)$：線性動量 - $I(t)\omega(t)$：角動量 ### 實作上 - 四元數 取代 矩陣 - Green's Theorem 計算轉動慣量 - 幾何形狀不規則的剛體 - [C code](http://www.cs.berkeley.edu/~jfc/mirtich/massProps.html) # ClothAnimation ## 布料 ### 布料模擬 #### 需求 - 角色動畫 - 遊戲 - 服裝設計 - 布料設計 #### 挑戰 - 真實感 - 互動性 - 穩定性 - 複雜性 - 碰撞偵測／處理 ### 布料模型 - 布料工程 - 機械性質量測 - 工業應用 - 電腦圖學 - 模擬布料形狀、型變 - 幾何方法 $\rightarrow$ 物理模擬 #### CG 布料模擬 - 幾何方法（離散） - 連續數值 - 粒子系統 ##### 粒子系統（Particle-based） - 紡織線 - 粒子組成線段 ###### 靜態 Breen et al.（1994） - 物體形狀符合最小能量 - Energy-based model - $U_{total_i}=U_{repel_i}+U_{stretch_i}+U_{bend_i}+U_{trellis_i}$ - 透過量測系統（Kawabata system）取得布料的材料系數 - 伸張測試、簡諧力 ###### 推廣到動態 - 利用彈簧 - 直線方向型變（Stretch） - 簡諧方向型變（Shearing） - 彎曲（Bending） - Provot（1995） - 加入彈簧系統 - ![](https://i.imgur.com/TFs3qjb.png) ### Baraff and Witkin（1998） - [Large steps in cloth simulation](https://dl.acm.org/doi/10.1145/280814.280821) - SIGGRAPH'98 - 布料模擬 - Implicit integration - Large time step、faster simulations - 三角形網格 - 利用 Jocaboian 的稀疏性 ### 牛頓第二運動定律 - n 個粒子 - $\ddot{x}=M^{-1}f(x, \dot{x})$ - $x$：$3n\times 1$ - $M$：$3n\times 3n$ - Diagonal matrix - $M_{i, j}$： - $i\neq j$：$0$ - $i=j$：$\begin{bmatrix} \frac{1}{m_i} && 0 && 0 \\ 0 && \frac{1}{m_i} && 0 \\ 0 && 0 && \frac{1}{m_i} \end{bmatrix}$ #### 微分方程 - $\frac{d}{dt}\begin{pmatrix} x \\ v \end{pmatrix}=\begin{pmatrix} v \\ M^{-1}f(x, v) \end{pmatrix}$ ##### 顯性 Euler method - $\begin{pmatrix} \Delta x \\ \Delta v \end{pmatrix}=h\begin{pmatrix} v_0 \\ M^{-1}f(x_0, v_0) \end{pmatrix}$ ##### 隱性 Euler method - $\begin{pmatrix} \Delta x \\ \Delta v \end{pmatrix}=h\begin{pmatrix} v_0+\Delta v \\ M^{-1}f(x_0+\Delta x, v_0+\Delta v) \end{pmatrix}$ ###### 近似 $f$ 函數（Taylor Series） - $f(x_0+\Delta x, v_0+\Delta v)=f(x_0, v_0)+\frac{\partial f}{\partial x}\Delta x+\frac{\partial f}{\partial v}\Delta v$ - $\rightarrow \begin{pmatrix} \Delta x \\ \Delta v \end{pmatrix}=h\begin{pmatrix} v_0+\Delta v \\ M^{-1}(f_0+\frac{\partial f}{\partial x}\Delta x+ \frac{\partial f}{\partial v}\Delta v) \end{pmatrix}$ - $\rightarrow (I-hM^{-1}\frac{\partial f}{\partial v}-h^2M^{-1}\frac{\partial f}{\partial x})\Delta v=hM^{-1}(f_0+h\frac{\partial f}{\partial x}v_0)$ ##### 解方程式 - 彈簧數目少：容易 - 複雜模型：困難 - 能量 $\rightarrow$ 計算力 - $E(x)$ - $f=-\frac{\partial E}{\partial x}$ - 解釋： - $w=f_e\cdot x \rightarrow f_e=\frac{\partial w}{\partial x}$ - $f_i=-f_e=-\frac{\partial U}{\partial x}$ - $w$：功 - $f_e$：外力 - $x$：位移量 - $f_i$：內部力（維持形狀） - $U$：系統位能 - 問題：阻尼力無法這樣得出 <br> - $E_C(x)=\frac{k}{2}{C(x)}^TC(x)$ - $E_C(x)$：純量 - $C(x)$：需要滿足的（形狀）限制條件，$C(x)=0$ - $f=-\frac{\partial E_C}{\partial x}=-k\frac{\partial {C(x)}^T}{\partial x}C(x)$ - $f \in \mathbb{R}^{3n\times 1}$ - $\frac{\partial {C(x)}^T}{\partial x} \in \mathbb{R}^{m\times 3n}$ - $C(x) \in \mathbb{R}^{m\times 1}$ - $\frac{\partial f_i}{\partial x_j}=-k\begin{pmatrix} \frac{\partial {C(x)}^T}{\partial x_i}\frac{\partial C(x)}{\partial x_j}+\frac{{\partial}^2{C(x)}^T}{\partial x_i \partial x_j}C(x) \end{pmatrix}$ ### 三角網格模型 - 線性型變、形狀角度變化 - $C(x)$：Contraint Equation #### 基本概念 - 布料型變 $\rightarrow$ 曲面 - 測量型變：$\mathbb{R^2}\rightarrow \mathbb{R}^3$ - $w_u=\frac{\partial w}{\partial u}$ - $w_v=\frac{\partial w}{\partial v}$ #### 伸展／壓縮 - $(\Delta x, \Delta y, \Delta z)\rightarrow (\Delta u, \Delta v)$ - Taylor Series - $w(u+\Delta u, v+\Delta v)=\begin{bmatrix} w_x(u+\Delta u, v+\Delta v) \\ w_y(u+\Delta u, v+\Delta v) \\ w_z(u+\Delta u, v+\Delta v) \end{bmatrix}\approx w(u, v)+J_w(u, v)\begin{bmatrix} \Delta u \\ \Delta v \end{bmatrix}$ - $J_w(u, v)=\begin{bmatrix}w_u && w_v\end{bmatrix}$ - $\Delta x=\begin{bmatrix} \Delta x \\ \Delta y \\ \Delta z \end{bmatrix}=w(u+\Delta u, v+\Delta v)-w(u, v)\approx J_w(u, v)\begin{bmatrix} \Delta u \\ \Delta v \end{bmatrix}=\begin{bmatrix}w_u && w_v\end{bmatrix}\begin{bmatrix} \Delta u \\ \Delta v \end{bmatrix}$ - 先看兩邊（三角形網格） - $\Delta x_1=w_u\Delta u_1+w_v\Delta v_1$ - $\Delta x_2=w_u\Delta u_2+w_v\Delta v_2$ - $\rightarrow \begin{bmatrix}w_u && w_v\end{bmatrix}=\begin{bmatrix}\Delta x_1 && \Delta x_2\end{bmatrix}{\begin{bmatrix}\Delta u_1 && \Delta u_2 \\ \Delta v_1 && \Delta v_2\end{bmatrix}}^{-1}$ ### 力與能量 - 線性力（Stretch Forces） - $C(x)=a\begin{pmatrix}\parallel w_u(x) \parallel -b_u \\ \parallel w_v(x) \parallel -b_v\end{pmatrix}$ - $a$：三角形範圍 - $b$：rest length - 簡諧方向型變（Shear Forces） - $C(x)=aw_u(x)^Tw_v(x)$ - 彎曲（Bending Forces） - $C(x)=\theta$ #### 阻尼力（Damping Forces） - $\frac{dE}{dt}={\frac{\partial E}{\partial x}}^T\frac{dx}{dt}=0$ - 在平衡點（速度最快）時 $E$ 最小 - 非阻尼力要求 - $d=-k_d\frac{\partial C(x)}{\partial x}\dot{C}(x)$ - $\frac{\partial C(x)}{\partial x}$：力的方向 - $\dot{C}(x)$：速度 - 方向與彈性力（spring force）方向一致 ### 限制 - penalty method - 剛體系統 - Lagrange multipliers（虛功） - 限制力 - 參數化限制（Parametric constraint／reduced coordinate／general coordinate） - 修正質量矩陣 #### 加速度為0 - 例：z 軸加速度為 $0$ - $\ddot{x}_i=\begin{pmatrix} \frac{1}{m_i} && 0 && 0 \\ 0 && \frac{1}{m_i} && 0 \\ 0 && 0 && 0 \end{pmatrix} f_i$ - $\rightarrow \ddot{x}_i=W_{ii}f_i$ - $W_{ii}=\frac{1}{m_{ii}}S_i \in \mathbb{R}^{3\times 3}$ ### 非軸上的 $0$ 加速度 - 對於第 $i$ 個粒子 - $\ddot{x}_i=W_{ii}f_i$ - $W_{ii}=\frac{1}{m_{ii}}S_i \in \mathbb{R}^{3\times 3}$ - $S_i$： - $I$：if ndof($i$)=$3$ - $(I-p_i{p_i}^T)$：if ndof($i$)=$2$ - $(I-p_i{p_i}^T-q_i{q_i}^T)$：if ndof($i$)=$1$ - $0$：if ndof($i$)=$0$ - $\parallel p_i \parallel = \parallel q_i \parallel =1$，$p_i \perp q_i$ #### 驗證 $S_i=(I-p_i{p_i}^T)$ - $f_i=\alpha p_i$ - $\ddot{x}_i=W_{ii}f_i=\frac{1}{m_i}(I-p_i{p_i}^T)\alpha p_i$ - $\parallel p_i \parallel =1={p_i}^Tp_i$ - $\rightarrow =\frac{\alpha}{m_i}(p_i-p_i{p_i}^Tp_i)=0$ ### 任意速度限制條件 - 無限制 - $(I-hM^{-1}\frac{\partial f}{\partial v}-h^2M^{-1}\frac{\partial f}{\partial x})\Delta v=hM^{-1}(f_0+h\frac{\partial f}{\partial x}v_0)$ - 加限制 - $(I-hW\frac{\partial f}{\partial v}-h^2W\frac{\partial f}{\partial x})\Delta v=hW(f_0+h\frac{\partial f}{\partial x}v_0)+z$ ## 其他方法 ### Edberhardt et al.（1995.） - 特殊材質布料 - 編織物 - 當作實心物體作顯像 ### 避免剛性 - 避免使用線性彈簧模擬 - 改用非線性彈簧（力與位移量關係非線性） - 互動性應用 ### Ko, Choi（SIGGRAPH 2002） - 布料特性 - 對壓縮抵抗力弱（容易彎曲） - 對延展、伸張抵抗力強 - 用彈簧連結 - 彈簧的 $k$ 值很大（剛性強） - 需要壓縮力夠強才能產生非平面方向的力 - 梁柱 - 受到垂直方向的力不太會產生彎曲型變 - 力大於一定程度就為崩潰（產生型變） - 用非線性模型描述彎曲／壓縮力 - 伸長量比例 - 力 ### Constrained Lagrange Mechanics - 布料的延展性 - Augment Lagrange equation with constraints - $L(x, v)=\frac{1}{2}v^TMv-V(x)-C(x)^T\lambda$ - $C(x)$：Constraints - $\lambda$：Lagrange Multipliers - $V(x)$：Potential energy - Constrained dynamics equation - $M\dot{v}+\bigtriangledown V(x)+\bigtriangledown C(x)^T\lambda =0$ - $C(x)=0$ #### Lagrange Mechanics - 牛頓力學 - 3D 座標（向量） - 座標轉換：困難 - 能量描述物體運動（純量） - 座標轉換：較容易 - generalized coordinate - $\rightarrow$ 等效的 $Lagrangian$ - $L(x, v)=$ Kinetic Energy $-$ Potential Energy $=T(x, v)-V(x, v)$ - $\frac{d}{dt}\frac{\partial L}{\partial v}-\frac{\partial L}{\partial x}=0$ #### 解 ODE - $M\dot{v}+\bigtriangledown V(x)+\bigtriangledown C(x)^T\lambda =0$ - $C(x)=0$ <br> - Implicit Constraint Direction (ICD) - $v^{n+1}=v^n-hM^{-1}(\bigtriangledown V(x^n)+\bigtriangledown C(x^{n+1})^T{\lambda}^{n+1})$ - $x^{n+1}=x^n+hv^{n+1}$ - $C(x^{n+1})=0$ ##### Step and Project (SAP) - 解 ICD：需要大量計算 - 解根：$5N$ 個 - $N$：vertex個數 - 替代方案 - 解第一、二式（忽略限制條件） - 得到 $x^{n+1}_0$ - $C(x^{n+1}_0)=0$ - 將$x^{n+1}_0$投影至限制空間（$\left\{x^{n+1}|C(x^{n+1})=0\right\}$） - 意即找到離 $x^{n+1}_0$ 最接近的 $x^{n+1}$ ### Subspace clothing simulatino using adaptive bases - SIGGRAPH 2014 - 低維度子空間 - 不同空間、時間：使用不同的基底向量描述 ### A perceptual control space for garment simulation, SIGGRAPH 2015 - 直覺性描述 - 彈性係數$\rightarrow$柔軟度 - $\cdots$ - 離散取樣 - 建立對應函數 # KeyFraming [4-3 Spatial Key Framing](https://pt.coursera.org/lecture/interactive-computer-graphics/4-3-spatial-key-framing-gQPxL) ## 關鍵影格 - 動畫師決定關鍵影格 - 電腦產生影格間的畫面 ### 關鍵？ - 關鍵影格 - 參數描述 - 系列的關鍵影格： - 高維空間的點 - 產生平滑曲線（自然運動） ### 關鍵影格產生 - 設定關鍵影格 - 直接給定 - 正／逆向運動學（FK、IK） - 填補（內插） - 線性、三次多項室、參數化曲線 - 軌跡（填補畫面）速度 - 速度曲線 ### 優缺點 - 容易控制動作 - 減輕作畫負擔 <br> - 參數過多（DOF，degree of freedom 高） - 水、煙 - 風吹草動 - 群眾運動 ## 插值 - Ex. 球體彈跳運動 - 曲線並非單數學性插值 - 平滑插值工具 - 使用者要能夠操控 ### 問題 - 給定位置（點）、時間 - 產生平滑曲線 - 根據時間差分配虛點 - 速度控制：根據不同時間點決定位置 ### 插值、曲線近似 #### 曲線描述 ##### 參數化曲線 - 參數型式：$P=P(u)=(x, y, z)$ - $x=P_x(u), y=P_y(u), z=P_z(u)$ #### 近似空間曲線 - 插值 vs. 近似 - 匹配資料 vs. 設計 - 複雜度 - 效率 vs. 可變性 - 三次多項式已足夠 - 連續性 - 全域／局部控制 ##### 全域／局部控制 - 使用者編輯 - 改變控制點 - 全域控制：牽一髮動全身 ###### 全域控制：多項式插值 - 多項式插值 - $n+1$ 個資料點：決定 $n$ 次多項式 - Lagrange Interpolation <br> - 用高次多項式來插值 - 過度捲曲 - 全域 - 曲線盡可能平滑 - 降低捲曲 - 高次方多項式不好 :no_good: ###### 局部控制：複合分段 - 將曲線分割為多個小段 - 參數化型式 - 維持連續性 - 位置 - 切線 - 曲率 ### Splines：分段式多項式（局部控制） - 多個低次方多項式（三次）對控制點（關鍵影格）做插值 - 誤差（bending energy） - 描述方式：曲率平方累加值 - 二階微分 $\rightarrow$ 曲率 - 最小化 - 嘗試讓曲率變化（curvature）$=0$ - 如果不行，則平均分散到整個曲線 - **三次多項式**最常見 - 滿足插值、達到 $C1$ 連續的最低次 - 更高次：捲曲過多 - 更低次：型態限制 #### 線性分段式多項式 - 基底向量 - Ex. 折線 - $P(u)=(1-u)p_1+up_2$ - $1-u$、$u$：基底函數 - $p_1$、$p_2$：控制點 #### Hermite 插值法 - Hermite 曲線 - $P(u)=(P_x(u),P_y(u),P_z(u))$ - $P_x(u)=a_xu^3+b_xu^2+c_xu+d_x$ - 參數（條件） - 端點的位置 - 端點的切線斜率 - 連續性 - 端點位置、切線斜率共用 - $C_0$、$C_1$ 連續 ##### Hermite 曲線型式 - 三次多項式、一階微分 - $P_x(u)=a_xu^3+b_xu^2+c_xu+d_x$ - $\dot{P_x}(u)=3a_xu^2+2b_xu+c_x$ - 條件：$P_x(0), P_x(1), \dot{P_x}(0), \dot{P_x}(1)$ - 解： - $a_x=2(P_x(0)-P_x(1))+\dot{P_x}(0)+\dot{P_x}(1)$ - $b_x=3(P_x(1)-P_x(0))-2\dot{P_x}(0)-\dot{P_x}(1)$ - $c_x=\dot{P_x}(0)$ - $d_x=P_x(0)$ <br> - $P_x(u)=\begin{bmatrix} u^3 && u^2 && u && 1 \end{bmatrix}\begin{bmatrix} a_x \\ b_x \\ c_x \\ d_x \end{bmatrix}$ $=\begin{bmatrix} u^3 && u^2 && u && 1 \end{bmatrix}\begin{bmatrix}2 && -2 && 1 && 1 \\ -3 && 3 && -2 && -1 \\ 0 && 0 && 1 && 0 \\ 1 && 0 && 0 && 0 \end{bmatrix}\begin{bmatrix} P_x(0) \\ P_x(1) \\ \dot{P_x}(0) \\ \dot{P_x}(1) \end{bmatrix}$ $=U^TMB_x$ ###### 矩陣型式下的參數化曲線 - $P(u)=U^TMB$ - $M$：係數矩陣 - $B$：幾何資訊 - $B=\begin{bmatrix} P_x(0) && P_y(0) && P_z(0) \\ P_x(1) && P_y(1) && P_z(1) \\ \dot{P_x}(0) && \dot{P_y}(0) && \dot{P_z}(0) \\ \dot{P_x}(1) && \dot{P_y}(1) && \dot{P_z}(1) \end{bmatrix}$ - 第 $i$ 段：$B=\begin{bmatrix} p_i \\ p_{i+1} \\ \dot{p_i} \\ \dot{p_{i+1}}\end{bmatrix}$ ##### Blending Functions - $P(u)=U^TMB={\begin{bmatrix} 2u^3-3u^2+1 \\ -2u^3+3u^2 \\ u^3-2u^2+u \\ u^3-u^2 \end{bmatrix}}^T\begin{bmatrix} p_1 \\ p_2 \\ \dot{p_1} \\ \dot{p_2} \end{bmatrix}$ - $P_x(u)=(2u^3-3u^2+1)p_{1x}+(-2u^3+3u^2)p_{2x}+(u^3-2u^2+u)\dot{p_{1x}}+(u^3-u^2)\dot{p_{2x}}$ - $U^TM$：基底函數 #### Bezier 曲線 - 給四個控制點 - Hermite：給兩端點位置＋切線斜率 - $\dot{P}(0)=3(p_2-p_1)$ - $\dot{P}(1)=3(p_4-p_3)$ - $P(u)=\begin{bmatrix} u^3 && u^2 && u && 1 \end{bmatrix}\begin{bmatrix}2 && -2 && 1 && 1 \\ -3 && 3 && -2 && -1 \\ 0 && 0 && 1 && 0 \\ 1 && 0 && 0 && 0 \end{bmatrix}\begin{bmatrix} 1 && 0 && 0 && 0 \\ 0 && 0 && 0 && 1 \\ -3 && 3 && 0 && 0 \\ 0 && 0 && -3 && 3 \end{bmatrix}\begin{bmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \end{bmatrix}$ - $P(u)=\begin{bmatrix} u^3 && u^2 && u && 1 \end{bmatrix}\begin{bmatrix}-1 && 3 && -3 && 1 \\ 3 && -6 && 3 && 0 \\ -3 && 3 && 3 && 0 \\ 1 && 0 && 0 && 0 \end{bmatrix}\begin{bmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \end{bmatrix}$ - Hermite spline 的變形 - $C_1$ 連續要另外處理 - $\dot{P}(0)=3(p_1-p_0)$ - $\frac{dx}{du}=3(x_1-x_0)$ - $\frac{dy}{du}=3(y_1-y_0)$ - $\frac{dy}{dx}=\frac{(y_1-y_0)}{(x_1-x_0)}$ #### Catmull-Rom Splines - Hermite、Bezier：需要注意控制點設定才能保證 $C_1$ 連續 - Catmull-Rom Splines：自動滿足 $C_1$ 連續 - $p_i$ 的切線：$s(p_{i+1}-p_{i-1})$，$i=2..n-1$ - $\dot{p_i}=s(p_{i+1}-p_{i-1})$ - 端點：外插 or 額外控制點 - $s$：張力參數，通常 $s=\frac{1}{2}$ - 條件 - $P(0)=p_2$ - $P(1)=p_3$ - $\dot{P}(0)=3(p_3-p_1)$ - $\dot{P}(1)=3(p_4-p_2)$ - $\rightarrow P(u)=U^T\begin{bmatrix} -s && 2-s && s-2 && s \\ 2s && s-3 && 3-2s && -s \\ -s && 0 && s && 0 \\ 0 && 1 && 0 && 0 \end{bmatrix}\begin{bmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \end{bmatrix}$ ### Now What? - 有： - 關鍵影格 - 軌跡（曲線） - 運動效果（速度） - 速度曲線 #### 速度控制 - 速度曲線 - 定義位移量（s）－時間（t）的關係 ##### 參數化不均勻問題 - 參數空間內的移動量與三維空間的移動量不一致 - $u_2-u_1\neq s(u_2)-s(u_1)$ - $s(u)=\int \sqrt{{\frac{dP_x(u)}{du}}^2+{\frac{dP_y(u)}{du}}^2+{\frac{dP_z(u)}{du}}^2} du$ #### 位移長度的再參數化 - 再參數化：函數對應（mapping） - 使位移變化量成正比 - 問題 - $arclength(u_1, u_2)=\Delta s$ - 給定不同參數值 $u_1, u_2$，算出位移量 - 給定位移量，算出參數值 - ##### Finite Differences（近似解） - 曲線切段 - 各段視為直線 - 積分 - 曲線上取樣 - 使用直線近似 - 建表（Lookup Table） - $u$－$ArcLength$ - $u$（參數）間隔越小 $\rightarrow$ 近似越準確 - $P(u)=P(u(s(t)))$ ### 流程 - Key frames（vector／control point） - 插值 - Space curve - Arclength reparameterization - Lookup table - Speed curve ### 速度曲線 #### Ease-in Ease-out - 開始、結束速度小 ##### Sine 插值法 - $s(t)=\frac{1}{2}sin(t\pi - \frac{\pi}{2})+\frac{1}{2}$，$0\leq t\leq 1$ ##### 分段式曲線 - 頭尾：Sinusoidal segments（Sine 插值法） - 中段：Linear segment ##### 不使用 sine - $V_1=V_2 \rightarrow A^*t_1=-D^*(1-t_2)$ # 3DRotation ## 旋轉 ### 3-D 轉換 - 移動 - Translate：$P'=P+T$ - $P, T\in \mathbb{R}^3$ - Scale：$P'=SP$ - $S\in \mathbb{R}^{3\times 3}$ - Rotate：$P'=RP$ - $R\in \mathbb{R}^{3\times 3}$ - $\rightarrow P'=MP$ - $P \in \mathbb{R}^4$：齊次座標系統 - $M$：轉換矩陣 - 物體本身的移動旋轉 - 攝影機相對物體的移動旋轉 #### 齊次座標系統 - $4\times 4$ 矩陣 - $(\frac{x}{w}, \frac{y}{w}, \frac{z}{w})=[x, y, z, w]$ - $(x, y, z)=[x, y, z, 1]$ - 通常設定 $w=1$ #### Translation（移動） - $\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix}=\begin{bmatrix} 1 && 0 && 0 && t_x \\ 0 && 1 && 0 && t_y \\ 0 && 0 && 1 && t_z \\ 0 && 0 && 0 && 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$ #### Scaling - $\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix}=\begin{bmatrix} s_x && 0 && 0 && 0 \\ 0 && s_y && 0 && 0 \\ 0 && 0 && s_z && 0 \\ 0 && 0 && 0 && 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$ #### Rotation - X 軸 - $R_x(0)=\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix}=\begin{bmatrix} 1 && 0 && 0 && 0 \\ 0 && cos\theta && -sin\theta && 0 \\ 0 && sin\theta && cos\theta && 0 \\ 0 && 0 && 0 && 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$ - Y 軸 - $R_y(0)=\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix}=\begin{bmatrix} cos\theta && 0 && sin\theta && 0 \\ 0 && 1 && 0 && 0 \\ -sin\theta && 0 && cos\theta && 0 \\ 0 && 0 && 0 && 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$ - Z 軸 - $R_z(0)=\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix}=\begin{bmatrix} cos\theta && -sin\theta && 0 && 0 \\ sin\theta && cos\theta && 0 && 0 \\ 0 && 0 && 1 && 0 \\ 0 && 0 && 0 && 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$ ### 轉換矩陣的結合 - $P'=M_1M_2M_3\cdots M_nP$ - $M=M_1M_2M_3\cdots M_n$ - $P'=MP$ - $P^T=(M_1M_2M_3\cdots M_nP)^T$ - $M^T=M_n^TM_{n-1}^T\cdots M_2^TM_1^T$ - $P'^T=P^TM^T$ #### 旋轉矩陣 推導 1. 向量旋轉 - $x'=rcos(\theta+\alpha)$ $=r(cos\theta cos\alpha -sin\theta sin\alpha)$ $=(cos\theta rcos\alpha -sin\theta rsin\alpha)$ $=(cos\theta x-sin\theta y)$ - $y'=rsin(\theta+\alpha)$ $=(sin\theta rcos\alpha + cos\theta rsin\alpha)$ $=(sin\theta x+cos\theta y)$ - $\rightarrow \begin{bmatrix} x' \\ y' \end{bmatrix}=\begin{bmatrix} cos\theta && -sin\theta \\ sin\theta && cos\theta \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix}$ 2. 坐標軸轉換 - $V=x^0\bar{x}+y^0\bar{y}=x^1\bar{u}+y^1\bar{v}$ $=x^1(cos\theta\bar{x}+sin\theta\bar{y})+y^1(-sin\theta\bar{x}+cos\theta\bar{y})$ - $\rightarrow \begin{bmatrix} x^0 \\ y^0 \end{bmatrix}=\begin{bmatrix} cos\theta && -sin\theta \\ sin\theta && cos\theta \end{bmatrix}\begin{bmatrix} x^1 \\ y^1 \end{bmatrix}=\begin{bmatrix} \bar{u} && \bar{v} \end{bmatrix}\begin{bmatrix} x^1 \\ y^1 \end{bmatrix}$ #### 旋轉矩陣 - 代表 朝向矩陣（座標系統） - 行／列向量間互相垂直、長度為$1$（單位長度） - orthonormal - 數值計算誤差可能造成 non-orthonormal - 不再是旋轉矩陣 - 矩陣 插值 - 可能造成 non-orthonormal - 不再是旋轉矩陣 ### 3D 旋轉 描述方法 - 旋轉矩陣 - Fixed Angle - Euler Angle - Axis angle - Quaternion（四元數） <br> - 參數不需要到 $3\times 3$ - 減少參數 - 自由度更低 #### Fixed Angle（固定角） - 三個角度＋旋轉順序 - 代表旋轉軸（**全域坐標軸**）的旋轉量 - 不能連續兩個以上同軸，但中間有間隔就可以 - Ex. x-y-x 可以，x-x-z 不行 - Ex. x-y-z order $(\theta_x, \theta_y, \theta_z)$ - $P'=R_z(\theta_z)R_y(\theta_y)R_x(\theta_x)P$ ##### 插值 問題 - Ex. $(0, 90, 0)$ and $(90, 45, 90)$ in x-y-z - $\rightarrow (0, 45, 0)$ in \*-x-\* - 直接插值（相加除二） - $\rightarrow (45, 67.5, 45)$ - 希望結果： - $(90, 22.5, 90)$ #### Euler Angle（尤拉角） - 三個角度＋旋轉順序 - 代表旋轉軸（**區域坐標軸**）的旋轉量 - 不能連續兩個以上同軸，但中間有間隔就可以 - Ex. x-y-x 可以，x-x-z 不行 - 尤拉角的順序等同於固定角順序的 inverse ### 問題：Gimbal Lock - Gimbal：允許旋轉的機械裝置 - 任兩旋轉軸同向 - 喪失自由度 - 旋轉矩陣的任兩個列向量相同（同方向） - non-orthornormal - 非旋轉矩陣 #### 旋轉軸角（Axis Angle） 描述法 - 尤拉旋轉定理 - 3-D 旋轉由 4 個參數描述 - 旋轉軸：A，角度：$\theta$ - $(A_x, A_y, A_z, \theta)$ - 插值（$(A_1, \theta_1), (A_2, \theta_2)$ 求 $(A_k, \theta_k)$） - $B=A_1\times A_2$ - $\phi =cos^{-1}\frac{A_1\cdot A_2}{|A_1||A_2|}$ - $A_k=R_B(k\phi)A_1$ - $R_B$：旋轉軸為 $B$ 的旋轉矩陣 - $\theta_k=(1-k)\theta_1+k\theta_2$ ##### 旋轉軸角 vs. 四元數 - 固定角／尤拉角 $\rightarrow$ 四元數 - 需要用到 旋轉軸角 #### 四元數（Quaternion） - 4-tuple - $q=(s, x, y, z)$／$[s, v]$ - $s$：純量，與旋轉角度成正比 - $v$：向量，與旋轉軸方向相同（長度不為 $1$） - 旋轉軸角 $\rightarrow$ 四元數 - $q=[cos(\frac{\theta}{2}), sin(\frac{\theta}{2})\cdot (A_x, A_y, A_z)]$ ##### 四元數的運算 - 加 - $[s_1, v_1]+[s_2, v_2]=[s_1+s_2, v_1+v_2]$ - 乘 - $[s_1, v_1]\cdot [s_2, v_2]=[s_1s_2-v_1\cdot v_2, s_1v_2+s_2v_1+v_1\times v_2]$ - 有結合率，沒有交換率 - $q_1(q_2q_3)=(q_1q_2)q_3$ - $q_1q_2\neq q_2q_1$ - 點在空間的描述：$[0, x, y, z]$ - 單位元素：$[1, 0, 0, 0]$ - $q\cdot [1, 0, 0, 0]=q$ - 反元素 - $^{-1}=\frac{[s, -v]}{{||q||}^2}$ - $||q||=\sqrt{s^2+x^2+y^2+z^2}$ - $qq^{-1}=[1, 0, 0, 0]$ ##### 四元數的旋轉 - 旋轉向量 $v$ - $[0, v]$ - $v'=Rot_q(v)=q\cdot v\cdot q^{-1}$ - $q$：旋轉的四元數表示式 - $q$、$-q$：相同朝向／旋轉量 ###### 旋轉 連乘 - $Rot_q(Rot_p(v)) =Rot_q(pvp^{-1}) =qpvp^{-1}q^{-1} =qpv(qp)^{-1} =Rot_{qp}(v)$ - $p^{-1}q^{-1}=(qp)^{-1}$ ### Summary - 旋轉矩陣 - orthornormal - 缺點：插值 - 固定角 - 全域性旋轉軸 - 缺：插值、Gimbal lock - 尤拉角 - 區域性旋轉軸 - 缺：插值、Gimbal lock - 旋轉軸角 - 優：插值、Gimbal lock - 缺：多個旋轉結合 - 四元數 - 優：插值、Gimbal lock、多個旋轉結合 ### 可視化旋轉（Visualizing Rotations） - 單旋轉量（一維） - 圓弧（2-D） - 雙旋轉量（二維） - 球面（3-D） - 插值：在 n-D 單位球面 移動 <br> - 三旋轉量（三維）？ #### 四元數插值 - 四元數：在 4-D 單位球面上的點 - 單位四元數：$q=(s, x, y, z)$，$||q||=1$ ##### 線性插值 - 插值結果不會在球面上 - 投射至球面 - 投射結果弧長不一定相同 ##### 球型線性插值（slerp） - 保持移動間距相同 - $slerp(A, B, u)=\frac{sin(1-u)\Omega}{sin\Omega}A+\frac{sinu\Omega}{sin\Omega}B$ ###### Proof - $P=\frac{sin(\Omega -\theta)}{sin\Omega}A+\frac{sin\theta}{sin\Omega}B$ - $\theta =u\Omega$ - $P=\alpha A+\beta B$ - $||P||=1$，$||A||=1$，$||B||=1$ - $A\cdot B=cos\Omega$ - $A\cdot P=cos\theta$ <br> - $A(\alpha A+\beta B)=\alpha {|A|}^2+\beta cos\Omega =cos\theta$ - $alpha +\beta cos\Omega=cos\theta$ - ${|P|}^2=P\cdot P={\alpha}^2{|A|}^2+2\alpha \beta A\cdot B+{\beta}^2{|B|}^2=1$ - ${\alpha}^2+2\alpha\beta cos\Omega +{\beta}^2=1$ - $\rightarrow \alpha=\frac{sin(\Omega -\theta)}{sin\Omega}$，$\beta=\frac{sin\theta}{sin\Omega}$ ##### Slerp：選取最短路徑 - $q_1\cdot q_2>0$ ### 類比（$\rightarrow$ 四元數） - 歐式空間 $\rightarrow$ 4D 球面 - 位置 $\rightarrow$ 朝向 - 線性內插 $\rightarrow$ Slerp ### 多段曲線 - 歐式空間：線性內插 $\rightarrow$ Slerp - $C_0$ 連續，$C_1$ 不連續 - 歐式空間 $C_1$ 連續：三次多項式 - $\rightarrow$ Slerp：？ #### 歐式空間的 Bezier - $P(u)=\begin{bmatrix} u^3 && u^2 && u && 1 \end{bmatrix}\begin{bmatrix}-1 && 3 && -3 && 1 \\ 3 && -6 && 3 && 0 \\ -3 && 3 && 3 && 0 \\ 1 && 0 && 0 && 0 \end{bmatrix}\begin{bmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \end{bmatrix}$ #### 四元數的 Bezier - 控制點：自動產生 - 三次方程式 - 遞迴式線性內插 - 應用 Slerp ##### 產生共線控制點 - $p(u)=\begin{bmatrix} u^3 && u^2 && u && 1 \end{bmatrix}\begin{bmatrix}-1 && 3 && -3 && 1 \\ 3 && -6 && 3 && 0 \\ -3 && 3 && 3 && 0 \\ 1 && 0 && 0 && 0 \end{bmatrix}\begin{bmatrix} p_n \\ a_n \\ b_{n+1} \\ p_{n+1} \end{bmatrix}$ ![](https://i.imgur.com/IC9w1aQ.png) ##### De Casteljau 產生 Bezier 曲線 - 遞迴線性內插 - 幾何直覺： - 將角切掉，無限多次 $\rightarrow$ 近似圓 - 次分割（subdivision） ###### 次分割（subdivision） - $p(u)=(1-u)((1-u)p_0+up_1)+u((1-u)p_1+up_2)$ - $B_2(u)=(1-u)^2p_0+2u(1-u)p_1+u^2p_2$ ##### De Casteljau on 4D 球面 - $p_1=slerp(q_n, a_n, \frac{1}{3})$ - $p_2=slerp(a_n, b_{n+1}, \frac{1}{3})$ - $p_3=slerp(b_{n+1}, q_{n+1}, \frac{1}{3})$ - $p_{12}=slerp(p_1, p_2, \frac{1}{3})$ - $p_{23}=slerp(p_2, p_3, \frac{1}{3})$ - $p=slerp(p_{12}, p_{23}, \frac{1}{3})$ ### Summary - 3D 旋轉表示 - 矩陣 - orthornormal matrix（旋轉矩陣） - 尤拉角／固定角 - 旋轉軸角，四元數 - 四元數空間 - 四元數插值 - Slerp - Bezier # Kinematics ## 運動學 ### 自由度（DOF） - 設定物體運動狀態的最小座標數 - Ex. 剛體 - 位置：$x, y, z$ - 朝向：raw, pitch, yaw - $\rightarrow 6$ DOF #### 骨架模型的自由度 - 基礎：$3$ 座標 DOF＋$3$ 旋轉 DOF - 旋轉性關節 - 每個關節最多 $3$ DOF - 肩：3 DOF - 腕：2 DOF - 膝：1 DOF ##### 旋轉接頭 - 3 DOF joint - gimbal - ball and socket - 2 DOF joint - universal ### 描述人體 - 層級模型（樹狀結構） - root：任意點 - 通常選擇靠近腰部處 - node：關節 #### 關節空間 vs. 卡式座標 - 關節空間 - 由關節角度組成的空間 - 設定高維度向量以決定骨架姿勢 - 卡式座標 - 3D 空間 ### 正向運動學（FK） 與 逆向運動學（IK） - 架設骨架為剛體 - 正向運動學 - $P=f(\theta_1, \theta_2)$ - joint space $\rightarrow$ cartesian space - 給定關節 角度 $\rightarrow$ 位置 - 渲染（rendering） - 逆向運動學 - $(\theta_1, \theta_2)=f^{-1}(P)$ - cartesian space $\rightarrow$ joint space - 給定關節 位置、朝向 $\rightarrow$ 角度 - 通常解不唯一 - 骨架與環境有互動 - 參數較少 $\rightarrow$ 較好控制 ## 正向運動學（FK） ### 符號 - $V_i$：向量在第 $i$ 個座標系統的描述方式 - $_iT$：在全域空間中第 $i$ 個座標系統的原點位置 - $_j^iR$：兩座標系統間轉換的矩陣 - $V_j= {^i_jR}V_i$ ### FK - $_i^{i+1}R={_i^0R}\cdot {_0^{i+1}R}$ - $_0^iR=\begin{bmatrix} _iX && _iY && _iZ \end{bmatrix}$ - $_i^0R=_0^iR^{-1}=_0^iR^T$ - $R^{-1}=R^T$ <br> - $_{i+1}T=_0^1R\left\{ _1^2R\cdots _{i-2}^{i-2}R(_{i-1}^iRV_i+V_{i-1})+V_{i-2}]\cdots ]+V_1 \right\}$ - $_{i+1}T={_0^iR}V_i+_iT$ #### 旋轉 結合 - $\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}=R_z(\alpha_1)\left\{ R_z(-\alpha_2)[R_z(\alpha_3)T_x(l_3)+T_x(l_2)]+T_x(l_1) \right\}$ - $R_z$：父-子 區域座標系統的相對旋轉 ##### 簡化 - $\theta_1=\alpha_1$，$\theta_2=\alpha_2(+/-)\alpha_2$，$\theta_3=\alpha_3(+/-)\alpha_1(+/-)\alpha_2$ - $x=l_1cos(\theta_1)+l_2cos(\theta_2)+l_3cos(\theta_3)$ - $y=l_1sin(\theta_1)+l_2sin(\theta_2)+l_3sin(\theta_3)$ ### Acclaim 格式 - 骨架動畫檔案 - .ASF：骨架檔 - .AMC：動作檔 - ASF：全域座標系統，AMC：區域座標系統 #### ASF - 描述骨架 ```ASF= begin id 2 name lfemur //左大腿 direction 0.342 -0.939 0 length 7.113 ``` - 各關節座標、朝向 ```ASF=+ axis 0 0 20 XYZ ``` - Ex. 尤拉角順序：$x\rightarrow y\rightarrow z$ - ${_0^iR}={_0^iR_z}\cdot{_0^iR_y}\cdot{_0^iR_z}$ ```ASF=+ dof rx ry rz limits (-160.0 20.0) (-70.0 70.0) (-60.0 70.0) end ``` - 兩座標系統間的相對轉換 - ${_iR_{asf}}={^{i+1}_iR}={^0_iR}\cdot{^{i+1}_0R}$ - $\hat{V_i}={^0_iR}\hat{V_0}$ #### AMC - 尤拉角描述 - ${_iR_{amc}}={_iR_z}\cdot{_iR_y}\cdot{_iR_x}$ #### 正向運動學 in ASF/AMC - ${_i^{i+1}R}={_iR_{asf}}\cdot{_iR_{amc}}$ - ${_0^iR}={_0^1R_1^2}R\cdots{_{i-1}^iR}$ - $V_i=\hat{V_i}\cdot l_i$ - $l_i$：length - ${_iT}={^{i-1}_0R}V_{i-1}+_{i-1}T$ ## 逆向運動學（IK） - $\theta_1, \theta_2, \theta_3=f^{-1}(P)$ ### 問題 #### 多重解（冗餘） - Ex. - 2 equations（限制） - 3 未知數 - $x=l_1cos(\theta_1)+l_2cos(\theta_2)+l_3cos(\theta_3)$ - $y=l_1sin(\theta_1)+l_2sin(\theta_2)+l_3sin(\theta_3)$ - $\rightarrow$ 多重解 - 同一個點但 path 中的每個 bone 可能可以任意移動 #### 無解 - 姿勢本身無法做到 #### IK 的難處 - 冗餘（多重解） - 動作是否自然 - 關節限制 - 算出來的姿勢 和 一般會做的姿勢 - jacobian matrix - inverse 可能不存在 ### 解 IK - Analytic method（解析解） - Inverse-Jacobian method - Optimization-based method（最佳化） - Example-based method（資料驅動） #### Analytic mehtod（解析解） - Goal $(X,Y)$ ![](https://i.imgur.com/rdQaCxZ.png) <br> - $cos(\theta_T)=\frac{X}{\sqrt{X^2+Y^2}}$ - $\theta_T=cos^{-1}\begin{pmatrix}\frac{X}{\sqrt{X^2+Y^2}}\end{pmatrix}$ - $cos(\theta_1-\theta_T)=\frac{L_1^2+X^2+Y^2-L_2^2}{2L_1\sqrt{X^2+Y^2}}$ - $\theta_1=cos^{-1}(\frac{L_1^2+X^2+Y^2-L_2^2}{2L_1\sqrt{X^2+Y^2}})$ - $cos(180-\theta_2)=\frac{L_1^2+L_2^2-(X^2+Y^2)}{2L_1L_2}$ - $\theta_2=180-cos^{-1}(\frac{L_1^2+L_2^2-(X^2+Y^2)}{2L_1L_2})$ #### Inverse-Jacobian method - 遞迴式計算 ##### Jacobian - $f(\theta)=p$ - $p \in \mathbb{R}^n (n=6$ usually$)$ - end effector - 連結的最終點 - $\theta \in \mathbb{R}^m (m=$ DOFs$)$ - Jacobian：對 p 微分時各自由度對各位置的影響 - $\frac{dp}{dt}=\frac{\partial f(\theta)}{\partial \theta}\frac{d\theta}{dt}=J(\theta)\frac{d\theta}{dt}$ - $J_{ij}=\frac{\partial f_i}{\partial \theta_j}$ - 速度：關節空間 $\rightarrow$ 卡式座標（全域空間） - $\rightarrow V=J(\theta)\dot{\theta}$ ###### Ex. Jocobian for a 2D arm - 2D 機械臂，每個關節自由度為 $1$ （只有一個角度） - $p=\begin{bmatrix} p_x && p_y \end{bmatrix}$ - $f(\begin{bmatrix} \theta_1 \\ \theta_2 \end{bmatrix})=\begin{bmatrix} p_x \\ p_y \end{bmatrix}$ - $J_f=J(\theta)=\begin{bmatrix} \frac{\partial p}{\partial\theta_1} && \frac{\partial p}{\partial\theta_2} \end{bmatrix}=\begin{bmatrix} \frac{\partial p_x}{\partial\theta_1} && \frac{\partial p_x}{\partial\theta_2} \\ \frac{\partial p_y}{\partial\theta_1} && \frac{\partial p_y}{\partial\theta_2} \end{bmatrix}$ ##### 計算 Jocobian（解析） - Ex. 3 個關節，各關節自由度為 $1$ - $\begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} f_1(\theta) \\ f_2(\theta) \end{bmatrix}=\begin{bmatrix} l_1cos\theta_1+l_2cos\theta_2+l_3cos\theta_3 \\ l_1sin\theta_1+l_2sin\theta_2+l_3sin\theta_3 \end{bmatrix}$ - $\begin{bmatrix} \dot{x} \\ \dot{y} \end{bmatrix}=J\begin{bmatrix} \dot{\theta_1} \\ \dot{\theta_2} \\ \dot{\theta_3} \end{bmatrix}$ - $J=\begin{bmatrix} \frac{\partial f_1(\theta)}{\partial\theta_1} && \frac{\partial f_1(\theta)}{\partial\theta_2} && \frac{\partial f_1(\theta)}{\partial\theta_3} \\ \frac{\partial f_2(\theta)}{\partial\theta_1} && \frac{\partial f_2(\theta)}{\partial\theta_2} && \frac{\partial f_2(\theta)}{\partial\theta_3} \end{bmatrix}=\begin{bmatrix} -l_1sin\theta_1 && -l_2sin\theta_2 && -l_3sin\theta_3 \\ l_1cos\theta_1 && l_2cos\theta_2 && l_3cos\theta_3 \end{bmatrix}$ - 多關節、多自由度下，Jacobian 計算複雜且不通用 ##### 計算 Jocobian（幾何） - 假設只考慮 end effort $p$ 的位置 - $p \in \mathbb{R}^3$ - $\rightarrow$ Jacobian：$3\times N$ - $N$：總自由度 - 對於各關節的各自由度，分析 $p$ 如何根據自由度改變 #### 旋轉自由度 - $v=\omega\times r$ - $\frac{dp}{dt}=|\omega|\frac{\omega}{|\omega|}\times r=\frac{d\theta}{dt}a\times r$ - $\frac{dp}{d\theta}=a\times r$ - $\frac{\partial p}{\partial \theta_i}=a_i\times (p-r_i)$ - $a_i=\frac{\omega_i}{|\omega_i|}$: 旋轉軸 朝向（單位長度） - $r_i$: 旋轉軸 位置 - $p$: end effector 位置 - 都要在全域座標系統下 - 多自由度關節：拆成單自由度的多關節 ### 遞迴式 IK - $\theta=f^{-1}(P)$ - $V=J(\theta)\dot{\theta}$ - $\dot{\theta}=J^{-1}(\theta)V$ - $\rightarrow \theta_{k+1}=\theta+\Delta tJ^{-1}(\theta_k)V$ - $t$：遞迴計算的遞增量 - $\Delta t$：小 #### Jacobian 的反矩陣可能不存在 - 非方形矩陣 - pseudo inverse - Singularity - 造成關節速度無限大 - 發生在無論 $\dot{\theta}$ 為多少都無法實現給定的姿勢 ##### Singularity 補救方法 - 增加冗餘 - 加入多餘的自由度 - Jacobian matrix 非方形 #### Pseudo Inverse of the Jocobian - $V=J\dot{\theta}$ - $\rightarrow J^TV=J^TJ\dot{\theta}$ - $\rightarrow (J^TJ)^{-1}J^TV=(J^TJ)^{-1}J^TJ\dot{\theta}$ - $J^+=(J^TJ)^{-1}J^T$ - $\rightarrow J^+V=\dot{\theta}$ ##### 加入更多控制項 - Pseudo inverse 計算使關節角速度為最小的解 - 可能不是自然姿勢 - 加入一個控制項 - 加入前後線性速度不會改變 - 不會影響到 end effctor #### 控制項（Control term） - $J\dot{\theta}=V$ - $\dot{\theta}=J^+V+(J^+J-I)z$ - $C=(J^+J-I)z$：控制項 <br> - $V=JC$ - $V=J(J^+J-I)z$ - $V=(J-J)z=0z=0$ - $\rightarrow$ 控制項 $C$：$J$ 的 $null space$ - $C=(J^+J-I)z$ - $J$ 的 $null space$：對限制條件沒有影響 - $\theta\in nullsapce(J)\Leftrightarrow J\theta=0$ ##### Null Space 效用 - 次要目標（自然姿勢） - $\dot{\theta}=J^+V+(J^+J-I)z$ - $min_z G(\theta)$ - 自然姿勢／關節剛性（關節活動度） - $G(\theta)=\sum_{i}^{}\alpha_i(\theta_{natural}(i)-\theta(i))^2$ ### Optimization-based method（最佳化） - 將 IK 公式化為非線性最佳化問題 - Ex. - minimize $x^2(y+1)+sin(x+y)$ - subject to $x\geq 0 ,y\geq 0$ - Objectve function - Constraint - Iterative algorithm #### Objective Function - $g$：goal，$e$：end effctor - 位置距離 - ${||p_g-p_e||}^2$ - 朝向距離 - ${||{r_x^g}-{r_x^e}||}^2+{||{r_y^g}-{r_y^e}||}^2$ - 位置／朝向權重 - $w{||p_g-p_e||}^2+(1-w)({||{r_x^g}-{r_x^e}||}^2+{||{r_y^g}-{r_y^e}||}^2)$ - $w$：權重值 #### 非線性最佳化 - 限制 - minimize $G(\theta)$ - subject to $\left\{ \begin{matrix} a^T\theta=b_1 \\ a^T\theta \leq b_2 \end{matrix} \right.$ - $a^T\theta=b_1$：關節座標 - $a^T\theta \leq b_2$：關節限制 - 解 - 數值方法 - 通常是區域性最小 - 非全域性 - 跟初始狀態有關係 ### Example-based method（資料驅動） - 運動數據庫 - 插值 - Rose et al., “Artist-directed IK using radial basis function interpolation,” Eurographics’01 - 統計模型 - Grochow et al., “Style-based inverse kinematics,” SIGGRAPH’04 # MotionCapture ## 動作捕捉 ### 使用 Motion Capture #### 動作捕捉？ - 紀錄 3D 即時動作 - 追蹤動作（骨架建立） - 參考點的 3D 座標 - 轉換成角度（IK） - 驅動骨架 #### 優缺點 - 優點 - 動作細節只要有 marker 就能完整 - 缺點 - 不易 - 編輯 - 一般化 - 控制 - 花費高 #### 應用 - 動畫 - 電腦遊戲 - 特效 - （人型）機器人控制 - 互動式角色 #### 捕捉物 - 3D 位置 - $X$, $Y$, $Z$ - roll、pitch、yaw - 誤差 造成： - 關節分離 - 與環境接觸點錯誤 #### 捕捉？ - 可大可小 - 全身 - 臉、手 - 動物 #### 資料使用 - 離線拍攝 - 預先錄製 - 拍攝時處理較少 - 資料庫 - 編輯 - 動作融合 - 線上拍攝（演出式動畫） - 完全靠 動作捕捉 產生 - 直接驅動角色 #### 歷史 - 生物力學 - 步態分析 - 動力學 - 記錄點少 - 手動標記、分析 - 受力狀態、肌肉活動 - 電腦動畫 - 旋轉掃描 - 捕捉影像 - 透明遮罩 追蹤 - 後期處理 - VR 追蹤 - 精確度需求較低 - sensor 較少 #### 流程 - 校正手續 - 動作捕捉 - 骨架預測 - IK 計算 ### 動作捕捉系統 - 光學 - 追蹤每一個 marker - 電磁式 - 電磁場感測 - 6 DOF - 機械式 - 外骨架 - 慣性感測 - 加速度計、陀螺儀 #### 光學 ##### 被動式 - Marker 本身不會送出訊號 - 攝影機： - 紅外線、光感、…攝影機 - 空間解析度 高 - 時間解析度（每秒幀數） 高 - 不適合戶外 - 不能有反光性強的物質 - Marker 貼身（緊身衣） - Marker 可能會互相影響 ##### 主動式 - Marker 自動發出 LED 光束 - 自由設定頻率（避免 marker 混淆） - 可在室外 - 成本便宜 - 精度（解析度）略差 #### 電磁式 - 機電轉換器 - 工具簡單 - 主要成本：sensors - 電磁波干擾 - 精度略差 #### 機械式 - 穿戴外骨架 - 不會受到光線、電磁場干擾 - 不會有 marker 混淆問題 - 沒有範圍限制 - 對運動造成限制 - 不知道絕對位置 <br> - Data glove - 彎曲感測、光學追蹤 - 6 DOFs - 提供力回饋 #### 慣性感測 - Sensors - 陀螺儀 - 加速度計 - 可在戶外 - 校準困難 - 全域座標系統下的位置 不定 - 誤差 #### RGBD Camera - RGB＋深度 攝影機 - 皮膚型變＋骨架動作 #### 技術議題 - 拍攝範圍 - 解析度 - 校正程序 - 不同設備有不同的校正程序 - 精度 - marker 移動範圍 - 環境 - 遮擋、對應 - 捕捉比率 - （Sensor）遮擋／對應 ### 近期 Motion Capture 研究 - Skin - Outdoor - Nonintrusive #### 皮膚（Skin Motion Capture） - Park & Hodgins, SIGGRAPH'06 - 增加 markers - 產生精細的表面模型 - 資料收集、清理 - Skin Animation #### 戶外（Outdoor Motion Capture） - Vlasic et al., "Practical Motion Capture in Everyday Surroundings," SIGGRAPH'07 - 慣性感測器＋超音波測量 - 超音波測量：絕對位置（全域座標系統） #### 非侵入式（Noninstrusive Motion Capture） ### Paper #### Correct MOCAP using high rate IMUs - Kuo et al., Creating impactful characters: correcting human impact accelerations using high rate IMUs in dynamic activities, TOG'19 - FK（Jacobian）預測 IMU 的加速度 - 修正關節角度，使得預測與測量到的 IMU 加速度適配 - 有需要（碰撞力／速度超過一定量）時再執行修正 # MotionEditingSynthesis ## Motion - - 非 $\in \mathbb{R}^n$ - 3 自由度 - 3 自由度 ## 動作編輯 問題 - 特定動作 - 動作捕捉、關鍵影格 - 特定角色、動作、風格 - 保留一部分，改變一部分 ## 動作編輯 Why? - ## 動作編輯 - 時間軸修改 - Time warp / Speed control - $m(t)=m_0(f(t))$ - $f: \mathbb{R}\rightarrow\mathbb{R}$ - ## 時間軸修改 - $m(t)=m_0(f(t))$ - 時間放大縮小：$f(t)=kt$ - 時間平移：$f(t)=t+k$ - Time warping - 插值 - 事件 對齊 - Speed control ### 動態 Time Warping（DTW） - 各影格對應到最適合的 - - 動態規劃$\rightarrow$找到最佳路徑 - 限制 - 不能有負數斜率 - 負數斜率：動作倒播 ## - 放大縮小 - 平移 - 混合 - 過濾 ### 動作混和 - 時間軸要先對齊 - - - $m(t)=am_0(t)+(1-a)m_1(t)$ - $a$：權重值 - 權重根據時間改變 - $m(t)=a(t)m_0(t)+(1-a(t))m_1(t)$ - ## RBF 插值 - RBF types - Guassian - $R(d)=e^{-\beta d^2}$ - Thin plate spline - $R(d)=d^2log(d)$ - Multiquadric - $R(d)=\sqrt{d^2+\beta^2}$ - - - $s(x)=A(x)+\sum_{i=1}^{N}r_iR_i(|x-x_i)$ - $A$： - $r_i$：實數權重 - $R_i$： - Ex. Fit data $(x, y)={(0.15, 1), (0.3, 0), (0.75, 0)}$ - $s(x)=A(x)+\sum_{i=1}^{3}r_iR_i(|x-x_i)$ ## Motion Transition 跳過