计算机动画内容(例如电影和游戏)需要快速且可靠的方法来进行模拟，以获得更灵活和逼真的视觉效果。特别是在进行服装动画模拟时，布料的模拟效果直接影响着整个动画场景的视觉逼真度。质量弹簧系统为各种物体建模提供了一种简单而实用的方法，包括布料、头发和其他可变形体。然而，与其他用于建模弹性的方法一样，获得真实的材料行为通常需要构建刚性系统。显式积分法的求解速度快，但其稳定性不能得到保障。传统的隐式积分法虽然能够保持系统的稳定，但其求解复杂，系统开销大，所需时间长，这些因素使得实时模拟效果不好。后来的改进隐式欧拉积分算法^[1-3]，以及相继提出的各种分层布料划分方法^[4-6]都为快速可靠地进行布料模拟提供了可行方案，并取得了不错的效果。但是，使用这些方法的成本依旧很高，不仅在实时应用程序(例如游戏)中，而且在离线图形系统(例如电影和视觉效果)中亦是如此。

近年来，与机器学习相结合的算法已经在各个领域崭露头角。在计算机动画，尤其是布料模拟领域，也已经开始有研究者利用机器学习的思想来对布料建模进行优化^[7-11]。例如Guan等人^[7]考虑到人体衣物的变形由人体的运动所驱动，提出了将人的衣物布料的变形分别在只考虑人体形态与只考虑人体运动姿势的情况下进行训练，最后再整合在一起的方法。该方法可以在任意形态及任意姿势的人身上产生合适的衣服布料模型，对服装动画的实时性方面有一定的贡献。石敏等人^[11]指出了Guan等人^[7]方法的不足，自定义了一种人体姿态特征，将人体定义为由11个关节驱动的骨架，并定义了每个关节的特征表达式，最后从动画实例数据中提取人体运动特征和服装变形特征数据，利用机器学习的方法学习了二者之间的关系，并成功构建了有效的关系模型，达到了输入新的人体运动，便可以预测人体上服装各区域变形程度的效果。

上述方法虽然都对服装形变进行了合理的预测，使系统不用再进行复杂的曲率计算，在一定程度上加速了服装模拟的速度，但由于其底部布料的划分还是基于物理驱动的，所以其整体的效率并未提高很多。本文针对此问题，对布料网格的划分方法进行优化，将传统物理方法与机器学习方法相结合，加快布料网格的划分速度，提高布料划分的实时性，从而达到优化服装动画的效果。

由于大多数织物非常柔软并且没有弹性，因此真实布料模拟产生的网格可以具有非常详细的特征，为了产生逼真和复杂的布料模拟效果，需要精细的布料网格来表示。对于快速布料模拟，已经提出了多级网格布料模拟方法^[4]以及动态变化的多分辨率布料模型^[12-15]。Bender等人^[6]提出了多分辨率的形状匹配方法，Tang等人^[16]将GPU并行计算技术引入高精度布料动画系统，以提高计算效率。

本文使用的分层布料模拟方法与以前相同方式模拟所有级别的分层方法不同，本文方法是将传统的基于物理的模拟与机器学习模型的推断结合起来。当使用细网格来替换粗网格时，将应用网格细化方法。常用的细分方法有1~4面分裂细分算法，如图 1所示。

该方法找到三角形(如$\Delta {P_1}{P_2}{P_3} $)的3条边的中点($ {P_4}, {P_5}, {P_6}$), 并将3个中点用线连接起来，从而将1个大三角形细分为4个子三角形。另一种细分方法称为$ \sqrt 3 $细分法^[17]，如图 2所示，该方法通过插入新顶点后按照一定的规则连接，将1个原始三角形网格细分为3个子三角形网格。原始网格中的三角形面片被标记为索引0，如图 2(a)所示，只要产生新的三角形其索引值便会加1，因此当网格被插入顶点并进行划分后新产生的三角形的索引值为1，如图 2(c)所示，因为此时产生的新三角形含有钝角，较为狭长，不够稳定，因此接下来会进行边翻转操作，边翻转后新产生的三角形不含钝角，稳定可靠，如图 2(d)所示。$ \sqrt 3 $细分方法所产生的网格顶点相对较少，所以对网格顶点的计算量会降低很多，减少了高分辨率网格所需要的计算时间，保证了布料模拟的真实感，且更有利于模拟的实效性。因此，本文采用此网格细分方法来进行讨论研究。

随机森林回归(RFR)算法是随机森林理论中的重要应用之一^[18-19]。随机森林回归算法是采用Bootstrap抽样方法来构造每个弱学习器(即决策树)的训练样本。然后对每个训练样本集进行决策树建模，并将多棵决策树组合起来进行预测，最后将组合决策树的预测结果求取平均值, 从而得到最终预测结果，其算法的本质是组合了多棵决策树来进行预测的多决策树模型，如图 3所示。

随机森林回归模型通过使用bootstrap重抽样方法，由随机向量$ \mathit{\boldsymbol{\theta }}$ (即回归树)构成了回归树组合模型$\left\{ {\mathit{\boldsymbol{h}}\left( {\mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{\theta }}_k}} \right), k = 1, \cdots p} \right\} $, 其中, $p $表示随机森林中决策树的个数。随机森林回归模型所预测的结果是通过求$ k$棵回归树的$\boldsymbol{h}\left\{\left(\boldsymbol{X}, \boldsymbol{\theta}_{k}\right)\right\} $的平均值得到，模型的训练集相互独立，选自随机向量$\mathit{\boldsymbol{X}}, \mathit{\boldsymbol{Y}} $。数值型预测向量$\mathit{\boldsymbol{h}}(\mathit{\boldsymbol{X}}) $的推广误差均方为

$ {E_{X, {\rm{ }}Y}}(\mathit{\boldsymbol{Y}} - \mathit{\boldsymbol{h}}(\mathit{\boldsymbol{X}})) $

(1)

随机森林回归有以下特性：

1) 当模型中回归树的数目趋于无穷大时有

$ \begin{array}{c}{E_{X, Y}\left(\boldsymbol{Y}-v \boldsymbol{h}\left(\boldsymbol{X}, \boldsymbol{\theta}_{k}\right)\right)^{2} \rightarrow} \\ {E_{X, Y}\left(\boldsymbol{Y}-E_{\theta} \boldsymbol{h}(\boldsymbol{X}, \boldsymbol{\theta})\right)^{2}}\end{array} $

(2)

式中, $ v$为取平均函数，指求取回归结果的平均值, ${E_\theta } $为期望函数。

2) 不同决策数的随机变量$ \mathit{\boldsymbol{\theta }}$和$ {\mathit{\boldsymbol{\theta '}}}$是相互独立的。若对于所有$ \mathit{\boldsymbol{\theta }}$，$E(\boldsymbol{Y})=E_{x} \boldsymbol{h}(\boldsymbol{X}, \boldsymbol{\theta}) $，则

$ P E^{*}(f) \leqslant \bar{\rho} P E^{*}(t r) $

(3)

式中，$P{E^*}(tr) = {E_\theta }{E_{X, Y}}{(\mathit{\boldsymbol{Y}} - \mathit{\boldsymbol{h}}(\mathit{\boldsymbol{X}}, \mathit{\boldsymbol{\theta }}))^2}, P{E^*}(f) $表示由一系列树构成的森林的泛化误差, $ P{E^*}(tr)$表示森林中任意一棵树的平均泛化误差, $ \bar{\rho}$为剩余$ \mathit{\boldsymbol{Y}} - \mathit{\boldsymbol{h}}(\mathit{\boldsymbol{X}}, \mathit{\boldsymbol{\theta }})$和$\mathit{\boldsymbol{Y}} - \mathit{\boldsymbol{h}}(\mathit{\boldsymbol{X}}, \mathit{\boldsymbol{\theta '}})$间的权重相关系数，$ \mathit{\boldsymbol{\theta }}$是独立的。

随机森林回归算法具有预测精度高、泛化误差可控、收敛速度快以及调节参数少等优点，并且因其采用Bootstrap抽样方法采集训练样本，可有效地避免“过拟合”现象发生，适用于各种数据集的运算，对高维数据^[11]的处理也有不俗的表现。本文将传统的基于物理的方法与随机森林预测方法相结合来进行可靠的布料模拟。

本文提出的融合随机森林模型的布料分层建模方法是一种结合了传统的基于物理的模拟方法和随机森林预测的布料模拟方法。

首先，使用传统的基于物理的方法来模拟分层布料的最粗糙等级($ {L_0}$)；其次，采用随机森林算法推算分层布料系统中更精细的级别($ {L_i}, i = 1, \cdots N$)。由于基于物理的方法来模拟分层布料最初始等级，可以防止随机森林模型在推断更精细水平布料时产生重大错误，并保证可靠地模拟效果，所以初始水平模拟时不使用随机森林模型进行预测。其详细步骤如下：

1) 使用隐式积分方法计算出初始布料网格中各个质点的位置，产生布料网格$ {L_0}$，将布料网格$ {L_0}$里的三角形的索引值标为0，即产生最初始水平的布料。

2) 使用随机森林模型中的回归算法，在初始水平布料的基础上计算新质点的位置，然后将新质点与步骤1)中产生的布料网格$ {L_0}$里对应于新质点的三角形的顶点相连，产生新的布料网格，将网格中新产生的三角形的索引值标为1。

3) 使用边翻转操作，将步骤2)中产生的布料网格中的狭长三角形转化为不含钝角的稳定三角形，产生新的布料网格$ {L_1}$，将$ {L_1}$中经边翻转产生的三角形索引值加1。

4) 对产生的布料网格进行判断，若对模拟结果满意，则停止算法，即完成基于随机森林算法的分层布料模拟；否则，重复步骤2)~4)，每当产生新的三角形，其索引值依次加1，直至产生满意的布料动画为止。

整个分层布料模拟方法的流程图如图 4所示，布料分层模拟过程如图 5所示。

前面已经提到要利用传统基于物理的方法即隐式积分方法来模拟层次布料系统的最初级别($ {L_0}$)。假设在级别$ {L_0}$布料中具有位置为$\boldsymbol{x}_{0}(t) $、速度为$ \boldsymbol{v}_{0}(t)$以及质量矩阵$\boldsymbol{M}_{0} $的质点，使用隐式积分法计算模拟中质点的下一个位置$ \boldsymbol{x}_{0}(t+\Delta t)$，具体为

$ {\boldsymbol{x}_{0}(t+\Delta t)=\boldsymbol{x}_{0}(t)+\boldsymbol{v}_{0}(t+\Delta t) \Delta t} $

(4)

$ \begin{array}{c} {\boldsymbol{M}_{0} \boldsymbol{v}_{0}(t+\Delta t)=\boldsymbol{M}_{0} \boldsymbol{v}_{0}(t)+} \\ {\left(\boldsymbol{f}_{\mathrm{ext}}(t)+\boldsymbol{f}(t+\Delta t)\right) \Delta t}\end{array} $

(5)

式中，${\mathit{\boldsymbol{f}}_{{\rm{ext}}}} $表示外力, $ \mathit{\boldsymbol{f}}$代表模型的隐含力。式(4)和式(5)的计算可以转换为以下最小化问题

$ \begin{array}{*{20}{c}} {{\mathit{\boldsymbol{x}}_0}(t + \Delta t) = }\\ {\arg \mathop {\min }\limits_{{\mathit{\boldsymbol{x}}_0}} \left( {\frac{1}{{2\Delta {t^2}}}\parallel {{\left( {{\mathit{\boldsymbol{M}}_0}} \right)}^{\frac{1}{2}}}\left( {{\mathit{\boldsymbol{x}}_0}(t)} \right) - } \right.}\\ {\left. {\left. {{{\mathit{\boldsymbol{\tilde x}}}_0}(t + \Delta t)} \right){\parallel ^2} + U\left( {{\mathit{\boldsymbol{x}}_0}} \right)} \right)} \end{array} $

(6)

式中，${{{\mathit{\boldsymbol{\tilde x}}}_0}(t + \Delta t)} $表示的是在没有隐含力$ \mathit{\boldsymbol{f}}$的情况下所预测的质点的下一位置，$ U$是影响布料模型的不同能量项的总和。

经过随机森林模型的预测，可以得到质点在更精细级别层中的下一个位置。随机森林算法自从提出后，便被广泛地应用在分类问题的研究上，但实际上，随机森林算法不仅能够用于解决分类问题，并且在解决回归问题上也有不俗表现。本文就是利用随机森林算法来解决回归问题，算法中的预测变量属于数值型变量，生成的随机森林模型为多元非线性回归分析模型。

使用随机森林模型对质点位置进行预测，其主要过程如下：

1) 随机森林算法只需调节算法中决策树的数量和生成决策树使用的特征值数量。原始数据样本含量为$ n$，每个训练样本含有7个输入特征维，利用bootstrap法有放回地随机抽取$ b$个新的训练样本集，每次未被抽到的样本组成了$n - b $个袋外数据(OOB)，作为随机森林模型的测试样本。随机选取的特征数目取$ M_{\mathrm{try}}=\log _{2}(M+1)(M$为训练样本的特征维数)，随机森林模型中回归树的容量则需根据预测结果进行调整。

2) 将三角形与其初始位置相比的局部差异作为输入特征向量，定义为

$ \mathit{\boldsymbol{\delta }}_{pqr }^{i + 1} = \left[ {\left( {\mathit{\boldsymbol{x}}_p^{i + 1} - \mathit{\boldsymbol{x}}_p^i} \right), \left( {\mathit{\boldsymbol{x}}_q^{i + 1} - \mathit{\boldsymbol{x}}_q^i} \right), \left( {\mathit{\boldsymbol{x}}_r^{i + 1} - \mathit{\boldsymbol{x}}_r^i} \right)} \right] $

(7)

式中，$\mathit{\boldsymbol{x}}_p^i, \mathit{\boldsymbol{x}}_q^i, \mathit{\boldsymbol{x}}_r^i $为$\mathit{\boldsymbol{x}}_p^{i + 1}, \mathit{\boldsymbol{x}}_q^{i + 1}, \mathit{\boldsymbol{x}}_r^{i + 1} $的初始位置。随机森林算法的输出为预测的新质点的位置与其真实位置的差异，定义为

$ \boldsymbol{O}_{s}^{i+1}=\boldsymbol{x}_{s}^{i+1}-\boldsymbol{x}_{s}^{i} $

(8)

式中，$ \boldsymbol{x}_{s}^{i}$为$ \boldsymbol{x}_{s}^{i+1}$的初始位置。随机森林算法所预测的新质点的位置$ \boldsymbol{x}_{s}^{i+1}$为

$ \boldsymbol{x}_{s}^{i+1}=\boldsymbol{x}_{s}^{i}+\boldsymbol{O}_{s}^{i+1} $

(9)

3) 使用袋外数据(即测试样本)预测的残差均方来评价随机森林回归模型的预测效果，具体为

$ {MS{E^{{\rm{OOB}}}} = {n^{ - 1}}\sum\limits_1^n {{{\left( {{y_i} - \hat y_i^{{\rm{OOB}}}} \right)}^2}} } $

(10)

$ {R_{{\rm{RF}}}^2 = 1 - \frac{{MS{E^{{\rm{OOB}}}}}}{{\hat \sigma _y^2}}} $

(11)

式中，$ {MS{E^{{\rm{OOB}}}}}$指的是测试样本的残差均方，${R_{{\rm{RF}}}^2} $为确定性系数，${R_{{\rm{RF}}}^2} $越大表示模型精度越高，预测效果越好，$ {{y_i}}$为测试样本中因变量的实际值, ${\hat y_i^{{\rm{OOB}}}} $为回归模型对测试样本预测值的方差，$ {\hat \sigma _y^2}$为随机森林对测试样本估计值的方差。

如1.1小节所介绍的，由于本文方法采取的布料划分方法为$\sqrt 3 $细分法，因此利用随机森林算法找到质点位置后，所产生的三角形含有钝角，不够稳定，故需要进行边翻转操作来产生稳定可靠的三角形。但并不是所有的三角形边都需要进行翻转，只有同时满足以下两个约束条件的三角形边才进行翻转操作：1)与三角形中钝角所对应的边共享此边的三角形。2)要进行边翻转操作的两个三角形具有相同的索引值。

为了在取得可靠的模拟效果的前提下，尽可能地缩短模拟所需的时间，需要为随机森林模型设置最合适的决策树数量，来保证模型的训练速度与误差。本文依据经验选取了几种决策树容量方案，并求得在不同方案下随机森林算法将布料模拟到同一水平(以模拟到3 000个质点为例)所需时间，实验结果如图 6所示。

实验结果表明，并不是随机森林模型中决策树的容量越大，布料模拟所需的时间就越短。决策树的容量为400时，随机森林算法模型能够在具有相同采样数的前提下，最快地完成模拟任务。

将使用本文算法的仿真结果和计算性能与应用了投影动力学以及ADMM算法的基于物理的仿真方法进行了比较。图 7(a)(b)显示了使用投影动力学和ADMM方法计算的高分辨率和低分辨率模拟结果。图 7(c)是使用本文方法生成的高分辨率模拟结果。如图 7(a)(c)所示，本文方法的模拟结果与相同分辨率下的传统物理模拟方法的模拟结果不同。因为本文方法使用传统基于物理的方法仅计算模拟了最粗糙的水平，所以本文的结果不如传统的基于物理的方法模拟的那样精确。然而，正如图 7(b)(c)所示，本文模拟结果又优于使用传统的基于物理的方法模拟计算的低分辨率模拟，这是因为本文随机森林算法模型是在传统基于物理方法模拟出最粗糙水平的基础上推断出更精细水平的模拟。

实验将本文算法与应用了共轭梯度法(CG)改进后的隐式积分方法，以及基于交替方向乘子法(ADMM)隐式积分^[3]算法进行了对比。在实验中，通过固定CG算法和ADMM算法的迭代次数，保证了两种传统方法计算的模拟结果具有相似的误差。CG算法和ACMM算法的迭代次数分别为100和20。对于本文方法，对最粗糙级别(${L_0} $级别)使用相同数量的ADMM算法迭代，并使用随机森林模型的预测生成更精细的级别。实验结果如图 8所示。

实验结果表明，在具有相同前提条件的情况下，融合随机森林算法的布料分层建模方法比传统的基于物理的模拟方法更快地生成模拟结果。在模拟质点数目较少时，融合随机森林算法的布料分层建模方法相比于其他传统方法优势并不明显。但随着所模拟的质点数目增加时，融合随机森林算法的布料分层建模方法便发挥其优势，省去了传统基于物理的模拟方法进行的大量数值计算，相比于ADMM算法，融合随机森林算法的布料分层建模方法的模拟效率提高了约26%。

本文之所以与共轭梯度法(CG)改进后的隐式积分方法，以及基于交替方向乘子法(ADMM)隐式积分算法进行对比，是因为CG改进后的隐式积分法是目前布料仿真领域最被人们接受且使用广泛的一种模拟方法，而ADMM隐式积分法是近年来提出的改进效果相对较好的一种传统模拟方法，因此将本文算法与两种经典的基于物理的模拟方法进行对比。

由上述两次实验可知，本文算法虽然不如传统的基于物理的方法模拟得那么精确，但它快速且适合于生成与传统方法一样可靠的高仿真模拟效果。

为了验证融合随机森林算法的布料分层建模方法可以产生稳定可靠的模拟效果，在使用本文方法进行布料模拟的基础上，添加了风力作用，观察其在外界力作用下的模拟结果。为了使实验结果更有代表性，随机抽取了几帧布料动画作为检验样本，如图 9所示。

从3次抽样的实验效果图来看，在施加了外力作用下，布料发生真实抖动，产生生动的波纹，无明显锯齿形状条纹，因此可以表明本文方法在施加了外力的影响下也可以产生稳定可靠的布料动画效果。

上述实验验证了本文方法在施加外力，但无外界物体干扰条件下能够产生稳定可靠的动画效果。为验证在与外界物体发生碰撞时，布料模拟的性能，设置场景，将一块布料自由落下在几个圆柱体间，观察布料在下落时与柱子发生摩擦、碰撞时的模拟表现。实验效果如图 10所示。

从实验效果图可知，布料在自由下落与物体发生碰撞后，布料依旧自然舒展，正常产生了褶皱，并且符合现实情况下，布料在圆柱体间自由下落的情景，因此可以证明，即使是与外界物体有碰撞摩擦的情况下，本文方法依旧可以产生稳定可靠的动画。

本文提出了一种融合随机森林算法的布料分层建模方法。通过利用随机森林算法取代传统的基于物理的积分方法，对布料进行分层次模拟。通过使用随机森林算法对质点在下一水平布料中的位置进行预测，然后通过边翻转操作生成稳定可靠的三角形网格布料。与两种传统基于物理的布料模拟方法进行对比，从多项评价指标验证了融合随机森林算法的布料分层建模方法的可行性与有效性。

虽然本文算法已经取得了不错的效果，但在以下方面还有待改进：1)算法在进行初始水平的模拟时，还是使用了传统的物理方法，增加了一定的模拟时间，并且模拟质量也有待于提高。下一步工作就是找出一种更加可靠的机器学习模型，保证在布料模拟开始时就产生稳定可靠的预测结果。2)边翻转操作在本质上也可以提取其特征，从而使用机器学习算法来代替这一过程，进一步减短布料模拟的整体时间。