针对布料动态模拟中快速稳定求解的瓶颈问题, 提出了一种局部自适应的混合积分方法。在每一时间步长, 网格中质点利用自身模拟参数求解一稳定的判断准则, 据此自适应判定该质点相连弹簧不同弹性力部分引起的运动方程采用何种数值积分求解, 从而有效提高了模拟效率且可以并行计算。另外, 针对线性方程组的特点, 用快速超松弛迭代法代替传统的共轭梯度法来求解, 进一步提高了系统的性能表现。实验表明, 该方法具有近似线性的复杂度, 便于并行计算, 并有良好的稳定视觉效果。
2742 计算机应用研究 第29卷 参数步长h,求解上述判断准则。如果结果为真,则令与该质 不同积分方法下训算速度比较 点相连接的拉伸或剪切弹簧跳过其雅克比矩阵计算,直接运用 招舌查混合积分法 单计复时间(ms 显式积分计算;否则,利用隐式积分计算。 在没有牺牲精确性的前提下,根据上述判断准则可以将布 局部自适庙合积众如 料网格自适应分解为多个子区域独立求解,从而提高模拟效率 局部自适速流合积分法 员第白活南合法 且可以并行计算。同时,这也提高了系数矩阵的稀疏性。 时间北长(ms) 半隐式积分方法的效率主要取决于雅可比矩阵的建立和 50100150200 线性方程组的求解。雅可比矩阵的建立并不复杂,因此线性方 图2不同数值积分方法计算速度比较 程组的求解就成了半隐积分方法的效率瓶颈所在。式(5) 屮(M-3豇-h豇)的规模是3n×3,这里的n是布料模型 的粒子数。因而线性系统规模将随着布料模型粒子数的増加 而迅速增大。与外,由丁共扼梯度法求解式(5)的算法复杂度 尚产正【其材 般在O(nl3)-O(n2),因此,当布料粒子模型的规模较大 时,线性方程组的求解将非常耗时。考虑上述线性方程组具有 图3布料悬垂模拟 冬4风力作用下的布料 正定、对称、稀硫的特点,本文采用超松弛迭代算法来求解该线 性方程组。 4结束语 记M=(M25-h0),则根据式(5)可构建其超松弛 实验结果表明,本文提出的局部自适应混合积分法在不粞 迭代通式为 牲准确性的前提下,在每一时间步长运用时域和空域上局部模 △n:0=hM:1f k=0,1,2,…;i=1,2,…,n 拟参数求解判断准则,据此自适应地将布料网格分解为多个 +1=△0)+M1.∑(M2-M1)△n+1)+ 子区域独立求解,并利用快速迭代法求解对称稀疏线性方程 组,这大大提高了模拟效率且可以并行计算,算法具有近似线 M1∑(M2-M2)△v;2 性复杂庋,可适用亍较大规模布料的实吋模拟。未来进一步考 虑将本文算法移植到基于CUDA语言的GPU平台上,模拟效 式中:为松弛因子,实验中其取值一般为1.0~2.0,值越大率将得到进一步提升,从而涛足大规模布料的实时模拟要求。 模拟精度越高 参考文献 相比共轭梯度法,上述迭代方法更为灵活,最终能够以自「1 TERZOPOULOST D, PLATT J, BARR A,cta. Elastically deformable 适应的方式适当降低模拟的精确性来提高布料动态模拟的效 modelsLJ. Computer graphics, 1987, 21(4): 205-214 率和生成速度。一般来说,本文方法的复杂度是O(n+e)(n [2 PROVOT X Deformation constraints in a mass sp nodel to de 为粒子数,e为弹簧数),从而它的计算开销不会随着模型规模 scribe rigid cloth behavior C//Proc of Conference on Graphics In 的増大而迅速增加,因此,这种算法乜适合于布料模型规模较 rface.1995:147-154. [3 BARAFF D, WITKIN A Large steps in eloth simulation[C]// Proc of 大吋的实时计算。 the 25th Annual Conference on Computer Graphies and Interactive 3实验结果和分析 Techniques. New York: ACM Press, 1998: 43-54 [4 DESBRUN M, SCHRODER P, BARR A. Interactive animation of 基于上述方法,在 Windows XP Sh2操作系统和 Intel structured deformable objects[ Cl//Proc of Conference on Graphics Pentium42.4G处理器的软雙件环境下,在Ⅴ isual o∵+ bilate 6.0平台下并结合Open(L图形库,对布料进行模拟。 [5 CHOI K J, KO H S. Stable but responsive cloth[ J]. ACM Trans on 为了测试本文局部自适应混合积分方法和其他常用数值 graphics,2002,21(3):604-61l 积分方法对计算速度的提升差异,利用10×10布料网格做单[6]张明敏恭于组织结构的织勒仿真与真实感展示[D].杭州:浙江 大学,2008 摆运动仿真实验,实验中分别应用显式龙格一库塔法(Ruge[7]周川.布料动画关键技木研究[D].杭州:浙江大学,20 Kt法)、半隐式欧拉法结合共轭梯度法(C法)以本文方[8] BRIDSON R, EDKIW R, ANDERSON1. RobusI Ire- almen of colli 汏各自模拟l00帧,记录总的计算时间,从而求出生成每軟的 sions, contact and friction for cloth animation J]. ACM Trans on 平均计算时间,利用这个参数来衡量不同数值方法的计算速 Graphics,2002,21(3):594-603. 度。另外根据仿真中总步长数还可以求解得到平均单步计算[9 BOXERMAN E, ASCHER U. Decomposing cloth[C]/ Proc of ACM 时间。实验结果如图2所示。由图2可知,尽管显式方法单步 SIGGRAPH/ Eurographics Symposium on Computer Animation. New 计算时间比本文方法要小,但考虑到本文方法在时间步长上要 York ACM Press. 2004: 153-161 远大于它,因此本文方法的速度还是会达到或超过显式方试,[10]刘宁,高成英,罗笑南织物模拟中的自适应网格剖分研究[J] 布料规模域大这和实时性能提升的效果明显。 计算机科学,2004,315):193-196 图3分别给出了25×9个质点、1202根弹簧构成的布料 LIl」孔川,罗大膚.利用弹賃质点模型和隐式方法的布料模拟研究 [J].计算机工程与应用,2011,47(9):2 (左图)和32×32个质点、5826根弹簧构成的布料(右图)的悬 12 LI Ling, VOLKOV V. Cloth animation with adaptively refined mesh 垂效果。图4给出了16×12个质点、1014根弹簧构成的布料 LC]//Proc of the 28th Australasian Computer Science Conference 旗帜在风力作用下的效果。 2005:107-114