Simulation

Simulation

模擬。真實現象化作數值,以數值模仿真實現象。

Mechanics

力學。質量、距離、時間,討論三者之間的關係。

http://www.apress.com/9781430263371
http://graphics.stanford.edu/courses/cs348c/
http://cs448z.stanford.edu/
http://www.cs.cmu.edu/~scoros/cs15467-s16/index.html
http://www.cs.cmu.edu/~scoros/cs15869-s15/index.html
http://allenchou.net/2013/12/

System

系統。大量物體,互相連動。

n-body       https://en.wikipedia.org/wiki/N-body_simulation
cloth        http://www.cs.cornell.edu/projects/YarnCloth/
hair         http://www.andyselle.com/papers/9/
soft object  http://www.alecrivers.com/fastlsm/
water wave   http://www.cemyuksel.com/research/waveparticles/
matter       http://chemists.princeton.edu/torquato/

UVa 11574

物理學家的分類方式

mechanics  力學
 - statics             有力,呈穩態(處處總和為零)
 - kinematics          無力(無加速度)
 - dynamics = kinects  有力(有加速度)

system    一堆東西混在一起
 - structure   不動
 - mechanism   會動

Particle Simulation

Particle Simulation

牛頓發現運動定律F=ma。歐拉發現物體運動可以簡化成質心運動,物體軌跡等於質心軌跡。從質點開始介紹,事情比較簡單。

質點移動

質點。擁有位置、速度、加速度。

移動。加速度改變了速度,速度改變了位置。

兩種方式:數值解(數值模擬)、符號解(公式解)。

兩者優缺點互補,通常採用數值模擬。優點:簡單明快。缺點:誤差逐步累積。

步法。數值模擬,Δt並非無限微小,導致軌跡逐漸偏斜。大家發明各種步法,盡量撥正軌跡。

兩種步法:Euler method、Verlet method。

兩者優缺點互補,通常採用Euler method。優點:簡單明快。缺點:軌跡較歪。

時間。以無窮迴圈,更新時間、更新位置、重新繪圖。

兩種更新時間方式:定量增加(時間差Δt是定值)、浮動增加(時間t是當前時刻,時間差Δt是前後兩幀時刻差距)。

兩者優缺點互補,建議採用定量增加。優點:步伐穩定,軌跡端正。缺點:動畫播放速度不符合真實時間流逝。

繪圖。質點畫成什麼形狀都行。質點位置視作像素座標。

質點施力

推進力。F = ma。

摩擦力。速度乘以摩擦係數等於摩擦力。

彈簧

彈力。可以類比為推進力。

虎克定律:位置差異乘以彈性係數等於彈力。

阻尼力。可以類比為摩擦力。

速度乘以阻尼係數等於阻尼力。

當力不在水平垂直方向,必須求得水平分量、垂直分量。

阻尼力,當速度不在彈簧方向,必須投影至彈簧方向。

位移、旋轉、縮放

幾何變換有三個獨立因素:位移、旋轉、縮放。

先前只介紹位移。此處同時使用位移、旋轉、縮放。

活用三種獨立因素,調整彈簧參數,製作各種動畫特效:

http://allenchou.net/2015/04/game-math-precise-control-over-numeric-springing/

參數設定

參數。質量、長度、時間、彈性係數、阻尼係數,設定成真實世界的數值。讓螢幕座標、真實世界座標兩者一致。我沒有研究。

兩個需要考慮的項目:像素寬度與真實長度的比例(dpi)、重新繪圖的時間間隔(frame rate)。

Fluid Simulation

Fluid Simulation

相關資源

http://bugman123.com/FluidMotion/
http://www.mijagourlay.com/fluid
https://www.cs.clemson.edu/savage/pba/
https://fluidenginedevelopment.org/
https://developer.nvidia.com/
http://pof.tnw.utwente.nl/research
http://panoramx.ift.uni.wroc.pl/~maq/eng/index.php

演算法一覽

流體模擬有兩種策略:

粒:紀錄每一個水滴的位置、速度、加速度(力)。

格:紀錄每一個位置的水滴總數量、總速度、總加速度(力)。

數學術語分別是質點法有限元素法

粒格衍生許多演算法:粒連續SPH、粒離散SEC、粒方程PBD、粒化格PIC、格八方LBM、格中粒MAC、格中格MG

近期的演算法:PCISPHPIC/FLIPAffine PIC、……。

關鍵字一覽

本文並未涉及這些內容。

粒子間作用力  Lennard-Jones potential、intermolecular force
內聚力、附著力 cohesion、adhesion
浮力、摩擦力  buoyancy、friction
障礙物     immersed boundary method、Werner-Wengle wall function
多相流     multiphase flow
交融      Rayleigh-Taylor instability、Kelvin-Helmholtz instability
層流、亂流   laminar、turbulence (mean + fluctuation)
無因次量    Reynolds number、Froude number
溫度、能量   temperature、energy
角動量     angular monentum、vorticity、helicity
流線      streamline、pathline、streakline、timeline
底形      bedform
氣泡流、氣塊流 bubble flow、slug flow
顆粒流     granular flow

Fluid Simulation (Particle)

模擬流程。源自LiquidFun說明文件這篇文章

粒子。建立100個粒子,隨機散布。

粒子擁有位置、速度、加速度(力)。

運動。考慮兩種力。

一、壓縮力:法線方向。設定為彈簧力。

二、黏滯力:切線方向。設定為阻尼力。

壓縮力。粒子互相推擠,導致外散。

粒子侵入距離×彈性係數=壓縮力。

距離改成距離比值,並且升高次方。低次方令粒子塌陷,高次方令粒子鞏固(彈性係數也要隨之增加)。水不可壓縮,理論上次方值非常大,實務上取平方就足夠耐看了。

黏滯力。粒子互相摩擦,導致連動。

相對速度的切線分量×阻尼係數=黏滯力。

切線分量改成法線分量,簡化計算。副作用是多了個緩速,無傷大雅。法線分量=相對速度-切線分量。相對速度乘上係數之後,效果是緩速。

鄰居。兩層迴圈窮舉所有點對,O(N²),太慢了。採用資料結構uniform grid,檢查周圍九宮格,O(N+K),快多了。

移動。加速度×時間=速度。速度×時間=移動距離。

步幅。移動不得穿越粒子,否則粒子可能高速噴射。保守策略是移動距離小於相間距離。Δt足夠小,力與速度足夠小。

牆壁。粒子撞牆有兩種解法:

一、粒子反彈:位置鏡射回來、速度顛倒方向。

二、牆如粒子:牆給予粒子壓縮力。

繪圖。粒子畫成圓形、正方形、三角形,隨你開心。

粒:空氣與水

重力。粒子添加一道力。理論上是9.8,實務上自訂。

繪圖。粒子不要畫成圓球,而是畫成blobby surface。想要更擬真,則需要3D graphics的知識。

Fluid Simulation (Grid)

模擬流程。源自這套教材這本書籍

格子。建立40×40個格子。

只紀錄速度。不紀錄數量:假設粒子密度均勻不變,假設數量是常數。不紀錄加速度:加速度乘上時間,直接添加到速度。

配置。兩種方式。

colocated grid:速度在格中央。
staggered grid:X速度在格左右,Y速度在格上下。

此處採用staggered grid。兩點優勢:一、水衝撞牆,會往兩側散開,不會只往其中一側流動。二、計算散度更加精確,不會省略中央速度。

上下添加一排X速度,以便內插上下牆壁附近的X速度。左右添加一排Y速度,以便內插左右牆壁附近的Y速度。

牆壁。四種方式。數學術語是邊界條件

  no-slip condition:牆壁沾黏,切線速度是特定值。
free-slip condition:牆壁光滑,切線速度等於鄰水速度。
   inflow condition:牆壁插管,法線速度是特定值。
  outflow condition:牆壁虛設,法線速度等於鄰水速度。

此處採用no-slip。水被牆壁帶動,牆壁切線速度是自訂數值;水不可穿牆,牆壁法線速度是零。

牆內速度、牆外速度,內插得到牆壁速度。以此反推牆外速度。

運動。考慮兩種現象。

diffuse:擴散。格中粒子均勻四散,其速度也隨之均勻四散。

         ∂          ∂       ∂         ∂          ∂       ∂      
         ―― u = ν ( ――― u + ――― u )   ―― v = ν ( ――― v + ――― v )
         ∂t         ∂x²     ∂y²    ,  ∂t         ∂x²     ∂y²
               ^^^                          ^^^
               這兩個是擴散速率,希臘字母ν,唸做nu,不是英文字母v。

   flow:流動。格中粒子依照自身速度集體移動,其速度也隨之集體移動。

         ∂          ∂       ∂         ∂          ∂       ∂      
         ―― u = - ( ―― uu + ―― vu )   ―― v = - ( ―― uv + ―― vv )
         ∂t         ∂x      ∂y     ,  ∂t         ∂x      ∂y     

數學術語是Navier-Stokes EquationEuler Method

步幅。移動不得穿越格子,否則速度可能高速逸散。保守策略是移動距離小於格子寬度。

數學術語是穩定條件CFL condition。格子邊長Δx越窄,時間差距Δt越小。格子越細膩,步幅越短小,動畫越緩慢。

不可壓縮。格中粒子速度,出入總量相等,流動順暢。

incompressibility:不可壓縮。

                   ∂      ∂       
                   ―― u + ―― v = 0
                   ∂x     ∂y      

按理來說,擴散、流動、不可壓縮必須同時聯立,一口氣求得新速度。不幸的是,大家尚未發現漂亮的解法。別無選擇,只好逐個計算。首先擴散與流動,接著校正速度場,使之不可壓縮。

數學術語是散旋諧分解。依序計算散度、散勢(壓力)、散場。速度場減去散場,使得速度場的散度變成零,成為無散場。

數學術語是投影。給定速度場,找到平方誤差最小的無散場。

鄰居。投影時,牆壁不計入。牆壁壓力設為零,做為無效的分子;事先算好鄰居有幾格,做為分母。

求解。一次方程組求解,兩種演算法。

SOR:稀疏矩陣,適合鬆弛法。容易實作,但是收斂速度慢。
PCG:半正定矩陣,適合共軛梯度法。請見這篇講義

數學術語是Discrete Poisson Equation

繪圖。速度場通常畫成軌跡圖、箭矢圖。亦得入境隨俗:

粒:散布大量粒子,沿著速度場跑。
格:建立粒子數量場(粒子濃度場),沿著速度場跑。

速度場繪圖方式:軌跡圖

速度場繪圖方式:箭矢圖

速度場繪圖方式:粒

粒子。隨機散布大量粒子。

繪圖。粒子畫成什麼形狀都行。

流動。粒子沿著速度場跑。總共需要考慮:內插、步幅、步法、牆壁。

內插。取得更精確的速度。速度位於格線,加0.5微調位置。

步幅。採用更大的步幅,以便製作即時動畫。

步法。三種步法。以邪門歪道撥正軌跡。大家習慣採用one-step method,簡單走一步。數學術語是積分方法。

one-step method
1. 抓本地速度,走一步。

predictor-corrector method
1. 抓本地速度,走一步,到終點。
2. 抓本地與終點的平均速度,從頭重新走一步。

midpoint method
1. 抓本地速度,走半步,到中點。
2. 抓中點速度,從頭重新走一步。

牆壁。Δt畢竟不是無限微小,靠牆的水容易一步穿牆。穿牆粒子,放回牆內。

速度場繪圖方式:格

格子。建立粒子數量場。

繪圖。每一格根據粒子數量(粒子濃度),決定顏色深淺。

流動。粒子數量沿著速度場跑。總共需要考慮:內插、步幅、步向、步法、牆壁、內插。

內插。取得更精確的速度。速度位於格線,加0.5微調位置。

步幅。採用更大的步幅,以便製作即時動畫。

步向。兩種方向。

forward
前進,往後補值。
優點是動量守恆。
缺點是空格與疊格。解法是縮小步幅、減少Δt。

backward
倒退,往前取值。
優點是流向精確。
缺點是零速度處無法流入、零速度處無限流出。解法是強制擴散。

步法。大家習慣採用backward步向、one-step method步法,兩者合稱semi-Lagrangian method。

牆壁。Δt畢竟不是無限微小,靠牆的水容易一步穿牆。一旦穿牆,立即挪回牆內。

內插。更精確的粒子數量。副作用是擴散。兩種方式。

前進與分配:根據面積大小分攤。
倒退與內插:一次內插、或者Catmull-Rom interpolation。
      牆壁事先設定粒子數量,方便內插。

步幅增長

先前章節,計算速度場,避免增長步幅,以滿足CFL condition;繪製速度場,作弊增長步幅,以便讓動畫順暢。然而此舉導致繪圖結果不符合真實流體。

事實上,計算速度場,可以增長步幅,但是必須改變擴散與流動的演算法。請見這篇文章

步幅。計算速度場、繪製速度場,步幅一致,不必作弊。

擴散。速度向四周擴散。

數學術語是implicit Euler method。

流動。粒子數量場沿著速度場跑,速度場也跟著一起跑。

數學術語是semi-Lagrangian method。

守恆。Δt變大,流動之後誤差變大,各個物理量不再守恆。必須校正速度場,令物理量守恆。兩種方法。

質量守恆:流動前後,粒子數量總和不變。
動量守恆:流動前後,粒子動量總和不變。
能量守恆:流動前後,粒子動能總和不變。
projection method
1. flow,走一步。V1 = V0 + V0 ⋅ Δt
2. project,減掉散場。V1p = V1 - div_part(V1)

reflection method [Zehnder et al 2018]
1. flow,走半步。V½ = V0 + V0 ⋅ ½Δt
2. project,減掉散場。V½p = V½ - div_part(V½)
3. reflect,再減掉一次散場。V½r = V½ - div_part(V½) - div_part(V½)
4. flow,走半步。V1 = V½r + V½p ⋅ ½Δt
5. project,減掉散場。V1p = V1 - div_part(V1)

校正。Δt變大,流動之後誤差變大。有人校正速度場。

modified MacCormack method
1. 更新速度場。V0 -> V1
2. 速度變號,再更新速度場。V1 -> V2
   理論上回復原狀:V0 = V2
   實際上產生誤差:V0 ≠ V2
3. 來回更新兩次,因此更新一次的誤差是一半:(V2 - V0) / 2
4. 正確答案是更新一次,再扣掉更新一次的誤差:V1 - (V2 - V0) / 2
5. 裁切答案,不超過V1四周的最大值和最小值。

格:空氣與水

模擬流程。源自這個專案這份講義這套教材

水域。以粒或格,紀錄水域資訊,沿著速度場跑。四種解法。

marker particles
水域建立排列整齊的大量粒子,沿著速度場跑。
檢查每一格,若格中駐留足夠粒子,則視作水域。
粒子流動,間距改變,需要重置粒子。

front tracking
水面建立網格,沿著速度場跑。
網格流動,間距改變,需要修正網格。
間距太近則刪除一點,間距太遠則插入新點。

volume of fluid
建立水量場,沿著速度場跑。
格子流動,水量分配給目的地周遭四格,根據面積比例。

level set
水面到格子的距離,建立距離場,沿著速度場跑。
距離場流動,距離必錯,需要修正距離場。
重新估計水面位置,重新計算水面到格子的距離。

此處採用level set。建立距離場,水中為負值,水外為正值,水面為零。

我的實作,牆壁的距離值設為半格寬度。我沒查到相關資料。

重算距離場。兩個步驟。

水面:距離異號的相鄰兩格,做一次內插,找到距離為零之處。
水內水外:從水面開始BFS遍歷每一格,並且計算距離。
     八鄰居取距離最小者,只取已有距離的格子。

我的實作,牆壁與水沒有做一次內插。我沒查到相關資料。

外插。如果採用倒退步法,則空氣必須有速度,而水才能流入空氣。故以水域速度設定空氣速度。兩種解法。

最短距離:找到距離最近的水面格子,速度設成相同。
逐層擴散:從水面開始,一層層設定速度。
     八鄰居的速度平均值,只取已有速度的格子。

我的實作,距離場的計算順序不正確。既不是最短路徑Dijkstra,也不是逐層設定BFS。導致速度外插有時候優先遭遇距離較小、但是離水面較遠的孤立格子。目前的應急措施是塞回queue。

不可壓縮。水域才投影,水外不必投影。

求解。水域才求解,水外不必求解。空氣壓力為零,須採計。

牆壁速度:方便起見設為鄰水速度外插。 理論上是零。
空氣速度:方便起見設為水面速度外插。 理論上是零。
牆壁壓力:不計,方便起見設為零。   理論上是水壓:水深乘以密度。
空氣壓力:採計,方便起見設為零。   理論上是一大氣壓。

重力。垂直速度,添加常數。

補充說明:

一、redistance可以跟project擺在一起,視作距離場校正;redistance也可以跟outerior擺在一起,視作距離場外插,視作flow的事前準備工作。我覺得後者是比較好的。以程式碼結構來說,速度場外插和距離場外插是可以合併一起做的。

二、level set是舊方法了。有個新方法是multigrid level set。請參考《Real-Time Eulerian Water Simulation Using a Restricted Tall Cell Grid》,然而這是NVIDIA的專利。

延伸閱讀:微觀與宏觀

粒:壓縮力、黏滯力。格:擴散、流動、不可壓縮。

粒微觀,格宏觀。有趣的是,迄今無人發現微觀與宏觀之間的數學關係式。

擴散包含了壓縮力和黏滯力。然而大家習慣將擴散視作黏滯,將雷諾數視作黏滯程度。雖然不完全正確,但是容易理解。

延伸閱讀:advect()命名錯誤

許多流體模擬文獻,將flow()誤植為advect(),將流動誤認為平流。

flow()是流動(連續方程式且密度為常數1)。project()讓流動變得不可壓縮。flow()和project()合體之後才是平流(平流方程式且密度為常數1)。

Continuity Equation

連續方程式。描述流動守恆的方程式。一個地點的物理量之所以增加減少,是因為跟隔壁跑來跑去。不會無中生有,不會無端消失。

時間變化。這個時刻、上個時刻的物理量差距。

物理量可以是質量、體積、力、………。

∂
―― q                             ---> q̇
∂t

空間變化。這個地點、隔壁地點的物理量差距。考慮流動速度。

物理量必須適合各維度加總,例如質量、體積、………,。

∂       ∂    
―― qu + ―― qv                    ---> div(qu)
∂x      ∂y   

連續方程式。時間變化=空間變化。

∂        ∂       ∂          
―― q + ( ―― qu + ―― qv ) = 0     ---> q̇ + div(qu) = 0
∂t       ∂x      ∂y         
^^^^   ^^^^^^^^^^^^^^^^^
time   space difference

Advection Equation

平流方程式。水位差距與流量成正比。水位差距會移動。

連續方程式,拆成平流與壓縮。微分的乘法公式:前微後不微、前不微後微。

∂          ∂        ∂            ∂      ∂         
―― q + ( u ―― q + v ―― q ) + q ( ―― u + ―― v ) = 0
∂t         ∂x       ∂y           ∂x     ∂y        
       ^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^
       advection               compression

平流。物理量往隔壁流動,差距越大,流量越大。

    ∂        ∂     
( u ―― q + v ―― q )              ---> u dot grad(q)
    ∂x       ∂y    

壓縮。物理量聚集或者散開。

    ∂      ∂     
q ( ―― u + ―― v )                ---> q div(u)
    ∂x     ∂y    

不可壓縮。壓縮項為零,速度的散度為零。速度出入總量相等,不生不滅;物質流動順暢,不推不擠。

    ∂      ∂     
q ( ―― u + ―― v ) = 0            ---> q div(u) = 0
    ∂x     ∂y    

平流方程式。時間變化=平流。

∂          ∂        ∂         
―― q + ( u ―― q + v ―― q ) = 0   ---> q̇ + u dot grad(q) = 0
∂t         ∂x       ∂y        
^^^^   ^^^^^^^^^^^^^^^^^^^
time   advection

有人簡寫成大寫D,稱為「質點導數」。

D
―― q = 0
Dt

Navier-Stokes Equation

流體方程組。三種式子同時聯立。請見教學網頁教學講義

一、密度:連續方程式。

時間變化=空間變化。

∂        ∂       ∂          
―― ρ + ( ―― ρu + ―― ρv ) = 0
∂t       ∂x      ∂y         

二、動量密度:連續方程式,再追加兩種力。

時間變化+空間變化=自身位勢(壓力)+相互動勢(應力)。

{  ∂         ∂        ∂            ∂        ∂        ∂       
{  ―― ρu + ( ―― ρuu + ―― ρvu ) = - ―― p + ( ―― τ   + ―― τ   )
{  ∂t        ∂x       ∂y           ∂x       ∂x  ˣˣ   ∂y  ˣʸ  
{  
{  ∂         ∂        ∂            ∂        ∂        ∂       
{  ―― ρv + ( ―― ρuv + ―― ρvv ) = - ―― p + ( ―― τ   + ―― τ   )
{  ∂t        ∂x       ∂y           ∂x       ∂x  ʸˣ   ∂y  ʸʸ  
   ^^^^^   ^^^^^^^^^^^^^^^^^^^     ^^^^   ^^^^^^^^^^^^^^^^^^^
    time          space            intra         inter       
 difference     difference         force         force       

三、能量密度:我不熟悉,就不講了。

Navier-Stokes Equation for Water

水是流體的特例。因此方程組可以簡化。

一、水滿足牛頓黏滯定律:應力與速度梯度成正比。

因此應力簡化成擴散。

  ∂        ∂     
  ―― τ   + ―― τ  
  ∂x  ˣˣ   ∂y  ˣʸ

  ∂      ∂        ∂      ∂     
= ―― ( μ ―― u ) + ―― ( μ ―― u )
  ∂x     ∂x       ∂y     ∂y    

      ∂       ∂      
= μ ( ――― u + ――― u )       ---> μ laplace(u)
      ∂x²     ∂y²    

二、水幾乎不可壓縮:速度散度為零。

因此空間變化簡化成平流。

  ∂        ∂     
  ―― ρuu + ―― ρvu
  ∂x       ∂y    
  ^^^^^^^^^^^^^^^
  space difference

      ∂         ∂              ∂      ∂     
= ( u ―― ρu + v ―― ρu ) + ρu ( ―― u + ―― v )
      ∂x        ∂y             ∂x     ∂y    
  ^^^^^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^
  advection                  compression = 0

      ∂         ∂      
= ( u ―― ρu + v ―― ρu )     ---> u dot grad(ρu)
      ∂x        ∂y     

三、水幾乎密度均勻不變:密度是常數。

因此時空變化可以一併提出密度。

  ∂           ∂         ∂      
  ―― ρu + ( u ―― ρu + v ―― ρu )
  ∂t          ∂x        ∂y     

      ∂          ∂        ∂       
= ρ [ ―― u + ( u ―― u + v ―― u ) ]     ---> ρ [ u̇ + u dot grad(u) ]
      ∂t         ∂x       ∂y      

水的Navier-Stokes Equation。教科書通常只介紹此版本。

{ ρ [ u̇ + (u dot grad(u)) ] = - grad(p) + μ laplace(u)
{ div(u) = 0
{ ρ ( u̇ + u·∇u ) = -∇p + μ ∆u
{ ∇·u = 0
{ u̇ + u·∇u = -∇p/ρ + ν ∆u     (let μ/ρ = ν)
{ ∇·u = 0

Navier-Stokes Equation for 2D Water

水的Navier-Stokes Equation,二維的情況下,有兩種形式。

一、壓力與速度(原式):可精確模擬層流

二、流函數與渦旋:可精確模擬亂流。例如自然現象leapfrogging vortex ring、microburst。

推導過程請見這篇講義。原式套用旋度,速度改成位勢。

pressure-velocity formulation
{ u̇ + (u dot grad(u)) = -(grad(p) / ρ) + ν laplace(u)
{ div(u) = 0

streamfunction-vorticity formulation
{ ̇ω - (grad(ψ) cross grad(ω)) = ν laplace(ω)
{ laplace(ψ) = -ω

Schrödinger Equation for Water

計算幾何有個手法,讓實數變複數:二維座標(x,y)改成複數x+yi,二維座標位移、縮放、旋轉改成複數加法、倍率、乘法。

流體力學也有個手法,讓實數變複數:Navier-Stokes equation改成Schrödinger equation,三維實數改成二維複數,質量(密度)改成複數長度平方,速度改成複數角度。請見這篇論文

Solid Simulation(Under Construction!)

Solid Simulation

最佳化與物理現象

物理  丨數學
一一一一十一一一一一一一一一一
力   丨向量         
合力  丨線性組合(加權總和) 如果有很多力,可以直接乘上倍率再相加。
力>位能丨積分         力對位置積分=位能。
位能>力丨微分         位能對位置微分=力。
位能  丨二次型        拋物面函數、凸函數,有唯一最小值。
物理  丨數學    丨位能         力        
一一一一十一一一一一一十一一一一一一一一一一一一一一一一一一一一
彈力  丨微分(梯度)丨0.5 k (x - l)²  丨k (x - l)
約束力 丨微分(梯度)丨0.5 k c(x)²     丨k c(x) c′(x)
慣性運動丨梯度等於零 丨min 位能       丨力 = 0
靜力平衡丨梯度等於零 丨min 位能總和     丨合力 = 0
施加外力丨拉格朗日乘數丨min 位能 st 約束能丨力 + λ ⋅ 約束力 = 0

例如彈簧系統。統計所有彈簧的彈力位能,求最小值,求最小值所在位置(每個彈簧的端點座標)。梯度等於零,就是靜力平衡,就是穩定狀態。實際應用諸如建築結構分析、化學結構分析。

例如軌道運動。物體位置限制在軌道上面,動能與位能的總和是常數。根據拉格朗日乘數,限制能量大小,等同施加外力;此例當中就是施加向心力。實際應用諸如太空衛星。

Collision

http://box2d.org/
https://code.google.com/archive/p/box2d/downloads
https://www.atmos.illinois.edu/courses/atmos100/userdocs/3Dcollisions.html
http://en.wikipedia.org/wiki/N-body_problem

Deformation

http://en.wikipedia.org/wiki/Soft_body_dynamics

《The Linearized Theory of Elasticity》

《Continuum Mechanics Theory》

force: F
displacement: ΔL
stress: σ = F/A  ---> df/dx²        area: A
strain: ε = ΔL/L ---> du/dx = ∇ₓu   length: L
stress-strain curve: 
hooke: σ = Eε                       young modulus / stiffness tensor: E
hooke: f = kΔL
strain energy:  U = 1/2Vσε = 1/2fΔL
elastic energy: U = 1/2kΔL²
deformation: F(x)
deformation gradient (transformation matrix): ∇F(x)ᵀ = J ---> F
displacement gradient: ∇u = Fᵀ-I
Cauchy infinitesimal strain tensor (even part):
E = [(F-I)+(F-I)ᵀ]/2 = (F+Fᵀ)/2-I = (∇u + ∇uᵀ)/2
Cauchy infinitesimal rotation tensor (odd part):
R = [(F-I)-(F-I)ᵀ]/2 = (F-Fᵀ)/2-I
Green finite deformation tensor:
C = FᵀF
Green finite strain tensor:
E = (C-I)/2 = (FᵀF-I)/2 = (∇u + ∇uᵀ + ∇uᵀ∇u)/2
strain->stress: Eᵀ = E
positive eigenvalue in strain tensor -> lengthen
negative eigenvalue in strain tensor -> shorten
reflection in rotation tensor -> shorten?
Poisson's ratio: dεy / dεₓ
Lamé's coefficients: 
Navier-Cauchy Equation
1. strain-displacement:   E = 1/2(∇u + ∇uᵀ)
2. equilibrium:           div(S) = 0 and S = Sᵀ
3. stress-strain (hooke): S = C[E]     stiffness tensor (order-4): C

Fracture

Strand

Cloth

Crowd Simulation(Under Construction!)

Crowd Simulation

http://gamma.cs.unc.edu/DCrowd/
http://gamma.cs.unc.edu/PLE/
http://mrl.snu.ac.kr/research/ProjectMorphableCrowds/MorphableCrowds.html
http://web-ext.u-aizu.ac.jp/~shigeo/research/formation/

Steering Behaviors

根據角色的位置及速率,進而採取行動,讓角色有著智慧。

http://www.red3d.com/cwr/steer/

Motion(Under Construction!)

Motion

動作。讓虛擬模型產生動作,讓實體機械產生動作。

Locomotion

力與姿態的改變。

比如走路姿態。無論是走路、跑步、爬行,四肢的循環時間總是一致(除非跛腳),而相位則不一致。特定的走路動作,有著特定的相位差。

http://graphics.ucsd.edu/courses/cse169_w15/slides/CSE169_13.pdf

備註

鍵盤控制。上下左右切換很快時,有時候同時按到左和右(上和下)。如果沒有正確處理,角色就會卡住不動。

一般來說,左和右兩者都按著,是以最後按下去的按鍵為主。左和右放開其中一個,是以還按著的按鍵為主。

作業系統處理鍵盤事件,是循序的;兩個鍵盤事件,必定一前一後。就算玩家一口氣按下多個按鍵,寫程式時仍是逐一處理。

Motion Analysis(Under Construction!)

Motion Capture

捕捉。觀測實物,擷取動作。

Motion Retargeting

重新定位。建立模型與實物的對應關係。

Motion Transmission

傳動。組裝實物,使之連動。

Motion Control

控制。組裝實物,實施動作。

Motion Planning

規劃。訂立規矩,尋找動作。

http://homes.cs.washington.edu/~todorov/
http://www.zhihu.com/question/26944678
http://www.vccoo.com/v/90589d
Graph Optimization
http://censi.mit.edu/pub/research/2013-mole2d-slides.pdf