浙江工業(yè)職業(yè)技術學院 李 偉

引言

長期以來，研究人員一直尋求布料仿真的高效、穩(wěn)定、實時的算法[1,2,3]，目前已提出了多種模型來解決這一問題。這些研究成果廣泛應用于3D電影、網(wǎng)絡游戲虛擬現(xiàn)實等領域。人物角色一直是網(wǎng)絡游戲和虛擬現(xiàn)實中最重要的對象之一，而服裝又覆蓋人體9O%區(qū)域以上，因此視覺上真實穩(wěn)定的動態(tài)布料仿真對網(wǎng)絡游戲和虛擬現(xiàn)實的重要性不言而喻，但具有高度真實感的布料仿真往往計算成本很高，實時性欠缺。

本文采用典型的質(zhì)點-彈簧模型，利用自適應混合積分方法來對微分方程求解，巧妙運用狀態(tài)方程中的局部結(jié)構(gòu)參數(shù)，計算得出自適應時間步長。仿真實驗表明，該方法在保證系統(tǒng)穩(wěn)定性同時加速了求解過程。

1.改進的質(zhì)點-彈簧模型

目前研究人員提出了各種基于物理性能建模的圖形表達。代表性模型分為兩大類，即粒子系統(tǒng)模型和連續(xù)介質(zhì)模型。本文中采用的布料模型與choi[4]的模型相類似，是一種粒子系統(tǒng)模型。這種模型的突出優(yōu)點是對彎曲力和壓縮力統(tǒng)一處理，因而得以避免了“后屈曲失穩(wěn)”現(xiàn)象的發(fā)生，從而提供了很有吸引力的穩(wěn)定結(jié)果。

本文將布料抽象為一個由m×n個虛擬質(zhì)點組成的網(wǎng)格，質(zhì)點之間用無質(zhì)量的、自然長度為零的彈簧相連接。其連接關系有三種：“結(jié)構(gòu)彈簧”，“剪切彈簧”，“彎曲彈簧”。

網(wǎng)格中每一個質(zhì)點與其周圍相鄰的四個質(zhì)點通過剛性的結(jié)構(gòu)彈簧（Stretch spring）相連。與其對角線上的質(zhì)點之間則通過剛性較小的剪切彈簧（Shear Spring）相連。最后，質(zhì)點與其空間上間隔一點相鄰的質(zhì)點間則通過非線性的彎曲彈簧（bend spring）相連。

布料的物理模型是基于質(zhì)點一彈簧模型的粒子系統(tǒng)，粒子間的連接是通過彈簧力。布料的類型和運動取決于粒子間的彈簧力和布料的拓撲結(jié)構(gòu)。作用在粒子上的力可分為內(nèi)力和外力，內(nèi)力包括彈簧力，而外力則包括重力、風力等各種阻尼力。

1.1 內(nèi)力分析

用fi,y表示質(zhì)點i和質(zhì)點j之間的彈簧作用在質(zhì)點i上的力，這里彈簧遵循h(huán)ooke定律，則有

這里xi,y=xi-xj，L是彈簧原長，ki,y是彈簧的彈性系數(shù)

該模型計算質(zhì)點的受力非常簡單直觀，并且用三種彈簧模擬了三種力：拉伸力、剪切力和彎曲抗力。但該模型的缺陷在于彎曲彈簧的處理，使得布料很難生成褶皺。Choi采用了力矩平衡方程來求得彎曲抗力，成功解決了壓桿穩(wěn)定性問題，同時給布料帶來的褶皺效果要比前者好的多，不過其計算相當復雜，這樣在要求實時計算的條件下是不可取的，因此采用了更為簡便的計算方式對彎曲抗力進行求解。彎曲抗力的計算公式如下：

注意，上述彎曲力計算公式表明彎曲彈簧僅僅在彈簧被壓縮（即彎曲發(fā)生）的時候才起作用。這里的ki,y要比結(jié)構(gòu)彈簧的剛度小的多，因此這個力對結(jié)構(gòu)力的影響并不大，只用來產(chǎn)生布料的有效彎曲，即褶皺。

另外，考慮到結(jié)構(gòu)彈簧和剪切彈簧的一致性，對其合并處理。最終采取的模型表示方法，其彈簧連接關系與Choi一致，結(jié)構(gòu)力和剪切力計算方法類似方程（1）。

這個模型結(jié)合了provot和Choi兩種代表性質(zhì)點彈簧模型的優(yōu)點，一方面它保持了provot模型的計算簡單的特點，另一方面它采用了choi模型的方法，大幅提高了布料的穩(wěn)定特性，可有效生成各種褶皺。

1.2 外力分析

以上給出了布料模型和內(nèi)力的計算方法。但這是一個理想化的模型，它忽略了布料運動過程中能量的耗散?，F(xiàn)實的布料運動會受到一些外力的影響，比如空氣阻力、摩擦力等等。為了使布料仿真具有足夠真實感的動態(tài)表現(xiàn)，布料物理模型必須考慮到這些外力的影響。為了讓布料運動更具真實性，在布料的運動模擬中添加一個阻尼模型是有必要的。

阻尼力是用來抵抗粒子之間剪切彈簧引起的平面內(nèi)運動，該力取決與相互作用粒子間的相對運動速度，我們采用的阻尼模型如下：

這里fd是連接質(zhì)點i,y之間的阻尼力，Cd是阻尼系數(shù)，vi,vy是兩質(zhì)點的運動速度。

這個阻尼模型在布料的模擬中廣為采用，在應用上也取得了良好的效果，有效地提高了算法的穩(wěn)定性，增強了布料模擬的真實感。

2.數(shù)值積分

布料受到的作用力與其運動狀態(tài)的關系可以由動力學方程來描述。一般來說，布料粒子系統(tǒng)的二階動力學方程可以表示為：

這里，M是彈簧一質(zhì)點系統(tǒng)的質(zhì)量矩陣，向量x包括了系統(tǒng)中所有質(zhì)點的位置。F代表了所有的非保守力，比如摩擦力、約束力等外力。表示了所有的保守力，比如重力、結(jié)構(gòu)力、剪切力等，每種保守力都關聯(lián)著一種勢能，比如重力能、彈性能等。

基于物理的布料變形動畫可以歸結(jié)為沿時間軸求解布料動力學方程的初值問題。動力學方程中位置和速度都是時間的未知函數(shù)，然而根據(jù)位置、速度和力三者之間的物理關系，我們可以將上述具有位置二階偏導的動力學方程分解為兩個具有一階偏導的運動方程，即:

這里f代表合力，為了獲得布料粒子系統(tǒng)在每一幀的位置和速度，我們需要利用數(shù)值積分方法對上式進行求解。一般來說，只要已知當前t時刻的布料系統(tǒng)中所有粒子的運動狀態(tài)(xt,vt)，并由方程構(gòu)造顯式、隱式或半隱式積分式，那么就可以計算出一個時間步長h后布料系統(tǒng)的運動狀態(tài)(xt+h,vt+h)，在每個時間步長內(nèi)，顯式方法直接計算，而隱式方法需要迭代求解。由于布料物理模型的數(shù)值積分求解是影響布料仿真系統(tǒng)性能的一個重要因素，因此對數(shù)值積分求解器進行改進和優(yōu)化始終是快速布料動畫研究的一個重要內(nèi)容。

2.1 混合積分

目前已有布料仿真的實踐中，顯式方法存在通常穩(wěn)定性問題，所有提到的隱式求解方法只有一階，因此精度較差，容易導致運動緩慢并可能丟失褶皺等細節(jié)。其他方法甚至不對系統(tǒng)求解，只是給出一些合理的近似。

當然，我們不是只有顯式和隱式兩種積分方法可以選擇，我們也可以把兩種方法結(jié)合到一起同時運用，這就是混合積分法?；旌戏e分法的核心思想就是將常微分方程系統(tǒng)解耦為剛性部分和非剛性部分，對于剛性部分使用隱式的方法，對于非剛性部分則使用顯式的方法，從而把隱式法的求解穩(wěn)定性和顯式法的計算簡單性很好的結(jié)合起來。我們將方程（1）所示系統(tǒng)的力拆分為線性部分和非線性部分，考慮到布料在空間運動的剛性特征，線性力同布料的剛性特征密切相關，以隱式方法求解；非線性力部分則直接采用顯式解法。

針對布料的質(zhì)點—彈簧模型，我們對結(jié)構(gòu)彈簧進行隱式求解，而剪切或彎曲彈簧則顯式求解。不妨將系統(tǒng)合力f解耦為f=gI+gH，gI代表剛性部分，gH代表非剛性部分，則有：

由上述方程知系統(tǒng)的剛性部分運用后向歐拉法計算而非剛性部分則采用前后向歐拉法計算。

半隱式積分法中每一時間步長都需要進行系統(tǒng)的單步牛頓迭代計算，因而顯著降低了每一時間步長的計算效率。混合積分法中不再需要顯式的計算相鄰質(zhì)點間的系數(shù)矩陣Jacobian矩陣。更重要的是，Jacobian矩陣是巨型稀疏矩陣，導致矩陣的向量積計算相對于共軛梯度法的巨大計算成本降低了很多。

2.2 自適應混合積分法

針對目前布料仿真領域廣泛使用的半隱式計算框架，在混合積分的基礎上，我們對其做進一步改進，提出了一種新的數(shù)值求解方法，即自適應混合積分法。我們不再費力分析推測對系統(tǒng)的哪一部分應用何種積分求解，相反我們依賴當前模擬參數(shù)和一定的穩(wěn)定性判斷準則迅速自主靈活決定積分方法的運用。另外，在空間上參數(shù)局部變化的區(qū)域，則依賴彈簧的連接類型來確定。與其他方法不同，我們的方法沒有犧牲準確性。與混合積分方法相比，該法計算簡單，降低了計算成本，改善了系統(tǒng)的稀疏性。

一般說來我們對彎曲彈簧顯式求解，但是彎曲彈簧剛度變化范圍幅度通常很大。當模擬布料對象具有較小的彎曲剛度時，這種顯式求解方法的結(jié)果很不錯。但是當模擬的布料對象具有大剛度特征時，這種處理方法就顯得不合時宜了，此時隱式求解就顯得更加合理。

設定一剪切或彎曲彈簧，定義其剛度為ks、阻尼系數(shù)為kd，原始長度為L。理想狀態(tài)下我們期待建立一個穩(wěn)定性準則使我們能夠在模擬過程中自動確定合適的時間步長如何對系統(tǒng)進行解耦。另外，針對自適應模擬技術，即每一空間網(wǎng)格間距h是變化的，或者說局部網(wǎng)格參數(shù)m,L,ks,kd均是可變的，我們需要一個在時間、空間上局部均可用的判斷準則。提出的一個自適應的時間步長計算方法如下：

圖1 彈簧間的連接關系模型

圖2 不同數(shù)值積分方法計算速度比較

圖3 風力作用下的布料

在任一時間步長，利用當前空間網(wǎng)格間距h和m,ks,kd取值，我們計算某一類型彈簧連接的一對粒子作用在其上的力時，我們利用上式進行判斷，如果判斷為真，則跳過相關Jacobian矩陣的計算，否則就如往常一樣，計算相應的Jacobian矩陣。這樣我們就可以主動控制系統(tǒng)的解耦計算而不是被動決定。

此外，該準則僅對線性化結(jié)構(gòu)或剪切彈簧有效，對小剛度的彎曲彈簧，我們一般用顯式方法處理，不會遇到穩(wěn)定性問題。

實驗結(jié)果表明，我們的自適應混合積分法是穩(wěn)定的，這一點和標準的半隱式積分法幾乎不分上下。比較這兩種算法的計算效率，自適應混合積分法大約降低了2O%左右的計算時間，且隨著網(wǎng)格質(zhì)點數(shù)增多計算成本節(jié)約更多。

3.實驗結(jié)果和分析

基于上述方法，在Windows XP sp2操作系統(tǒng)和Intel pentium 4 2.4G處理器的軟硬件環(huán)境下，在Visual C++ 6.O平臺并結(jié)合Open GL圖形庫，對布料進行模擬。

為了測試本文局部自適應混合積分方法和其他常用數(shù)值積分方法對計算速度的提升差異，我們利用一1O×1O布料網(wǎng)格做單擺運動仿真實驗，實驗中分別應用顯式龍格-庫塔法（Runge-Kutta法）、半隱式歐拉法結(jié)合共軛梯度法（CG法）以及本文方法各自模擬1OO幀，記錄總的計算時間，從而求出生成每幀的平均計算時間，利用這個參數(shù)來衡量不同數(shù)值方法的計算速度。另外根據(jù)仿真中總步長數(shù)還可以求解得到平均單步計算時間。實驗結(jié)果如圖（2）所示。由實驗結(jié)果可知，盡管顯式方法單步計算時間比本文方法要小，但考慮到本文方法在時間步長上要遠大于它，因此本文方法的速度還是會達到超過顯示方法，布料規(guī)模越大這種實時性能提升的效果越明顯。

圖3給出了16×12個質(zhì)點，1O14根彈簧構(gòu)成的布料旗幟在風力作用下效果。

實驗結(jié)果表明，自適應混合積分法保持了很好的數(shù)值穩(wěn)定性，仿真系統(tǒng)始終保持穩(wěn)定，無散亂失真現(xiàn)象。通過仿真過程中自適應混合積分方法的使用，能夠有效而逼真地動態(tài)仿真織物，不僅保證了精度，同時提高了計算效率。

[1]Ari Stern and Mathieu Desbrun.Discrete geometric mechanics for varia tional integrators(a primer for cs).ACM SIGGRAPH ’06 Course Notes on Discrete Di erential Geometry,2006.

[2]R.Bridson,S.Marino,and R.Fedkiw.Simulation of clothing with folds and wrinkles. In ACM SIGGRAPH/Eurographics Symposium Computer Animation,pages 28-36.ACM Press,2003.

[3]E.Boxerman and U. Ascher,“Decomposing cloth,”in Proc.ACM SIGGRAPH/Eurographics Symp.on Comput.Anim.,pp.153-161,2004.

[4]K.Choi and H.Ko.Stable but responsive cloth.In Proceedings of the 29thannual conference on Computer graphics and interactive techniques,pages 604-611.ACM Press,2002.

[5]D.Baraf,A.Witkin,and M.Kass.Untangling cloth.In ACM Trans.Graphics,pages 862{870.ACM Press,2003.

[6]J.Teran,S.Salinas-Blemker,V.Ng,and R.Fedkiw.Finite volume methods for the simulation of muscle tissue.Eurographics/ACM Symp.on Comp.Animation,2003.

[7]P.Volino and N.Magnenat-Thalmann,“Implicit midpoint integration and adaptive damping for eff i cient cloth simulation,”Computer Animation and Virtual Worlds,vo l.16,pp.163-175,2005.