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

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

0 引 言

在變形體仿真建模過程中，碰撞檢測算法的計算量最大，耗時最多。為了滿足應(yīng)用中實時性的要求，提高算法的效率成為虛擬仿真領(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)了一種基于層次代表性包圍盒的目標干涉檢測的研究框架(Yazid等，2019)，并行布料仿真(Kim等，2019)和基于罰函數(shù)的碰撞求解(呂夢雅 等，2020)。雖然效率有一定提升，但使用的都是單一的包圍盒。

2008年以后，許多專家發(fā)現(xiàn)單一的包圍盒都有自己的劣勢，單獨使用一種包圍盒會存在精度不足等問題，為了減少單一包圍盒的局限性，越來越多的學者開始研究混合包圍盒算法?；旌习鼑兴惴ㄒ郧蛐?sphere)包圍盒、方向包圍盒(oriented bounding box，OBB)、軸對齊包圍盒(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)中，如果對象形狀和球體相似，采用sphere，否則使用OBB。通過使用Sphere-OBB和并行檢測技術(shù)來提高效率。但是，目前混合包圍盒的應(yīng)用大多使用多個不同的包圍盒，如在BVH樹上、下層分別使用簡單包圍盒和復(fù)雜包圍盒，或者所有結(jié)點外層使用緊密率差的包圍盒，內(nèi)層使用緊密率好的包圍盒(Zhu等，2016)。雖然混合包圍盒發(fā)揮了多個包圍盒的優(yōu)勢，但在計算成本、精確度和復(fù)雜環(huán)境下的數(shù)據(jù)處理很難達到平衡，局限性需要進一步改進。

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

針對目前的問題，本文在包圍盒方面提出了根節(jié)點雙層包圍盒算法，使用最簡單的包圍盒剔除沒有發(fā)生碰撞的粒子。同時，提出融合神經(jīng)網(wǎng)絡(luò)的碰撞檢測算法，訓(xùn)練神經(jīng)網(wǎng)絡(luò)學習復(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)

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

包圍盒技術(shù)是碰撞檢測領(lǐng)域的主要方法，常見的包圍盒有球形包圍盒、方向包圍盒、軸對齊包圍盒和離散多面體包圍盒(Wang等，2018)。本文根節(jié)點雙層包圍盒算法基于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軸坐標，xmin,xmax,ymin,ymax和zmin,zmax表示物體頂點投影在x、y和z軸上坐標的最小、最大值，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的坐標，xmin,xmax,ymin,ymax,zmin,zmax表示物體頂點投影在x、y和z軸上坐標的最小、最大值，r表示半徑。

1.2 包圍盒相交檢測

球形包圍盒的相交測試如圖2(a)所示。Oa和Ob為兩個包圍球的球心，在坐標軸上的投影為O1和O2，R1和R2分別是兩個包圍球的半徑。若|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坐標軸上的投影都相交，若在某一個坐標軸上投影不相交，則兩個包圍盒不相交。La和Lb為兩個AABB包圍盒在坐標軸上的投影，C1和C2為中點Ca和Cb的投影點。如果|Ca-Cb|>La+Lb，則投影不重疊，包圍盒沒有相交。

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

圖3 球心O在AABB包圍盒上的最近點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é)點雙層包圍盒算法

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

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

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

圖4 包圍盒層級結(jié)構(gòu)和根節(jié)點雙層包圍盒效果圖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é)點開始，采用sphere包圍盒構(gòu)建BVH樹，并進行遍歷。

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

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

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

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

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

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

(8)

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

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

(9)

(10)

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

圖5 根節(jié)點雙層包圍盒主視圖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é)點雙層包圍盒，使用了最簡單的兩個包圍盒，不僅構(gòu)造簡單，而且效率高。構(gòu)造包圍盒所用的時間比復(fù)雜包圍盒所用的時間少，且與簡單的包圍盒相比，本文的方法緊密率高。本文發(fā)揮了簡單包圍盒的優(yōu)勢，通過構(gòu)建雙層包圍盒消除了其劣勢。

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

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

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òu)建。

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

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

(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個縮放層、兩層感知器和1個概率層組成，如圖6所示。輸入層有15個輸入變量，相應(yīng)的縮放層有15個神經(jīng)元，第1層感知器有3個神經(jīng)元，第2層感知器有1個神經(jīng)元，概率層有1個神經(jīng)元。

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

程序中使用neural network類負責構(gòu)建神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，并使用構(gòu)造函數(shù)以適當?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)

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

(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ù)是標準化平方誤差(normalized squared error，NSE)，具體為

(15)

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

正則化項通常用來度量神經(jīng)網(wǎng)絡(luò)中的參數(shù)值。在損失函數(shù)中加入該項將使神經(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，表達式為

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

(17)

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

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

(18)

(19)

進一步推出

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ù)集實例誤差最小，需要進行神經(jīng)網(wǎng)絡(luò)模型中神經(jīng)元個數(shù)的選擇。在實驗中，使用增量順序法從少量神經(jīng)元開始優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)中的神經(jīng)元數(shù)量。增量順序法每次迭代都會增加復(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)評估模型的性能。評估模型需要使用測試分析類，目的是驗證模型的泛化性能。將神經(jīng)網(wǎng)絡(luò)提供的輸出與數(shù)據(jù)集測試實例中的相應(yīng)目標進行比較。同時必須對神經(jīng)網(wǎng)絡(luò)輸入進行逆過程，以縮放數(shù)據(jù)，進行測試。在實驗中，使用混淆矩陣和ROC(receiver operating characteristic)曲線評估神經(jīng)網(wǎng)絡(luò)模型的性能。

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

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

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

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

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

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

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

3.3 驗證算法的真實性

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

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

場景2：將布料全部重量懸掛在動物模型一只尖尖的左耳上，從圖11(b)的模擬效果可知，在動物耳朵比較尖銳的部分，布料沒有發(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)

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

4 實驗結(jié)果與分析

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

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

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

圖12 神經(jīng)元個數(shù)對誤差的影響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)練的實驗結(jié)果如圖13所示。圖13顯示了每個迭代中的訓(xùn)練誤差和選擇誤差。兩者都隨著時間的推移而減少，訓(xùn)練誤差的初始值為1.352 2，600個周期后的最終值為0.151 9。選擇誤差的初始值為1.338 1，600個周期后的最終值為0.319 1。

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

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

表1 混淆矩陣Table 1 Confusion matrix

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

圖14 ROC曲線Fig.14 ROC curve

4.3 不同算法碰撞檢測耗時比較

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

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

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

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

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

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

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

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

4.4 驗證算法模擬效果的真實性

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

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

5 結(jié) 論

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

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