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是前後兩幀時刻差距)。

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

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

質點施力

推進力。

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

幾何變換有三個獨立因素:位移、旋轉、縮放。此處只介紹位移,至於旋轉和縮放,做法相同。

彈簧

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

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

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

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

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

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

質量、長度、時間、力量係數,放到螢幕畫面,必須重新調整,相當麻煩。

想讓參數跟真實世界一致,則必須考慮:像素寬度與真實長度的比例、重新繪圖的時間間隔。相關術語是dpi和frame rate。

Fluid Simulation

Fluid Simulation

流體模擬有兩種策略:

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

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

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

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

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

運動。考慮兩種力:

一、壓縮力:法線方向。可以類比為推進力。

二、黏滯力:切線方向。可以類比為摩擦力。

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

壓縮力設定成彈簧力。粒子侵入距離,乘以彈性係數。

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

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

黏滯力設定為阻尼力。相對速度的法線分量,乘以阻尼係數。

黏滯應該是切線分量吧?也對!切線分量=相對速度-法線分量。黏滯力=緩速&阻尼力。其實只多了個緩速。

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

流動。加速度乘以時間差,得到速度變化。速度乘以時間差,得到移動距離。

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

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

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

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

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

粒:空氣與水

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

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

Fluid Simulation(Under Construction!)

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

格子。建立100×100個格子。數學術語是

只紀錄速度。粒子密度均勻,不必紀錄數量。粒子合力為零,不必紀錄加速度。

配置。兩種方式,此處採用staggered grid。

colocated grid:速度、壓力,皆在格中央。
staggered grid:速度在格線,壓力在格中央。

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

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

此處採用no-slip。水不可穿牆,牆面法線速度是零。令水格子是正速度、牆格子是負速度。兩者內插之後,牆面是零速度。

運動。考慮兩種現象:

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

二、平流:格中粒子依照自身速度移動,其速度也隨之移動。

粒:壓縮力、黏滯力。格:擴散、平流。粒微觀,格宏觀。有趣的是,迄今仍無人發現微觀與宏觀之間的數學關係式。

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

數學術語是穩定條件CFL condition。格子邊長Δx越窄,時間差距Δt越小。格子細膩,步輻短小,動畫步調緩慢。穩定條件影響了動畫步調,導致我們無法算得太細膩。

投影。令格中粒子流入流出相等,其速度也隨之如此。

數學術語是令速度場散度為零。減去其散場。

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

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

一、粒:散布大量粒子,沿著速度場跑。

二、格:建立粒子數量場(粒子濃度場),沿著速度場跑。

速度場繪圖方式:粒

隨機散布大量粒子。

流動。粒子沿著速度場跑。若步幅太小,則調整步幅。

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

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

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

速度場繪圖方式:格

建立粒子數量場。

流動。粒子數量沿著速度場跑。若步幅太小,則調整步幅。

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

流動

流動擁有大量細節:步幅、步向、步法、校正、外插、內插。

步幅。流動不得跨越格子,否則軌跡不夠精確、水滴容易疊合。

步向。兩種方向,前進或倒退。

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

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

步法。以邪門歪道撥正軌跡。三種步法:Euler method、predictor-corrector method、midpoint method。

大家習慣採用倒退步向、Euler method步法。兩者合稱semi-Lagrangian method。

校正。以邪門歪道調校速度場,避免能量佚失。兩種方法:modified MacCormack method、reflection method。

modified MacCormack method
1. 更新速度場。V0 -> V1
2. 速度變號,再更新速度場。V1 -> V2
   理論上回復原狀:V0 = V2
   實際上產生誤差:V0 ≠ V2
3. 來回更新兩次,因此更新一次的誤差是一半:(V2 - V0) / 2
4. 正確答案是更新一次,再扣掉更新一次的誤差:V1 - (V2 - V0) / 2
5. 裁切答案,不超過V1四周的最大值和最小值。
reflection method [Zehnder 2018]
1. advect,走半步。V½ = V0 + V0 ⋅ ½Δt
2. project,減掉散場。Vp = V½ - div_part(V½)
3. reflect,再減掉一次散場。Vr = V½ - div_part(V½) - div_part(V½)
4. advect,走半步。V1 = Vr + Vp ⋅ ½Δt
5. project,減掉散場。V = V1 - div_part(V1)

外插。如果採用倒退步法,則水域之外也要有速度。解法:一旦穿牆,立即挪回牆內,如此僅需設定牆壁速度,不必設定牆外速度。先前的牆壁小節,已經設定牆壁速度。

粒子數量如法炮製。

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

前進與外擴:根據面積大小分攤。

倒退與內插:一次內插、Catmull-Rom interpolation。

格:空氣與水

模擬流程。源自這套教材

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

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

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

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

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

level set:水面到格子的距離,建立距離場,沿著速度場跑。距離場移動,距離必錯,需要修正距離場。重算水面,重算距離場。

投影。設定空氣和牆壁的壓力和速度。

重力場是諧場,投影不會刪除諧場。要如何解決?

空氣速度:零。
空氣壓力:零。理論上是一大氣壓。
牆壁速度:零。
牆壁壓力:鄰水壓力。理論上是水壓:水深乘以密度。

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

最短距離:找到距離最近的水面格子,速度設成相同。

逐層擴散:從水面開始,一層層設定速度。九宮格的速度平均值,只取已有速度的格子。

Fluid Simulation(Under Construction!)

格流動

模擬流程。源自這篇文章這份講義這本書籍這本書籍

步幅。Δt非常大,以便製造流體動畫。

配置。此處採用colocated grid。

牆壁。設定牆壁速度、粒子數量。

運動。擴散與平流,先前一齊計算,現在依序計算。

擴散。速度向四周擴散。Δt很大,必定違背CFL condition,解法是改成backward Euler method。

偷工減料,沒數鄰居。牆壁速度,本來不可計入,現在改成外插速度。導致靠牆格子速度略減,無傷大雅。

平流。粒子數量場、速度場,一起沿著速度場跑。

投影。校正速度,使得處處出入相等。

偷工減料,沒數鄰居。牆壁壓力,本來不可計入,現在改成鄰水壓力。導致靠牆格子壓力略增,無傷大雅。

格流動:空氣與水

模擬流程。源自這個專案

我的實作還有許多問題尚未解決:

一、Δt和h省略了。diffuse省略了。

二、總是漏水。我猜測原因是project遞推次數太少,壓力沒有收斂,速度太快水穿牆。不動點遞推法還是太慢了,必須換成預條件共軛梯度法PCG。

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

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

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

Fluid Simulation(Under Construction!)

本文未涉及的演算法

粒格混和,衍生許多演算法:粒連續SPH、粒離散SEC、粒方程PBD、粒化格PIC、格八方RBM、格中粒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

相關資源

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/fluid_compare.php

Navier-Stokes Equation

兩種形式:

pressure-velocity formulation          div grad f =  laplace F
streamfunction-vorticity formulation   curl curl F = - laplace F   (2D)

一、速度與壓力。可精確模擬層流

二、等號兩邊同時求旋度,得到渦旋。可精確模擬亂流,呈現leapfrogging vortex ring、cavity flow、microburst等自然現象。

Schrödinger Equation

計算幾何有個手法,讓實數變複數:二維座標(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

Fracture

Deformation

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

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