每個(gè)人都身懷天賦掰曾,但如果用會(huì)不會(huì)爬樹來衡量一條魚璃哟,那它到死都只會(huì)認(rèn)為自己愚蠢。 —— 愛因斯坦
這一講是緊接著上一講的內(nèi)容肄方,開始討論如何通過數(shù)值方法來完成對(duì)彈性體形變的模擬,另外蹬癌,順帶提一句权她,這部分內(nèi)容跟游戲開發(fā)中的物理引擎具有較高關(guān)聯(lián)。
上一講降到逝薪,我們的彈性勢(shì)能可以表示為:
值得澄清的是隅要,這里是省略了高階項(xiàng)之后的彈性勢(shì)能,即這個(gè)公式是在線性形變的情況下成立的董济,如果要考慮更為復(fù)雜的形變步清,后面還要加上更多的高階項(xiàng)。
下面來介紹,我們?cè)谟?jì)算機(jī)中要如何計(jì)算出彈性體形變之后產(chǎn)生的internal force廓啊,大致思路是先計(jì)算出形變梯度矩陣(Deformation Gradient)欢搜,之后根據(jù)這個(gè)矩陣算出Green Strain Tensor,之后再算出勢(shì)能表達(dá)式谴轮,最后對(duì)勢(shì)能求導(dǎo)炒瘟,就得到了對(duì)應(yīng)的conservative force。
首先來看下第步,我們要如何計(jì)算形變梯度矩陣疮装,這里先考慮3D軟體的情況,2D軟體的情況如布料等在后面再考慮粘都。
首先斩个,要想在計(jì)算機(jī)中進(jìn)行模擬,就需要將3D軟體離散化驯杜,2D表面離散化是通過將之拆解成三角形來完成受啥,而3D Volume的離散則是將之拆分成一個(gè)個(gè)的四面體。
形變發(fā)生后鸽心,單個(gè)四面體就會(huì)從material space映射到deformed space滚局,即四面體本身發(fā)生了形變,如下圖所示:
緊接著給出兩個(gè)假設(shè):
- 四面體足夠小顽频,那么假設(shè)藤肢,我們可以進(jìn)行如下的推導(dǎo):
由于四面體足夠小,因此滿足微分中的一個(gè)極小的局部變化的要求糯景,可以采用泰勒展開:
在線性形變的情況下嘁圈,我們可以省略高階項(xiàng),我們可以得到:
上述公式中的我們是知道的(最開始的時(shí)候蟀淮,最住,所以自然是知道的,之后怠惶,經(jīng)過一個(gè)timestep迭代涨缚,最新的位置經(jīng)過后續(xù)的計(jì)算,自然也是知道的)策治,而形變前的數(shù)據(jù)我們也知道脓魏,因此就可以計(jì)算出F,另外通惫,我們前面也說過茂翔,F(xiàn)是一個(gè)與位置有關(guān)的變量,要精確考慮的話履腋,四面體上的每一點(diǎn)對(duì)應(yīng)的F都應(yīng)該是不同的珊燎,不過這里我們可以假設(shè):
- 四面體內(nèi)部的F是一個(gè)常量,那么F就變成了一個(gè)piece-wise constant(可以聯(lián)想分段函數(shù)),當(dāng)然俐末,這里我們其實(shí)還隱藏了一個(gè)假設(shè)料按,那就是從到的變化是一個(gè)線性變化(想象一下兩個(gè)頂點(diǎn)之間有一個(gè)彈簧),在這種假設(shè)下卓箫,F(xiàn)才會(huì)是一個(gè)常量载矿,否則可能會(huì)是一個(gè)多項(xiàng)式,目前市面上的物理引擎基本上都是按照線性變化來模擬的烹卒,雖然精度上不能做到完全保證闷盔,但是考慮到性能跟效果的平衡,這是一種最好的選擇了旅急。
在上述假設(shè)下逢勾,我們可以有更多的等式:
將前面的三組公式放在一起,我們就得到了下面的矩陣乘法形式藐吮,從而推導(dǎo)出F:
簡(jiǎn)化一下:
跟都是一個(gè)3x3的矩陣溺拱,根據(jù)上面公式可以推導(dǎo)出:
這里是其中一個(gè)四面體的F,其他四面體也會(huì)有對(duì)應(yīng)的F谣辞,根據(jù)F我們就可以計(jì)算Green Strain Tensor迫摔,這也是每個(gè)四面體一份的:
以及勢(shì)能,對(duì)勢(shì)能進(jìn)行求導(dǎo)(具體來說泥从,consititutive model有公式的話句占,可以手動(dòng)推導(dǎo)其彈性力的表達(dá)式),我們就能得到internal force(彈性力):
這里躯嫉,勢(shì)能是物體共有的一個(gè)參數(shù)纱烘,是一個(gè)標(biāo)量,而則是物體上所有四面體的頂點(diǎn)組成的一個(gè)向量祈餐,那么經(jīng)過求導(dǎo)后得到的彈性力也自然是一個(gè)n維的向量擂啥,每一維代表的是每個(gè)頂點(diǎn)的受力。
上面是內(nèi)部的力昼弟,外面來自于重力或者碰撞的力啤它,我們用外力表示。
其中的質(zhì)量m是一個(gè)很大的vector舱痘,在上面的公式下,我們就可以用之前說過的implicit euler或者explicit euler完成時(shí)間步長(zhǎng)積分离赫,從而算出更新的位置向量芭逝。
上面這種用離散的四面體來模擬軟體的彈性形變的方法叫做Finite Element Method(FEM),這種方法可以通過不斷提高分辨率(縮小四面體的尺寸)來保證準(zhǔn)確性渊胸,不過同時(shí)也會(huì)導(dǎo)致計(jì)算復(fù)雜度增加旬盯,所以游戲或者很多電影特效模擬不是用的這種方法,而是基于優(yōu)化的方法,Optimization-Based Methods胖翰,這種方法可以實(shí)現(xiàn)快速模擬接剩。
先來回顧一下隱式歐拉方法,速度跟位置向量的演變可以用下面公式來表達(dá):
這里的兩個(gè)向量都是包含了多個(gè)四面體的相關(guān)數(shù)據(jù)的萨咳,是一個(gè)3xn的矩陣。
前面說過隱式歐拉最終會(huì)變成一個(gè)高維方程,很難求解张弛,這里考慮將之轉(zhuǎn)換成一個(gè)優(yōu)化問題草添。
首先,internal force是勢(shì)能的導(dǎo)數(shù)給出如下:
根據(jù)上面的公式舀凛,我們有:
這邊希望構(gòu)造出一個(gè)函數(shù)俊扳,并且使得這個(gè)函數(shù)的極值:
達(dá)成的條件跟前面的公式相一致,也就是說猛遍,希望這個(gè)函數(shù)的極值對(duì)應(yīng)的解就正好是上面一個(gè)等式的解馋记,而這個(gè)函數(shù)可以給出為(比較容易推導(dǎo)?):
其中
從而我們可以知道:
前面說到懊烤,這個(gè)函數(shù)提出的目的是為了求得前面implicit timestep等式的等價(jià)解抗果,這里的一個(gè)疑惑就是,同樣是解方程奸晴,前面implicit方程不好解冤馏,這里的方程同樣也不好解,那么這種變化的意義在哪里呢寄啼?
這里的作用在于公式中的后面部分逮光,這個(gè)部分表示的是系統(tǒng)的勢(shì)能,前面說過彈性形變的勢(shì)能公式是通過一系列的物理推導(dǎo)得出的墩划,是精確解涕刚,這種求解起來會(huì)比較麻煩,但是在游戲中乙帮,我們可以使用非精確解杜漠,只要保證模擬的結(jié)果看起來真實(shí)就好,這樣一來察净,我們就能夠選擇一些能夠讓這個(gè)求解過程變得容易的公式代入這里的勢(shì)能項(xiàng)中驾茴,從而達(dá)到簡(jiǎn)化問題的目的。
那么這個(gè)勢(shì)能公式要怎么來設(shè)計(jì)呢氢卡?我們知道锈至,彈性形變導(dǎo)致的勢(shì)能總體來說,可以分成兩種译秦,分別是體積變化導(dǎo)致的形變(如從體積為1變成體積為2)峡捡,或者是扭曲導(dǎo)致的形變击碗,如一個(gè)cube變成平行六面體等。
前者勢(shì)能可以表示為:
det是矩陣的行列式们拙,這個(gè)公式的意義在于稍途,當(dāng)沒有形變的時(shí)候,矩陣就是單位矩陣砚婆,這個(gè)勢(shì)能的結(jié)果就是0
后者勢(shì)能可以表示為:
tr(trace)是矩陣的跡械拍,一個(gè)n×n矩陣A的主對(duì)角線(從左上方至右下方的對(duì)角線)上各個(gè)元素的總和被稱矩陣A的跡(也就等于所有特征值的和)。同樣射沟,當(dāng)沒有形變時(shí)殊者,這個(gè)F就是單位矩陣,所以跡就是3验夯,那么勢(shì)能依然為0猖吴。
總結(jié)可以看出,我們需要的勢(shì)能公式其實(shí)就是一個(gè)約束條件挥转,這個(gè)約束條件或者說約束函數(shù)在無形變的時(shí)候輸出為0海蔽,在有形變的時(shí)候輸出的是一個(gè)正值(或者說在無形變的時(shí)候取得極小值0),比如其形式為:
在這個(gè)條件下绑谣,我們就可以定義勢(shì)能為:
上式中的A是一個(gè)對(duì)角陣党窜,C(q)是一個(gè)向量,對(duì)于其中的每個(gè)元素:
這里希望有:
這里的i用來指示四面體的序號(hào)借宵,這里翻譯一下幌衣,就是說我們希望每個(gè)四面體的形變梯度矩陣的行列式為1,也就是說每個(gè)四面體都是體積不變的壤玫。
下面來介紹一下Position-based Dynamics方法豁护,回到前面的公式:
這里,我們將勢(shì)能用脈沖函數(shù)(實(shí)際上是脈沖函數(shù)取反欲间,不過為了描述方便楚里,這里用脈沖函數(shù)來表示)來表示:
其中脈沖函數(shù):
之所以這樣設(shè)計(jì),就是為了滿足前面說過的猎贴,我們希望函數(shù)J取得最小值班缎,那么就需要保證,這里的i依然是四面體的序號(hào)她渴。
繼續(xù)下去达址,Position-based Dynamics方法會(huì)采用Gauss-Siedel Iteration(假設(shè)1)進(jìn)行求解,即對(duì)于后面的眾多四面體而言惹骂,我們會(huì)先只考慮一個(gè)四面體作用下的求解苏携,并將結(jié)果代入原公式之后考慮第二個(gè)四面體作用下的求解,循環(huán)往復(fù)对粪。如果只考慮單個(gè)四面體作用右冻,原公式就變成了:
再定義:
公式就變成:
將公式轉(zhuǎn)換一下,我們想要求解J的最小值著拭,就等價(jià)于在條件:
下求解
的最小值纱扭。
之后,再假設(shè)足夠欣苷凇(假設(shè)2)乳蛾,那么前面的條件就可以做泰勒展開為:
而這個(gè)就可以用上一講的拉格朗日乘子來求解,也就是說鄙币,在上面條件下的最小值求解就變成了:
而Gauss-siedel Iteration的問題是肃叶,需要進(jìn)行多次迭代才能收斂,從而導(dǎo)致計(jì)算比較慢十嘿,性能較差因惭,這也是Position-based Dynamics(PBD)的缺點(diǎn),如果Iteration數(shù)目不夠就會(huì)導(dǎo)致一些模擬效果質(zhì)量較低绩衷,比如布料會(huì)看起來像彈簧一樣生硬蹦魔。
我們來回顧下之前的內(nèi)容:
- 最開始我們是以隱式歐拉開頭,因?yàn)檎f到咳燕,想要求得下一步的位置勿决,需要求解一個(gè)十分復(fù)雜的非線性方程,不但計(jì)算量巨大招盲,而且由計(jì)算機(jī)來計(jì)算的話無法給出準(zhǔn)確解低缩;
- 于是,我們將問題轉(zhuǎn)換成了一個(gè)最優(yōu)化問題曹货,通過PBD+迭代的方式來求得近似解咆繁,但是這個(gè)方法的問題在于迭代時(shí)間較長(zhǎng),很難快速得到結(jié)果控乾。
那么很自然的問題就是么介,是否有一種方法是居于兩者之間的,一方面我們不需要求解一個(gè)十分復(fù)雜的方程蜕衡,而是只需要求解一個(gè)簡(jiǎn)單的方程壤短,且這個(gè)方程可以通過少數(shù)的迭代就能輸出結(jié)果的。
這個(gè)方法就是物理界常用的Projective Dynamics慨仿,實(shí)際上這種方法跟PBD是處于同一框架下得久脯,不同的是PBD這里的internel energy函數(shù)是一個(gè)脈沖函數(shù)之和,而Projective Dynamics方法的internal energy函數(shù)則是:
這個(gè)式子中一共引入了兩個(gè)新的符號(hào)镰吆,一個(gè)是變量p帘撰,這個(gè)變量代表的是某個(gè)粒子(如前面的四面體)的一個(gè)目標(biāo)狀態(tài)(比如,我們可以選擇四面體不發(fā)生形變時(shí)的狀態(tài)為一個(gè)目標(biāo)狀態(tài)万皿,當(dāng)然我們也可以選擇其他狀態(tài)作為目標(biāo)狀態(tài)摧找,具體如何選核行,后面再說),而d則是表達(dá)p跟q差異性的函數(shù)蹬耘,可以是一個(gè)非常簡(jiǎn)單的函數(shù)芝雪,比如就取兩者的距離作為函數(shù)。
整個(gè)函數(shù)是什么意思呢综苔,我們這里來舉個(gè)例子說明一下惩系,假如我們選擇某個(gè)函數(shù)(simple distance measure)作為上面的函數(shù)d:
這里的F跟前面一樣,還是deformation gradient如筛,是一個(gè)沒有形變堡牡,但是經(jīng)過一個(gè)旋轉(zhuǎn)的狀態(tài),兩者都是3x3的矩陣杨刨,其中可以通過一個(gè)叫做Shape Matching的算法求得晤柄。
另外一項(xiàng)是一個(gè)脈沖函數(shù),這個(gè)脈沖函數(shù)的取值受到約束條件c的影響拭嫁,當(dāng)的時(shí)候可免,取值為0,否則取值為無窮大做粤,而由于這個(gè)函數(shù)的存在浇借,要想使得整體的internal energy最小,就必須得滿足這里的約束條件怕品,從而使得脈沖函數(shù)取值為0妇垢。
在這個(gè)例子中,我們選取了p為經(jīng)過某個(gè)旋轉(zhuǎn)后的狀態(tài)肉康,而在這個(gè)狀態(tài)下闯估,可以滿足上面的脈沖函數(shù)結(jié)果為0,那么最終的internal energy的計(jì)算就變成了一個(gè)非常簡(jiǎn)單的矩陣的線性計(jì)算吼和。
這里涨薪,我們還可以選擇其他的p,比如:
這里的也是一個(gè)deformation gradient炫乓,表示的是最接近于當(dāng)前形變狀態(tài)的deformation gradient刚夺,但是在這個(gè)gradient的作用下,形變后的四面體的體積跟原始四面體保持一致(這種對(duì)于動(dòng)物形體的模擬比較有用末捣,比如肚子在受擊之后體積保持不變)侠姑,的計(jì)算同樣可以通過脈沖函數(shù)求得,比如只需要找到體積不變的形變的約束條件箩做,就能得到對(duì)應(yīng)的deformation gradient莽红。
在這種internal energy的作用下,最優(yōu)解的求解就變成了如下的函數(shù)形式:
可以看到邦邦,p只出現(xiàn)在后兩項(xiàng)安吁,q則只出現(xiàn)在前兩項(xiàng)醉蚁,從而我們可以通過有限的迭代來求解這個(gè)最優(yōu)化問題。
而由于脈沖函數(shù)的存在柳畔,p的求解只需要保證脈沖函數(shù)為0即可馍管,因此整個(gè)問題可以快速變成q變量下的最優(yōu)解郭赐,這個(gè)過程叫做local projection薪韩,即找到限制條件c(constraint)來保證脈沖函數(shù)為0,從而將問題從兩個(gè)變量降維成一個(gè)變量捌锭。
在求得p之后俘陷,就可以來求解q以獲得整個(gè)函數(shù)的最優(yōu)解:
而由于上面的函數(shù)實(shí)際上都是q的一個(gè)二次函數(shù),而其導(dǎo)數(shù)則是q的一次函數(shù)观谦,從而只需要將導(dǎo)數(shù)等于0拉盾,就能得到最終的解,這一步叫做global solve豁状。
前面說過捉偏,projective Dynamics是一個(gè)迭代的過程,上面展示的local projection跟global solve就是這個(gè)過程中的僅有兩個(gè)步驟泻红,這兩個(gè)步驟需要循環(huán)往復(fù)的去執(zhí)行(因?yàn)閜是local projection的夭禽,也就是一個(gè)局部解,這個(gè)解并不一定就對(duì)應(yīng)著最優(yōu)解谊路,而是需要不斷調(diào)整q來逼近最優(yōu)解)讹躯。
這個(gè)方法的迭代數(shù)目比PBD會(huì)少很多,目前UE缠劝、Houndini等軟件使用的是X-PBD方案潮梯,是在PBD方案上的一種更新方案,但是其迭代次數(shù)依然比Projective Dynamics方法要多惨恭,之所以不用Projective Dynamics方法秉馏,是因?yàn)榫€性系統(tǒng)的求解在維數(shù)很大(比如q是一個(gè)很大的向量)的時(shí)候會(huì)存在比較大的困難。