针对头发动画化的弹力和碰撞的高效稳定方案

摘要

一种用于动画化头发的示例性处理包括接收表示动画帧的一个时间步长中的多根头发和多个对象的数据。根据接收的数据，第一树被产生来表示多个对象的运动对象而且树被产生来表示多个对象的动态对象。根据接收的数据，第一弹力预条件算子被创建来表示多根头发的内部弹性能量。根据第一树和第二树，所述多根头发的两根或更多头发之间的或者所述多根头发的一根或更多头发与多个对象的一个或更多对象之间的第一组潜在接触被确定。根据第一组潜在接触和第一弹力预条件算子确定多根头发的位置。

说明书

技术领域

本发明总体涉及计算机动画，更具体地涉及使得计算机生成动画中的头发动画化。

背景技术

计算机生成动画中的改进已经使得动画电影能够绘制出具有极强逼真度的角色和对象。例如，服装、头发、面部表情、场景背景等变得越来越复杂，使得动画电影具有惊人的视觉效果。在这些各种动画场景元素中，由于动画角色上通常出现的头发数量的巨大、头发执行的复杂动作以及施加至各根头发上的大量内外力，而使得头发尤其难动画化。

虽然已经开发了处理来动画化头发，但是现有处理可能在计算上很复杂而且可能产生不精确的结果。

发明内容

描述了用于动画化头发的处理。一个示例处理可包括：接收表示动画帧的一个时间步长中的多根头发和多个对象的数据；根据接收的数据来生成第一树以表示多个对象的运动对象；根据接收的数据来生成第二树以表示多个对象的动态对象；根据接收的数据来创建表示多根头发的内部弹性能量的第一弹力预条件算子；根据第一树和第二树，确定所述多根头发的两根或更多头发之间的或者所述多根头发的一根或更多头发与多个对象的一个或更多对象之间的第一组潜在接触；以及根据确定的第一组潜在接触和第一弹力预条件算子来确定多根头发的位置。

在一个示例中，根据确定的第一组潜在接触和第一弹力预条件算子来确定多根头发的位置可包括迭代执行：利用第一弹力预条件算子来执行投影高斯-赛德尔算法以确定针对第一组潜在接触的法向力和摩擦力的大小；利用所确定的针对第一组潜在接触的法向力和摩擦力的大小来执行Cholesky回代以确定多根头发的位置；以及对于第一次迭代之后的迭代，检测所述多根头发的两根或更多头发之间的或所述多根头发的一根或更多头发与所述多个对象的一个或更多对象之间的持续碰撞接触。

在另一示例中，接收的数据可定义多个对象的运动、多根头发的形状以及多根头发对内外力的响应。

在另一示例中，接收的数据可包括：能够与多根头发碰撞的一个或多个碰撞体的运动序列；多根头发的静止柱；多根头发的目标柱的运动序列；以及对多根头发建模的多个约束。

在另一示例中，多根头发可被建模为离散弹性杆，其中多个约束表示离散弹性杆之间的吸引力。

在另一示例中，第一树和第二树每个都包括轴对齐限界盒树。

在另一示例中，该处理可进一步包括：根据确定的多根头发的位置更新表示动态对象的第二树；根据接收的数据和确定的多根头发的位置创建表示多根头发的内部弹性能量的第二弹力预条件算子；根据第一树和更新的第二树，确定所述多根头发的两根或更多头发之间的或所述多根头发的一根或更多头发与所述多个对象的一个或更多对象之间的第二组潜在接触；以及根据确定的第二组潜在接触和第二弹力预条件算子来确定多根头发的新位置。

在另一示例中，根据确定的第二组潜在接触和第二弹力预条件算子来确定多根头发的新位置包括迭代执行：利用第二弹力预条件算子来执行投影高斯-赛德尔算法以确定针对第二组潜在接触的法向力和摩擦力的大小；利用确定的针对第二组潜在接触的法向力和摩擦力的大小来执行Cholesky回代以确定多根头发的位置；以及对于第一次迭代之后的迭代，检测所述多根头发的两根或更多头发之间的或所述多根头发的一根或更多头发与所述多个对象的一个或更多对象之间的持续碰撞接触。

在另一示例中，创建第一弹力预条件算子可包括对表示多根头发的内部弹性能量的第一矩阵执行Cholesky因数分解，而且其中创建第二弹力预条件算子可包括对表示多根头发的内部弹性能量的第二矩阵执行Cholesky因数分解。

还描述了用于动画化头发的系统和计算机可读存储介质。

附图说明

通过结合附图参考后续说明能够最好地理解本申请，其中相同数字可引用相同部分。

图1图示出可利用根据各种示例的头发动画化处理产生的示例渲染图像。

图2图示出用于动画头发的变量的示例视觉表示。

图3图示出示例图形，其显示出针对参考情况和此处描述的头发模型的弯力和转角的变化。

图4图示出根据各种示例的用于动画化头发的示例处理。

图5图示出根据各种示例的用于调度任务的并行处理的示例处理。

图6-8图示出采用图5的处理进行任务的并行调度的视觉表示。

图9图示出示例图形，其显示出利用图4的处理产生的示例输出与已知解析解法的比较。

图10图示出示例计算系统。

具体实施方式

提供下面的描述以使得本领域普通技术人员能够做出及实现各种实施例。具体装置、技术和应用的描述仅仅被提供作为示例。本领域普通技术人员很容易想到对此处描述的示例的各种修改，而且此处定义的总原理可适用于其它示例和应用，而不脱离本技术的精神和范围。因此，公开的技术并不限于此处描述和表示的示例，而是与权利要求一致的相应范围。

下文描述了各种实施例，涉及用于结合碰撞响应、摩擦和用户定义约束来对头发弹力进行建模和动画化的处理。在一个示例处理中，将被动画化的头发可利用允许伸缩、弯曲及扭曲但是不能剪切的离散弹性杆来建模。可利用Cholesky因数分解产生弹力预条件算子的组合弹力和碰撞求解器、检测可能的碰撞、并且迭代地执行预处理的投影高斯赛德尔(Preconditioned Projected Gauss-Seidel，PPGS)算法以确定所有潜在接触的法向和摩擦力的大小，产生每帧的头发输出。PPGS算法可被用来实现具有高顶点数的头发的有效处理，同时保持投影迭代求解器实现具有高接触和约束数的处理的优势。该处理没有在针对弹力进行求解以及针对碰撞/摩擦进行求解之间变换。相反，在每个时间步长下，适当的法向和摩擦力可通过利用非穿透性和摩擦约束导致的内部动态及单边约束所确定的目标函数求解二次规划问题来确定。对内部动态和碰撞的处置的紧密结合去除了视觉不精确性的一个可能源头，因为没有必要限制仿真期间的应变率。

素材曲率可被线性化以确保弹性能量Hessian对于离散弹性杆的任意配置是聚集且半正定的。这可提高了处理效率，因为这确保了线性系统的矩阵对于任意时间步长是聚集且对称正定的，导致物理上更加精确的弯曲响应以及运动学扭曲模型的退化的消除。该能量Hessian对于所有杆配置是非负定的，而且Hessian项的数量显著地少于现有技术。而且，该处理包括针对诸如伸缩、弯曲和扭曲之类的所有类型的变形的减振力。时间积分器可被均匀地应用至伸缩、弯曲和扭曲，而且可针对长时间步长保持稳健性。

1.概览

图1描绘了可利用根据各种示例的头发动画化处理渲染的示例的计算机生成图像100。注意，图1描绘了覆盖有各种长度的头发的狮子的图像。为了以视觉逼真的方式动画化头发，每根头发可由对施加了内外力时头发的弯曲和扭曲进行仿真的头发模型表示。如上所述，头发动画化的处理可能由于动画化角色上通常有的头发的数量巨大、头发执行的复杂动作、以及施加至每根头发的大量内外力而在计算上很昂贵。

2.头发模型

各个发缕可被建模为与Bergou等人的“Discrete Elastic Rods”SIGGRAPH(ACM Transactions on Graphics),27,3(2008年8月)以及Bergou等人的“Discrete Viscous Threads”SIGGRAPH(ACM Transactionson Graphics),29,4(2010年7月)中描述的那些类似的离散弹性杆，但是会有一些变化。具体地，可允许杆伸缩、弯曲及扭曲但是不能剪切。因此，连续模型可以是对Kirchhoff，G的“Ueber das Gleichgewicht unddie Bewegung eines unendlich dunnen elastichen Stabes”Journal fur diereine und angewandte Mathematik,56(1859)中描述的可伸缩杆的概括。在几何上，光滑弹性杆可被表示为适应帧化曲线，其具有中心线和素材帧其中s是沿中心线的坐标。

头发的动作可以就来自未变形的(例如，无应力)配置的形状中的变化、变形形状x(s，t)的当前时间t下的dα(s，t)进行理解。

a.离散化

杆的中心线可被离散化为具有位置[x₀；x₁；：：：；x_n；x_n+1]的一系列的n+2个顶点。具有素材指示符的正交帧可对应于每个边缘该帧可被调整成离散化的中心线(例如，包括标准正交帧的单位矢量之一可对齐至中心线的切线)：

$>d_2=t^j\stackrel{\mathrm{def}}{=}\frac{e^j}{\left|e^j\right|},---\left(1\right)$>

其中|e^j|是边缘长度。

由于素材帧可正交并且适应于离散化的中心线，其遵循的是素材帧在边缘处的时间演化可由刚好一个标量τ^j表示，该标量是描述了第一素材指示符的定向上的增量变化的角度；相对于仿真步骤的起始时它的定向，t₀≤t≤t₀+h。描述了头发配置的广义坐标的矢量则是：

在一些示例中，简洁起见，可不使用参考指示符以及素材指示符。

b.力

杆的基尔霍夫理论将弹性能量分配给从中导出内部弹力的适应帧化曲线。总弹性能量可包括与伸缩、弯曲和扭曲相对应的三项：

E＝E_s+E_b+E_t.   (2)

这些能量函数中的每个都可按照测量局部变形(例如，张力)的标量函数进行定义。Bergou等人的“Discrete Viscous Threads”SIGGRAPH(ACM Transactions on Graphics),29,4(2010年7月)中描述了伸缩力的导出。弯曲和扭曲力将在下文详细描述。

c.弯曲和扭曲力

离散曲率和离散曲率次法线矢量–对于内部示例i，离散曲率可被定义为两个连续边缘之间的转角Φ_i：

$>{\Phi }_i\stackrel{\mathrm{def}}{=}\mathrm{angle}(e^{i-1},e^i),1\le i\le n.---\left(3\right)$>

这就导出针对离散曲率次法线的下述表达：

$>{\left(\mathrm{\Phi b}\right)}_i={\Phi }_i\frac{t^{i-1}\times t^i}{|t^{i-1}\times t^i|}.---\left(4\right)$>

针对离散曲率的这一选择确保了对于圆形弹性杆，对于所有n≥3，弯曲能量在连续情况和离散情况下是一样的。

离散素材曲率–在试图定义内部顶点处的离散素材曲率时，离散曲率ki可以是顶点定义的量，其中素材指示符可被定义在相邻边缘处。相邻边缘的参考帧的简单求平均，如Bergou等人的“Discrete Viscous Threads”SIGGRAPH(ACM Transactions onGraphics),29,4(2010年7月)中那样，在更高的弯曲和扭曲角度下变得越来越不精确，而且如果接合处上参考帧中存在180度的扭曲还会恶化。为了解决这一内插，素材指示符可替换地定义在顶点处。内插正切矢量可首先被定义为：

$>{\tilde{t}}_i\stackrel{\mathrm{def}}{=}\frac{x_{i+1}-x_{i-1}}{|x_{i+1}-x_{i-1}|}.---\left(5\right)$>

可通过利用相等权值对并行传递的边缘素材指示符进行球形插值来获取顶点处的素材指示符：

$>{\tilde{d}}_{\alpha ,i}={\mathrm{slerp}}_{\frac{1}{2}}(P_{t^{i-1}}^{{\tilde{t}}_i}·d_{\alpha }^{i-1},P_{t^i}^{{\tilde{t}}_i}·d_{\alpha }^i),---\left(6\right)$>

其中从一个单位矢量u₁至另一单位矢量u₂的并行或零扭曲传递是使得u₁与u₂对齐的最小角度旋转。

最终，素材曲率可被定义为

角度的线性化–以顶点i为中心的接合处的弯曲和扭曲的内部能量被定义为：

$>E_{\mathrm{b\alpha },i}=\frac{1}{2}\frac{k_{\mathrm{b\alpha },i}}{{\bar{l}}_i}{({\phi }_{\alpha ,i}-{\bar{\phi }}_{\alpha ,i})}^2,\alpha \in \left\{\mathrm{0,1}\right\},---\left(7\right)$>$>E_{t,i}=\frac{1}{2}\frac{k_t}{{\bar{l}}_i}{({\theta }_i-{\bar{\theta }}_i)}^2.---\left(8\right)$>

解析能量表达的差异可以是经由链式法则的推导中的大负荷训练，而且可产生相对大量的复杂项，其评估可能对总仿真时间增加大量成本。更重要的是，一些得到的能量Hessian项可导致无限线性系统，无限线性系统阻碍了它们在隐式积分解法中的应用。其它数值方法，例如双共轭梯度，可克服这些项，但是矩阵的条件数已经很高而且得到的自乘可放大聚合问题。可替换地，识别无限项对于在压缩负载下变得无限的伸缩Hessian项可相对简单，但是对于弯曲和扭曲Hessian项可更复杂，因为它们有更多数量以及数学复杂性。

因此，角度可替换地针对状态示例进行线性化。这可简化求导而且所得到的所有Hessian项可以是正定的。实施期间的其它优势在于，解析求导法的正确性可利用能量表达式的数值差进行验证。

可相对于接合处的结构顶点的状态变量中的干扰围绕当前系统状态矢量q来线性化角变量，对照相邻边缘{e^i-1，eⁱ}和旋转{τ^i-1；τⁱ}写成：

$>{\mathrm{d\phi }}_{0,i}\approx \underset{j=i-1}{\overset{i}{\Sigma }}[{(-1)}^{i-j-1}{u}_i^j·{\mathrm{de}}^j+\frac{{\phi }_{1,j}}{2}{\mathrm{d\tau }}^j],---\left(9\right)$>

$>{\mathrm{d\phi }}_{1,i}\approx \underset{j=i-1}{\overset{i}{\Sigma }}[{(-1)}^{i-j-1}{v}_i^j·{\mathrm{de}}^j-\frac{{\phi }_{0,j}}{2}{\mathrm{d\tau }}^j]---\left(10\right)$>

$>{\mathrm{d\theta }}_i\approx \underset{j=i-1}{\overset{i}{\Sigma }}{(-1)}^{i-j-1}[\left(\tan \frac{\Phi }{2}\right)\frac{1}{\Phi \left|e^j\right|}{\left(\mathrm{\Phi b}\right)}_i·{\mathrm{de}}^j-{\mathrm{d\tau }}^j]---\left(11\right)$>

矢量s和可以是素材曲率角度相对于边缘矢量的空间导数的近似值。

$>u_i^j=(e^j\times {\tilde{d}}_{0,i})\frac{1}{{\left|e^j\right|}^2}{\beta }_i---\left(12\right)$>

$>v_i^j(e^j\times {\tilde{d}}_{1,i})\frac{1}{{\left|e^j\right|}^2}{\beta }_i---\left(13\right)$>

图2图示出上面列出的变量中的一些的视觉表示。

采用可在高弯曲角度下引入小的不平衡力矩的线性化角度近似值可出现一些误差。这可仅仅在许多时间步长之后的自由体(例如，未附接的)紧密卷曲头发的测试期间变得明显。为了进行补偿，系数β^j，转角Φ^j的表现良好的函数，可通过应用对接合处的角动量的守恒来进行计算。

$>\beta \left({\Phi }_i\right)=\frac{{\Phi }_i}{2}{\left(\sin \left(\frac{{\Phi }_i}{2}\right)\right)}^{-1}---\left(14\right)$>

图3的图形300示出了针对参考情况(由线304表示)的弯曲力(y轴)与转角(x轴)的变化以及采用此处描述的具有单位边缘长度和与次法线平行的素材指示符的头发模型(由线302表示)的示例。如线302所示，在从等式7的弹性能量开始时，可获得几乎在转角值的整个域上界定并线性变化的弯曲力。这不同于线304的指数特性。线302的轻微的非线性可源自等式14的校正系数。虽然线性化角度可能看起来使得数学一开始变得复杂，它们可实际上简化求导的计算。相比于从对非线性化角度微分得到的表达，此处公开的技术得到的表达具有相对少的分量，由此它们更易求导、验证以及最终使用更便宜。

d.减振

为了增加减振，可以假设采用Kelvin-Voigt黏弹性素材来精确近似头发。每个弹力可具有相应的减振力，针对弹性和减振分量的张力可相等，而且组合应力可以是弹性和减振应力之和。

减振力可通过针对位置和时间进行微分再次从弹性能量表达开始导出。是与边缘j处的伸缩力相对应的阻尼系数，伸缩减振力为：

$>-\frac{c_s^j}{k_s^j}\frac{d}{\mathrm{dt}}\frac{{\partial E}_s^j}{{\partial x}_{i+1}}=-c_s^j(t^j·(V_{i+1}-V_i))t^j---\left(15\right)$>

其中V_i是顶点i的速度。

类似地，弯曲减振力可被评估为：

$>-\frac{c_{\mathrm{b\alpha },i}}{k_{\mathrm{b\alpha },i}}\frac{d}{\mathrm{dt}}\frac{{\partial E}_{\mathrm{b\alpha },i}}{{\partial x}_{i+1}}=\frac{c_{\mathrm{b\alpha },i}}{{\bar{l}}_i}\frac{{\mathrm{d\phi }}_{\alpha ,i}}{\mathrm{dt}}{u}_j^i---\left(16\right)$>

其中

$>\frac{{\mathrm{d\Phi }}_{i+1}}{\mathrm{dt}}=u_j^i·(V_{i+1}-V_i)-u_j^{i+1}·(V_{i+2}-V_{i+1})---\left(17\right)$>

而且c_αb，i是与α素材方向上的弯曲相对应的顶点i处的阻尼系数。最后，扭曲减振力为：

$>-\frac{c_{t,i}}{k_{t,i}}\frac{d}{\mathrm{dt}}\frac{{\partial E}_{t,i}}{{\partial x}_{i+1}}=-\frac{c_{t,i}}{{\bar{l}}_i}\frac{{\mathrm{d\theta }}_i}{\mathrm{dt}}\left(\tan \frac{\Phi }{2}\right)\frac{1}{\Phi \left|e^i\right|}{\left(\mathrm{\Phi b}\right)}_i---\left(18\right)$>

其中

$>\frac{{\mathrm{d\theta }}_i}{\mathrm{dt}}=\left(\tan \frac{\Phi }{2}\right)\frac{1}{\Phi }{\left(\mathrm{\Phi b}\right)}_i·[\frac{(V_i-V_{i-1})}{\left|e^{i-1}\right|}+\frac{(V_{i+1}-V_i)}{\left|e^i\right|}]+\frac{d}{\mathrm{dt}}({\tau }^i-{\tau }^{i-1})---\left(19\right)$>

而且c_t，i是与扭曲相对应的顶点i处的阻尼系数。

e.头发间的约束

头发间的粘贴和分离可采用不同引导头发上的或者属于相同引导头发的顶点之间的软约束进行建模。约束可被建模为在压缩硬度和减震可不同于伸缩硬度和减振的意义上是两阶段的减震弹簧。可选地，伸缩硬度可被允许在约束点之间的距离增大时减小，以利用增大的分离距离对头发束的分离的更小阻力进行建模。给定具有静止长度的该尖削约束的两端x_a和x_b，从与伦纳德-琼斯势的吸引项类似的势函数导出伸缩力：

$>V(x_a,x_b)\frac{1}{1+\frac{1}{2}k{\left(\right|x_a-x_b|-\bar{l})}^2}---\left(20\right)$>

这可导致在静止长度下等于k并且随着距离平滑衰减的伸缩硬度。如下文在部分6中将详细描述的那样，头发间的约束可与接触约束一起处理。

3.隐式积分

使得q＝(x₀； θ₀； ...； x_n； θ_n； x_n+1)为广义坐标的矢量而且h＝t_k+1-t_k为步长大小。时间积分解法可可由下述等式定义：

$>q_{k+1}-q_k=h({\stackrel{·}{q}}_k+{\stackrel{·}{q}}_{k+1})---\left(21\right)$>

$>M({\stackrel{·}{q}}_{k+1}-{\stackrel{·}{q}}_k)=\mathrm{hf}(q_{k+1},{\stackrel{·}{q}}_{k+1})---\left(22\right)$>

其中k定义了时间，而且f是内部弹力和减振引发的力。项q_k+1可去除以直接将位置和角度的变化关联至力和力的函数行列式(Jacobian)：

$>{\stackrel{·}{q}}_{k+1}=\frac{1}{h}(q_{k+1}-q_k)-{\stackrel{·}{q}}_k---\left(23\right)$>

$>\frac{M}{h^2}I(q_{k+1}-q_k)=\frac{M}{h}{\stackrel{·}{q}}_k+f(q_{k+1},{\stackrel{·}{q}}_{k+1})---\left(24\right)$>

由于f可非线性地取决于q，所以针对每个时间步长的几次牛顿迭代可被使用。例如，使得Δq_i为第i-th次牛顿迭代之后q_k+1-q_k的估计，其中Δq₀＝0。使用围绕q_k+Δq_i的一阶泰勒级数展开，可以获得下述线性系统等式：

$>\left(\begin{array}{c}(\frac{M}{h^2}I-\frac{\partial f}{\partial q}-\frac{1}{h}\frac{\partial f}{\partial \stackrel{·}{q}})({\mathrm{\Delta q}}_{i+1}-{\mathrm{\Delta q}}_i)=\\ \frac{M}{h^2}(-{\mathrm{\Delta q}}_i+h{\stackrel{·}{q}}_k)+f(q_k+{\mathrm{\Delta q}}_i,{\stackrel{·}{q}}_k)-\frac{\partial f}{\partial \stackrel{·}{q}}{\stackrel{·}{q}}_k\end{array}\right)---\left(25\right)$>

碰撞检测和响应(将在下文的部分6中讨论)以及约束满足可集成在隐式求解器中，而不在它们和弹力求解之间交替。

4.头发动画化处理

可针对将被动画化的帧的每个时间步长执行下面示出的算法1以便后求解等式25来求解状态矢量q_k+1。

算法1

算法1的视觉表示由图4的处理400示出。总体上，块402可对应于算法1的第一步，块404、406、408、410、412、414、416、418、420和422可对应于外面的“for”循环执行的步骤，而且块410、412、414、416和418可对应于里面的“for”循环执行的步骤。可针对具有任意数量的时间步长的动画化帧的每个时间步长执行处理400。因此，在执行处理400之前，表示动画帧的时间步长的数据可被接收。表示动画帧的时间步长的数据可包括一个或多个碰撞体(例如，皮肤、眼镜、衣服、刷子等的表示)(运动序列)、头发的静止姿势(例如，头发在没有任何干扰力的情况下的形状)(典型静态)、头发的目标姿势(仿真的头发被附接至该形状)(运动序列)以及约束(例如，头发模型中的弹簧的特性)。

在块402，可根据表示动画帧的时间步长的数据来生成表示帧的时间步长中运动对象的空间位置的轴对齐限界盒(AABB)树(例如，创建并生成新树或更新先前存在的树)。运动对象可包括帧的时间步长中的在仿真期间不会受到动态影响的对象。Van Den Bergen等人的“EfficientCollision Detection of Complex Deformable Models Using AABB Trees”J.Graphics Tools，2(1998)中提供了对AABB树更详细的讨论。

在块404，可根据表示动画帧的时间步长的数据来生成表示帧的时间步长中动态对象的空间位置的AABB树(例如，创建并生成新树或更新先前存在的树)。动态对象可包括在仿真期间可能受到动态影响的对象。

在块406，可利用例如Cholesky因数分解来创建弹力预条件算子。可利用Cholesky因数分解A＝LL^T以数值稳定且有效的方式求解具有对称正定矩阵A的等式的线性系统。Cholesky因数分解的稳定性的原因在于这样的事实，L的元素不会增长，这是因为它们由A的对角元素紧紧地限定着：Golub等人的“Matrix Computations”The JohnsHopkins University Press(1996)中可以找到对此更详细的讨论。稳定的一个结果就是可以不要求枢转。枢转使用的存储器操作可严重地影响依赖于存储器高速缓存和多线程的计算系统的运行时间效率。而且，当矩阵A是分带的，对Cholesky因数分解的计算可能不会产生任何带外填充。

在块408，潜在的近距离接触(例如，头发间的接触或头发与对象的接触)可根据表示运动对象和动态对象的AABB树进行检测。潜在的近距离接触可通过测试各种原始对原始对类型(例如顶点-顶点、顶点-边缘、顶点-面以及边缘-边缘)之间的重叠进行检测。所有顶点可具有相关半径r，其表示头发的碰撞半径或者表面的厚度。在近距离计算期间，半径r可沿边缘以及在面上线性插值以得到连续(G⁰)偏移碰撞表面。可仅仅在给定时间步长的开始和结束状态计算近距离检测。碰撞接触信息可针对重叠的所有原始对以及近距离中的对进行保存。由于投射迭代求解器的使用，额外的非碰撞近距离的包含不会不利地影响解法的质量，而且如果在时间步长原始地发生接触，约束可有效。

块410、412和414可随后迭代地执行与PPGS迭代数相等的次数(例如，2，3，4或者更多)，PPGS迭代数可以是预定的或者由用户选择的，以产生对在块408检测的潜在的近距离接触的法向和摩擦力的大小的估计。具体地，在块410和412，PPGS算法可被用来确定在块408确定的所有潜在的近距离接触的法向和摩擦力的大小。PPGS是一种用于求解由于受制于内部弹力和接触约束的动态状态的演变而产生的下面的二次规划问题的迭代方法：

针对Δq最小化：

条件：CΔq≤c   (27)

其中A和b分别是等式25的左侧和右侧，(C，c)表示非穿透约束以及对摩擦力大小的Coulomb类约束。

为了说明PPGS的操作，首先假设仅仅存在接触约束而不存在弹力。在检测时，针对每个接触的下述量可被计算：穿透深度p、法向恢复矢量n、以及表达为质心权值β_a和β_b的任一原始上的接触点。可构建下面的针对求解给定时间步长上的约束所需的法向力的线性系统(参见Baraff等人的“Large Steps in Cloth Simulation”Proceedings ofSIGGRAPH，(1998)，对于同等约束情况)：

$>\frac{h^2}{2}{\mathrm{JM}}^{-1}{J}^T\lambda =p,\lambda \ge 0---\left(28\right)$>

一旦针对拉姆达求解，与约束j相对应的法向力可被计算为F_nj＝λ_jn_j。矩阵J可以是对m个约束的互连性编码的稀疏的m x3n矩阵。与约束j和顶点i相对应的J的1x3顺时针元素定义为：

J_ji＝n_j(β_aji-β_bji)   (29)

可采用Catto,E.的“Iterative Dynamics With Temporal Coherence”InProc.ofthe Game Developers Conference(2005)中详细描述的投影高斯赛德尔(PGS)方法来求解等式28的线性互补问题，其确定了满足约束所需的有效组正(例如，推)非零法向力。然而，公式不包括内部弹力，所以简单求解等式的结果处于约束附近。

这可能适合于与光滑碰撞对象具有许多顶点碰撞的松软头发，但是对于与尖锐碰撞特征的高分辨率头发碰撞、或者具有高弯曲硬度的头发，可能需要全局信息来确定正确恢复力。由于信息在PGS中相对慢的传播，不利场景下求解约束可能进行相对高的迭代次数，否则解将包含大的张力或者未解决的碰撞。

在已经确定了法向力之后，由于接触产生的关联摩擦力可计算为：

$>F_f=\min (\frac{2}{h^{2}w}\mathrm{\Delta x},\mathrm{\mu \lambda }\frac{\mathrm{\Delta x}}{\left|\mathrm{\Delta x}\right|})---\left(30\right)$>

其中Δx是接触的两个点之间的相对运动，而且w＝(1/m_a)+(1/m_b)是接触中包含的逆向局部质量之和。

因此，最小操作的第一选择表示完全阻止接触的两个点之间的运动所需的力。第二选择表示具有摩擦系数μ的最大可用摩擦力，其可以是运动系数μ_k(如果相对运动的幅度超过一些小距离)、或静态摩擦μ_s的更大系数(如果相对运动的幅度没有超过这些距离)。

注意，利用适当质心权值和约束长度，该碰撞机制还可以用于头发上的任意点、碰撞表面、或空间中的任意点之间的约束，虽然在那种情况下可能没有摩擦力分量。

在块412，一旦约束力的所有分量都已知，它们可被添加至弹力系统(等式25)的右边，其随后可利用先前的因数分解后向求解以找到状态矢量q_k+1的这次迭代的新估计。

按照这样的方式执行块410和412允许PPGS求解在每个将使用的牛顿迭代仅仅需要弹力矩阵的单个Cholesky因数分解的循环。在PPGS中，以不昂贵的(相对于因数分解)后向求解执行循环，从而将远场弹力信息传播至系统的所有节点(例如，单个导向头发的所有顶点)。

在块414，对于块410、412和414的大于一次的PPGS迭代数，暂时碰撞检测可被用来识别快速移动的原始类型的碰撞，否则会在静态近距离测试中丢失。处理可进一步通过排除其相对运动不超过它们的组合碰撞半径的任意对来进行优化，使得具有小运动的区域中的计算节省。而且，可不使用暂时碰撞的移半径r，从而降低针对接触时间的多项式的阶并且允许仅仅考虑顶点-面以及边缘-边缘碰撞。一个潜在消极面可能是出现中等时间步长的轻擦碰撞可能被错过，但是这种瞬态误差未被察觉而且也仅仅发生在快速运动的区域中。

在块416，可以判断是否已经到达块410、412和414的最后一次迭代(例如，当前PPGS迭代数等于预定的或自定义的PPGS迭代数)。如果确定不是最后一次迭代，处理可进入块418，其中当前PPGS迭代数可增大。在增大当前PPGS迭代数之后，处理可返回块410。块410、412和414可被迭代地执行与预定的或自定义的PPGS迭代数相等的次数。

在迭代了与PPGS迭代数相等的次数之后，可在块416做出肯定判断，使得处理400进入块420。在块420，可以判断是否已经到达块404、406、408、410、412和414的最后一次迭代(例如，当前牛顿迭代数等于预定的或自定义的牛顿迭代数，例如2、3、4或更多)。如果确定不是最后一次迭代，处理可进入块422，其中当前牛顿迭代数可增大。在增大当前牛顿迭代数之后，处理可返回块404，其中动态对象的树可根据动态对象的树的之前状态以及通过迭代地执行块410、412和414。块404、406、408确定的针对潜在的近距离接触的法向和摩擦力的大小的估计进行更新，而且块410、412和414的迭代循环可按照前面描述的方式重复与预定的或自定义的牛顿迭代数相等的次数。

在块404、406、408、410、412和414迭代与预定的或自定义的牛顿迭代数相等的次数之后，可在块420做出肯定判断，从而终止针对帧的目前时间步长的处理400。处理400的输出可以是建模并仿真的头发的所确定的位置的运动序列。可针对动画帧中的任意数量的时间步长重复处理400任意次数，其中针对一个时间步长的处理400的输出被用作针对续时间步长的处理400的执行的输入。

5.平行化

头发间的碰撞和约束的包含使得算法的平行化更复杂；没有这些，系统平行化将简单些，因为每根头发将仅仅取决于其内部弹力和与固体对象的碰撞。邻近头发可被组成适当尺寸的对象以平衡开销和工作量，这在一些示例中可介于每个对象800-1200(例如，1000)个顶点之间。碰撞检测和状态更新对于每个对象可独立进行计算。

每次牛顿迭代可检测一次对象间的以及对象内部的碰撞，同时用户约束可给出作为系统的输入。根据约束和接触的列表，可创建所有互动对象对的列表。

下面示出的算法2可被执行以创建可依次允许的任务的组的列表。每个组可包括任务对的可完全并行的列表。对象可在每个组中出现不超过一次。通常大的头发仿真可能具有大致10000次接触的数量级。由于接触和约束的稀疏特性，接触通常连接至小的邻组。由此，多个组可相对小，通常10的数量级。每个组可按照完全并行循环的方式运行。所有线状物可在开始在下一组上工作之前同步。为了避免拖延，对象对任务的顺序可按照成本的递减次序进行排序，这可被估计为两个对象之间的接触或约束的数量。

算法2

在一些示例中，调度成本可小于总体预算的1％而且可仅仅在检测到新碰撞时进行重新计算。

算法2的视觉表示由图5的处理500示出。总体上，块504可对应于算法2的第一步，块506可对应于算法2的第二步，块508、510、512、514、516和518可对应于“while”循环执行的步骤，块510、512和514可对应于“for”循环执行的步骤。

在块502，未分配任务的列表可被访问。该任务可包括互动对象的对。为了说明，图6图示出通过边缘连接在一起的对象A、B、C、D和E的视觉表示，该边缘表示连接的对象之间的碰撞和约束。与这些对象相关的任务包括由边缘(例如，任务AB、AD、DC、CE和DE)连接在一起的对象的对。

在块504，未分配任务的列表可从最大任务尺寸至最小任务尺寸进行排序。继续前面提供的示例，图7示出了从图6的连接的对象A、B、C、D和E产生的任务702的排序后的列表。如所示，任务AB是最大任务，任务DE是最小任务。

在块506，进度表数据结构可被创建。进度表在创建时可能是空的，但是在执行处理500之后可包括可依次运行的任务的多个组，其中每个组可包括任务对的可完全并行的列表。

在块508，任务的组可被创建。组在创建时可能是空的，但是可被用来存储可依次运行的任务的列表。

在块510，可以判断未分配任务的排序后的列表的当前任务是否包括存在于在块508创建的组中的对象。在块510的第一次迭代，当前任务可被选择成未分配任务的排序后的列表中的第一任务。如果确定当前任务不包括存在于在块508创建的组中的对象，当前任务可从未分配任务的排序后的列表去除并放在块508创建的组中。

为了说明，采用前面提供的示例，可以判断来自第一任务AB的对象是否是在任务的组中。由于对象A和B都不在该组中，任务AB可从未分配任务的排序后的列表去除并放在该组中。由此，组可包括任务AB，未分配任务的排序后的列表可包括任务AD、DC、CE和DE。

在块512，可以判断当前任务是否是未分配任务的排序后的列表中剩下的最后一个任务。如果确定当前任务不是最后一个任务，处理可进入块514，其中未分配任务的排序后的列表中的下一个任务可被设置为当前任务。可针对未分配任务的排序后的列表中的每个任务重复块510、512和514。

为了说明，使用前面提供的示例，由于任务AB不是未分配任务的排序后的列表中的最后一个任务，可在块512做出否定判断，使得处理进入块514。在块514，未分配任务的排序后的列表中的下一个任务(任务AD)可被设置为当前任务。

一旦利用块510、512和514评估了未分配任务的排序后的列表中的每个任务，可在块512做出肯定判断，使得处理进入块516。在块516，任务的组可被添加至在块506创建的进度表。

为了说明，使用前面提供的示例，块510可被执行以确定任务AD的对象是否包含在任务的组中。由于任务AD的对象A已经在该组中(作为任务AB的一部分)，任务AD在块510可不被添加至组。块512、514和510可随后被执行以确定任务DC的对象是否包含在任务的组中。由于任务DC的对象D和对象C都没有在任务的组中，任务DC可从未分配任务的排序后的列表中去除并被添加至该组。因此，组可包括任务AB和DC，未分配任务的排序后的列表可包括任务AD、CE和DE。块512、514和510可再执行两次以确定来自任务CD和DE的对象是否包含在任务的组中。由于任务CE和DE分别包含处于组中的对象C和D，两个任务都不被添加至组。包含任务AB和DC的组可随后被添加至进度表在块516。

在块518，可以判断未分配任务的排序后的列表是否为空。如果确定该列表不为空，处理可返回块508，其中任务的另一组可被创建，而且未分配任务的排序后的列表中的剩余任务可通过迭代执行块510、512和514来处理。

块508、510、512、514、516和518可被迭代执行，直到未分配任务的列表中的每个任务被分配给组而且被添加至进度表。一旦完成，可在块518做出肯定判断以结束处理500。

为了说明，使用前面提供的示例，由于未分配对象的排序后的列表不为空，可在块518做出否定判断，而且处理可返回块508。在块508，可创建新的空组而且可以判断任务AD的对象是否包含在任务的组中。由于组为空，所以对象A和对象D都未包含在组中。由此，任务AD可在块510从未分配任务的排序后的列表中去除并被添加至该组。组则可包含任务AD，而且未分配任务的排序后的列表可包括任务CE和DE。块512、514和510可随后被执行以确定任务CE的对象是否包含在任务的组中。由于任务CE的对象C和对象E都不包含在任务的组中，任务CE可从未分配任务的排序后的列表中去除并被添加至该组。因此，组可包括任务AD和CE，而且未分配任务的排序后的列表可包括任务DE。块512、514和510可被再次执行以确定来自任务DE的对象是否包含在任务的组中。由于任务DE包含同样也包含在组中的对象，任务DE不被添加至组。包含任务AD和CE的组可随后被添加至进度表在块516。

由于未分配对象的排序后的列表不为空，可在块518做出否定判断，而且处理可返回块508。在块508，可创建新的空组，而且可以判断任务DE的对象是否包含在任务的组中。由于组为空，对象D和对象E都不包含在该组中。由此，任务DE可在块510从未分配任务的排序后的列表中去除并被添加至组。组可包含任务DE，未分配任务的排序后的列表可为空。包含任务DE的组可被添加至进度表在块516，而且在块518确定未分配对象的排序后的列表为空之后处理可结束。

图8示出了可使用处理500根据任务702的排序后的未分配列表创建得到的进度表802。如所示，组1可包括任务AB和DC，组2可包括任务AD和CE，组3可包括任务DE。由于不同组中的任务不取决于彼此，它们可被并行评估。

6.结果和讨论

弹性曲线–图9的图形900图示出对两端夹持的连续弹性杆的静态均衡问题的利用处理400创建的示例输出与已知解析解法的比较。该解法属于屈折的弹性曲线系列，其具有可通过雅可比椭圆函数表达的封闭形式而且由连续参数m标记。在Levien,R的“The Elastica:AMathematical History”Tech.Rep.，University ofCalifornia,Berkeley(2008)的部分13中描述了更详细的讨论。在一些示例中，m＝7/10。

螺旋状压屈–弯曲和扭曲之间的相互作用可导致许多不稳定现象。其中之一是螺旋状压屈，其中两端夹持且扭曲的自然笔直的杆在扭曲量小于阈值时保持其笔直形状而且在变量半径超过该阈值时变形成螺旋形状。处理400可产生正确的行为。

与表面的碰撞–在动画场景中，头发可与角色的皮肤、衣服和环境中的其它对象互动。这些对象在运动学意义上说来，是在程序上地规定各个头发仿真、它们的运动以及形状变形。利用处理400，碰撞可被稳健地处理。

头发间的碰撞–头发间的碰撞与摩擦可被用来防止容积损失以及对头发的不同层之间的滑动效应进行建模。可检测不同束之间以及相同头发内的碰撞。为了确保稳健且稳定的碰撞响应，顶点-边缘和边缘-边缘近距离检测都可被用来产生接触。

头发间的约束–为了产生头发间的约束(参见部分2b)，可对头发的静止形状执行近距离检测。可以设置头发顶点所属的约束的最大数量。约束的硬度和减振参数可根据发型内的约束的位置进行设置。

表1所示的性能和缩放图示出针对包括大范围顶点、约束和接触的各种情况的此处以每帧平均毫秒数描述的头发动画化处理的示例性能。给定固定迭代数的使用，以及使用密集带线性系统上的直接求解器，期望的平均运行时间是O(n+m)，其中n是顶点数，而且m是约束和接触的数量。

表1

表2示出了公开的头发动画化处理在工作量和线状物的范围上的示例性能。在单个线状物的情况下，操作量表大致线性地随着顶点增长，而不管接触数量的近似平方增长。然而，随着线状物的数量增大，该效率下降。这可增进平行化约束分辨率的难度，但是注意，在4个处理器的情况下性能下降至75％的缩放效率，而且在采用12个处理器时仍然处于50％以上。

表2

平行化效率可在最重工作量(例如，47000个顶点)的情况下最佳，介于针对四个处理器的68％至针对12个处理器的37％。该差异可促进理想引纸效率相对于引纸的并非不重要的任务之间的差异，在所有测试情况下数量超过顶点数一个数量级的许多约束和接触。

图9示出了示例性计算系统1000，其具有可被用于执行上述处理400和500的多个组件。主系统1002包括具有输入/输出("I/O")部分1006的母板1004、一个或多个中央处理单元("CPU")1008和存储部分1010，存储部分1010可具有与之相关的闪存卡1012。I/O部分1006连接至显示器1024、键盘1014、盘存储单元1016和介质驱动单元1018。介质驱动单元1018可读取/写入可包含用于执行处理400和500的程序1022或数据的计算机可读介质1020。

能够保存基于上述处理结果的至少一些值用于后续使用。或者，计算机可读介质能够用来存储(如，切实体现)用来通过计算机方式实施上述处理400或500的任意一个的一个或多个程序。可以写入计算机程序，例如采用通用编程语言(如Pascal，C，C++)或一些特定应用的指定语言。

在此描述了各种示例性实施例。以非限制的方式参考这些示例。它们被提供来示例可更宽范围应用的公开的技术方面。可作出各种变化以及可以替换等效形式，而不脱离各种实施例的真实精神和范围。此外，可作出各种变更以适应具体情况、素材、主体成分、处理、对对象的处理动作或步骤、各种实施例的精神或范围。而且，本领域技术人员可以理解的是，此处描述及示例的每个单独的变形具有单独的组成和特征，它们可容易地与其它一些实施例中的任意实施例的特征区分开或组合，而不脱离各种实施例的范围或精神。