Verlet integration(韋爾萊積分法)是一種針對牛頓第二運動定力的積分法，常用於程式中的布料模擬以及計算繩索、Ragdoll之類的效果。
最初發現Verlet integration的契機，是之前在做Ragdoll研究的時候，碰巧翻到一篇Hitman(刺客任務)開發者以前發表過的一Advanced Character Physics，文中提到他必須想辦法讓遊戲內被殺死的NPC做出夠有說服力的Ragdoll效果(玩家要可以互動、拖拉…等等)，又必須讓Ragdoll計算的效能足夠輕量化，把身體每個部位都當成Rigidbody想必是不可行的(當時是西元2000年)，於是Verlet integration就是他們用來計算ragdoll motion的方法。
Hitman: Codename 47" src="https://cdn-images-1.medium.com/max/2000/1*1Tx-yybbOWj4kea-DS6BdA.png">
Verlet integration主要有兩種(或三種)實作，這次我實作的是在Youtube上面看到的第一種 - 粒子本身不考慮速度的版本。
利用Verletion Integration計算粒子的運動
Verlet integration下，每個物體下一次的位移由當前Position減去前一次的Position即可得出，不需要額外記錄一個velocity變數，換句話說 — 如果想改變粒子的運動方向(比如說撞到牆要反彈)就要去修改前一次紀錄的Position。
上圖中碰到牆壁時，為了讓粒子能夠反彈，我們只要修改OldPosition，將最近一次的OldPosition設為牆外一點，在下一次進行Verlet integration的計算時，粒子就會朝牆壁內跑了。
有了基本的移動後，我們可以定義重力，以及每次碰撞牆壁後因為摩擦力導致的能量損失。
Constraint(約束)
真正的應用要配合各種constraint，像是可以定義讓兩個粒子維持固定距離的約束 - 當兩個粒子之間距離太遠時，就讓兩個粒子互相靠近，當兩個粒子之間的距離太近時，就讓粒子遠離彼此。
{:.blog-post-md-img-half }
{:.blog-post-md-img-half }
利用這個constraint，可以將粒子排成一個簡易的人型，這其實就是當年Hitman製作Ragdoll的方法，實作意外的簡單。
{:.blog-post-md-img-half }
我們還可以定義像是處理碰撞的constraint，也可以定義讓某些粒子固定住(Pin)的constraint，最終Code的架構大概會是長這樣
在code產出30*30個粒子，彼此之間都用constraint來限制住距離。將最上排的粒子都用Pin Constraint固定住，我們可以做出一個簡單的布料模擬。
優化
依照上面截圖內的code，應該可以看出此時的計算量隨著粒子總數的提升，也大幅地增加了，在30*30個粒子的情況，這裡總共做了 900 + 3 * (450+900+900 )次的計算，因為都是for迴圈，改成用Job system並不難，用IJobParallelFor將所有計算平行化 (但須注意有些constraint間的計算是有順序關係的，需用JobHandle來做job間執行順序的相依)。
原本在main thread需要5ms才能計算4片粒子數量為3030的cloth。 用Job System修改之後計算時間可以降為0.59ms*。
把不同的個constraint都拆成獨立的Job，彼此之間用JobHandle做相依，一種constraint的Job算完才會換下一種，雖然這樣邏輯拆的比較乾淨，不過Schedule的Job數量也變多了，因為Schedule Job本身有Overhead，在CPU上有Burst Compiler加持+量不到太大的情況，也許用單一Job直接計算所有constraint會更快也說不定。
Demo
📖左 - 將生成的布料粒子視覺化
中 - 將布料的每個粒子計算後的結果設回mesh對應的頂點，讓mesh可以根據verlet integration的計算結果變形。
右 - 生成粒子，左右端的兩點使用pin constraint，可以做出繩索的動態
之前無聊修改了一下shadergraph內底層Graph的UI code，把Edge的繪製override掉，改成用另外畫出的一堆dot shape + 用這次的verlet integration來計算所有dot的位移。可以讓node之間變成是用繩索連結彼此。
雜談
這次做的是單靠當前與上一次的位置來計算下一次的位移，完全沒有velocity的版本。wiki上有另一種叫Velocity — Verlet的實作，看起來也是滿容易寫的，而有velocity的話我想可以針對象是布料的模擬(尤其是遊戲)有更完整的掌控，避免手動位移物件造成粒子瞬間的爆衝現象，隨手翻了一下目前我覺得Unity插件中做得最好的 - Magica Cloth的source code。他們也是有將速度expose給使用者來做控制。
不過對於需要一個簡單的rope或者類似rope的動態的情況(海的海草?)，這仍然是個不錯的方法。
Collider的計算也是需要優化的一塊，如果有大量Collider需要互動的話計算量也會暴增，可以讓每個獨立的cloth各自存有一個只對自己有影響的collider list是一種作法，或者使用BVH之類的演算法來找出同個空間的collider，再做計算。
參考資料
5.13: What is Toxiclibs Verlet Physics? — The Nature of Code
Simulate Tearable Cloth and Ragdolls With Simple Verlet
Integrationhttps://pikuma.com/blog/verlet-integration-2d-cloth-physics-simulation