融合神经网络的布料碰撞检测算法

靳雁霞，马博，贾瑶，陈治旭，芦烨

中北大学大数据学院，太原 030051

0 引 言

在变形体仿真建模过程中，碰撞检测算法的计算量最大，耗时最多。为了满足应用中实时性的要求，提高算法的效率成为虚拟仿真领域里的重要问题。在碰撞检测过程中，层次包围体(bounding volume hierarchies，BVH)技术是目前使用最多的方法。Hubbard(1993)首次提出了包围盒技术，用4维几何体或者球体逼近3维模型。为了适应不同的模型，找到紧密率更高的包围盒，又出现了自适应椭球包围盒(唐勇 等，2013)和基于虚拟球的包围体(Wang等，2019)等新的包围盒。随着层次包围体技术应用的成熟，出现了一种基于层次代表性包围盒的目标干涉检测的研究框架(Yazid等，2019)，并行布料仿真(Kim等，2019)和基于罚函数的碰撞求解(吕梦雅 等，2020)。虽然效率有一定提升，但使用的都是单一的包围盒。

2008年以后，许多专家发现单一的包围盒都有自己的劣势，单独使用一种包围盒会存在精度不足等问题，为了减少单一包围盒的局限性，越来越多的学者开始研究混合包围盒算法。混合包围盒算法以球形(sphere)包围盒、方向包围盒(oriented bounding box，OBB)、轴对齐包围盒(axis aligned bounding box，AABB)和离散有向多面体(discrete orientation polytopes，k-DOPs)为基础，出现了Sphere-OBB混合包围盒(朱元峰 等，2008)、AABB-OBB混合包围盒(Tu和Yu，2009)和混合3种不同包围盒AABB、OBB和k-DOPs(Feng等，2010)的混合算法。在复合平衡二叉树碰撞检测算法(Liu和Chen，2017)中，如果对象形状和球体相似，采用sphere，否则使用OBB。通过使用Sphere-OBB和并行检测技术来提高效率。但是，目前混合包围盒的应用大多使用多个不同的包围盒，如在BVH树上、下层分别使用简单包围盒和复杂包围盒，或者所有结点外层使用紧密率差的包围盒，内层使用紧密率好的包围盒(Zhu等，2016)。虽然混合包围盒发挥了多个包围盒的优势，但在计算成本、精确度和复杂环境下的数据处理很难达到平衡，局限性需要进一步改进。

机器学习具有处理大量数据的能力，可以进行预测。目前，许多布料仿真都结合了机器学习来提高效率。Ye等人(2017)提出了一种新的管道技术，从预定义的表面方向、历史数据和全局相交分析得出3种不同的方法。在服装动画中使用机器学习研究人体运动与服装变形(石敏 等，2017；张惠，2019)的关系，使布料更加精确。Jiang等人(2019)提出一种利用不同织物实现织物悬垂模拟的方法。通过构造BP(back propagation)神经网络，得到织物力学参数与3维纺织仿真系统控制参数之间的非线性关系。Holden等人(2019)利用子空间模拟技术与机器学习相结合，当耦合时，该方法可以非常有效地支持子空间的物理模拟。

针对目前的问题，本文在包围盒方面提出了根节点双层包围盒算法，使用最简单的包围盒剔除没有发生碰撞的粒子。同时，提出融合神经网络的碰撞检测算法，训练神经网络学习复杂的碰撞检测过程，通过训练好的模型预测模型粒子是否发生碰撞。神经网络可以减少循环，避免检测复杂的过程，提高碰撞检测效率。

1 相关工作

1.1 包围盒技术

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

(1)

则认为物体没有发生碰撞。

包围盒技术是碰撞检测领域的主要方法，常见的包围盒有球形包围盒、方向包围盒、轴对齐包围盒和离散多面体包围盒(Wang等，2018)。本文根节点双层包围盒算法基于sphere和AABB两种包围盒，两者的2维结构如图1所示。

图1 包围盒2维结构图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，则表示没有发生相交，否则两球相交。

图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维结构如图3所示。然后计算出球心O与点P之间的距离，如果|O-P|>r，则没有发生相交。

图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 根节点双层包围盒算法

在碰撞检测过程中，不同包围盒的构建、更新以及包围盒之间的相交检测消耗的时间都不相同。在保证剔除率的前提下，为了减少包围盒构建和更新消耗的时间，本文利用简单的包围盒，提出根节点双层包围盒算法解决此问题。

2.1 根节点双层包围盒的构建与碰撞检测

使用最简单的AABB包围盒和sphere包围盒构建BVH结构，如图4(a)所示。在BVH中，非根节点使用sphere单个包围盒，根节点使用双层包围盒。在布料模拟过程中，首先对根节点构建一个sphere包围盒，当sphere包围盒发生碰撞后，再对根节点构建AABB包围盒，这时根节点才具有双层包围盒，它的实际效果图如图4(b)所示。当根节点的第2个包围盒AABB发生碰撞以后，往下遍历BVH结构，直到叶子结点。

图4 包围盒层级结构和根节点双层包围盒效果图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)从根节点开始，采用sphere包围盒构建BVH树，并进行遍历。

2)当检测到根节点发生碰撞时，对根节点构建AABB包围盒，否则，执行步骤5)。

3)当根节点的AABB包围盒发生碰撞时，采用深度优先的原则遍历BVH树，直到叶子结点。如果碰撞没有发生，执行步骤5)。

4)当检测到叶子结点发生碰撞，则进行底层基本图元的碰撞检测，然后进行碰撞响应。

5)在下一个时间步长内再次从根节点开始检测碰撞是否发生。

2.2 根节点双层包围盒算法的优势

本文使用包围盒的紧密率τ来更好地说明算法优势。紧密率τ、sphere包围盒的紧密率τS和AABB包围盒的紧密率τA计算为

(8)

式中，V(O)表示模拟布料的体积，V(B)表示包围盒的体积。

将sphere包围盒和AABB包围盒的体积代入式(8),得

(9)

(10)

由图5(a)可知，布料为平整状态时，sphere包围盒紧密率最差。在图5(a)中，碰撞粒子运动方向与布料垂直，当粒子与sphere包围盒发生碰撞时，粒子与布料之间还有很大的空隙D。为了更精确地剔除未与布料发生碰撞的粒子，当sphere包围盒检测出碰撞时，对根节点构建AABB包围盒。当粒子与AABB包围盒发生碰撞时，粒子与布料的间距很小，距离为图5(b)中的d。这时再使用紧密率更好的包围盒，不但布料与粒子距离的减少微乎其微，而且会增加包围盒的构造时间。为了减少包围盒的构造时间，使用最简单的sphere包围盒。然后通过遍历BVH结构，找出发生碰撞的精确位置。

图5 根节点双层包围盒主视图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)

本文提出的根节点双层包围盒，使用了最简单的两个包围盒，不仅构造简单，而且效率高。构造包围盒所用的时间比复杂包围盒所用的时间少，且与简单的包围盒相比，本文的方法紧密率高。本文发挥了简单包围盒的优势，通过构建双层包围盒消除了其劣势。

3 融合神经网络

上述方法虽然可以提高碰撞检测的效率，但是不适合处理模型复杂、数据量多的情况。由于布料的碰撞检测需要检测大量的点与三角形之间是否发生穿透，传统包围盒技术虽然可以将没有碰撞的点进行快速剔除，但无法在短时间内处理大量的点。而机器学习中的方法可以处理大量的数据，并且运行时间迅速，所以本文使用神经网络优化碰撞检测算法，减少包围盒构造的时间，提高算法碰撞检测的效率。

3.1 构建神经网络结构

本文神经网络的构建基于开源神经网络库OpenNN(open neural networks library)，OpenNN神经网络模型通过以下5个主要步骤进行构建。

1)数据集准备。数据集准备是解决问题的信息源。实验中，当布料的点穿透了另一个模型的三角面片时，就发生了碰撞。本文将与布料发生碰撞模型的三角面片当前的位置、布料粒子当前的位置和经过Verlet积分运动后的位置作为输入，是否发生碰撞作为目标输出。发生碰撞标记为1，没有发生碰撞标记为0。

将得到的实例集分为训练、选择和测试子集，分别占原始实例的60%、20%和20%。为了使所有输入都有一个合适的范围，使神经网络在尽可能好的条件下工作，使用最小最大标度法对数据集进行缩放，具体为

(11)

2)构建网络初始结构。神经网络结构主要用于分类功能，判断是否发生碰撞。神经网络结构由1个缩放层、两层感知器和1个概率层组成，如图6所示。输入层有15个输入变量，相应的缩放层有15个神经元，第1层感知器有3个神经元，第2层感知器有1个神经元，概率层有1个神经元。

图6 神经网络初始结构图Fig.6 Initial structure diagram of neural network

程序中使用neural network类负责构建神经网络结构，并使用构造函数以适当的方式组织神经元层。一旦建立了神经网络，就可以在层中引入输入信息，输出信息。

感知器层最重要的是感知器神经元，如图7(a)所示。其中，x1,x2,…,xn代表输入信息，w1,w2,…,wn代表权重，b代表偏差，c代表组合值，将输入的数值组合起来。act()代表激活函数，y表示最后的输出。

图7 感知器和逻辑激活函数图Fig.7 Perceptron and logical activation function diagram((a) perceptron structure;(b) logical activation function curve)

(12)

感知器神经元的输出为

(13)

概率层是将输出解释为概率的方法。本文概率层使用的方法是二进制概率方法。二进制方法用于二元分类问题，具体为

(14)

式中，输出y可以取值1或0，x为输入，λ为决策阈值。

3)制定培训策略。培训策略包括损失函数和优化算法。损失函数在神经网络的应用中起着至关重要的作用。它定义了神经网络需要完成的任务，测量神经网络如何拟合数据集。本文使用的损失函数是标准化平方误差(normalized squared error，NSE)，具体为

(15)

NSE将神经网络的输出out与数据集中的目标tar之差的平方和除以归一化系数A。如果结果为1，则神经网络将按均值预测数据，如果是0则意味着对数据进行了完美预测。

正则化项通常用来度量神经网络中的参数值。在损失函数中加入该项将使神经网络具有更小的权值和偏差，使模型更加稳定，提高了泛化能力。本文使用L2正则化方法，该方法由神经网络中所有参数的平方和组成，具体为

(16)

式中，w为正则化权重，θ为网络中的参数。

本文优化算法使用拟牛顿法(quasi Newton methods)寻找使损失函数最小的神经网络参数xk，表达式为

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

(17)

式中，学习速率η在每个神经元用线性最小化方法进行调整。Gk的推导如下：

将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)选择合适的模型。为了找到具有最佳泛化特性的网络结构，使所选数据集实例误差最小，需要进行神经网络模型中神经元个数的选择。在实验中，使用增量顺序法从少量神经元开始优化网络结构中的神经元数量。增量顺序法每次迭代都会增加复杂度，图8显示了最适合本文算法的神经网络结构。

图8 最合适的神经网络结构Fig.8 The most suitable neural network structure

5)评估模型的性能。评估模型需要使用测试分析类，目的是验证模型的泛化性能。将神经网络提供的输出与数据集测试实例中的相应目标进行比较。同时必须对神经网络输入进行逆过程，以缩放数据，进行测试。在实验中，使用混淆矩阵和ROC(receiver operating characteristic)曲线评估神经网络模型的性能。

3.2 融合神经网络算法的优势

自从Louchet等人(1995)提出弹簧—质点模型以来，其依然是现在的主流布料模型。实验中布料由弹簧—质点模型构成。弹簧就是布料模型中三角形的边，也称为约束。质点就是布料模型中三角形的顶点，即布料中的粒子。

在布料碰撞检测过程中，除了高层包围盒碰撞检测耗时多，底层的碰撞检测也非常耗时。底层的基本图元检测，包括三角形与三角形之间的检测，可以分为3次点—面检测和9次边—边测试。一对三角形就存在12次检测，当布料模型复杂，包含大量三角形时，其计算量非常庞大。

为了防止布料穿透，使模拟有更真实的效果，布料往往使用高精度，同时也提高了算法计算量。在实际应用中，人们为了追求流畅性，往往降低布料的精度，导致模拟效果的真实性不理想。在模拟过程中发现，边与边的穿透往往出现在低精度的布料中，如图9(a)所示，虽然布料模型的粒子在碰撞物体外面，但布料的约束却发生了穿透。当布料模型精度提高，如图9(b)所示，这种现象就会大量减少，不会影响视觉上的观感。本文方法除了可以一次性处理大量的粒子，还可以省略掉边与边之间的碰撞检测，提高了效率。

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

本文方法的另一个优势在于，传统检测中，叶子结点包含一个基本图元三角形，当叶子结点发生碰撞后，需要进行三角形之间的碰撞检测。每一对三角形，要进行3次点—面检测。通过弹簧—质点模型了解到，相邻的三角形共用一个顶点。在图元检测过程中，如果存在相邻的三角形，则一定会有一些共用顶点是重复检测的。如图10所示，图中一共有8个三角形，每次取一个三角形进行点—面相交检测，一共需要检测24个顶点，而实际上模型只有9个顶点。在实际应用中，模型结构远比图10复杂，如果不排除已经检测过的顶点，就会出现大量重复检测的粒子，增加算法的计算量，降低运行速率。为了避免这种情况，布料在构建包围盒时，里面包含的基本元素是粒子，而不是三角形。这样可以避免许多重复测试，同时又可以对更多的粒子进行处理。

图10 简单布料结构图Fig.10 Simple fabric structure diagram

3.3 验证算法的真实性

本文不仅在效率上有良好的性能，为了防止其在模拟过程中发生穿透，特别针对极端情况进行了模拟。穿透现象一般容易出现在物体比较尖锐的部分，为了检验本文方法模拟效果的真实性，在以下两个场景进行了实验。

场景1：粒子是3维空间中最小的物体，用粒子撞击悬垂在空中的布料，观察是否发生穿透。从图11(a)的效果可以看出，发生碰撞后的粒子没有穿透布料，而是反弹回去。

场景2：将布料全部重量悬挂在动物模型一只尖尖的左耳上，从图11(b)的模拟效果可知，在动物耳朵比较尖锐的部分，布料没有发生穿透，效果良好。

图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 实验结果与分析

为了验证本文方法的有效性，在Windows操作系统下，利用开发工具VS2017，同时使用C++和OpenGL技术建立仿真模拟系统。将本文的两种算法与已有算法进行对比，得到实验结果。

4.1 优化神经网络神经元个数

为了选择合适的神经网络结构，使用增量顺序法，从少量神经元开始，每次迭代都会增加复杂度。图12显示了不同神经元选择过程中选择误差和训练误差的历史记录。最小选择误差的神经元个数是9。因此，选择第1层感知器层有9个神经元的神经网络。

图12 神经元个数对误差的影响Fig.12 The influence of the number of neurons on the error

4.2 神经网络性能分析

神经网络训练的实验结果如图13所示。图13显示了每个迭代中的训练误差和选择误差。两者都随着时间的推移而减少，训练误差的初始值为1.352 2，600个周期后的最终值为0.151 9。选择误差的初始值为1.338 1，600个周期后的最终值为0.319 1。

图13 训练误差和选择误差曲线图Fig.13 Training error and selection error curve

为了评估神经网络的性能，使用神经网络的输出与训练实例进行比较。在本文中，如果实例发生碰撞，这样的实例称为正类。如果没有发生碰撞，这样的实例称为负类。实验结果的混淆矩阵如表1所示。可以看出，所有的测试实例都能很好地分类，正确分类的实例数为435个，错误分类的实例数为32个。分类准确率为93.75%，错误率为6.25%。

表1 混淆矩阵Table 1 Confusion matrix

实验结果的ROC曲线如图14所示，其在X轴上表示假正类，在Y轴上表示真正类，通过计算曲线下面积(area under the curve，AUC)来测量分辨能力。AUC越接近1，分类器越好。本文实验结果AUC = 0.927，说明神经网络在大部分情况下预测效果良好。

图14 ROC曲线Fig.14 ROC curve

4.3 不同算法碰撞检测耗时比较

在布料仿真实验中，使用了3种不同精度的布料模型，它们面积相等，包含的顶点个数和三角面片个数依次增加，具体布料模型信息如表2所示。

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

为了评估本文算法的耗时情况，与经典包围盒算法和融合DNN(deep neural network)的自碰撞检测算法(靳雁霞 等，2020)进行对比，计算不同方法碰撞检测所用的平均时间。在模拟实验中，用相同的布料模型B和不同的碰撞物模型分别进行实验，结果如表3所示。

表3 不同模型的碰撞检测用时Table 3 Collision detection time of different models /s

图15 布料与不同模型碰撞检测耗时变化Fig.15 Time-consuming change of cloth collision detection with different models

通过与不同模型实验对比发现，模型越复杂，本文算法在时间上的优势越明显。为了进一步验证这个结论，将不同精度布料A、B和C分别与鱼模型进行碰撞模拟，实验结果如表4所示。

表4 不同精度布料碰撞检测用时Table 4 Time for collision detection of different precision fabrics /s

从表4可以发现，随着布料模型数据量的增大，每种算法的碰撞检测用时都随之增加。当布料模型从A到C精度增加了84%时，两种传统算法和本文根节点双层包围盒算法用时增加了96%，融合DNN的自碰撞检测算法增加了90.11%，而基于OpenNN的算法只增加了68.37%。对于简单模型布料A，基于OpenNN算法所用的时间最多。在传统方法中，用时最少的是根节点双层包围盒算法。说明基于OpenNN的算法适合处理复杂且高精度的模型，而不是处理简单模型。根节点双层包围盒和传统的包围盒算法适用条件一样，都适合中小模型的处理。在相同的条件下，根节点双层包围盒算法用时更少，具有优势。

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 结 论

本文提出了根节点双层包围盒碰撞检测算法。利用简单的包围盒，提高了包围盒的剔除率，使碰撞检测算法的效率得到提升。然后结合神经网络，进一步改进了碰撞检测算法，使算法在一个时间步长内可以处理大量的布料粒子，减少了包围盒的构造时间，加速了碰撞检测的速度。通过与传统的单个包围盒算法、混合包围盒算法和融合DNN的自碰撞检测算法相比，本文在减少碰撞检测时间的同时，准确性也得到了保证，性能得到很大提升。

实验中通过训练神经网络得到的模型，其稳定性还可以进一步提升。在下一步工作中，将试图得到更多更全面的样本数据量，并以此训练神经网络得到更好的模型。同时，为了更好地将碰撞检测算法与神经网络相融合，将尝试用神经网络预测布料模型粒子碰撞后的位置，减少碰撞响应所用的时间，提高整个算法模拟的效率。