我们提出了一种数据驱动的方法，以在诸如游戏等交互式应用程序中实现高质量的细腻头发动画。通过设计评估头发动态相似性的误差度量方法，我们尽可能考虑头发特征。我们还提出了一种基于二次动作图（SMG）的新型数据库构造算法。

我们的算法可以提高这些图形的效率，减少冗余数据，并且在考虑将来动作的同时实现两个可视化剪辑的视觉平滑连接。使用我们的SMG的运行过程的成本相对较低，允许实时交互操作。
关键字：数据驱动，交互式应用，头发动画，游戏角色，次级动作图

1 介绍

数十年前，在视频游戏等交互式应用程序中，角色的头发通常被表示为具有α映射的三维曲面（例如NURBS），这看起来非常不自然。 头发之间摩擦，碰撞和静电力非常复杂，头发的粗糙表面或小而不规则的半径[1]特征使得真实的头发模拟成为一项非常艰巨的任务。 而且，游戏中有限的资源使得当时的头发动画几乎无法表现出来。
提出了许多方法来解决这个问题，如圆柱体或带状结构[2]。
这些方法可以加快线头发模拟的计算时间并获得更好的结果。 然而，由此产生的动作仍然过于粗糙并且不令人满意。 为了达到视觉上令人满意的效果，独立模拟每条链的方法[3，4]是目前的主要趋势。 这些方法的成本非常高，因此实时交互式应用程序非常耗时。
在本文中，我们提出了一种数据驱动的方法来在交互式应用程序（如游戏）中近似详细的头发动画（如图1所示）。 仅考虑游戏人物的特定特征，只需要操作有限的动作（走路，左转，右转，跳跃等），我们可以说实际出现的动画是可以预测的。 使用数据驱动和子空间技术[5,6,7]，提前构建一个包含头发动画片段的数据库，以非常低的成本使用这种预先计算的数据库加速运行时过程。
这种方法的一些具体问题包括：如果细节被寻找，数据库的大小往往会很大，并且惯性力等连续动作的影响不能被忽略，以避免视觉上的不兼容。为了解决这些问题，我们提出了一种基于次级活动图的新型数据库构建算法。我们的算法可以提高这些图形的效率以减少冗余数据，并且在考虑到它们的未来动作的同时实现两个动画片段的视觉平滑连接。

2 相关工作

目前，尽管电子游戏图形的质量很高，但为了解决头发模拟的高成本问题，提出了各种方法。最常用的方法是将几根线作为引导线，并对其余部分进行插值，如[8]所示。柴等。提出了一种简化的头发模型方法[9]，通过从训练数据中选择有效的引导头发和插值权重来加速运行时间模拟。但是，由此产生的速度在引导头发的数量和模拟方法上是不同的。此外，模拟的运行时成本对于游戏等应用来说仍然过高。我们的方法与Chai等人的方法不同，我们主要关注于降低计算成本并且在运行时过程中不依赖模拟器。
Han等人提出的其他方法，如GPU上的并行计算。 [10]加快模拟时间。然而，并行计算方法和插值方法都不能很好地处理头发碰撞，这在动画头发的外观中起着非常重要的作用。
数据驱动和子空间方法被用于许多地方，以解决运行时计算成本问题（例如流体[11]，变形[12]）。 数据驱动方法的主要概念是建立一个数据库来支持实时计算。 James和 Fatahalian [5]提出了一种方法来处理交互式应用的可预测动作。 脉冲响应函数（IRF）和脉冲调色板可以表示特定的动作序列，通过组合多个动作并回顾所选动作的预计算数据，可以实现交互式的实现和复杂的变形。 但是，这种方法主要针对单瞬时脉冲的动作，并且不能实现复杂的动作。 从一种冲动转换到另一种冲动也缺乏准确性，并且不能很好地证明先前行动留下的惯性。
Guan等人[6]提出了一种方法，通过使用多线性代数将头发参数（长度，柔软度等）从学习数据库中分解出头发外观。该方法可以在调整头发参数的同时实时实现头发动画。然而，与James等人的方法一样，Guan等人的方法并不重视动作之间的惯性力。
Kim等人[7]将IRF与动作图结合在一起（在第3.1节中解释），作为James处理复杂动作序列的实时布阵方法的扩展。布料沿着身体的动作存储在次动作图（SMG）中，其中每个节点对应于人体的动画片段。通过从最大布料状态的连接错误发生的位置扩大图形，可以在一定程度上保留先前动作留下的惯性效果。这种方法可以实现比[5]中James的方法更复杂的动作，并且在交互式应用中实现令人满意的布料动画。
Kim等人的方法是有希望的，但是考虑到非常大的数据库，构建的数据库的质量变得重要。Stanton等人。在[13]中将Kim等人的方法应用于流体。通过检测玩家往往采取的最常见的行为，Stanton等人的方法着重于如何提高含有重要数据的构建的SMG的效率。
考虑到头发也是角色身体上的附属物，Kim等人的方法为交互式应用中如何处理头发动画提供了新的思路。但是，头发的特殊性使得直接应用这种方法变得困难。因此，我们试图找到一种方法来提高数据库的质量（基于SMG）。

3 动作图和二次动作图

在本节中，我们将动作图形描述为输入，将次动作图形描述为我们的输出。 我们还简要描述了我们方法中使用的脉冲响应函数。

3.1 动作图

在我们的方法中，使用主动作图（MG）作为输入。 它可以通过像[14]这样的方法构建，其动作可以通过Blender或Maya等软件工具手动调整。 角色的身体动作序列包含在该图中（图2）。 每个节点代表由许多身体姿势构成的特定动作（行走，跳跃等）。 转换限制被添加为图形的边。 我们在这里从MG获取的信息是头部沿着身体的动作。

3.2 次级动作图

次级动作图（SMG）是存储与动作图节点相对应的头发动作数据的图形。 用户想要采取的下一个动作通常是未知和不可预测的。 尽管不必考虑身体动作的惯性或碰撞力，但如果以与身体相同的方式处理头发的动画，由于缺乏这些力的效果，它们将变得非常不自然。
为了表现自然附着于身体的其他部位，我们需要构建SMG（参见图3）以存储这些部分的相应头发动作。 SMG节点包含，

1. 对应的MG节点ID（MGID），
2. 具有与其动作图节点相同数量的帧的动作序列数据（IRF）
3. 父节点的ID（与之相对应的前一个动作，即从它哪里转换而来），
4. 子节点的ID。

构建的SMG包含比原始动作图更多的节点。这意味着，身体的动作可能对应于几个不同的头发动作节点，这取决于之前采取的动作。 特别是在游戏中，当没有给出命令时，放松状态（例如空闲动作）被认为是默认状态。相比于其他，这种放松的动作可能与多的SMG节点有关联。
一个转换是两个SMG节点之间的定向链路。 两个动作序列从转换的开始到结束SMG节点连接。 请注意，一个转换和一个反向的转换可能有完全不同的动作顺序。还有从节点到同一节点的自循环转换。

3.3 动作序列的表示

每个SMG节点中的动作序列数据存储在类似于IRF（脉冲响应函数）数据库[5]的结构中。 构建一个包含整个动作序列数据的矩阵。矩阵的行是帧，列是预先定位的发丝的顶点坐标。对于这样的矩阵，可以使用奇异值分解来进行压缩。然后将压缩的动作序列表示为一组基向量，其维数远小于帧。

4 构建头发的次级动作图

当用户给出命令时，为了获得平滑和自然的头发动画效果，我们必须沿着主动作图构建次级动作图（SMG）。此外，为了表示先前动作传递的细节惯性力，我们需要将SMG扩展到满意的水平以包含所需的细节。例如，如果角色从空闲状态开始，则进行步行动作并再次返回到空闲状态，由于惯性力，后面空闲状态的头发动作将与起始动作不同。图中还将存储两个与同一MG节点（空闲）相关的SMG节点。
我们需要注意的是如何选择和保存所需的重要动作片段，以使图形更加充分（即包含更重要的数据，同时尺寸更小）。

4.1 头发的形状直方图

为了选择足够的动作数据，我们必须找到彼此接近的动作。详细的头发模型包含数千条单独运动的发丝。一次剧烈的动作可能导致不同的发丝彼此交替，这使得发丝顶点之间的距离与其他状态相差非常大，但是头发的形状似乎是相似的（如图5所示）。
偏差值度量方法Kim等人在[7]中使用的只是顶点之间的L0或L1欧几里德距离。对于头发，这种方法无法正确识别相似的状态或动作。考虑到顶点的数量要比布料多得多，并且少量偏差不应该影响整个外观，所以需要一种评估两种头发动作相似性的好方法。
在这里，我们介绍形状直方图（类似于[15]），如图4a所示，以评估头发状态之间的相似性。首先，当构建IRF时，通过将头部动作的逆（从MG已知）相乘，头发状态全部局限于中心。局部头发模型周围的空间被分成许多网格，并且每个网格中的顶点数被计算为每个直条中的直方图值。两个头发状态的直方图中的非零直条被用作计算偏差值的有效直条（如图4c所示）。
两个直条的直方图之间的绝对差的平均值被用作两个当前头发状态之间的偏差值。为了评估整个序列，我们还使用每个帧的偏差值的平均值作为SMG的两个节点a，b的合并误差ε（a，b）
ε（A，B）=
Haj（i）-Hj（i），（1）
1N 1nj
N nj
j = 1 i = 1
b
其中N是帧的数量，nj是帧j的有效直条的数量，Haj（i）是
节点a，第i直条，第j帧的直方图值。 请注意，对于SMG中的一对节点，N是一个常数值，但nj可能会每帧都会改变。
所计算的合并偏差值用于确定当前两个动作是否足够相似以便合并，或者将从哪个节点开始应用下一个扩展，这将在稍后的小节中进行描述。

4.2. 为头发构建SMG

与Kim等人的方法[7]不同，它只考虑当一个动作发生切换时的即时状态偏差值，我们想要考虑未来动作的整个序列。 为了考虑这样一个未来的动作序列，我们在这里提出了一种新的构造算法，以便能够建立两个动作序列之间更加平滑的连接。 构建SMG的过程包括以下步骤：1.初始化，2.扩展，3.合并（和扩展）以及4.添加响应序列节点。 我们将逐步描述我们的算法。 在附录A中，我们还展示了我们完整算法的伪代码。
为了帮助理解我们的算法，我们将使用图2中的MG作为示例。 在该图中有五个节点（待机，行走，左转，右转和跳跃）以及18个转换，包括自循环（橙色允许，例如待机到待机）。
初始化.首先，选择起始节点（例如待机），并且MG中的所有转换以广度优先的方式遍历以构建如图6a所示的SMG的初始树。 在此树中，相同颜色的节点具有相同的MG节点标识（MGID）。
该树中包含两种节点。 一个是正式的SMG节点，另一个是所谓的鬼节点。正式的SMG节点是在实时过程中实际使用的节点。 相比之下，鬼节点是SMG的潜在节点。 它们被存储来确定SMG的准确性是否足够，同时是否需要添加为正式SMG节点。 引入鬼节点是我们算法的关键，因为它们被认为是可以实际采用的未来动作的候选对象。
在初始树结构中，MG节点模拟得到的结果里，我们将初次访问到的设置为SMG节点，而已经被计算过的设置为鬼节点。
扩张.接下来，我们应用来自鬼节点的图形扩展，以减少两个动作序列之间的偏差值。对于每个鬼节点g，使用等式（1）计算满足以下三个准则的节点的偏差值：

1. 来自同一转换的节点，同时有相同的MGID。
2. 祖先节点有相同MGID。
3. 两节点具有相同MGID，且没有节点满足条件1和2。

然后，我们在上面计算出的偏差值之间选择最小误差εmin（这里称之为合并误差），而对应的节点h（这里称为合并节点）则是g最相似的动作。如图7所示，对于一个鬼节点No.6，No.4（来自条件1）和No.0（来自条件2）被选为候选者，而No.4最终作为合并偏差值节点。
我们现在处理扩展步骤如下：我们首先准备一个堆E，并为每个鬼节点存储一个三元组（g，h，εmin）。然后，我们使用delete-max操作从E中取出具有最大键值的鬼节点，并将其设置为正式的SMG节点。然后，我们遍历新的SMG节点的转换，创建鬼点，计算合并偏差值并将它们存储到E.重复此过程直到最大键值小于阈值λ。图7显示了扩展过程的工作原理。
合并（+扩展）.* 扩展过程完成后，堆中所有键值的合并偏差值应小于阈值λ。 接下来，我们合并每对偏差值εmin的两个节点g和h以减小SMG的尺寸。两个要合并的节点具有相似的动作。
为了执行合并操作，我们继续使用在扩展过程中创建的堆E. 对于堆中的每个鬼节点g，如果待合并节点h是正式的SMG节点，则进行合并。也就是说，g被丢弃并且其父节点的转换指向h。 如果h是鬼节点，则不能应用合并操作，因为两个节点都是鬼节点。 在这种情况下，我们首先将h设置为正式的SMG节点，并将扩展操作应用于新的SMG节点。 然后，我们将合并操作应用于上述的g。
当这个过程完成时，剩下的鬼节点全部被丢弃。 图8显示了合并操作完成后的SMG。
添加响应序列节点. 在扩展步骤中，使用阈值。用户给出的这个阈值将直接决定图形的大小。较大的值会导致更详细的动作丢失，而较小的值会导致图形过于庞大。为了将图形缩小到合理的大小并同时获得平滑的结果，我们考虑引入IRF的思想[5]，并保留最容易注意的细节。例如，MG节点“待机”是角色最常见的状态，动作保留了最多的SMG节点，并添加了额外的细节以扩展这些动作。
如图9所示，我们在图中添加了一个更长的循环“待机”动作序列作为响应序列节点（RS节点）。 RS节点与SMG节点有如下不同：1.节点长度，2.与其他节点的关系，3.它们如何显示。
这里，1.指向自循环节点的“待机”，2.指向“待机”节点，3.是自循环节点的SMG节点将考虑进行合并。然后，我们将每个节点合并到相应的RS节点中的适当位置。这个位置是最相似的动作序列结束的地方，所以节点可以转向具有较少不兼容性的响应序列。
为了在相应的RS节点中确定适当的位置，我们准备了一个矩阵形式的偏差值（偏差值矩阵），如图10所示。在该图中，行表示RS节点的帧，列表示合并后SMG节点的帧。 然后，将RS节点和SMG节点中的每个帧之间的不相似性存储为矩阵的每个元素中的灰度颜色，其中较亮的颜色具有较大的形状直方图误差，如等式（1）中所述。
在误差矩阵中，要选择的动作序列表示为右下行（图10中的红线）。 在这些行中，我们选择一条线上形状直方图误差最小的方差。 这确保了两个动作以类似的方式移动，并且通常也具有小的错误。 上述方法的一个优点是与阈值无关，即，在不使用阈值的情况下确定RS节点中的适当位置。

5 运行时过程

在构建SMG之后，我们将其用作支持运行时过程的数据库。由于SMG基于动作图，因此只能显示图中包含的动作。当头部位置发生变化时，我们通过基础向量和权重的线性组合来计算当前SMG节点及其当前帧中头发的顶点坐标。包含在IRF中的头发动作数据不包括位移信息，并且仅包含局部坐标中头发的变形数据。随着头发与头皮（或头部）一起移动，我们只需要将头发模型与头部关节位移信息一起转移。
我们现在设置一个关于从当前节点到下一个节点的变化的动作图的约束：尽管在移动过程中用户给出了一个动作命令，但角色继续移动直到它到达可切换点（当前节点的结尾） 。然后，正在执行的动作发生变化，字符从当前节点移动到下一个节点（请参见图11中的运行时进程）。
同时，SMG中的头发节点将根据下一个动作的ID切换到子节点。当转换约束被添加到动作图中时，不会发生非法切换，并且相应的节点也不会在子节点列表中。
由于SMG是无限循环图，MG中的交换机总是可以找到相应的SMG节点。然而，如果响应序列节点存在，当动作切换到空闲状态并保持循环（当SMG节点切换到响应序列节点时），则选择节点并且动画将从开始帧开始，其中前一个SMG节点是指点。因为合并SMG之前的响应节点的子节点已经合并到空闲节点，所以下一个动作的响应节点和节点之间的错误可以被忽略。

5.1 连接惩罚

由于我们使用鬼节点而不是即时状态错误，因此从一个节点切换到另一个节点时发生的失真大于Kim等人的方法[7]。然而，通过混合两个节点，即使它们的开始和结束状态完全不同，我们也可以实现从一个节点到另一个节点的转移，而在几个帧内没有不明显的误差。
我们只是使用线性混合来连接两个节点。随着动作图节点继续其结束，误差必须发生在第一个节点的末尾和下一个节点的开始之间。我们将前一个节点的结束状态保存为转换时发生的惩罚，作为这两个节点的顶点位置之间的距离，并将该惩罚加回到下一帧的开始序列（对于某个混合长度），如图12.注意混合长度必须小于节点长度，所以惩罚不会传递到下一个动作。

6 结果和讨论

在我们的实验中，使用18个转换的CMU动作捕捉数据库[16]中包含待机，行走，左转，右转和跳跃的五个动作捕捉动作用于主动图。我们使用包含4134个指甲毛发和41340个顶点的头发模型，并将Maya的nHair系统作为黑箱模拟器来计算头发动作。计算头发碰撞和头发皱纹，但没进行头发身体碰撞。
对于合理的阈值5.5，模拟10662帧有效动作序列（约5.1GB）。根据这些原始数据，最终的SMG中包含2220帧动作序列（SVD后约460MB）。表1显示了构建具有多个阈值的SMG组的统计结果。随着阈值的增加，图形尺寸变小（阈值为6.5时为1576帧，阈值为8.0时为1251帧），但我们仍然可以通过添加RS节点获得视觉上满意的结果。与Kim等人的方法相比，我们的图的大小在阈值降低时更有效地增加，并且可以获得具有相同图形尺寸的更自然的结果，因为由惯性力（或未来误差）会被考虑在内（请参阅附件中的视频）。使用我们的方法，图中包含的冗余数据较少。
在运行过程中，我们使用AMD的TressFX头发系统作为渲染器。在CPU使用率低于20％，内存使用量约为512MB的情况下，可以达到超过100 fps（CPU Intel Core i7-4770和GPU NVIDIA GeForce GTX TITAN），而无需任何GPU加速或并行计算。
局限性.由于SVD矩阵的列/行速率很大，所以数据压缩比不能满足要求。要获得详细的头发动画，我们必须使用大量的头发顶点。虽然在运行时流程中，渲染时间得以节省，但内存成本是不可避免的。对于交互式应用，单链插值可以结合使用以实现低内存成本。可以应用Chai等人 [9]减少头发的方法，以获得每个IRF的最具代表性的引导毛发（只要每个IRF的引导发股的数量是相同的），并通过内插恢复详细的结果。

7 结论

我们提出了一种新颖的数据驱动方法，可以为游戏等实时应用程序实现详细的头发动画，在运行时过程中计算成本非常低。顶点对之间的L0或L1误差度量对于头发来说是无意义的，因为详细的头发动画需要大量头发，并且即使头发的总体形状非常相似，每个线的误差也可能非常大。
我们提出一种使用头发形状图来识别重要（有意义）的数据的方法。通过存储最重要的数据，我们可以构造一个冗余较少的辅助动作图。如果考虑顶点对之间的关系，阈值会有很大的变化，但是，通过使用我们的形状直方图的误差准则，我们可以获得一个比较稳定的阈值，当发丝数或主动作图的数量发生变化时，这个阈值会略有变化。
由于在从一个节点切换到另一个节点时使用了混合，所以连接偏差值对头发动画来说不如布料重要。考虑到总序列误差而不是即时连接误差，由于考虑到惯性力，我们可以在动作之间切换时获得更自然的结果。