图1
计算机图形学中针对数据驱动方法的中心论点取决于维度的咒语：对复杂空间的“一切”进行预计算是棘手的。在本文中，我们通过使用数千的CPU运行时间来挑战这一假设，以便通过大型运动图，对辅助服装空间（the space of secondary clothing）在动画角色上的影响进行大规模探索。

我们的系统将不断探索布料动力学的拓扑空间，逐步构建一个可以捕捉动力学系统的辅助布料运动图（secondary cloth motion graph）。我们发现有可能将动态空间采样到低视觉容错，并且包含数十千兆字节原始网格数据的辅助运动图可以被压缩到仅几十兆字节。 这些结果使我们能够捕捉高分辨率及离线布料仿真对丰富的角色动作空间的影响，并将其作为交互式应用程序的一部分进行高效传送。
关键词: 布料模拟，数据驱动动画，视频游戏

1 简介

数据驱动技术已经实现了有着惊人复杂现象的实时动画，这些现象原本要么过于昂贵而难以实时模拟（例如高分辨率布料的褶皱 [Kavan等人 2011; Wang等人 2010] ）或是缺乏优异的模型（例如人体动作）。
然而，反对这些基于预计算的方法的中心论点取决于维度的诅咒：不可能捕捉到“一切”，因为每个额外模拟条件下的动态空间都在指数性爆炸增长。基于此原因，之前几乎所有的数据驱动动画都工作在很少的激励模式下，在严格控制的环境中研究现象，并且严格假设现象会周期性地返回到单一静止配置[James和Pai 2002; James和Fatahalian 2003; de Aguiar等人 2010; Guan等人 2012]。
鉴于低成本，大规模计算能力的快速增长，我们认为现在是重新审视这一假设的时候了。尽管捕捉复杂动力学系统的所有内容并不容易，但是捕捉几乎所有重要的内容却是可能的。这反映了计算机科学的发展趋势：研究人员在理论上研究机器翻译等无限空间时，已经捕获了翻译的“几乎所有内容”。例如，仅需使用足够大的数据语料库[Halevy等人 2009]即可完成。

在本论文中，我们将重点放在通过有限运动图进行动画角色辅助布料效果的预计算上。我们引入了辅助运动图的概念：对于主运动图中的每个状态（在本例中为角色的姿态），辅助运动图中可能有许多相应的状态（在本例中为身体上的衣服配饰）。因为布料是一种动力学系统，布料的状态而不仅取决于身体的姿态，还取决于之前的布料状态，所以辅助运动图可能比主动作图复杂得多。
我们通过对辅助运动图空间进行大规模的探索来报告我们的发现。与之前关于预计算的工作相比，我们模拟了更多的数据以构建动力学相位空间的大型图像。我们的主要示例使用超过55分钟的模拟布料动画以及超过4500个CPU小时的计算来表现。我们探索的规模使我们能够观察动力学中的分枝现象，即布料配置的持续变化会产生新的子图，这些子图与计算过的状态大部分保持不相交。我们证明，即使对于大型动作图形，也可以探索辅助动态空间以降低视觉容错 - 基本上，预计算几乎所有重要的 - 可以将结果数据压缩到相当小的内存占用。在实际应用中，这些结果使我们能够捕捉到高分辨率离线布料模拟对角色动作丰富空间的影响，并将其作为交互式应用程序的一部分在适度的硬件上进行实时传送。
与许多数据驱动技术相比，我们的模型保证了预计算模型中近似误差的范围。由于采样不足导致的误差仅在数据库中稀疏的一组帧中出现。因此可以完全验证误差，甚至可以手动检查这些误差帧。此外，与之前的预计算方法通常需要详细设置预计算确切场景相反，我们的系统旨在支持动态空间的“持续探索”，在相位空间的不断扩大的空间中构建动态空间。

2 相关工作

使用计算机模拟生成布料动作已成为一个长达四分之一世纪的活跃研究课题[Terzopoulos等人 1987]。在那段时间里，有关布料动力学和碰撞处理的关键问题已经得到解决[Baraff和Witkin 1998; Bridson等人 2002; Choi和Ko 2002; Bridson等人 2003]。 有关布料模拟方法发展的总结可以在Nealen等人[2006] 和Thomaszewski等人[2007]的调查文章中找到。目前许多模拟布料的方法可以产生非常逼真的结果，甚至可以以假乱真[Mu ̈ller和Chentanez 2010; Narain等人 2012]。这些方法的逼真程度可以通过使用测量材料特性来增强[Wang等人 2010; Miguel等人 2012]，甚至模拟独特纱线层次物理学来增强[Kaldor等人 2010]。
然而不幸的是，目前逼真高分辨率布料仿真的计算成本导致了它在交互式应用中难以使用。图形研究人员使用各种方法解决了这个问题，其中许多方法也使用预计算的数据。
一种常见的方法是进行低分辨率仿真，然后使用基于预计算的高分辨率仿真来添加额外的褶皱细节[Wang等人 2010; Kavan等人 2011; Feng等人 2010]，记录真实布料[Popa等人 2009; Hilsmann和Eisert 2012]或简化的物理模型[Mu ̈ller和Chentanez 2010; Rohmer等人 2010]。 尽管这些方法能以最小计算开销来显着提高布料真实性，但结果运动仍然会反映出低分辨率的底层模拟网格。
研究人员还研究了减少模型的方法，以求在一个降阶模型中充分捕获流体[Treuille等人 2006; Barbicˇ和Popovic 2008; Wicke等人 2009]、可变形对象[James和Pai 2002; Barbicˇ和James 2005; An等人 2008]等复杂系统。这种方法可以显着地加速，但是很难捕捉不连续物体，并且会对底层动力学产生其他限制。 此外，这种数据驱动的方法通常要求模拟运动与预计算的数据密切相关，如果被捕获的模型数据偏离系统预期太远，将会出现不可预知的错误。本文探讨了一种不同的方法，使用更简单的基于图表的模型来进行动力学统计，同时强调大量的预计算以捕捉大部分布料相位空间。
de Aguiar等人 [2010]的稳定空间技术完全避开了运行模拟，选择从黑箱模拟数据中学习准线性模型，而不是减少人物角色上的服装动力学。这个学习模型基于身体姿态（数据驱动反馈的蒙皮方法）和近期布料状态来拟合布料动作。
与de Aguiar的工作相反，James和Fatahalian [2003]明确列出了可变形系统的（任意非线性）动力学。 通过导航驻留在预计算子空间中的布料轨迹数据库来实现实时布料动画。我们的工作在精髓上与他们相似，但在两个关键方面有所不同。首先，我们不使用简单脉冲的小调色板来驱动系统，而是通过使用角色运动图来表现更加丰富的外部布料空间。其次，我们的状态空间抽样过程的规模允许我们统计更复杂的布料行为，包括展示行为分枝和布料的空间，而并不会返回单独的休息状态。我们的工作致力于将大量预计算的数据提取为一种表示形式，从而在交互式系统中提供高质量的布料动画，以实现子空间采样和数据压缩挑战。
我们的方法的一个关键优点是，它自然地模拟了相位空间中的分枝，这是预计算方法的一个关键挑战。Twigg和James利用动力学分枝（来自碰撞）控制图形。他们的方法之一探讨了接触不确定性来创建动画，并聚合到期望的最终状态[Twigg和James 2008]。另一个将碰撞物体的分枝动力学形象化为控制的交互范式[Twigg和James 2007]。我们的工作同样研究包括分枝在内的大规模相位空间，但是我们的目标是不同的：我们将分枝视为数据驱动的交互式仿真过程中不断修复建模的方式，而不是寻求控制它们。

3 辅助运动图

我们追求一个完全数据驱动的系统，用于综合人性化服装的实时、高分辨率动作。我们的方法依赖于模拟布料运动的大量抽样，这是通过大型运动图对角色进行动画处理而产生的。随着新的布料动作的产生，它们被分析并压缩成一个紧凑的表示形式，从而实现低成本的运行时使用。我们接下来描述我们的布料动作表示方法，以及用于采样，压缩和交互式回放预计算布料运动的技术。

3.1 辅助图定义

图3

我们用两个运动图[Kovar等人 2002; Arikan和Forsyth 2002]表示人物动作及其相关的辅助布料动力学。第一张图，我们称之为主图，是描述角色移动的标准运动图。我们图表规范中使用图节点$p_{i}$代表个人角色姿势（而不是运动剪辑）。那么，图中$p_{i}$到$p_{j}$的边代表在动画中可以由$p_{i}$状态直接变成$p_{j}$状态。 图3中以黑色标识了具有七种状态的主运动图的一个小例子。
我们用一个辅助布料运动图来附加到主运动图，这个图表将布料运动的巨大（可能是无限的）空间制成表格。 辅助图中的每个节点（图3中的13个红色状态）表示一个布料姿态$c_{i}$，并且它与现有的一个主图节点$P(c_{i})$相关联。 也就是说，当布料呈现姿态$c_{i}$时，角色处于状态$P(c_{i})$。 布料相位空间的大量采样将导致辅助动作图明显大于主图。因此，如图3所示，主图形中的每个节点都可以跟许多辅助图状态相关联。
在播放过程中，主图的遍历由应用程序的角色控制器控制，这在当今的交互式应用程序中很常见。为了生成布料运动，从$p_{j}$到$p_{k}$的每个主图转换也触发从当前布料状态$c_{i}$到$C(ci,p_{j}\to{p_{k}})$的相应辅助图转变。在图中提供了一个枚举布料状态$c_{0}$和$c_{5}$的辅助图转换的表格。
辅助图及其相关的转换表$C(ci,p_{j}\to{p_{k}})$描述了布料在角色施加外力下响应的运动。总之，它们的功能类似于James和Fatahalian [2003]描述的脉冲响应函数数据库。 通过将外力表示为主运动图中的转换，我们可以编写比James和Fatahalian的脉冲调色板更加丰富的力空间。

3.2 图探索

由于其动态动作，服装可以通过主图从角色连续动画获取任意量的配置信息。因此，整体制定辅助运动图很可能是棘手的。 相反，我们通过重复遍历主图的片段并使用黑盒离线布料模拟器计算相应的布料运动，从而逐步建立辅助运动图[Narain等人 2012]。 我们的系统专门设计为能够“永远取样”，探索未发现的动作，同时持续保持有效的辅助运动图，以便立即交互使用。
图初始化。图初始化。我们通过从任意选择的初始角色姿态开始，进行宽度优先遍历来探索每个主图边，初始化辅助图。衣服置于该初始姿势上，角色进行完姿态以后，穿过该姿势对应正面模拟衣服的图。
图4左边展示了在初始布料状态为$c_{0}$的情况下从节点$p_{0}$开始的探索。得到的结果是由仿真产生的布料轨迹树（以红色显示）。（为了清晰起见，在图的左下角重新绘制该树。）从树的根$c_{0}$到叶$c_{i}$的每条路径表示从初始姿势$P(c_{0})=p_{0}$到$P(c_{i})$。

RemoveDeadend(c_end):
    (c_similar, err) = FindMostSimilar(c_end)
    // merge cend into c_similar
    foreach edge e incoming to c_end do:
        modify e to point to c_similar remove c_end from graph
    workQueue.AddJob(err, (c_end, c_similar))

ExpandGraph():
    do forever:
    (c_end , c_similar) = workQueue.LargestErrorJob()
    // revert the merge of c_end into c_similar re-insert c_end into graph
    foreach edge e incoming to csimilar do:
        if e resulted from prior merge with c_end: modify e to point to c_end
            newSubtree = SimulateCloth(c_end)
    foreach new dead-end cnew in newSubtree do:
        RemoveDeadend(c_new)

此时，树的叶子在辅助运动图中是末端点。我们找出与它共享相同主图状态同时具有最相似的内部布料状态的节点，通过合并他们来删除每个末端点状态（参见函数RemoveDeadend()）。请注意，在图4的中间面板中，末端节点$c_{5}$和$c_{9}$已分别合并为$c_{0}$和$c_{2}$。 （删除的节点$c_{5}$和$c_{9}$在辅助图中以灰色显示。）先前通向末端节点的边现在通向合并的目标（以蓝色显示）。一旦所有末端点都被删除，图表初始化就完成了。现在，辅助图为任意角色动作序列提供布料动画结果，因此可以粗略地近似布料动力学的整个空间。图中的红色边与实际模拟轨迹相对应，蓝色边则构成了过渡到真实布料动力学的转换。当近似值较差时（即图中没有内部节点与末端状态相似），需要进一步采样布料相位空间以减少此误差并避免播放期间的低质量运动。
无穷图扩展。 在每个末端合并操作之后，我们将（合并前）末端布料图状态及其相关联的（合并后）边近似误差值存储在优先工作队列中以供进一步采样。为了减少布料的动作误差，我们使用函数ExpandGraph()给出的步骤来大幅优化辅助运动图。在每个扩展步骤中，我们从优先级队列中取出含有最大的误差值的末端$c_{max}$，并通过恢复先前的图，也就是撤销合并操作来将$c_{max}$重新插入图中。然后，我们模拟从$c_{max}$（和角色姿势$P(c_{max})$）开始的布料运动。进一步模拟取样布料相位空间之前未探测的区域，并在辅助图中产生另外的新的末端。 如前所述，通过添加合并消除这些新的末端。
图4右图显示了从入队的末端状态$c_{5}$开始执行图探索的一个步骤的结果。额外的仿真会导致两个新的末端，这两个末端都被合并到$c_{2}$中。辅助图细化的过程不断重复后，消除了在探索布料相位空间时遇到的最大物理误差值，同时始终保持无末端的辅助运动图。虽然在每个新扩展步骤中执行的仿真都依赖于先前的结果，但是在工作队列中每个末端扩展图是独立的，使图扩展得以并行。

3.3 细化

服装定制的误差指标。 某些布料过渡误差值比其他布料过渡误差值更令人反感。为了给系统提供最劣误差值的概念，我们可以为特定的服装或动作领域定制布料-姿势相似性度量。例如，对于长袍服装（在第5节中讨论），特别令人反感的是，布料图包含将头巾从角色肩膀上的一个位置向上抬起的反向链接。我们发现简单的误差度量（例如，顶点位置和速度的$L_{1}$或$L_{∞}$误差）并不能将这样的过渡标识为恶劣的，所以我们采用一种度量方法来将布制品的姿势分类为向上或向下，并分配高误差来合并这些会导致难以置信的从下到上的过渡。这些过渡会升至优先队列的顶部，系统通过从这些高误差末端开始探索动态，从而得到快速消除偏差值的结果。
图形混合。 二次图中的运动误差会在末端合并（图4中的蓝色边缘）所生成的边处发生。为了减少由这些不连续性引起的视觉伪影，我们通过在合并状态之前和之后线性混合轨迹来将它们的误差值分散在一系列帧（我们实现使用十个）上。

4 压缩

在任意辅助图拓展步骤之后，我们可以压缩和打包数据以进行交互式可视化或集成到游戏引擎中。压缩对于交互式播放至关重要，因为我们原始的辅助图数据由成千上万个需要数百GB存储空间的布料网格构成。但是，正如其他人以前所观察到的[Wang等人 2010]，服装往往形成几乎重复的模式，而且这些数据存在大量冗余。我们发现原始的辅助图数据可以压缩的非常好，而压缩后的结果体积小，可以实时有效地解压缩。这种压缩对于现代游戏这些通常具有有限内存预算的程序而言至关重要，特别是对于辅助效果。
我们首先通过执行James和Fatahalian [2003]描述的核心外SVD来降低数据集的维数。该步骤将布料数据矩阵$D\in{R^{3v\times{n}}}$（包含v个顶点位置的n个帧）分解成b维布料基础$B\in{R^{3v\times{b}}}$和轨迹系数矩阵$C\in{R^{b\times{n}}}$，使得$D\thickapprox{BC}$。我们通过实验确定，使用200个基（$b=200$），重建的布料网格在视觉上与原始模型非常相似。但是，在布料与底层人体模型接触的地方，即使小的压缩误差也会导致深度顺序颠倒，从而导致清晰的渲染伪影。我们在渲染过程中使用深度偏移技术[de Aguiar等人 2010]，并通过非常轻微缩小身体模型来消除这些伪影。
我们进一步观察到，尽管较少的基向量不足以保持良好的视觉保真度，但个别基向量在其几何影响方面差别很大。我们使用$m_{i}=max_{j}|C_{ij}|$表示每个基的最大绝对贡献，发现$m_{i}$可以在整个基上以数量级变化（图5）。我们通过用较少的位表示对几何影响较小的基向量来实现进一步压缩。
我们用{$m_{i}$}重新缩放布料基，得到$B'=BM$和$C=M^{-1}C$，其中$M=diag(m_{1},...,m_{b})$。缩放$B'$可以解释为长度单位最大顶点位移，现在可以进行量化。我们发现在视觉效果变得明显之前，最可能的量化是300微米的量子。在这个容错下，使用16位比特和8位比特可以很容易地表示基向量。就我们的便装demo场景而言（第5节），使用8位比特可以表示82％的基本矢量。生成的压缩基础只需要22MB的存储空间。 对轨迹系数也执行类似量化为16位比特。这种使用两位宽度的简单压缩方案实现了高压缩，同时在运行时能够高效地对矩阵$C'$中的轨迹数据进行解码。

5 结果

为了评估我们的方法，我们通过由HDM05动作捕捉数据集构建的运动图对角色进行动画制作，从而对布料进行了大规模的探索[Mülleret等人 2007]。我们的主运动图包含12个独特的动作剪辑（总计3115帧）。我们选择了包括跑步，投掷，踢球，跳跃和执行车轮在内的各种有力动作的剪辑，以引发高度动态的布料动作，并将服装引入各种配置。从这张主图中，我们为两个布料配置设置生成了辅助运动图：长袍，单件连帽长袍和便装，其中包括三件衣服（包括宽松的裤子和宽松的背心）。我们使用高质量的离线布料模拟器ARCSim1来计算布料运动[Narai等人 2012; Wang等人2011]。为了适应我们的压缩方案，我们禁用自适应重新网格划分并使用固定的网格拓扑。平均来说，我们两个演示的离线帧模拟时间分别为165秒和243秒。虽然这两个演示都具有类似分辨率的服装，但便装中多个布层之间的复杂碰撞处理会导致较长的执行时间。

5.1 大规模探索

使用超过6,400个CPU小时计算（在英特尔提供的一组机器上），我们生成了超过99,000帧长袍布料动画（大约55分钟的模拟动作，可以直接在图2和图6看到），和27,000帧便装动画（15分钟）。 两个辅助图都比角色运动图大了将近一个数量级。 为了简洁起见，我们将重点放在本节的长袍探索中的发现，读者可以转到随附的视频中查看便装的结果。
简而言之，我们发现我们的大量计算已经充分地将布料动力学的相位空间采样为拥有良好的视觉容错。我们能够为主图的任意遍历生成令人愉快的布料动画。 正如随附的视频所显示的那样，即使在剧烈的角色动作（例如侧手翻（图1））之后，通过辅助图也能产生高度细致平滑的布料运动，使布料明显不同于其起始状态。
尽管我们的最终辅助图确实变现了高质量的运动，但在探索的早期阶段，情况并非如此。紧随着图形初始化，辅助图对于每个主要角色姿态仅包含一个布料姿态，类似于布料运动的动作学近似。正如预期的那样，这种近似不足以为我们的服装产生逼真的动作，从而证实辅助布料图必须比主图更加复杂。在这些早期阶段，当布料从复杂结构转变回接近初始起始状态的配置时，可以清楚地看到大的误差。
进一步的探索逐渐消除了令人震惊的动作误差，更重要的是，揭示了辅助运动空间中的有趣结构，如分枝。虽然我们最初的长袍配置的特点是头罩罩住了角色的头部，但我们发现一些动作序列（例如走路→跳跃→走路，或走路→慢跑→走后→右跑）导致头罩落下。图6显示了根据头罩状态进行着色的完整长袍辅助图。（红色表示头罩保留在角色的头部，而蓝色表示头罩已经掉落。）我们的探索发现五个独特的角色动作序列，导致头罩落下。然后它并行探索相位空间的这些不同区域。当第一次遇到分枝时，头罩落下的次数很少。因此，末端的合并往往会形成将头罩从下往上掉的过渡（没有类似的头罩摘下合并的姿势）。但是，我们的误差（将机器状态分类）会以高误差标记这些不合理的过渡，因此系统会立即将计算资源用于探索图形的这些部分。一旦辅助图达到99,000帧尺寸，就不存在从头罩落下到头罩戴着状态的合并转换。该图基于头罩状态大致分为两个子图。连接这些子图的边缘全都对应于正确的模拟动作，其中头罩在翻转时自然落下或罩在角色的头部上。
图7绘制了辅助图中最劣过渡的$L_{∞}$误差（从包含顶点位置和时间标度速度的向量）的演变。在粗尺度下，当我们详细探索相位空间时，图中的误差会减小。然而，误差有重要的细微差异，我们归因于两个原因。首先，一个简单的距离度量可能是相位空间未来误差的一个不好的预测器。 （改进误差度量以考虑未来可能出现的误差，以便早期发现高误差区域，这是未来工作的一个重要领域。）其次，探索揭示了需要进一步采样的空间新部分（例如，头罩落下）将最大误差降低到先前的水平。
我们选择了长袍的例子，因为它包含大量的流动区域，它们具有相对较高的滞后性。这种行为会为每个主状态产生很多辅助状态，但是我们最终会得到合理大小的压缩数据库。便装示例的滞后性较差，因此需要较少的预计算并生成较小的压缩数据库。

5.2 交互式播放

我们可以在Apple MacBook Pro笔记本电脑（Core i7 CPU）上以每秒70帧以上的速度从压缩的辅助图播放布料动画。使用一个简单的基于CPU的实现（使用OpenMP进行并行化），可以执行解压缩以及计算矩阵向量乘积以合成每个布料相位姿态（可以使用定点算法执行）。

6 讨论

在这项工作中，我们利用大量计算资源将数据驱动的动画推向前所未有的规模。尽管之前的数据驱动方法仅限于简单的受控设置，但我们使用了数千小时的CPU时间来彻底探索辅助布料运动的巨大相位空间。我们相信我们大规模探索的结果是惊人的。我们不仅捕捉到丰富的具有足够密度的布料细节，消除了广泛的人物动作的回放伪影，还能够发现相位空间中的分枝并继续在每个不同区域中对布样动态进行采样。我们演示中的衣服不会简单地返回到单独的休息状态：头罩落下，衣服以各种方式环绕角色。
许多技术对于进行大规模的探测和随后的实时播放都是必要的。最重要的是，我们引入了辅助运动图的概念来指导阶段空间探索过程，并实现对运行时用户输入的高效响应。分析布料基减少导出一个简单的自适应量化方案，进一步压缩数据集。我们还创建了一个布匹相似度函数，专门考虑了长袍头罩的位置，以强有力地识别最严重的辅助图转换误差。总之，我们的系统生成了超过43GB的布料数据，将这些数据压缩为34MB和66MB大小的辅助布料图，并在70多个笔记本电脑上响应用户输入提供了高质量的辅助布料动画FPS。
关于数据驱动技术的可行性的一个常见问题集中在运行时内存占用。虽然我们的大约70MB的要求对于以现代控制台系统为目标的游戏来说可能太大了（例如，Xbox360只有512MB的RAM），但我们认为它的成本在当今现代PC（和即将到来的次时代游戏机），它们目前拥有多GB的内存。 此外，我们还没有完全探索布料基或辅助图压缩策略的各个方面，所以更好的压缩以及运行时解决方案都会使辅助图的区域流（仅留下基本表示形式）变得很有可能。
我们对辅助运动图表示的许多潜在好处感到兴奋。例如，在创作游戏的情况下，能查看布料运动的整个数据库可能是一个显着的优势。作为游戏制作检查的常规任务的一部分，预先计算的辅助布料动画云可以被手动查看，标记为重新模拟，甚至编辑。可以识别不良的辅助图形转换，而将人体组件添加到当前的工作则完全只需程序性的姿态相似性度量。这项检查工作的结果将是高质量的，计算代价低廉的交互式服装，这种服装已知不存在令人反感的人为因素。
更一般地说，尽管将图形探索视为预计算是很自然的事情，但我们认为相空间采样是一个正在进行的过程，其改进结果可以不断被压缩并提供给交互系统。因此，相位空间探索不仅需要像数据驱动方法那样进行交互式回放，还可能由它触发并影响它自身。未来的在线虚拟世界可以在发现新行为时为客户提供新的辅助图。相反，玩家在虚拟环境中的行为可以指示相位空间中最重要的样本区域。我们相信通过大规模计算来增加互动环境有许多令人兴奋的可能性。