Simulation

質點移動

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

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

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

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

步法。數值模擬當中,dt不是無限微小,軌跡必定逐漸偏斜。於是大家發明各種步法,盡量撥正軌跡。兩種步法:Euler Method、Verlet Method。

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

時間。以無窮迴圈,更新時間、更新位置、重新繪圖。兩種更新時間方式:定量增加(時間差dt是定值)、浮動增加(時間t是當前時刻,時間差dt是前後兩幀時刻差距)。

兩者優缺點互補,建議採用定量增加。優點:步伐穩定,軌跡端正。缺點:當電腦效能不穩定,則動畫走走停停。

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

質點施力

推進力。

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

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

彈簧

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

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

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

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

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

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

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

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

Fluid Simulation(Under Construction!)

Fluid Simulation

兩種模擬方式:

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

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

兩種力:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

粒:空氣與水

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

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

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

格子。建立100×100個格子,排列整齊。

格子擁有數量和速度。此處的模擬,強制數量均勻!粒子處處等量,不必紀錄數量。

數學術語是。無需數量場、只需速度場。

牆壁。牆壁速度是零。

數學術語是邊界條件

壓縮力。兩種情況:一、周圍格子,粒子數量一致,壓縮力總和為零,可忽略。二、自身格子,粒子互相推擠,傳遞速度。

牆壁不提供壓縮力、黏滯力。方便起見,暫時讓牆壁速度等於鄰水速度。

黏滯力。切線方向。

擴散。方便起見,合併壓縮力與黏滯力,強迫兩者係數一致。加總四方向的相對速度,乘上係數。

數學術語是Laplace operator,物理意義正是擴散。

投影。令每個格子流入流出相等,強制數量均勻。

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

流動。數量場、速度場一起參照速度場前進。由於強制數量均勻,不必模擬數量場。

步幅。流動不得跨越格子,否則軌跡不夠精確、水滴容易疊合。保守策略是移動距離小於格子寬度,稱做CFL condition

步向。兩種方向:

前進:往後補值。優點是動量守恆。缺點是空格與疊格。後著是CFL condition。

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

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

速度外插。如果採用倒退步法,則水域之外也要有速度。

水不可穿牆,牆面法線速度是零。令水格子是正速度、牆格子是負速度。兩者內插之後,牆面是零速度。

速度內插。更精確的速度值。副作用是擴散。兩種方式:

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

倒退與內插:線性內插、Catmull-Rom interpolation。

速度校正。modified MacCormack method。

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

防水。dt畢竟不是無限微小,靠牆的水容易一步穿牆。

有個歪招:投影的邊界條件,設定為負速度,令水遠離牆。

水域。速度場外觀醜陋,需要一點美術。兩種方式:

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

格:建立粒子數量場,沿著速度場跑。

格:空氣與水

重力。速度場垂直方向增加一常數。速度場+重力場。

防水。之前的歪招不管用。重力場是諧場,投影將保留重力場。

如果你知道怎麼解決,麻煩教我。

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

空氣速度:理論上是風速;此處是零。
空氣壓力:理論上是一大氣壓;此處是零。
牆壁速度:理論上是零;此處也是零。
牆壁壓力:理論上是水壓:水深乘以密度;此處是隔壁水壓。

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

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

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

水域。速度場外觀醜陋,需要一點美術。三種歪解:

粒:散布大量粒子,沿著速度場跑。若格中駐留足夠粒子,則視作水域。粒子移動,漸漸靠攏,因此每隔一段時間重新散布粒子。

格:有水的格子標1,沒水的格子標0,建立01場,沿著速度場跑。水面位置內插是個難題。

格:水面到格子的距離,建立距離場,沿著速度場跑。距離場移動,距離必錯,因此每隔一段時間修正距離場,以當前水面為準,重算距離場。

粒與格衍生許多演算法

粒衍生離散、連續。

格衍生colocated grid、staggered grid。

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

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

又衍生許多演算法:PCISPHAffine PIC、……。

未涉及主題

粒子間作用力  Lennard-Jones potential
內聚力、附著力 cohesion、adhesion
浮力      buoyancy
摩擦力     friction、no-slip condition
障礙物     immersed boundary method、Werner-Wengle wall function
層流、亂流   laminar、turbulence (mean + fluctuation)、Reynolds number
溫度、能量   temperature、energy
交融      Rayleigh-Taylor instability、Kelvin-Helmholtz instability
角動量     angular monentum、vorticity、helicity
流線      streamlines、streakline、pathline
底形      bedform
顆粒流     granular flow

應用範圍

水、火、雲、煙、大氣環流、‎大洋環流、牙膏、醬料、果汁機、洗衣槽、水墨畫、心肺循環、化學反應、緊急疏散、……,皆可使用流體模擬,細節略有差異。

入門介紹請參考這系列文章

繪圖方式

藝術作品

http://bugman123.com/FluidMotion/index.html
http://fabianoefner.com/
http://pof.tnw.utwente.nl/research

Navier-Stokes Equation

描述流體的數學式子。請見科普文章課程講義

時變+空變(平流)=位勢(壓力)+動勢(應力)

流場:速度場,參照自身而流動;還可額外載物。

Navier-Stokes equation有另一種形式:等號兩邊同時求旋度。優點是渦旋明顯,可精確模擬亂流,呈現leapfrogging vortex ring、cavity flow、microburst等自然現象。請見課程講義實作結果

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

七大數學難題:Navier-Stokes existence and smoothness,目前還不確定此方程式是否有公式解。

Schrödinger Equation

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

流體力學有個類似手法:Navier-Stokes equation的實數運算原理,改成Schrödinger equation的複數運算原理。三維實數改成二維複數,質量(密度)改成複數長度平方,速度改成複數角度。

請見這篇論文

Solid Simulation(Under Construction!)

Solid Simulation

https://developer.nvidia.com/
http://davidhsu666.com/315/gamecollisiondetection
https://www.atmos.illinois.edu/courses/atmos100/userdocs/3Dcollisions.html
https://code.google.com/archive/p/box2d/downloads

Motion(Under Construction!)

Motion

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

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/

Mechanism

機制。拼湊大量物體,物體之間互相連動。

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

Locomotion

力與姿態的改變。

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

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

Steering Behaviors

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

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

備註

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

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

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

Motion Control(Under Construction!)

Motion Analysis

分析。觀測實物,擷取動作。

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

Animation(Under Construction!)

Animation

動畫。狹義是卡通動畫。廣義是電腦模擬動畫。

知名的動畫製作軟體如AfterEffect、NUKE、MAYA、MARI、CelAction2D。

http://www.youtube.com/playlist?list=PL-bOh8btec4CXd2ya1NmSKpi92U_l6ZJd
http://animapp.tw/
https://www.zhihu.com/question/61990609/answer/193543646
http://www.youtube.com/channel/UC0GpuO2aEbGMG8N0iLE9_TA
http://www.cse.ohio-state.edu/~parent/

3D。建立3D模型。現在最流行的方式。

3D仿2D。調整3D模型,營造2D效果。例如採用特殊的shading。

http://animapp.tw/blog/insight/people/1816

2.5D。調整2D圖片,營造3D效果。例如多層貼圖、image warping。

2D仿3D。以2D圖片為基礎,打造3D模型。

http://www.alecrivers.com/2.5dcartoonmodels/
http://graphics.csie.ncku.edu.tw/double_side/doublegfx.TVCG.final.pdf

Stop-frame Animation。停格動畫、定格動畫。拍攝靜態畫面,串成一個影片。

Cinemation

電影。相關的學問叫做「攝影學Cinematography」。

電視廣告。所有技巧集大成。

https://www.facebook.com/worthtostudy

Visual Effects(VFX)

視覺特效。

知名的視覺特效軟體如Houdini。

http://freespace.virgin.net/hugo.elias/

Sakuga

作畫。傳統的卡通動畫是人工作畫。現代的卡通動畫是運用演算法協助作畫。

經典的作品是小小武打

日本發展出許多令人驚豔的作畫風格。台灣曾經是作畫代工大國,不過已經沒落了。

Animation Effect(Under Construction!)

Easing Function

https://github.com/kaelzhang/easing-functions
https://syphobia.wordpress.com/2011/04/07/useful-mathematic-curves/

Particle System

Object Generation

Fur
http://www.xbdev.net/directx3dx/specialX/Fur/
http://www.catalinzima.com/xna/tutorials/fur-rendering/
https://www.mikecauchiart.com/single-post/2017/01/23/Research-Tillable-images-\
and-cloth-shading
Map
https://www.zhihu.com/question/27157193
Flow
http://www.iquilezles.org/www/articles/warp/warp.htm

Perlin noise應用廣泛,例如紋路(座標)、地勢(高度)、痕跡(表面法向量)、移動(速度)、濃淡(密度)。

Non-photorealistic Rendering(Under Construction!)

Non-photorealistic Rendering(NPR)

非寫實繪圖

Painterly Rendering
Artistic Rendering
Vision-Realistic Rendering
http://www.dgp.toronto.edu/~hertzman/
http://www.cs.cf.ac.uk/npr/
http://www.red3d.com/cwr/npr/
http://www.cs.virginia.edu/~luebke/publications/pdf/npr.pdf

Shader

Cel Shading

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

Hatching

http://research.microsoft.com/en-us/um/people/hoppe/hatching.pdf

Silhouette

Watercolor

Dimensional Typography

3D文字動畫。

http://acg.media.mit.edu/projects/thesis/pchothesis.pdf