自碰撞检测是增强变形体模拟真实感的关键，也是计算量最大的环节，提高自碰撞检测效率是虚拟仿真领域的前沿问题。最早的自碰撞检测只进行层次包围盒测试，然而，层次包围盒测试无法剔除相邻图元。针对这一问题，Volino和Thalmann(1995)提出了两个优化方法：基于曲率的测试和轮廓测试。之后的研究(Provot，1997；Schvartzman等，2010；Wang等，2017, 2018；Wong和Cheng, 2016, 2014)大多是通过对这两个优化方法进行改进来提升自碰撞检测的效率。基于曲率的测试和轮廓测试对邻近图元有良好的剔除效果，但无法剔除由于包围盒冗余空间保留下来的非相交图元。使用紧密的包围盒可以提高剔除准确率，但测试和更新计算会变复杂，反而增加了渲染耗时(Wang等，2018)。

混合层次包围盒将多种包围盒结合在一起，解决贴合性和整体耗时导致的速度瓶颈，使碰撞检测的精度更高、速度更快(Liu等，2017)。随着图元数量的增加，混合层次包围盒的效率明显提升(孙敬荣和卢新明，2018；Wang等，2018；刘超，2018)。然而，在混合层次包围盒遍历过程中，存在影响算法效率的复杂计算。

机器学习方法擅长逼近复杂计算过程(Schmidhuber，2015；Mammadli等，2019)，大量研究将机器学习方法应用到变形体模拟中来改进算法效率。Oh等人(2018)提出了一种将传统的基于物理的仿真方法与深度神经网络相结合的布料仿真方法。石敏等人(2017)通过机器学习模型，建立了人体运动与服装变形之间的关系。Chen等人(2018)提出了一种基于深度学习的网格超分辨率方法，用来丰富低分辨率织物的褶皱网格。

针对上述问题，本文提出融合深度神经网络的AABB(Aixe align bounding box)—圆形包围盒方法。首先，采用AABB剔除不相交的图元；其次，采用圆形包围盒再次剔除不相交的图元，减少图元相交测试次数。最后，采用深度神经网络优化圆形包围盒的相交检测复杂度，提升检测速度。

在自碰撞检测中，诸如AABB、Sphere与$k$-DOP(discrete orientation polytopes)等包围盒在三角形的法向矢量方向上会产生冗余空间，导致BVTT(bounding volume test tree)树的叶子节点的剔除率降低。针对这一问题，本文提出了一种融合深度神经网络的AABB-圆形包围盒方法。提升BVTT在叶子节点的剔除率，降低图元相交测试次数，提升自碰撞检测的整体速度。具体步骤如下：

1) 对变形体构建AABB—圆形包围盒；

2) 根据AABB—圆形包围盒构建BVTT；

3) 基于深度神经网络优化BVTT树进行包围盒测试和法向锥测试，输出三角形碰撞对。

法向锥测试后，需要使用经典包围盒对候选集进行二次剔除。由于经典包围盒在图元的法向量的方向上具有厚度，导致三角形对的剔除效率低。针对以上问题，本文提出没有厚度的圆形包围盒。圆形包围盒与三角形面片处于同一个平面上，并且三角形面片处于圆形包围盒内部，如图 1所示。

圆形包围盒的参数定义如下：

1) 圆心坐标$ \boldsymbol{C}$。将三角形的质心作为圆形的圆心。具体为

$ \mathit{\boldsymbol{C}} = \frac{1}{3}(\sum\limits_{i = 1}^3 {p_x^i} ,\sum\limits_{i = 1}^3 {p_y^i} ,\sum\limits_{i = 1}^3 {p_z^i} ) $

(1)

式中，三角形顶点坐标$ \boldsymbol{P}^{i}=(p^{i}_{x}, p^{i}_{y}, p^{i}_{z}), i=1, 2, 3$。

2) 半径$r$。选用圆心到顶点距离的最大值，即

$ r = {\rm{max}}\{ |\mathit{\boldsymbol{C}} - {\mathit{\boldsymbol{P}}^1}|,|\mathit{\boldsymbol{C}} - {\mathit{\boldsymbol{P}}^2}|,|\mathit{\boldsymbol{C}} - {\mathit{\boldsymbol{P}}^3}|\} $

(2)

3) 法向矢量$ \boldsymbol{n}$。圆形法向矢量即三角形的法向矢量，即

$ \mathit{\boldsymbol{n}} = \frac{{({\mathit{\boldsymbol{P}}^1} - {\mathit{\boldsymbol{P}}^2}) \times ({\mathit{\boldsymbol{P}}^1} - {\mathit{\boldsymbol{P}}^3})}}{{|({\mathit{\boldsymbol{P}}^1} - {\mathit{\boldsymbol{P}}^2}) \times ({\mathit{\boldsymbol{P}}^1} - {\mathit{\boldsymbol{P}}^3})|}} $

(3)

由于AABB对图元的贴合性差，而圆形包围盒对图元贴合性好，使得检测、更新速度快，相交检测计算、更新计算简便，所以本文提出AABB与圆形包围盒混合的层次包围盒。对叶子节点构建圆形包围盒，对根节点以及内部节点构建AABB包围盒，如图 2所示，正方形代表AABB，圆形代表圆形包围盒。

AABB与圆形包围盒的相交测试算法的具体步骤如下：

输入：圆形和AABB的参数。

输出：两个包围盒相交状态。

1) 判断圆心$ \boldsymbol{C}$是否在AABB内，若在，则返回“相交”，结束算法；若不在，执行步骤2)；

2) 计算圆形所在平面$\boldsymbol{\pi }_{c}: \boldsymbol{n}_{c}×X=d_{c}$与AABB其中一个矩形所在平面$\boldsymbol{\pi }_{r}: \boldsymbol{n}_{r}×X=d_{r}$的交线$L$，检测$ \boldsymbol{C}$到$L$的距离$l_{C－L}$是否大于$r$，若是，执行步骤3)。其中，$ \boldsymbol{n}_{c}$和$\boldsymbol{n}_{r}$分别为平面$\boldsymbol{\pi }_{c}$和$\boldsymbol{\pi }_{r}$的法向量。否则，执行步骤4)。交线$L$和距离$l_{C－L}$的计算公式为

$ {L = ({d_c}{\mathit{\boldsymbol{n}}_r} - {d_r}{\mathit{\boldsymbol{n}}_c}) \times \mathit{\boldsymbol{d}}/(\mathit{\boldsymbol{d}} \cdot \mathit{\boldsymbol{d}}) + t\mathit{\boldsymbol{d}}} $

(4)

$ {{l_{C - L}} = \frac{{(\mathit{\boldsymbol{C}} - ({d_c}{\mathit{\boldsymbol{n}}_r} - {d_r}{\mathit{\boldsymbol{n}}_c}) \times \mathit{\boldsymbol{d}}/(\mathit{\boldsymbol{d}} \cdot \mathit{\boldsymbol{d}})) \times \mathit{\boldsymbol{d}}}}{{|\mathit{\boldsymbol{d}}|}}} $

(5)

式中，$\boldsymbol{d}=\boldsymbol{n}_{c}×\boldsymbol{n}_{r}$, 表示$\boldsymbol{n}_{c}$和$\boldsymbol{n}_{r}$的叉积。

3) 计算圆形所在平面$\boldsymbol{\pi }_{c}$与下一个AABB矩形面所在平面$\boldsymbol{\pi }_{r+1}$的交线$L$，执行步骤2)，直到检测完AABB的6个面，返回“未相交”，结束算法；

4) 计算$L$是否与对应矩形的四条边发生相交，若与任意边发生相交，返回“相交”，结束算法；否则，返回步骤3)。

基于几何的圆形包围盒之间相交测试算法的具体步骤如下：

输入：两个圆形的圆心位置坐标$\boldsymbol{C}_{1}$、$\boldsymbol{C}_{2}$及法向量$\boldsymbol{n}_{1}$、$\boldsymbol{n}_{2}$。

输出：两个圆形相交状态。

1) 通过$\boldsymbol{C}_{1}$和$\boldsymbol{C}_{2}$求向量$ \boldsymbol{m}$，计算$\boldsymbol{n}_{1}$和$\boldsymbol{n}_{2}$之间的点积$a$，以及$ \boldsymbol{m}$和$\boldsymbol{n}_{1}$之间的点积$b$，具体为

$ {\mathit{\boldsymbol{m}} = {\mathit{\boldsymbol{C}}_1} - {\mathit{\boldsymbol{C}}_2}} $

(6)

$ {a = {\mathit{\boldsymbol{n}}_1} \cdot {\mathit{\boldsymbol{n}}_2}} $

(7)

$ {b = \mathit{\boldsymbol{m}} \cdot {\mathit{\boldsymbol{n}}_1}} $

(8)

2) 当$a=1$或$－1$并且$b=0$时，$|\boldsymbol{m}|$大于两圆形的半径之和，退出测试，返回“不相交”；否则，退出测试，并返回“相交”。当$a=－1$或$1$且$b=0$，退出测试，并返回“不相交”。当$a=－1$或$1$时，执行步骤3)；

3) 假设两个圆形所在平面分别为$\boldsymbol{\pi }_{1}:\boldsymbol{n}_{1}×X=d_{1}$和$\boldsymbol{\pi }_{2}:\boldsymbol{n}_{2}×X=d_{2}$。根据式(4)和式(5)，求两个圆形所在平面的交线$L$和圆心$\boldsymbol{C}_{1}$和$\boldsymbol{C}_{2}$到$L$的距离$l_{1}$和$l_{2}$，若$l_{1} < r_{2}$且$l_{2} < r_{2}$，退出测试，返回“相交”；否则，退出测试，返回“不相交”。

圆形包围盒之间的相交测试流程如图 3所示，基于几何的圆形包围盒相交测试俯视效果如图 4所示，图中$\boldsymbol{\pi }_{1}$和$\boldsymbol{\pi }_{2}$分别为两个圆形所在平面，$L$为两平面的交线。

两个圆形的姿态保持不变，圆形CB1沿向量$ \boldsymbol{m}$的反方向平移，当$| \boldsymbol{m}|$距离小于阈值$δ$时，两个圆形发生相交。图 5为两个圆形在它们的法向量构成的平面上投影的侧视效果图，图中CB1和CB2分别为两个圆形的投影，CB1′为CB1平移后的投影，CB1与CB2没有发生相交，CB1′与CB2发生了相交。

两个圆形的圆心距离不变，它们夹角越大，阈值$δ$越小。图 6为两个圆形在它们的法向量构成的平面上的投影的侧视效果图，图中CB1和CB2分别为两个圆形的投影，CB1′为CB1绕圆心反转一定角度后的投影，CB1与CB2没有发生相交，CB1′与CB2发生了相交。

为了保持圆心之间的距离和圆形之间的夹角不变，移动圆形CB1，阈值$δ$也会随之发生变化，这一影响因素称为圆形之间的“相对方位”。图 7为两个圆形在它们的法向量构成的平面上投影的侧视效果图，图中CB1和CB2分别为两个圆形的投影，CB1′为CB1保持圆心距离和夹角不变情况下平移后的位置，即“相对方位”发生了变化，CB1与CB2没有发生相交，CB1′与CB2发生了相交。

由上述可知，圆形的圆心距离、夹角以及相对方位都影响着两个圆形是否相交。本文用圆形的圆心距离向量的模长$|\boldsymbol{m}|$、两个圆形的法向量点积$a$、$ \boldsymbol{m}$的单位矢量和圆形法向矢量的点积$s$分别表示圆形的圆心距离、夹角以及相对方位。

1) 圆形的圆心距离向量的模长$|\boldsymbol{m}|$，计算为

$ |\mathit{\boldsymbol{m}}| = \sqrt {m_x^2 + m_y^2 + m_z^2} $

(9)

式中，$\boldsymbol{m}=(m_{x}, m_{y}, m_{z})$。

2) 两个圆形的法向量点积$a$，计算为

$ a = {\mathit{\boldsymbol{n}}_1} \cdot {\mathit{\boldsymbol{n}}_2} $

(10)

$a$越大，两个圆形的夹角越小。因为$\boldsymbol{n}_{1}$和$\boldsymbol{n}_{2}$均为单位向量，且两个圆形之间的夹角$α∈[0, \mathsf{π}]$，所以$a∈[－1, 1]$。

3)$ \boldsymbol{m}$的单位矢量和圆形法向矢量的点积$s$，计算为

$ s = \frac{\mathit{\boldsymbol{m}}}{{|\mathit{\boldsymbol{m}}|}} \cdot {\mathit{\boldsymbol{n}}_1} $

(11)

式中，$ \frac{{\boldsymbol{m}}}{{|\boldsymbol{m}|}}$为单位矢量，$s∈[－1, 1]$。

$a$和$s$的变化影响阈值$δ$的大小。保持$s$不变，$a$越大，则$δ$越大；保持$a$不变，当$s∈\{－1, 0, 1\}$时，$δ$达到最小值。而$|\boldsymbol{m}|$与$δ$之间的大小关系决定圆形是否相交。由于深度神经网络具有拟合任意函数的特性，本文建立深度神经网络，如图 8所示。

将$a$, $s$和$|\boldsymbol{m}|$作为输入量；在输出层求$|\boldsymbol{m}|$和最后一个隐含层输出值之和的差值$h_{f}$，具体为

$ {h_f} = o(|\mathit{\boldsymbol{m}}| - \sum\limits_{j = 1}^{{j_{{\rm{max}}}}} {a_j^{{l_{{\rm{max}}}}}} ) $

(12)

若输出层的函数$o(·)$为tanh函数，则

$ o(z) = \frac{{{{\rm{e}}^z} - {{\rm{e}}^{ - z}}}}{{{{\rm{e}}^z} + {{\rm{e}}^{ - z}}}} $

(13)

由于该模型主要解决在0处的分类问题，所以对于tanh函数，当$z$值很大或者很小时产生的梯度消失问题并不会影响训练结果。

深度神经网络圆形包围盒相交测试过程如下：

1) 深度神经网络训练阶段。首先，对提取的数据进行预处理，将发生相交的圆形标记为-1，未发生相交的圆形标记为1；其次，对各层进行全连接。输入层有3个神经元，依次对应特征值$a$, $s$, $|\boldsymbol{m}|$，输出层的结果为$h_{f}$，隐含层数和每层隐含层中神经元数量分别预设为3和5。隐含层中激活函数选用PReLU函数，具体为

$ \sigma (x) = {\rm{max}}(ax,x),a \in [0,1] $

(14)

隐含层之间利用上层输出计算下层输入，具体为

$ {{z^{l + 1}} = {\mathit{\boldsymbol{W}}^l}{a^l} + {\mathit{\boldsymbol{b}}^l}} $

(15)

$ {{a^{l + 1}} = \sigma ({z^{l + 1}})} $

(16)

式中，$z^{l+1}$为$l$层输出值的加权和，$\boldsymbol{W}^{l}$为$l$层到$l+1$层的权重矩阵，$\boldsymbol{b}^{l}$为$l$层的偏置向量，$σ(·)$为隐含层的激活函数。

输出层接受最后一层隐含层的值后，利用输出函数输出结果，具体为

$ {h_f} = o(a_j^{{l_{{\rm{max}}}}}) $

(17)

式中，$o(·)$为输出层函数，$a^{l_{\max}}_{j}$为输出层接受的输入值。

输出结果的好坏通过损失函数来判断。本文通过深度神经网络对圆形之间是否发生相交作出判断，即解决二分类问题，所以采用交叉熵函数作为损失函数，计算预测值和标签值之间的距离，具体为

$ \begin{array}{*{20}{c}} {J(\mathit{\boldsymbol{W}},\mathit{\boldsymbol{b}}) = }\\ { - \left[ {\frac{1}{m}\sum\limits_{i = 1} { m } ({y^{(i)}}{\rm{log}}{\kern 1pt} {\kern 1pt} {o^{(i)}} + (1 - {y^{(i)}}){\rm{log}}(1 - {o^{(i)}}))} \right]} \end{array} $

(18)

式中，$J(\boldsymbol{W}, \boldsymbol{b})$为交叉熵，$m$为数据容量，$y^{(i)}$为标签值，$o^{(i)}$为标签值$y^{(i)}$对应的概率。

根据损失函数计算预测值与真实值之间的距离，通过反向传播算法对模型中的权重进行调整，直到输出满足要求，计算为

$ ({\mathit{\boldsymbol{W}}^l},{\mathit{\boldsymbol{b}}^l}) \leftarrow ({\mathit{\boldsymbol{W}}^l},{\mathit{\boldsymbol{b}}^l}) - \lambda \frac{{\partial J(\mathit{\boldsymbol{W}},\mathit{\boldsymbol{b}})}}{{\partial ({\mathit{\boldsymbol{W}}^l},{\mathit{\boldsymbol{b}}^l})}} $

(19)

式中，$λ$为学习率。

2) 实时模拟阶段。在自碰撞检测过程中，通过式(9)—(11)计算候选集中每组潜在碰撞对的$a$, $s$, $|\boldsymbol{m}|$，输入到模型中；由式(12)得到结果$h_{f}$，若$h_{f}≥0$，两个圆形没有相交，反之则相交。

基于深度神经网络的圆形包围盒相交检测流程如图 9所示。

由于三角形与圆形之间的相交检测剔除效果不如三角形之间的相交检测，但计算复杂度相似，而且圆形内仅包含单个三角形，所以，当圆形之间发生相交后，对相应三角形进行相交测试，而不检测圆形与三角形之间是否相交。

为了在保持算法的剔除率基本不变的情况下满足实时性的要求，优化深度神经网络的隐藏层数和每层节点数。首先测试不同隐含层数对准确率和计算效率的影响，如图 10所示，图中的测试率和计算耗时是对10组样本集进行测试后取平均值的结果，每个隐含层的节点个数为5。可以看出，准确率和测试耗时都随着隐含层数的增加而增加，但准确率的增长率逐渐降低，测试耗时的增长率逐渐增高，为满足实时自碰撞检测的要求，需要将测试耗时限制在30 ms内，当隐含层数为5时，耗时首次超过30 ms，当隐含层数为4时，准确率曲线开始趋于平缓，所以将4作为最优隐含层数。

通过改变每层节点数(悬垂布料)，比较对应的准确率和计算耗时，得出每个隐含层中的最优节点数，如图 11所示。可以看出，当每层节点数增加，准确率与测试耗时逐渐升高，与选取最佳隐含层数标准一样，当每层节点数达到7时，测试耗时首次超过30 ms。因此，本文将6作为每个隐含层最佳节点数。

实验在3个场景下进行，如图 12所示。1)悬垂布料, 布料固定左上角，自然下垂；2)从实体间下落, 布料从两个胶囊体间的空隙滑落至地面；3)布料与小球碰撞，布料垂直下落在小球上。

为了阐述本文方法的时效性，与AABB-OBB、Sphere-tree、OBB、10-DOP方法进行比较，分别对3个场景中的模拟耗时及耗时缩减率进行实验，结果如表 1和表 2所示。

耗时缩减率计算为

$ \eta = \frac{{{T_{{\rm{com}}}} - {T_{{\rm{our}}}}}}{{{T_{{\rm{com}}}}}} $

(20)

式中，$η$为耗时缩减率，$T_{\rm com}$为对比方法耗时，$T_{\rm our}$为本文方法耗时。

从表 1可以看出，在3个场景中，本文方法耗时比其他4种方法少，并且融合DNN方法比未融合DNN方法耗时少，说明本文方法更具有高效性。

从表 2可以看出，由于AABB-OBB方法是混合层次结构，在速度上优于Sphere-tree、OBB和10-DOP方法，而本文算法作为一种融合DNN的改进混合层次结构，耗时比AABB-OBB缩减了19%~33%，比本文未融合DNN的方法(即3.2节基于几何的圆形包围盒相交检测方法)耗时缩减11%~18%(表 2最后一行数据)，说明本文方法更适合布料的实时模拟。

为了验证本文方法的计算复杂度，以悬垂的布料为基准，比较了6种方法在每帧的测试耗时，结果如图 13所示。由图 13可以看出，在模拟开始阶段，没有发生自碰撞时，6种方法的自碰撞检测耗时没有太大区别，当抽样帧数为第5帧时，布料发生了自碰撞，本文方法的每帧计算耗时明显低于其他方法，并且，本文融合DNN的方法(图 13中浅蓝色折线)每帧计算耗时低于本文未融合DNN的方法(图 13中红色折线)，说明本文方法在频繁发生自碰撞的场景中，计算更具简便性，计算速度更快。

为了表明本文方法在包围盒的贴合性以及相交检测方面的优势，以悬垂布料为基准进行实验，比较了6种方法的更新率、检测效率和图元测试时间，实验结果如图 14所示。

从图 14可以看出，AABB-OBB方法的更新耗时比Sphere-tree方法多，比OBB和10-DOP方法少；图元相交测试耗时低于Sphere-tree、OBB和10-DOP方法。本文方法的更新耗时低于AABB-OBB方法，图元相交测试耗时更少，总耗时比AABB-OBB方法缩减了19%。在检测耗时上，本文方法融合DNN比未融合DNN时缩减了17%。

剔除率计算为

$ {r_{{\rm{ cull }}}} = 1 - \frac{{{n_{{\rm{ pot }}}}}}{{{n_{{\rm{ pri }}}}}} $

(21)

式中，$r_{\rm cull}$为剔除率，$n_{\rm pot}$为经过包围盒层次结构剔除后剩下的有发生碰撞可能的图元对数量，$n_{\rm pri}$为图元对总数量。贴合性好的包围盒剔除率高。

因为3个场景中布料的三角形面片数量相同，根据式(21)，只需要比较$n_{\rm pot}$即可知道各种方法贴合性的优劣。由于经过层次包围盒结构剔除剩下的潜在碰撞图元对必然经过图元相交测试，因此通过统计图元相交测试的次数即可知道$n_{\rm pot}$的大小。从3个场景中各抽取1个关键帧，统计同一关键帧下6种方法的图元相交测试的次数，结果如表 3所示。可以看出，3种场景下本文方法的图元相交测试次数最少，因此间接论证了本文方法在贴合性方面的优越性。

针对包围盒冗余空间导致自碰撞检测速率低的问题，本文提出了AABB-圆形包围盒方法的自碰撞检测算法。通过利用AABB-圆形包围盒快速剔除不碰撞的图元对，然后利用圆形良好的紧密性，大量剔除潜在碰撞集中的图元对，减少图元相交测试计算量。通过使用深度神经网络对圆形包围盒进行相交检测，加速了圆形包围盒之间的相交检测速度。与3种经典的包围盒及AABB-OBB混合包围盒进行对比，从多项评价指标上验证了融合深度神经网络的AABB-圆形包围盒方法的可行性与有效性。在未来的工作中，可以尝试对AABB包围盒构建神经网络模型来进一步提升算法效率。