靳雁霞 程思岳 王賀 程琦甫 張晉瑞
摘 ?要: 為了解決目前布料仿真中用隱式積分法預(yù)測(cè)所得的下一個(gè)時(shí)間步長(zhǎng)位移不精確的情況,提出一種新的平均力法來(lái)預(yù)測(cè)下一個(gè)時(shí)間步長(zhǎng)的位移。該方法通過(guò)力來(lái)預(yù)測(cè)一個(gè)時(shí)間步長(zhǎng)內(nèi)的位移,比起直接預(yù)測(cè)位移的隱式積分方法更加精確,其位移預(yù)測(cè)的誤差能夠減少5%~10%,并且隨著時(shí)間步長(zhǎng)的增加,誤差會(huì)越來(lái)越小。此外,針對(duì)碰撞檢測(cè)后檢測(cè)到的穿透現(xiàn)象,提出一種基于分離軸的碰撞響應(yīng)算法解決穿透現(xiàn)象。該方法首先確定碰撞平面以及分離軸,將發(fā)生穿透的部分投影到分離軸上,得到穿透深度和穿透方向,給發(fā)生穿透的物體一個(gè)瞬時(shí)的沖量和阻尼力,讓物體返回碰撞平面上。通過(guò)大量的實(shí)驗(yàn)對(duì)比可以得出,基于分離軸的碰撞響應(yīng)算法在解決穿透現(xiàn)象方面是切實(shí)可行的。
關(guān)鍵詞: 布料仿真; 碰撞檢測(cè); 幾何約束; 碰撞響應(yīng); 平均力法; 分離軸
中圖分類(lèi)號(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ī)仿真中,布料仿真是重要的研究?jī)?nèi)容之一,并且在游戲制作、動(dòng)畫(huà)影視方面也具有很大的應(yīng)用價(jià)值。但是由于其材料的特性以及結(jié)構(gòu),使得布料仿真在實(shí)際模擬中并沒(méi)有那么簡(jiǎn)單。
近20多年計(jì)算機(jī)仿真技術(shù)在不斷進(jìn)步,人們通過(guò)對(duì)布料結(jié)構(gòu)不斷改進(jìn),算法效率不斷提高,布料仿真技術(shù)也有了質(zhì)的飛躍。但是,在模擬過(guò)程中還是會(huì)出現(xiàn)比如“超彈”和“穿透”等難以處理的情景,在視覺(jué)上呈現(xiàn)出的效果難以達(dá)到預(yù)期效果。本文通過(guò)對(duì)碰撞響應(yīng)的整理分析,對(duì)現(xiàn)有的算法做了如下改進(jìn):在預(yù)測(cè)位移時(shí),使用單位時(shí)間步長(zhǎng)的平均力來(lái)預(yù)測(cè)下一時(shí)間步長(zhǎng)的位移,減小了預(yù)測(cè)的誤差;在處理“穿透”現(xiàn)象時(shí),提出使用分離軸的方法來(lái)修正結(jié)果,增強(qiáng)其穩(wěn)定性,在視覺(jué)效果上表現(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)之間的彈簧種類(lèi)不同。文獻(xiàn)[1]針對(duì)傳統(tǒng)服裝仿真方法提出了改進(jìn)。本文在建模時(shí)布料采用三角面片組成,因此選擇改進(jìn)后的質(zhì)點(diǎn)彈簧模型進(jìn)行布料建模[2]。
改進(jìn)后的彈簧模型減少了彈簧的種類(lèi),提高了計(jì)算效率。利用三角網(wǎng)格模擬布料使布料更穩(wěn)定,避免運(yùn)動(dòng)過(guò)程中產(chǎn)生的抖動(dòng)現(xiàn)象[3]。彈簧?質(zhì)點(diǎn)模型是由質(zhì)點(diǎn)和無(wú)質(zhì)量、自然長(zhǎng)度不為零的線性彈簧組成。由胡可定律可知,在彈性限度內(nèi)當(dāng)質(zhì)點(diǎn)之間彈簧的自然長(zhǎng)度發(fā)生改變時(shí),無(wú)論伸長(zhǎng)還是縮短,其改變量和彈簧所受的彈力是成正比的。假設(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]表示彈簧的自然長(zhǎng)度。
本文用泰勒公式一階展開(kāi)式對(duì)式(1)進(jìn)行一些簡(jiǎn)化。因?yàn)閺椈傻淖匀婚L(zhǎng)度為[L],在[x=L]處的一階泰勒展開(kāi)式近似表示平方根函數(shù),得到式(2),式中只進(jìn)行一次除法操作,對(duì)于模型的[N]個(gè)質(zhì)點(diǎn)來(lái)說(shuō),每一幀都只要計(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)行積分,通過(guò)牛頓定律計(jì)算之后確定質(zhì)點(diǎn)的位置以及速度,而是在求解了內(nèi)力之后根據(jù)內(nèi)力對(duì)彈簧質(zhì)點(diǎn)的位置進(jìn)行修正(距離約束),即當(dāng)彈簧長(zhǎng)度大于或者小于其自然長(zhǎng)度[L]時(shí),拉近或者推遠(yuǎn)兩個(gè)質(zhì)點(diǎn)的位置,移動(dòng)的向量為[L1]:
[L1=L2xij+L2-12xij] (3)
2 ?布料碰撞檢測(cè)
在計(jì)算機(jī)仿真中,布料的運(yùn)動(dòng)會(huì)受到各種力的作用,還可能會(huì)與周?chē)奈矬w發(fā)生碰撞。如果碰撞問(wèn)題處理的不夠好,則可能會(huì)發(fā)生穿透現(xiàn)象,會(huì)影響視覺(jué)上的觀感,而且還影響模擬結(jié)果。文獻(xiàn)[4]在ICRA上提出了基于采樣的運(yùn)動(dòng)規(guī)劃工作空間中的包圍體層次快速碰撞檢測(cè)。文獻(xiàn)[5]提出基于矢量的窄相碰撞檢測(cè)距離計(jì)算方法。文獻(xiàn)[6]通過(guò)實(shí)驗(yàn)確定基于離散導(dǎo)向多面體包圍盒(26?DOPs)的包圍盒層次樹(shù)(BVHs)。文獻(xiàn)[7]提出一種依賴包圍盒緊密率及多層建模結(jié)構(gòu)的混合碰撞檢測(cè)算法。為了保證正常模擬,本文對(duì)布料質(zhì)點(diǎn)與三角面片進(jìn)行碰撞檢測(cè)。
2.1 ?基元相交檢測(cè)
對(duì)于檢測(cè)質(zhì)點(diǎn)和三角面片的碰撞現(xiàn)象用的比較多的是文獻(xiàn)[8]提出的碰撞檢測(cè)算法,該算法的核心思想首先要判斷質(zhì)點(diǎn)是否在三角面片上,然后再判斷它們是否發(fā)生相交,如圖2a)所示。該算法比較簡(jiǎn)便,但是要找一個(gè)閾值[n],確定這個(gè)閾值的值是比較困難的,因?yàn)檫@個(gè)[n]值直接決定碰撞檢測(cè)結(jié)果的好壞。
本文參考唐勇等人改進(jìn)后的算法來(lái)進(jìn)行布料和物體之間的基元相交檢測(cè),如圖2b)所示。為了簡(jiǎn)化計(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)軌跡線段與三角面片相交,則可以通過(guò)聯(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 ?包圍盒相交檢測(cè)
在虛擬環(huán)境中檢測(cè)物體是否發(fā)生碰撞的主要方法之一是層次包圍盒法。層次包圍盒法采用包圍盒樹(shù)來(lái)逐漸逼近碰撞體的幾何特性。本文使用AABB包圍盒來(lái)進(jìn)行相交檢測(cè)[9],通過(guò)圖3中的算法流程(二叉樹(shù)的相交檢測(cè))可以大大提高檢測(cè)速度。
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ù)測(cè)位移的思想,通過(guò)計(jì)算力對(duì)發(fā)生碰撞之后的情況進(jìn)行更加詳細(xì)的分析和計(jì)算,使得布料動(dòng)畫(huà)表現(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ǎng)質(zhì)點(diǎn)的位置,須考慮[FT]的準(zhǔn)確度;因?yàn)橘|(zhì)點(diǎn)的受力情況在一個(gè)時(shí)間步長(zhǎng)內(nèi)可能會(huì)發(fā)生變化,此時(shí)合力[FT]就與上述所講不符。 由于合力是變力,本文改進(jìn)了合力的求解方法,采用這個(gè)時(shí)間步長(zhǎng)內(nèi)的平均受力來(lái)近似地表示在一個(gè)時(shí)間步長(zhǎng)內(nèi)的力(下文統(tǒng)一稱(chē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ù)測(cè)的是[T+Δt]時(shí)刻質(zhì)點(diǎn)的力,式(13)是[λ]的計(jì)算方法。將式(13)代入式(12)中可以計(jì)算出[T+Δt]時(shí)刻的力,將式(12)代入到式(9)中則可以求出在一個(gè)時(shí)間步長(zhǎng)的平均受力。這樣,得到了更為準(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)然,在布料仿真的過(guò)程中很容易發(fā)生穿透現(xiàn)象。對(duì)于碰撞過(guò)程中發(fā)生的穿透現(xiàn)象,本文提出使用分離坐標(biāo)軸的方法。該方法需要計(jì)算出碰撞物的相交深度和碰撞物分離開(kāi)的方向。相交深度和方向的組合即為最小平移距離,該距離作為將物體分離的最小向量。當(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]通過(guò)計(jì)算其在分離軸上的投影而得到。 確定了分離軸之后,兩個(gè)穿透的物體會(huì)返回一個(gè)相交深度值。此時(shí),給[a]面片一個(gè)初始的沖量和力,讓其在一個(gè)時(shí)間段內(nèi)從穿透的位置返回到碰撞平面上。這里需要計(jì)算這個(gè)初始沖量和力的大小。為了理解簡(jiǎn)單一些,從反方向考慮,一個(gè)質(zhì)點(diǎn)受力從靜止到加速到[vt],經(jīng)過(guò)的位移是[l]。根據(jù)式(17),可以求得加速度為式(18)。質(zhì)點(diǎn)初始速度為0,末速度為[vt],將式(18)代入式(20)中可得[vt]為式(21)。將得到的[vt]作為初速度,給[a]面片一個(gè)大小為[mv0]的瞬間沖量,并施加一個(gè)大小為[F]的阻尼力,[a]面片位移在達(dá)到相交深度[l]時(shí)可以剛好停下來(lái)。 [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模擬布料仿真過(guò)程。硬件環(huán)境為:Inter[?] Xeon[?] CPU E5?2630 v3 @ 2.40 GHz 64.0GRAM 顯卡為NVIDIA Quadro K5200。 本文在碰撞響應(yīng)的算法中,采用單位步長(zhǎng)的平均力來(lái)計(jì)算加速度,相對(duì)于已有的隱式積分法來(lái)計(jì)算加速度的方法,提高了算法的精確性。 圖5為平均力法和傳統(tǒng)約束力法得出結(jié)果的對(duì)比圖,從圖5中可以明顯看出,比起傳統(tǒng)約束力法,平均力法得出的預(yù)測(cè)值更加接近實(shí)際值,誤差降低5%~10%,并且隨著時(shí)間步長(zhǎng)的增大,平均力法得出的預(yù)測(cè)值相較于瞬時(shí)力法得出的預(yù)測(cè)值誤差會(huì)越來(lái)越低。 在處理穿透現(xiàn)象時(shí),本文提出的分離軸算法可以解決布料在自碰撞過(guò)程中的穿透現(xiàn)象。圖6是在未使用分離軸算法的情況下做實(shí)驗(yàn)的效果圖,從圖中標(biāo)記處可以很明顯地看出布料從球面上滑下到落地后靜止,一直都會(huì)有穿透現(xiàn)象的發(fā)生。從圖7中可以看到布料從球面滑下直到落地后靜止,即使布料發(fā)生了自碰撞也并沒(méi)有穿透現(xiàn)象。所以,分離軸算法解決穿透現(xiàn)象十分可行且穩(wěn)定。 5 ?結(jié) ?論 本文通過(guò)實(shí)驗(yàn)針對(duì)位移的預(yù)測(cè)和穿透現(xiàn)象得出以下結(jié)論: 1) 平均力法計(jì)算加速度,預(yù)算在下一個(gè)時(shí)間步長(zhǎng)質(zhì)點(diǎn)的位移。通過(guò)計(jì)算一個(gè)時(shí)間步長(zhǎng)的平均力來(lái)計(jì)算加速度,預(yù)算在這個(gè)時(shí)間步長(zhǎng)內(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ì)算方法。解決了仿真過(guò)程中的穿透現(xiàn)象,令發(fā)生穿透的物體可以在不影響視覺(jué)觀感的前提下返回到被穿透物體的表面,穩(wěn)定流暢地表現(xiàn)了布料的仿真運(yùn)動(dòng)。 參考文獻(xiàn) [1] 張華忠,侯進(jìn).基于碰撞檢測(cè)算法的動(dòng)態(tài)服裝仿真研究[J].科學(xué)技術(shù)與工程,2017(31):294?297. [2] 唐勇,嚴(yán)凱麗,劉宇涵,等.多形態(tài)布料仿真中與剛體的實(shí)時(shí)碰撞檢測(cè)[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(10):2347?2350. [3] 呂夢(mèng)雅,許立瑤,唐勇,等.隨機(jī)可控風(fēng)場(chǎ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ù)碰撞檢測(cè)算法[J].中國(guó)圖象圖形學(xué)報(bào),2016,21(7):901?912. [7] 胡春安,謝偉超,王振東.依賴包圍盒緊密率及多層建模結(jié)構(gòu)的混合碰撞檢測(cè)算法[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. 作者簡(jiǎn)介:靳雁霞(1973—),女,博士,副教授,CCF會(huì)員,主要研究方向?yàn)樘摂M現(xiàn)實(shí)、圖形圖像處理。