碰撞響應中對傳統幾何約束法的改進

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

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

關鍵詞： 布料仿真; 碰撞檢測; 幾何約束; 碰撞響應; 平均力法; 分離軸

中圖分類號： TN911.1?34; TP391.4 ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 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 ?引 ?言

隨著計算機仿真技術的不斷提高，各種各樣的布料都可以在計算機中模擬，并且應用在各種領域中。在計算機仿真中，布料仿真是重要的研究內容之一，并且在游戲制作、動畫影視方面也具有很大的應用價值。但是由于其材料的特性以及結構，使得布料仿真在實際模擬中并沒有那么簡單。

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

1 ?布料模型的建立

質點彈簧模型主要分為兩種：一種是經典質點彈簧模型，如圖1a）所示;另一種是改進后的質點彈簧模型，如圖1b）所示。這兩種結構模型的不同點是質點之間的彈簧種類不同。文獻[1]針對傳統服裝仿真方法提出了改進。本文在建模時布料采用三角面片組成，因此選擇改進后的質點彈簧模型進行布料建模[2]。

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

[Fij=k1-Lxijxij] （1）

式中：[Fij]表示質點[i，j]之間的彈力;[k]表示彈性系數;[xij]表示彈簧在某個時刻的矢量;[L]表示彈簧的自然長度。

本文用泰勒公式一階展開式對式（1）進行一些簡化。因為彈簧的自然長度為[L]，在[x=L]處的一階泰勒展開式近似表示平方根函數，得到式（2），式中只進行一次除法操作，對于模型的[N]個質點來說，每一幀都只要計算[N]個除法，并且當[L2]初始化時還可以預計算，這樣可以節省大量時間，并且還能保證計算的準確性。

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

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

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

2 ?布料碰撞檢測

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

2.1 ?基元相交檢測

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

本文參考唐勇等人改進后的算法來進行布料和物體之間的基元相交檢測，如圖2b）所示。為了簡化計算，假設質點在一個時間片段內的運動軌跡[s]是一個線段。步驟如下：

1） 如果質點運動軌跡的兩個端點為[M0]和[M1]，[t]是一個時間片段，則線段上任意一點[M]的運動軌跡滿足式（4）：

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

若被碰撞物體的三角面片的三個端點分別為[A0]，[A1]，[A2]，則三角面片上任意一點[H]的運動軌跡滿足式（5）：

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

2） 假設運動軌跡線段與三角面片相交，則可以通過聯立式（4）和式（5）求出交點，解出[w]，[u]，[v]的數值。判斷[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 ?包圍盒相交檢測

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

3 ?碰撞響應

3.1 ?碰撞響應的處理

處理碰撞響應的方法主要是對碰撞質點施加一個瞬間的力[10]。但是這種方法容易產生“邊緣跳動”現象。本文則主要對幾何約束法加以改進，在隱式積分法思想的基礎上，改變其預測位移的思想，通過計算力對發生碰撞之后的情況進行更加詳細的分析和計算，使得布料動畫表現更加穩定、真實。

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

1） 如果[FT

2） 當[FT≥kfFN]時，[FT]為滑動摩擦，摩擦力為滑動摩擦力，大小與[FN]的大小成正比，方向與[FT]反向，此時質點受力如式（7）所示：

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

若估計在下一個時間步長質點的位置，須考慮[FT]的準確度;因為質點的受力情況在一個時間步長內可能會發生變化，此時合力[FT]就與上述所講不符。

由于合力是變力，本文改進了合力的求解方法，采用這個時間步長內的平均受力來近似地表示在一個時間步長內的力（下文統一稱為平均力），如式（8）所示：

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

聯立式（7），式（8）可得式（9），其中，[kf]是摩擦系數，實際上滑動摩擦系數與靜摩擦系數并不相等，這里假定兩種摩擦系數取值相同。

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

式（12）預測的是[T+Δt]時刻質點的力，式（13）是[λ]的計算方法。將式（13）代入式（12）中可以計算出[T+Δt]時刻的力，將式（12）代入到式（9）中則可以求出在一個時間步長的平均受力。這樣，得到了更為準確的位移的值。

[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）

這時，可以求得質點的速度如式（15）所示，質點的位置如式（16）所示。

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

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

3.2 ?穿透現象的處理

當然，在布料仿真的過程中很容易發生穿透現象。對于碰撞過程中發生的穿透現象，本文提出使用分離坐標軸的方法。該方法需要計算出碰撞物的相交深度和碰撞物分離開的方向。相交深度和方向的組合即為最小平移距離，該距離作為將物體分離的最小向量。當兩個物體發生相交時，計算兩個物體在分離軸上的相交深度，這個相交深度提供一個推動向量，將向量應用到一個物體上，以便物體在軸上的投影停止交疊。

這里需要設定一個分離軸，如果兩個面片發生穿透現象的話，可以將其中一個三角面片所在的平面設定為發生碰撞的平面，而將垂直于這個平面的軸設置為分離軸，如圖4所示，若以[b]面片所在的面為碰撞平面，垂直于[b]面的軸為分離軸（分離軸的方向為相交深度的返回方向），相交深度[l]通過計算其在分離軸上的投影而得到。

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

[l=12at2] （17）

[a=2lt2] （18）

[F=ma] （19）

[v2t-v20=2al] （20）

[vt=2lt] （21）

4 ?實驗結果與分析

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

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

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

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

5 ?結 ?論

本文通過實驗針對位移的預測和穿透現象得出以下結論：

1） 平均力法計算加速度，預算在下一個時間步長質點的位移。通過計算一個時間步長的平均力來計算加速度，預算在這個時間步長內質點的位移，得到的結果比傳統約束法更加精確。但是，只取兩個點的話準確度離準確值還有點距離，如果要取更多點的話，會增大計算量，所以下一步還需要改進算法，降低計算量。

2） 針對布料在自碰撞時發生的穿透現象，本文提出基于分離軸的計算方法。解決了仿真過程中的穿透現象，令發生穿透的物體可以在不影響視覺觀感的前提下返回到被穿透物體的表面，穩定流暢地表現了布料的仿真運動。

參考文獻

[1] 張華忠，侯進.基于碰撞檢測算法的動態服裝仿真研究[J].科學技術與工程，2017（31）：294?297.

[2] 唐勇，嚴凱麗，劉宇涵，等.多形態布料仿真中與剛體的實時碰撞檢測[J].小型微型計算機系統，2016，37（10）：2347?2350.

[3] 呂夢雅，許立瑤，唐勇，等.隨機可控風場中三維布料實時仿真[J].小型微型計算機系統，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] 周清玲，劉艷，程天翔.大規模柔體的連續碰撞檢測算法[J].中國圖象圖形學報，2016，21（7）：901?912.

[7] 胡春安，謝偉超，王振東.依賴包圍盒緊密率及多層建模結構的混合碰撞檢測算法[J].科學技術與工程，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] 常元章.基于質點—彈簧模型的布料仿真[D].天津：天津大學，2008.

作者簡介：靳雁霞（1973—），女，博士，副教授，CCF會員，主要研究方向為虛擬現實、圖形圖像處理。