靳雁霞 程思岳 王賀 程琦甫 張晉瑞

摘 ?要： 為了解決目前布料仿真中用隱式積分法預(yù)測所得的下一個(gè)時(shí)間步長位移不精確的情況，提出一種新的平均力法來預(yù)測下一個(gè)時(shí)間步長的位移。該方法通過力來預(yù)測一個(gè)時(shí)間步長內(nèi)的位移，比起直接預(yù)測位移的隱式積分方法更加精確，其位移預(yù)測的誤差能夠減少5%～10%，并且隨著時(shí)間步長的增加，誤差會(huì)越來越小。此外，針對(duì)碰撞檢測后檢測到的穿透現(xiàn)象，提出一種基于分離軸的碰撞響應(yīng)算法解決穿透現(xiàn)象。該方法首先確定碰撞平面以及分離軸，將發(fā)生穿透的部分投影到分離軸上，得到穿透深度和穿透方向，給發(fā)生穿透的物體一個(gè)瞬時(shí)的沖量和阻尼力，讓物體返回碰撞平面上。通過大量的實(shí)驗(yàn)對(duì)比可以得出，基于分離軸的碰撞響應(yīng)算法在解決穿透現(xiàn)象方面是切實(shí)可行的。

關(guān)鍵詞： 布料仿真; 碰撞檢測; 幾何約束; 碰撞響應(yīng); 平均力法; 分離軸

中圖分類號(hào)： TN911.1?34; TP391.4 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2020）01?0122?04

Improvement of traditional geometric constraint method in collision response

JIN Yanxia， CHENG Siyue， WANG He， CHENG Qifu， ZHANG Jinrui

Abstract： In view of the imprecise displacement of next time step obtained by the implicit integration method in fabric simulation， a mean force method is proposed to predict the displacement of next time step. As far as this method is concerned， the displacement within a time step is predicted by force， which is more accurate than the implicit integration method which directly predicts the displacement. The error of displacement prediction can be reduced by 5% to 10%， and the error will become smaller and smaller as the time step increases. In addition， a collision response algorithm based on the separation axis is proposed to deal with the detected penetration by the collision detection. In this method， the collision plane and the separation axis are determined firstly， and the penetrating part is projected onto the separation axis to obtain the penetration depth and penetration direction， then an instantaneous impulse and a damping force are exerted to the penetrating object to get the object back to the collision plane. It can be concluded from a large number of comparative experiments that the collision response algorithm based on the separation axis is feasible in solving penetration.

Keywords： cloth simulation; collision detection; geometric constraint; collision response; average force method; separation axis

0 ?引 ?言

隨著計(jì)算機(jī)仿真技術(shù)的不斷提高，各種各樣的布料都可以在計(jì)算機(jī)中模擬，并且應(yīng)用在各種領(lǐng)域中。在計(jì)算機(jī)仿真中，布料仿真是重要的研究內(nèi)容之一，并且在游戲制作、動(dòng)畫影視方面也具有很大的應(yīng)用價(jià)值。但是由于其材料的特性以及結(jié)構(gòu)，使得布料仿真在實(shí)際模擬中并沒有那么簡單。

近20多年計(jì)算機(jī)仿真技術(shù)在不斷進(jìn)步，人們通過對(duì)布料結(jié)構(gòu)不斷改進(jìn)，算法效率不斷提高，布料仿真技術(shù)也有了質(zhì)的飛躍。但是，在模擬過程中還是會(huì)出現(xiàn)比如“超彈”和“穿透”等難以處理的情景，在視覺上呈現(xiàn)出的效果難以達(dá)到預(yù)期效果。本文通過對(duì)碰撞響應(yīng)的整理分析，對(duì)現(xiàn)有的算法做了如下改進(jìn)：在預(yù)測位移時(shí)，使用單位時(shí)間步長的平均力來預(yù)測下一時(shí)間步長的位移，減小了預(yù)測的誤差;在處理“穿透”現(xiàn)象時(shí)，提出使用分離軸的方法來修正結(jié)果，增強(qiáng)其穩(wěn)定性，在視覺效果上表現(xiàn)更加真實(shí)。

1 ?布料模型的建立

質(zhì)點(diǎn)彈簧模型主要分為兩種：一種是經(jīng)典質(zhì)點(diǎn)彈簧模型，如圖1a）所示;另一種是改進(jìn)后的質(zhì)點(diǎn)彈簧模型，如圖1b）所示。這兩種結(jié)構(gòu)模型的不同點(diǎn)是質(zhì)點(diǎn)之間的彈簧種類不同。文獻(xiàn)[1]針對(duì)傳統(tǒng)服裝仿真方法提出了改進(jìn)。本文在建模時(shí)布料采用三角面片組成，因此選擇改進(jìn)后的質(zhì)點(diǎn)彈簧模型進(jìn)行布料建模[2]。

改進(jìn)后的彈簧模型減少了彈簧的種類，提高了計(jì)算效率。利用三角網(wǎng)格模擬布料使布料更穩(wěn)定，避免運(yùn)動(dòng)過程中產(chǎn)生的抖動(dòng)現(xiàn)象[3]。彈簧?質(zhì)點(diǎn)模型是由質(zhì)點(diǎn)和無質(zhì)量、自然長度不為零的線性彈簧組成。由胡可定律可知，在彈性限度內(nèi)當(dāng)質(zhì)點(diǎn)之間彈簧的自然長度發(fā)生改變時(shí)，無論伸長還是縮短，其改變量和彈簧所受的彈力是成正比的。假設(shè)用[i，j]表示兩個(gè)相鄰的質(zhì)點(diǎn)，其質(zhì)點(diǎn)之間的彈力計(jì)算如式（1）所示：

[Fij=k1-Lxijxij] （1）

式中：[Fij]表示質(zhì)點(diǎn)[i，j]之間的彈力;[k]表示彈性系數(shù);[xij]表示彈簧在某個(gè)時(shí)刻的矢量;[L]表示彈簧的自然長度。

本文用泰勒公式一階展開式對(duì)式（1）進(jìn)行一些簡化。因?yàn)閺椈傻淖匀婚L度為[L]，在[x=L]處的一階泰勒展開式近似表示平方根函數(shù)，得到式（2），式中只進(jìn)行一次除法操作，對(duì)于模型的[N]個(gè)質(zhì)點(diǎn)來說，每一幀都只要計(jì)算[N]個(gè)除法，并且當(dāng)[L2]初始化時(shí)還可以預(yù)計(jì)算，這樣可以節(jié)省大量時(shí)間，并且還能保證計(jì)算的準(zhǔn)確性。

[Fij=kL2xij2+L2-12xij] （2）

此外，還要考慮內(nèi)力對(duì)實(shí)驗(yàn)的影響。本文的實(shí)驗(yàn)并未使用經(jīng)典方法對(duì)內(nèi)力進(jìn)行積分，通過牛頓定律計(jì)算之后確定質(zhì)點(diǎn)的位置以及速度，而是在求解了內(nèi)力之后根據(jù)內(nèi)力對(duì)彈簧質(zhì)點(diǎn)的位置進(jìn)行修正（距離約束），即當(dāng)彈簧長度大于或者小于其自然長度[L]時(shí)，拉近或者推遠(yuǎn)兩個(gè)質(zhì)點(diǎn)的位置，移動(dòng)的向量為[L1]：

[L1=L2xij+L2-12xij] （3）

2 ?布料碰撞檢測

在計(jì)算機(jī)仿真中，布料的運(yùn)動(dòng)會(huì)受到各種力的作用，還可能會(huì)與周圍的物體發(fā)生碰撞。如果碰撞問題處理的不夠好，則可能會(huì)發(fā)生穿透現(xiàn)象，會(huì)影響視覺上的觀感，而且還影響模擬結(jié)果。文獻(xiàn)[4]在ICRA上提出了基于采樣的運(yùn)動(dòng)規(guī)劃工作空間中的包圍體層次快速碰撞檢測。文獻(xiàn)[5]提出基于矢量的窄相碰撞檢測距離計(jì)算方法。文獻(xiàn)[6]通過實(shí)驗(yàn)確定基于離散導(dǎo)向多面體包圍盒（26?DOPs）的包圍盒層次樹（BVHs）。文獻(xiàn)[7]提出一種依賴包圍盒緊密率及多層建模結(jié)構(gòu)的混合碰撞檢測算法。為了保證正常模擬，本文對(duì)布料質(zhì)點(diǎn)與三角面片進(jìn)行碰撞檢測。

2.1 ?基元相交檢測

對(duì)于檢測質(zhì)點(diǎn)和三角面片的碰撞現(xiàn)象用的比較多的是文獻(xiàn)[8]提出的碰撞檢測算法，該算法的核心思想首先要判斷質(zhì)點(diǎn)是否在三角面片上，然后再判斷它們是否發(fā)生相交，如圖2a）所示。該算法比較簡便，但是要找一個(gè)閾值[n]，確定這個(gè)閾值的值是比較困難的，因?yàn)檫@個(gè)[n]值直接決定碰撞檢測結(jié)果的好壞。

本文參考唐勇等人改進(jìn)后的算法來進(jìn)行布料和物體之間的基元相交檢測，如圖2b）所示。為了簡化計(jì)算，假設(shè)質(zhì)點(diǎn)在一個(gè)時(shí)間片段內(nèi)的運(yùn)動(dòng)軌跡[s]是一個(gè)線段。步驟如下：

1） 如果質(zhì)點(diǎn)運(yùn)動(dòng)軌跡的兩個(gè)端點(diǎn)為[M0]和[M1]，[t]是一個(gè)時(shí)間片段，則線段上任意一點(diǎn)[M]的運(yùn)動(dòng)軌跡滿足式（4）：

[M=M0+t?ss=M1-M0，0≤t≤1] （4）

若被碰撞物體的三角面片的三個(gè)端點(diǎn)分別為[A0]，[A1]，[A2]，則三角面片上任意一點(diǎn)[H]的運(yùn)動(dòng)軌跡滿足式（5）：

[H=wA0+uA1+vA2w+u+v=1，0≤w，v，u≤1] （5）

2） 假設(shè)運(yùn)動(dòng)軌跡線段與三角面片相交，則可以通過聯(lián)立式（4）和式（5）求出交點(diǎn)，解出[w]，[u]，[v]的數(shù)值。判斷[t，u，v∈[0，1]]，若成立，則相交，如式（6）所示：

[tuv=1（s×（A-A0））?（A1-A0）?（（M0-A0）×（A1-A0））?（A2-A0）（s×（A2-A0））?（M0-A0）（（M0-A0）×（A1-A0））×s] （6）

2.2 ?包圍盒相交檢測

在虛擬環(huán)境中檢測物體是否發(fā)生碰撞的主要方法之一是層次包圍盒法。層次包圍盒法采用包圍盒樹來逐漸逼近碰撞體的幾何特性。本文使用AABB包圍盒來進(jìn)行相交檢測[9]，通過圖3中的算法流程（二叉樹的相交檢測）可以大大提高檢測速度。

3 ?碰撞響應(yīng)

3.1 ?碰撞響應(yīng)的處理

處理碰撞響應(yīng)的方法主要是對(duì)碰撞質(zhì)點(diǎn)施加一個(gè)瞬間的力[10]。但是這種方法容易產(chǎn)生“邊緣跳動(dòng)”現(xiàn)象。本文則主要對(duì)幾何約束法加以改進(jìn)，在隱式積分法思想的基礎(chǔ)上，改變其預(yù)測位移的思想，通過計(jì)算力對(duì)發(fā)生碰撞之后的情況進(jìn)行更加詳細(xì)的分析和計(jì)算，使得布料動(dòng)畫表現(xiàn)更加穩(wěn)定、真實(shí)。

據(jù)現(xiàn)有的物理知識(shí)可知，布料發(fā)生的碰撞基本上是非彈性碰撞。發(fā)生碰撞的兩個(gè)物體表面接觸會(huì)產(chǎn)生摩擦力。假設(shè)一個(gè)質(zhì)點(diǎn)[P]與物體表面在點(diǎn)[H]上相接觸，[n]表示物體表面在[H]點(diǎn)的單位法向量，質(zhì)點(diǎn)會(huì)在沿著[H]點(diǎn)法向量方向有一個(gè)正壓力[FN]，令[FN=（F?n）?n]，[n]為（0，0，1）。而切向方向，有一個(gè)[F]的切向分量[FT]，令[FT=（F?n）?n]，[n]為（1，1，0）。根據(jù)摩擦力定律得出：

1） 如果[FT

2） 當(dāng)[FT≥kfFN]時(shí)，[FT]為滑動(dòng)摩擦，摩擦力為滑動(dòng)摩擦力，大小與[FN]的大小成正比，方向與[FT]反向，此時(shí)質(zhì)點(diǎn)受力如式（7）所示：

[Fs=FT-kf?FN?FTFT] （7）

若估計(jì)在下一個(gè)時(shí)間步長質(zhì)點(diǎn)的位置，須考慮[FT]的準(zhǔn)確度;因?yàn)橘|(zhì)點(diǎn)的受力情況在一個(gè)時(shí)間步長內(nèi)可能會(huì)發(fā)生變化，此時(shí)合力[FT]就與上述所講不符。

由于合力是變力，本文改進(jìn)了合力的求解方法，采用這個(gè)時(shí)間步長內(nèi)的平均受力來近似地表示在一個(gè)時(shí)間步長內(nèi)的力（下文統(tǒng)一稱為平均力），如式（8）所示：

[F=FT+FT+Δt2] （8）

聯(lián)立式（7），式（8）可得式（9），其中，[kf]是摩擦系數(shù)，實(shí)際上滑動(dòng)摩擦系數(shù)與靜摩擦系數(shù)并不相等，這里假定兩種摩擦系數(shù)取值相同。

[Fs=FT+FT+Δt2-kf?FN?FTFT] （9）

式（12）預(yù)測的是[T+Δt]時(shí)刻質(zhì)點(diǎn)的力，式（13）是[λ]的計(jì)算方法。將式（13）代入式（12）中可以計(jì)算出[T+Δt]時(shí)刻的力，將式（12）代入到式（9）中則可以求出在一個(gè)時(shí)間步長的平均受力。這樣，得到了更為準(zhǔn)確的位移的值。

[pT+Δt=pT+ΔTvT+（Δt）2FT2] （10）

[vT+Δt=vT+λΔtFT] （11）

[FT+Δt=F（pT+Δt，vT+Δt）] （12）

[λ=0.5+T=1N（FT+Δt）（FT-0.5ΔtFDT+Δt）T=1N（FT-0.5ΔtFDT+Δt）2] ? ? （13）

[FDT+Δt=kf?FN?FTFT] （14）

這時(shí)，可以求得質(zhì)點(diǎn)的速度如式（15）所示，質(zhì)點(diǎn)的位置如式（16）所示。

[v=v+Fsm?Δt] （15）

[p=p+Fsm?Δt] （16）

3.2 ?穿透現(xiàn)象的處理

當(dāng)然，在布料仿真的過程中很容易發(fā)生穿透現(xiàn)象。對(duì)于碰撞過程中發(fā)生的穿透現(xiàn)象，本文提出使用分離坐標(biāo)軸的方法。該方法需要計(jì)算出碰撞物的相交深度和碰撞物分離開的方向。相交深度和方向的組合即為最小平移距離，該距離作為將物體分離的最小向量。當(dāng)兩個(gè)物體發(fā)生相交時(shí)，計(jì)算兩個(gè)物體在分離軸上的相交深度，這個(gè)相交深度提供一個(gè)推動(dòng)向量，將向量應(yīng)用到一個(gè)物體上，以便物體在軸上的投影停止交疊。

這里需要設(shè)定一個(gè)分離軸，如果兩個(gè)面片發(fā)生穿透現(xiàn)象的話，可以將其中一個(gè)三角面片所在的平面設(shè)定為發(fā)生碰撞的平面，而將垂直于這個(gè)平面的軸設(shè)置為分離軸，如圖4所示，若以[b]面片所在的面為碰撞平面，垂直于[b]面的軸為分離軸（分離軸的方向?yàn)橄嘟簧疃鹊姆祷胤较颍嘟簧疃萚l]通過計(jì)算其在分離軸上的投影而得到。

確定了分離軸之后，兩個(gè)穿透的物體會(huì)返回一個(gè)相交深度值。此時(shí)，給[a]面片一個(gè)初始的沖量和力，讓其在一個(gè)時(shí)間段內(nèi)從穿透的位置返回到碰撞平面上。這里需要計(jì)算這個(gè)初始沖量和力的大小。為了理解簡單一些，從反方向考慮，一個(gè)質(zhì)點(diǎn)受力從靜止到加速到[vt]，經(jīng)過的位移是[l]。根據(jù)式（17），可以求得加速度為式（18）。質(zhì)點(diǎn)初始速度為0，末速度為[vt]，將式（18）代入式（20）中可得[vt]為式（21）。將得到的[vt]作為初速度，給[a]面片一個(gè)大小為[mv0]的瞬間沖量，并施加一個(gè)大小為[F]的阻尼力，[a]面片位移在達(dá)到相交深度[l]時(shí)可以剛好停下來。

[l=12at2] （17）

[a=2lt2] （18）

[F=ma] （19）

[v2t-v20=2al] （20）

[vt=2lt] （21）

4 ?實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)基于Windows操作系統(tǒng)，使用Unity3D模擬布料仿真過程。硬件環(huán)境為：Inter[?] Xeon[?] CPU E5?2630 v3 @ 2.40 GHz 64.0GRAM 顯卡為NVIDIA Quadro K5200。

本文在碰撞響應(yīng)的算法中，采用單位步長的平均力來計(jì)算加速度，相對(duì)于已有的隱式積分法來計(jì)算加速度的方法，提高了算法的精確性。

圖5為平均力法和傳統(tǒng)約束力法得出結(jié)果的對(duì)比圖，從圖5中可以明顯看出，比起傳統(tǒng)約束力法，平均力法得出的預(yù)測值更加接近實(shí)際值，誤差降低5%～10%，并且隨著時(shí)間步長的增大，平均力法得出的預(yù)測值相較于瞬時(shí)力法得出的預(yù)測值誤差會(huì)越來越低。

在處理穿透現(xiàn)象時(shí)，本文提出的分離軸算法可以解決布料在自碰撞過程中的穿透現(xiàn)象。圖6是在未使用分離軸算法的情況下做實(shí)驗(yàn)的效果圖，從圖中標(biāo)記處可以很明顯地看出布料從球面上滑下到落地后靜止，一直都會(huì)有穿透現(xiàn)象的發(fā)生。從圖7中可以看到布料從球面滑下直到落地后靜止，即使布料發(fā)生了自碰撞也并沒有穿透現(xiàn)象。所以，分離軸算法解決穿透現(xiàn)象十分可行且穩(wěn)定。

5 ?結(jié) ?論

本文通過實(shí)驗(yàn)針對(duì)位移的預(yù)測和穿透現(xiàn)象得出以下結(jié)論：

1） 平均力法計(jì)算加速度，預(yù)算在下一個(gè)時(shí)間步長質(zhì)點(diǎn)的位移。通過計(jì)算一個(gè)時(shí)間步長的平均力來計(jì)算加速度，預(yù)算在這個(gè)時(shí)間步長內(nèi)質(zhì)點(diǎn)的位移，得到的結(jié)果比傳統(tǒng)約束法更加精確。但是，只取兩個(gè)點(diǎn)的話準(zhǔn)確度離準(zhǔn)確值還有點(diǎn)距離，如果要取更多點(diǎn)的話，會(huì)增大計(jì)算量，所以下一步還需要改進(jìn)算法，降低計(jì)算量。

2） 針對(duì)布料在自碰撞時(shí)發(fā)生的穿透現(xiàn)象，本文提出基于分離軸的計(jì)算方法。解決了仿真過程中的穿透現(xiàn)象，令發(fā)生穿透的物體可以在不影響視覺觀感的前提下返回到被穿透物體的表面，穩(wěn)定流暢地表現(xiàn)了布料的仿真運(yùn)動(dòng)。

參考文獻(xiàn)

[1] 張華忠，侯進(jìn).基于碰撞檢測算法的動(dòng)態(tài)服裝仿真研究[J].科學(xué)技術(shù)與工程，2017（31）：294?297.

[2] 唐勇，嚴(yán)凱麗，劉宇涵，等.多形態(tài)布料仿真中與剛體的實(shí)時(shí)碰撞檢測[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37（10）：2347?2350.

[3] 呂夢(mèng)雅，許立瑤，唐勇，等.隨機(jī)可控風(fēng)場中三維布料實(shí)時(shí)仿真[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（12）：2769?2772.

[4] SCHWESINGER U， SIEGWART R， FURGALE P. Fast collision detection through bounding volume hierarchies in workspace?time space for sampling?based motion planners [C]// 2015 IEEE International Conference on Robotics and Automation. Seattle， WA： IEEE， 2015： 63?68.

[5] SULAIMAN H A， OTHMAN M A， SAAT M S M， et al. Vector?based technique for distance computation in narrow phase collision detection [C]// 2014 International Symposium on Technology Management and Emerging Technologies. Bandung： IEEE， 2014： 506?510.

[6] 周清玲，劉艷，程天翔.大規(guī)模柔體的連續(xù)碰撞檢測算法[J].中國圖象圖形學(xué)報(bào)，2016，21（7）：901?912.

[7] 胡春安，謝偉超，王振東.依賴包圍盒緊密率及多層建模結(jié)構(gòu)的混合碰撞檢測算法[J].科學(xué)技術(shù)與工程，2018（16）：74?80.

[8] BRIDSON R， ANDERSON J， FEDKIW R. Robust treatment of collisions， contact and friction for cloth animation [J]. ACM transactions on graphics， 2002， 21（3）： 594?603.

[9] HUBER M， EBERHARDT B， WEISKOPF D. Boundary handling at cloth?fluid contact [J]. Computer graphics forum， 2015， 34（1）： 14?25.

[10] 常元章.基于質(zhì)點(diǎn)—彈簧模型的布料仿真[D].天津：天津大學(xué)，2008.

作者簡介：靳雁霞（1973—），女，博士，副教授，CCF會(huì)員，主要研究方向?yàn)樘摂M現(xiàn)實(shí)、圖形圖像處理。