靳雁霞，馬博，賈瑤，陳治旭，蘆燁

中北大學(xué)大數(shù)據(jù)學(xué)院，太原 030051

0 引 言

在變形體仿真建模過程中，碰撞檢測算法的計(jì)算量最大，耗時(shí)最多。為了滿足應(yīng)用中實(shí)時(shí)性的要求，提高算法的效率成為虛擬仿真領(lǐng)域里的重要問題。在碰撞檢測過程中，層次包圍體(bounding volume hierarchies，BVH)技術(shù)是目前使用最多的方法。Hubbard(1993)首次提出了包圍盒技術(shù)，用4維幾何體或者球體逼近3維模型。為了適應(yīng)不同的模型，找到緊密率更高的包圍盒，又出現(xiàn)了自適應(yīng)橢球包圍盒(唐勇 等，2013)和基于虛擬球的包圍體(Wang等，2019)等新的包圍盒。隨著層次包圍體技術(shù)應(yīng)用的成熟，出現(xiàn)了一種基于層次代表性包圍盒的目標(biāo)干涉檢測的研究框架(Yazid等，2019)，并行布料仿真(Kim等，2019)和基于罰函數(shù)的碰撞求解(呂夢(mèng)雅 等，2020)。雖然效率有一定提升，但使用的都是單一的包圍盒。

2008年以后，許多專家發(fā)現(xiàn)單一的包圍盒都有自己的劣勢(shì)，單獨(dú)使用一種包圍盒會(huì)存在精度不足等問題，為了減少單一包圍盒的局限性，越來越多的學(xué)者開始研究混合包圍盒算法。混合包圍盒算法以球形(sphere)包圍盒、方向包圍盒(oriented bounding box，OBB)、軸對(duì)齊包圍盒(axis aligned bounding box，AABB)和離散有向多面體(discrete orientation polytopes，k-DOPs)為基礎(chǔ)，出現(xiàn)了Sphere-OBB混合包圍盒(朱元峰 等，2008)、AABB-OBB混合包圍盒(Tu和Yu，2009)和混合3種不同包圍盒AABB、OBB和k-DOPs(Feng等，2010)的混合算法。在復(fù)合平衡二叉樹碰撞檢測算法(Liu和Chen，2017)中，如果對(duì)象形狀和球體相似，采用sphere，否則使用OBB。通過使用Sphere-OBB和并行檢測技術(shù)來提高效率。但是，目前混合包圍盒的應(yīng)用大多使用多個(gè)不同的包圍盒，如在BVH樹上、下層分別使用簡單包圍盒和復(fù)雜包圍盒，或者所有結(jié)點(diǎn)外層使用緊密率差的包圍盒，內(nèi)層使用緊密率好的包圍盒(Zhu等，2016)。雖然混合包圍盒發(fā)揮了多個(gè)包圍盒的優(yōu)勢(shì)，但在計(jì)算成本、精確度和復(fù)雜環(huán)境下的數(shù)據(jù)處理很難達(dá)到平衡，局限性需要進(jìn)一步改進(jìn)。

機(jī)器學(xué)習(xí)具有處理大量數(shù)據(jù)的能力，可以進(jìn)行預(yù)測。目前，許多布料仿真都結(jié)合了機(jī)器學(xué)習(xí)來提高效率。Ye等人(2017)提出了一種新的管道技術(shù)，從預(yù)定義的表面方向、歷史數(shù)據(jù)和全局相交分析得出3種不同的方法。在服裝動(dòng)畫中使用機(jī)器學(xué)習(xí)研究人體運(yùn)動(dòng)與服裝變形(石敏 等，2017；張惠，2019)的關(guān)系，使布料更加精確。Jiang等人(2019)提出一種利用不同織物實(shí)現(xiàn)織物懸垂模擬的方法。通過構(gòu)造BP(back propagation)神經(jīng)網(wǎng)絡(luò)，得到織物力學(xué)參數(shù)與3維紡織仿真系統(tǒng)控制參數(shù)之間的非線性關(guān)系。Holden等人(2019)利用子空間模擬技術(shù)與機(jī)器學(xué)習(xí)相結(jié)合，當(dāng)耦合時(shí)，該方法可以非常有效地支持子空間的物理模擬。

針對(duì)目前的問題，本文在包圍盒方面提出了根節(jié)點(diǎn)雙層包圍盒算法，使用最簡單的包圍盒剔除沒有發(fā)生碰撞的粒子。同時(shí)，提出融合神經(jīng)網(wǎng)絡(luò)的碰撞檢測算法，訓(xùn)練神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)復(fù)雜的碰撞檢測過程，通過訓(xùn)練好的模型預(yù)測模型粒子是否發(fā)生碰撞。神經(jīng)網(wǎng)絡(luò)可以減少循環(huán)，避免檢測復(fù)雜的過程，提高碰撞檢測效率。

1 相關(guān)工作

1.1 包圍盒技術(shù)

D=(P1(tj)∩P2(tj)∩…∩Pn(tj))∪
(S1(tj)∩S2(tj)∩…∩Sn(tj))=?

(1)

則認(rèn)為物體沒有發(fā)生碰撞。

包圍盒技術(shù)是碰撞檢測領(lǐng)域的主要方法，常見的包圍盒有球形包圍盒、方向包圍盒、軸對(duì)齊包圍盒和離散多面體包圍盒(Wang等，2018)。本文根節(jié)點(diǎn)雙層包圍盒算法基于sphere和AABB兩種包圍盒，兩者的2維結(jié)構(gòu)如圖1所示。

圖1 包圍盒2維結(jié)構(gòu)圖Fig.1 Two-dimensional structure diagram of bounding box((a) AABB structure;(b) sphere structure)

球形包圍盒可以表示為

R={(x,y,z)|(x-Ox)2+
(y-Oy)2+(z-Oz)2

(2)

(3)

(4)

式中，Ox、Oy和Oz表示球形包圍盒中心O的x、y和z軸坐標(biāo)，xmin,xmax,ymin,ymax和zmin,zmax表示物體頂點(diǎn)投影在x、y和z軸上坐標(biāo)的最小、最大值，r表示半徑。

AABB包圍盒可以表示為

R={(x,y,z)||xc-x|≤rx,|yc-y|≤ry,|zc-z|≤rz}

(5)

rx=xmax-xmin,ry=ymax-ymin,rz=zmax-zmin

(6)

(7)

式中，xc、yc和zc表示AABB包圍盒中心C的坐標(biāo)，xmin,xmax,ymin,ymax,zmin,zmax表示物體頂點(diǎn)投影在x、y和z軸上坐標(biāo)的最小、最大值，r表示半徑。

1.2 包圍盒相交檢測

球形包圍盒的相交測試如圖2(a)所示。Oa和Ob為兩個(gè)包圍球的球心，在坐標(biāo)軸上的投影為O1和O2，R1和R2分別是兩個(gè)包圍球的半徑。若|Oa-Ob|>R1+R2，則表示沒有發(fā)生相交，否則兩球相交。

圖2 包圍盒相交測試原理圖Fig.2 Schematic diagram of bounding box intersection test((a) sphere intersection test;(b) AABB intersection test)

AABB包圍盒的相交測試如圖2(b)所示。AABB包圍盒的相交是包圍盒在x、y和z坐標(biāo)軸上的投影都相交，若在某一個(gè)坐標(biāo)軸上投影不相交，則兩個(gè)包圍盒不相交。La和Lb為兩個(gè)AABB包圍盒在坐標(biāo)軸上的投影，C1和C2為中點(diǎn)Ca和Cb的投影點(diǎn)。如果|Ca-Cb|>La+Lb，則投影不重疊，包圍盒沒有相交。

球形包圍盒和AABB包圍盒的相交測試，都是首先在AABB包圍盒上利用Voronoi域找到距離球形包圍盒球心O的最近點(diǎn)P，平面2維結(jié)構(gòu)如圖3所示。然后計(jì)算出球心O與點(diǎn)P之間的距離，如果|O-P|>r，則沒有發(fā)生相交。

圖3 球心O在AABB包圍盒上的最近點(diǎn)Fig.3 The nearest point of the center of the sphere on the AABB bounding box ((a) Voronoi field for a certain edge;(b) Voronoi field for a vertex)

2 根節(jié)點(diǎn)雙層包圍盒算法

在碰撞檢測過程中，不同包圍盒的構(gòu)建、更新以及包圍盒之間的相交檢測消耗的時(shí)間都不相同。在保證剔除率的前提下，為了減少包圍盒構(gòu)建和更新消耗的時(shí)間，本文利用簡單的包圍盒，提出根節(jié)點(diǎn)雙層包圍盒算法解決此問題。

2.1 根節(jié)點(diǎn)雙層包圍盒的構(gòu)建與碰撞檢測

使用最簡單的AABB包圍盒和sphere包圍盒構(gòu)建BVH結(jié)構(gòu)，如圖4(a)所示。在BVH中，非根節(jié)點(diǎn)使用sphere單個(gè)包圍盒，根節(jié)點(diǎn)使用雙層包圍盒。在布料模擬過程中，首先對(duì)根節(jié)點(diǎn)構(gòu)建一個(gè)sphere包圍盒，當(dāng)sphere包圍盒發(fā)生碰撞后，再對(duì)根節(jié)點(diǎn)構(gòu)建AABB包圍盒，這時(shí)根節(jié)點(diǎn)才具有雙層包圍盒，它的實(shí)際效果圖如圖4(b)所示。當(dāng)根節(jié)點(diǎn)的第2個(gè)包圍盒AABB發(fā)生碰撞以后，往下遍歷BVH結(jié)構(gòu)，直到葉子結(jié)點(diǎn)。

圖4 包圍盒層級(jí)結(jié)構(gòu)和根節(jié)點(diǎn)雙層包圍盒效果圖Fig.4 Bounding box hierarchy and root node double-layer bounding box effect diagram ((a) double-layer bounding box BVH structure of root node;(b) double-layer bounding box of root node)

碰撞檢測的具體步驟如下：

1)從根節(jié)點(diǎn)開始，采用sphere包圍盒構(gòu)建BVH樹，并進(jìn)行遍歷。

2)當(dāng)檢測到根節(jié)點(diǎn)發(fā)生碰撞時(shí)，對(duì)根節(jié)點(diǎn)構(gòu)建AABB包圍盒，否則，執(zhí)行步驟5)。

3)當(dāng)根節(jié)點(diǎn)的AABB包圍盒發(fā)生碰撞時(shí)，采用深度優(yōu)先的原則遍歷BVH樹，直到葉子結(jié)點(diǎn)。如果碰撞沒有發(fā)生，執(zhí)行步驟5)。

4)當(dāng)檢測到葉子結(jié)點(diǎn)發(fā)生碰撞，則進(jìn)行底層基本圖元的碰撞檢測，然后進(jìn)行碰撞響應(yīng)。

5)在下一個(gè)時(shí)間步長內(nèi)再次從根節(jié)點(diǎn)開始檢測碰撞是否發(fā)生。

2.2 根節(jié)點(diǎn)雙層包圍盒算法的優(yōu)勢(shì)

本文使用包圍盒的緊密率τ來更好地說明算法優(yōu)勢(shì)。緊密率τ、sphere包圍盒的緊密率τS和AABB包圍盒的緊密率τA計(jì)算為

(8)

式中，V(O)表示模擬布料的體積，V(B)表示包圍盒的體積。

將sphere包圍盒和AABB包圍盒的體積代入式(8),得

(9)

(10)

由圖5(a)可知，布料為平整狀態(tài)時(shí)，sphere包圍盒緊密率最差。在圖5(a)中，碰撞粒子運(yùn)動(dòng)方向與布料垂直，當(dāng)粒子與sphere包圍盒發(fā)生碰撞時(shí)，粒子與布料之間還有很大的空隙D。為了更精確地剔除未與布料發(fā)生碰撞的粒子，當(dāng)sphere包圍盒檢測出碰撞時(shí)，對(duì)根節(jié)點(diǎn)構(gòu)建AABB包圍盒。當(dāng)粒子與AABB包圍盒發(fā)生碰撞時(shí)，粒子與布料的間距很小，距離為圖5(b)中的d。這時(shí)再使用緊密率更好的包圍盒，不但布料與粒子距離的減少微乎其微，而且會(huì)增加包圍盒的構(gòu)造時(shí)間。為了減少包圍盒的構(gòu)造時(shí)間，使用最簡單的sphere包圍盒。然后通過遍歷BVH結(jié)構(gòu)，找出發(fā)生碰撞的精確位置。

圖5 根節(jié)點(diǎn)雙層包圍盒主視圖Fig.5 The front view of the double-layer bounding box of the root node ((a) double-layer bounding box;(b) enlarged view of bounding box AABB)

本文提出的根節(jié)點(diǎn)雙層包圍盒，使用了最簡單的兩個(gè)包圍盒，不僅構(gòu)造簡單，而且效率高。構(gòu)造包圍盒所用的時(shí)間比復(fù)雜包圍盒所用的時(shí)間少，且與簡單的包圍盒相比，本文的方法緊密率高。本文發(fā)揮了簡單包圍盒的優(yōu)勢(shì)，通過構(gòu)建雙層包圍盒消除了其劣勢(shì)。

3 融合神經(jīng)網(wǎng)絡(luò)

上述方法雖然可以提高碰撞檢測的效率，但是不適合處理模型復(fù)雜、數(shù)據(jù)量多的情況。由于布料的碰撞檢測需要檢測大量的點(diǎn)與三角形之間是否發(fā)生穿透，傳統(tǒng)包圍盒技術(shù)雖然可以將沒有碰撞的點(diǎn)進(jìn)行快速剔除，但無法在短時(shí)間內(nèi)處理大量的點(diǎn)。而機(jī)器學(xué)習(xí)中的方法可以處理大量的數(shù)據(jù)，并且運(yùn)行時(shí)間迅速，所以本文使用神經(jīng)網(wǎng)絡(luò)優(yōu)化碰撞檢測算法，減少包圍盒構(gòu)造的時(shí)間，提高算法碰撞檢測的效率。

3.1 構(gòu)建神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

本文神經(jīng)網(wǎng)絡(luò)的構(gòu)建基于開源神經(jīng)網(wǎng)絡(luò)庫OpenNN(open neural networks library)，OpenNN神經(jīng)網(wǎng)絡(luò)模型通過以下5個(gè)主要步驟進(jìn)行構(gòu)建。

1)數(shù)據(jù)集準(zhǔn)備。數(shù)據(jù)集準(zhǔn)備是解決問題的信息源。實(shí)驗(yàn)中，當(dāng)布料的點(diǎn)穿透了另一個(gè)模型的三角面片時(shí)，就發(fā)生了碰撞。本文將與布料發(fā)生碰撞模型的三角面片當(dāng)前的位置、布料粒子當(dāng)前的位置和經(jīng)過Verlet積分運(yùn)動(dòng)后的位置作為輸入，是否發(fā)生碰撞作為目標(biāo)輸出。發(fā)生碰撞標(biāo)記為1，沒有發(fā)生碰撞標(biāo)記為0。

將得到的實(shí)例集分為訓(xùn)練、選擇和測試子集，分別占原始實(shí)例的60%、20%和20%。為了使所有輸入都有一個(gè)合適的范圍，使神經(jīng)網(wǎng)絡(luò)在盡可能好的條件下工作，使用最小最大標(biāo)度法對(duì)數(shù)據(jù)集進(jìn)行縮放，具體為

(11)

2)構(gòu)建網(wǎng)絡(luò)初始結(jié)構(gòu)。神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)主要用于分類功能，判斷是否發(fā)生碰撞。神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)由1個(gè)縮放層、兩層感知器和1個(gè)概率層組成，如圖6所示。輸入層有15個(gè)輸入變量，相應(yīng)的縮放層有15個(gè)神經(jīng)元，第1層感知器有3個(gè)神經(jīng)元，第2層感知器有1個(gè)神經(jīng)元，概率層有1個(gè)神經(jīng)元。

圖6 神經(jīng)網(wǎng)絡(luò)初始結(jié)構(gòu)圖Fig.6 Initial structure diagram of neural network

程序中使用neural network類負(fù)責(zé)構(gòu)建神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，并使用構(gòu)造函數(shù)以適當(dāng)?shù)姆绞浇M織神經(jīng)元層。一旦建立了神經(jīng)網(wǎng)絡(luò)，就可以在層中引入輸入信息，輸出信息。

感知器層最重要的是感知器神經(jīng)元，如圖7(a)所示。其中，x1,x2,…,xn代表輸入信息，w1,w2,…,wn代表權(quán)重，b代表偏差，c代表組合值，將輸入的數(shù)值組合起來。act()代表激活函數(shù)，y表示最后的輸出。

圖7 感知器和邏輯激活函數(shù)圖Fig.7 Perceptron and logical activation function diagram((a) perceptron structure;(b) logical activation function curve)

(12)

感知器神經(jīng)元的輸出為

(13)

概率層是將輸出解釋為概率的方法。本文概率層使用的方法是二進(jìn)制概率方法。二進(jìn)制方法用于二元分類問題，具體為

(14)

式中，輸出y可以取值1或0，x為輸入，λ為決策閾值。

3)制定培訓(xùn)策略。培訓(xùn)策略包括損失函數(shù)和優(yōu)化算法。損失函數(shù)在神經(jīng)網(wǎng)絡(luò)的應(yīng)用中起著至關(guān)重要的作用。它定義了神經(jīng)網(wǎng)絡(luò)需要完成的任務(wù)，測量神經(jīng)網(wǎng)絡(luò)如何擬合數(shù)據(jù)集。本文使用的損失函數(shù)是標(biāo)準(zhǔn)化平方誤差(normalized squared error，NSE)，具體為

(15)

NSE將神經(jīng)網(wǎng)絡(luò)的輸出out與數(shù)據(jù)集中的目標(biāo)tar之差的平方和除以歸一化系數(shù)A。如果結(jié)果為1，則神經(jīng)網(wǎng)絡(luò)將按均值預(yù)測數(shù)據(jù)，如果是0則意味著對(duì)數(shù)據(jù)進(jìn)行了完美預(yù)測。

正則化項(xiàng)通常用來度量神經(jīng)網(wǎng)絡(luò)中的參數(shù)值。在損失函數(shù)中加入該項(xiàng)將使神經(jīng)網(wǎng)絡(luò)具有更小的權(quán)值和偏差，使模型更加穩(wěn)定，提高了泛化能力。本文使用L2正則化方法，該方法由神經(jīng)網(wǎng)絡(luò)中所有參數(shù)的平方和組成，具體為

(16)

式中，w為正則化權(quán)重，θ為網(wǎng)絡(luò)中的參數(shù)。

本文優(yōu)化算法使用擬牛頓法(quasi Newton methods)尋找使損失函數(shù)最小的神經(jīng)網(wǎng)絡(luò)參數(shù)xk，表達(dá)式為

xk+1=xk-GK·yk·ηk

(17)

式中，學(xué)習(xí)速率η在每個(gè)神經(jīng)元用線性最小化方法進(jìn)行調(diào)整。Gk的推導(dǎo)如下：

將f(x)在xk用泰勒公式二級(jí)展開，得

(18)

(19)

進(jìn)一步推出

gk+1-gk=HK(xk+1-xk)

(20)

令yk=gk+1-gk，δk=xk+1-xk，則擬牛頓法為

(21)

Gk+1=Gk+ΔGk

(22)

4)選擇合適的模型。為了找到具有最佳泛化特性的網(wǎng)絡(luò)結(jié)構(gòu)，使所選數(shù)據(jù)集實(shí)例誤差最小，需要進(jìn)行神經(jīng)網(wǎng)絡(luò)模型中神經(jīng)元個(gè)數(shù)的選擇。在實(shí)驗(yàn)中，使用增量順序法從少量神經(jīng)元開始優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)中的神經(jīng)元數(shù)量。增量順序法每次迭代都會(huì)增加復(fù)雜度，圖8顯示了最適合本文算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。

圖8 最合適的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.8 The most suitable neural network structure

5)評(píng)估模型的性能。評(píng)估模型需要使用測試分析類，目的是驗(yàn)證模型的泛化性能。將神經(jīng)網(wǎng)絡(luò)提供的輸出與數(shù)據(jù)集測試實(shí)例中的相應(yīng)目標(biāo)進(jìn)行比較。同時(shí)必須對(duì)神經(jīng)網(wǎng)絡(luò)輸入進(jìn)行逆過程，以縮放數(shù)據(jù)，進(jìn)行測試。在實(shí)驗(yàn)中，使用混淆矩陣和ROC(receiver operating characteristic)曲線評(píng)估神經(jīng)網(wǎng)絡(luò)模型的性能。

3.2 融合神經(jīng)網(wǎng)絡(luò)算法的優(yōu)勢(shì)

自從Louchet等人(1995)提出彈簧—質(zhì)點(diǎn)模型以來，其依然是現(xiàn)在的主流布料模型。實(shí)驗(yàn)中布料由彈簧—質(zhì)點(diǎn)模型構(gòu)成。彈簧就是布料模型中三角形的邊，也稱為約束。質(zhì)點(diǎn)就是布料模型中三角形的頂點(diǎn)，即布料中的粒子。

在布料碰撞檢測過程中，除了高層包圍盒碰撞檢測耗時(shí)多，底層的碰撞檢測也非常耗時(shí)。底層的基本圖元檢測，包括三角形與三角形之間的檢測，可以分為3次點(diǎn)—面檢測和9次邊—邊測試。一對(duì)三角形就存在12次檢測，當(dāng)布料模型復(fù)雜，包含大量三角形時(shí)，其計(jì)算量非常龐大。

為了防止布料穿透，使模擬有更真實(shí)的效果，布料往往使用高精度，同時(shí)也提高了算法計(jì)算量。在實(shí)際應(yīng)用中，人們?yōu)榱俗非罅鲿承?，往往降低布料的精度，?dǎo)致模擬效果的真實(shí)性不理想。在模擬過程中發(fā)現(xiàn)，邊與邊的穿透往往出現(xiàn)在低精度的布料中，如圖9(a)所示，雖然布料模型的粒子在碰撞物體外面，但布料的約束卻發(fā)生了穿透。當(dāng)布料模型精度提高，如圖9(b)所示，這種現(xiàn)象就會(huì)大量減少，不會(huì)影響視覺上的觀感。本文方法除了可以一次性處理大量的粒子，還可以省略掉邊與邊之間的碰撞檢測，提高了效率。

圖9 不同精度布料模擬圖Fig.9 Different precision cloth simulation map((a) low-precision cloth edge penetration diagram;(b) high-precision cloth simulation diagram)

本文方法的另一個(gè)優(yōu)勢(shì)在于，傳統(tǒng)檢測中，葉子結(jié)點(diǎn)包含一個(gè)基本圖元三角形，當(dāng)葉子結(jié)點(diǎn)發(fā)生碰撞后，需要進(jìn)行三角形之間的碰撞檢測。每一對(duì)三角形，要進(jìn)行3次點(diǎn)—面檢測。通過彈簧—質(zhì)點(diǎn)模型了解到，相鄰的三角形共用一個(gè)頂點(diǎn)。在圖元檢測過程中，如果存在相鄰的三角形，則一定會(huì)有一些共用頂點(diǎn)是重復(fù)檢測的。如圖10所示，圖中一共有8個(gè)三角形，每次取一個(gè)三角形進(jìn)行點(diǎn)—面相交檢測，一共需要檢測24個(gè)頂點(diǎn)，而實(shí)際上模型只有9個(gè)頂點(diǎn)。在實(shí)際應(yīng)用中，模型結(jié)構(gòu)遠(yuǎn)比圖10復(fù)雜，如果不排除已經(jīng)檢測過的頂點(diǎn)，就會(huì)出現(xiàn)大量重復(fù)檢測的粒子，增加算法的計(jì)算量，降低運(yùn)行速率。為了避免這種情況，布料在構(gòu)建包圍盒時(shí)，里面包含的基本元素是粒子，而不是三角形。這樣可以避免許多重復(fù)測試，同時(shí)又可以對(duì)更多的粒子進(jìn)行處理。

圖10 簡單布料結(jié)構(gòu)圖Fig.10 Simple fabric structure diagram

3.3 驗(yàn)證算法的真實(shí)性

本文不僅在效率上有良好的性能，為了防止其在模擬過程中發(fā)生穿透，特別針對(duì)極端情況進(jìn)行了模擬。穿透現(xiàn)象一般容易出現(xiàn)在物體比較尖銳的部分，為了檢驗(yàn)本文方法模擬效果的真實(shí)性，在以下兩個(gè)場景進(jìn)行了實(shí)驗(yàn)。

場景1：粒子是3維空間中最小的物體，用粒子撞擊懸垂在空中的布料，觀察是否發(fā)生穿透。從圖11(a)的效果可以看出，發(fā)生碰撞后的粒子沒有穿透布料，而是反彈回去。

場景2：將布料全部重量懸掛在動(dòng)物模型一只尖尖的左耳上，從圖11(b)的模擬效果可知，在動(dòng)物耳朵比較尖銳的部分，布料沒有發(fā)生穿透，效果良好。

圖11 布料與尖銳物體碰撞效果圖Fig.11 The effect of the collision between cloth and sharp objects ((a) particles hit the cloth;(b) the cloth hangs on the left ear of the animal)

極端條件下的模擬實(shí)驗(yàn)表明，本文方法不僅運(yùn)行效率快，而且模擬效果也有保障。

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

為了驗(yàn)證本文方法的有效性，在Windows操作系統(tǒng)下，利用開發(fā)工具VS2017，同時(shí)使用C++和OpenGL技術(shù)建立仿真模擬系統(tǒng)。將本文的兩種算法與已有算法進(jìn)行對(duì)比，得到實(shí)驗(yàn)結(jié)果。

4.1 優(yōu)化神經(jīng)網(wǎng)絡(luò)神經(jīng)元個(gè)數(shù)

為了選擇合適的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，使用增量順序法，從少量神經(jīng)元開始，每次迭代都會(huì)增加復(fù)雜度。圖12顯示了不同神經(jīng)元選擇過程中選擇誤差和訓(xùn)練誤差的歷史記錄。最小選擇誤差的神經(jīng)元個(gè)數(shù)是9。因此，選擇第1層感知器層有9個(gè)神經(jīng)元的神經(jīng)網(wǎng)絡(luò)。

圖12 神經(jīng)元個(gè)數(shù)對(duì)誤差的影響Fig.12 The influence of the number of neurons on the error

4.2 神經(jīng)網(wǎng)絡(luò)性能分析

神經(jīng)網(wǎng)絡(luò)訓(xùn)練的實(shí)驗(yàn)結(jié)果如圖13所示。圖13顯示了每個(gè)迭代中的訓(xùn)練誤差和選擇誤差。兩者都隨著時(shí)間的推移而減少，訓(xùn)練誤差的初始值為1.352 2，600個(gè)周期后的最終值為0.151 9。選擇誤差的初始值為1.338 1，600個(gè)周期后的最終值為0.319 1。

圖13 訓(xùn)練誤差和選擇誤差曲線圖Fig.13 Training error and selection error curve

為了評(píng)估神經(jīng)網(wǎng)絡(luò)的性能，使用神經(jīng)網(wǎng)絡(luò)的輸出與訓(xùn)練實(shí)例進(jìn)行比較。在本文中，如果實(shí)例發(fā)生碰撞，這樣的實(shí)例稱為正類。如果沒有發(fā)生碰撞，這樣的實(shí)例稱為負(fù)類。實(shí)驗(yàn)結(jié)果的混淆矩陣如表1所示。可以看出，所有的測試實(shí)例都能很好地分類，正確分類的實(shí)例數(shù)為435個(gè)，錯(cuò)誤分類的實(shí)例數(shù)為32個(gè)。分類準(zhǔn)確率為93.75%，錯(cuò)誤率為6.25%。

表1 混淆矩陣Table 1 Confusion matrix

實(shí)驗(yàn)結(jié)果的ROC曲線如圖14所示，其在X軸上表示假正類，在Y軸上表示真正類，通過計(jì)算曲線下面積(area under the curve，AUC)來測量分辨能力。AUC越接近1，分類器越好。本文實(shí)驗(yàn)結(jié)果AUC = 0.927，說明神經(jīng)網(wǎng)絡(luò)在大部分情況下預(yù)測效果良好。

圖14 ROC曲線Fig.14 ROC curve

4.3 不同算法碰撞檢測耗時(shí)比較

在布料仿真實(shí)驗(yàn)中，使用了3種不同精度的布料模型，它們面積相等，包含的頂點(diǎn)個(gè)數(shù)和三角面片個(gè)數(shù)依次增加，具體布料模型信息如表2所示。

表2 不同布料模型對(duì)比Table 2 Comparison of different cloth models

為了評(píng)估本文算法的耗時(shí)情況，與經(jīng)典包圍盒算法和融合DNN(deep neural network)的自碰撞檢測算法(靳雁霞 等，2020)進(jìn)行對(duì)比，計(jì)算不同方法碰撞檢測所用的平均時(shí)間。在模擬實(shí)驗(yàn)中，用相同的布料模型B和不同的碰撞物模型分別進(jìn)行實(shí)驗(yàn)，結(jié)果如表3所示。

表3 不同模型的碰撞檢測用時(shí)Table 3 Collision detection time of different models /s

圖15 布料與不同模型碰撞檢測耗時(shí)變化Fig.15 Time-consuming change of cloth collision detection with different models

通過與不同模型實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，模型越復(fù)雜，本文算法在時(shí)間上的優(yōu)勢(shì)越明顯。為了進(jìn)一步驗(yàn)證這個(gè)結(jié)論，將不同精度布料A、B和C分別與魚模型進(jìn)行碰撞模擬，實(shí)驗(yàn)結(jié)果如表4所示。

表4 不同精度布料碰撞檢測用時(shí)Table 4 Time for collision detection of different precision fabrics /s

從表4可以發(fā)現(xiàn)，隨著布料模型數(shù)據(jù)量的增大，每種算法的碰撞檢測用時(shí)都隨之增加。當(dāng)布料模型從A到C精度增加了84%時(shí)，兩種傳統(tǒng)算法和本文根節(jié)點(diǎn)雙層包圍盒算法用時(shí)增加了96%，融合DNN的自碰撞檢測算法增加了90.11%，而基于OpenNN的算法只增加了68.37%。對(duì)于簡單模型布料A，基于OpenNN算法所用的時(shí)間最多。在傳統(tǒng)方法中，用時(shí)最少的是根節(jié)點(diǎn)雙層包圍盒算法。說明基于OpenNN的算法適合處理復(fù)雜且高精度的模型，而不是處理簡單模型。根節(jié)點(diǎn)雙層包圍盒和傳統(tǒng)的包圍盒算法適用條件一樣，都適合中小模型的處理。在相同的條件下，根節(jié)點(diǎn)雙層包圍盒算法用時(shí)更少，具有優(yōu)勢(shì)。

4.4 驗(yàn)證算法模擬效果的真實(shí)性

為了驗(yàn)證本文算法不僅在效率上有所提升，同時(shí)也保證了模擬效果的真實(shí)性，將布料B分別與不同模型進(jìn)行碰撞實(shí)驗(yàn)。實(shí)驗(yàn)包括3種情況：1)布料受重力作用下落，與木箱子碰撞，停留在木箱子上；2)布料與有著尖銳棱角的游戲角色相碰撞，覆蓋在了游戲角色上面；3)運(yùn)動(dòng)的人體穿過垂直下落的布料，布料落在人體上。圖16為截取的實(shí)驗(yàn)過程中不同幀的模擬效果，可以看出，本文算法模擬效果的真實(shí)性和AABB包圍盒算法模擬效果大致相同，不影響視覺觀感，真實(shí)性得到了保障。

圖16 布料與不同模型碰撞效果圖Fig.16 The effect of cloth collision with different models((a) using bounding box AABB simulation;(b) ours)

5 結(jié) 論

本文提出了根節(jié)點(diǎn)雙層包圍盒碰撞檢測算法。利用簡單的包圍盒，提高了包圍盒的剔除率，使碰撞檢測算法的效率得到提升。然后結(jié)合神經(jīng)網(wǎng)絡(luò)，進(jìn)一步改進(jìn)了碰撞檢測算法，使算法在一個(gè)時(shí)間步長內(nèi)可以處理大量的布料粒子，減少了包圍盒的構(gòu)造時(shí)間，加速了碰撞檢測的速度。通過與傳統(tǒng)的單個(gè)包圍盒算法、混合包圍盒算法和融合DNN的自碰撞檢測算法相比，本文在減少碰撞檢測時(shí)間的同時(shí)，準(zhǔn)確性也得到了保證，性能得到很大提升。

實(shí)驗(yàn)中通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)得到的模型，其穩(wěn)定性還可以進(jìn)一步提升。在下一步工作中，將試圖得到更多更全面的樣本數(shù)據(jù)量，并以此訓(xùn)練神經(jīng)網(wǎng)絡(luò)得到更好的模型。同時(shí)，為了更好地將碰撞檢測算法與神經(jīng)網(wǎng)絡(luò)相融合，將嘗試用神經(jīng)網(wǎng)絡(luò)預(yù)測布料模型粒子碰撞后的位置，減少碰撞響應(yīng)所用的時(shí)間，提高整個(gè)算法模擬的效率。