（计算机系统结构专业论文）基于gpu加速的毛线布料仿真.pdf

中文摘要 进入新世纪以来，图形硬件取得飞速发展，特别是最近几年可编程图形硬 件( g p u ) 的推出和其性能的不断提升，开创了图形编程的新时代。由于毛纺编 织布料结构的相对复杂性，相关的研究不是很充分，为此本文采用质子弹簧模型 和毛结穿越结绘制相给合的办法，重点对毛线布料的微观结构和g p u 加速仿真 进行研究。 本文综述了布料研究的现状和相关理论基础，论述了拉格朗日能量方程与质 子弹簧模型，并选择质子弹簧模型为仿真所用物理模型。说明了仿真物理模型的 三种数值积分方法和过程，重点分析了4 阶龙格一库塔( r u n g e k u _ t t a ) 积分方法。 接着，分析了布料碰撞和反馈处理的基本原理，指出两种最基本的碰撞类型，并 提出了基于层级树的自碰撞优化流程。接下来，又引述了b 样条线的基本原理， 讨论了采用b 样条线来对毛线微观结构进行仿真绘制的过程和方法。本文的最 后部分，简介了g p u 发展历程，说明了用c u d a 进行硬件并行计算的方法，分 析了本文所采用的物理模型g p u 部分编程细节。 到此，本文对已有布料物理数学模型进行优化，采用新的编程语言c u d a 和 g p u 计算硬件来完成密集型积分和受力计算，同时采用传统c + + 语言实现布料结 构生成和碰撞检测，取得令人满意的交互结果。 关 销司：毛线布料质子弹簧能量方程g p u 加速布料仿真 a b s t r a c t w h e n c o m i n gt ot h en e wc e n t u r y , t h eg r a p h i c sh a r d w a r eh a sb e e ni m p r o v e dal o t ， e s p e c i a l l yw i t ht h er e l e a s i n go fg p u ( g r a p h i c sp r o c e s s i n gu n i t ) a n di t sp e r f o r m a n c e i m p r o v e m e n t ，i ti n i t i a t e dan e wg r a p h i c sp r o g r a m m i n ge r a f o rt h er e l a t i v ec o m p l e x i t y , t h ek n i f e dc l o t hh a sn o tb e e nd e e p l ys t u d i e d i nt h i sa r t i c l ew eu s et h em a s s s p r i n g m o d e la n dt o g e t h e rw i t ht h e3 dd e p i c to fk n i t t e dc l o t hp e n e t r a t i n gk n o ts t r u c t u r e ，w e p u tm o s tw o r ki n t ot h es t u d yo fk n i u e dc l o t hs i m u l a t i o n i nt h i sa r t i c l e ，iq u o t e dt h ec u r r e n ts i t u a t i o ni nc l o t hs i m u l a t i o na n dr e l a t e d t h e o r i e s ，d i s c u s s e dt h ee n e r g yb a s e dl a g r a n g i a nd y n a m i c se q u a t i o na n dm a s s - s p r i n g m o d e l t h r e ec l o t hm o d e l sn u m e r i c a li n t e g r a t i o nm e t h o d sa n dp r o c e s s e sw e r e p r o p o s e da n dm a i n l yd i s c u s s e dt h e4 t ho r d e rr u n g e - k u t t ai n t e g r a t i o nm e t h o d s l a t e r , a n a l y z e dt h ef o u n d a t i o np r i n c i p l e so fc l o t hc o l l i s i o nd e t e c t i o na n dc o l l i s i o nr e s p o n s e ， p o i n t e do u tt w ob a s i cc o l l i s i o nt y p e sa n dp r o p o s e da nc o l l i s i o nd e t e c t i o no p t i m i z a t i o n m e t h o db a s e do nh i e r a r c h yt r e e t h e n ，t a l k e da b o u tt h ep r i n c i p l e so fb s p l i n ec u r v e s a n dt h em e t h o dt os i m u l a t et i n yk n i ts t r u c t u r eu s i n gb - s p l i n ec u r v e s i nt h el a s t ， b r i e f l yi n t r o d u c e dt h ed e v e l o p m e n th i s t o r yo fg p u s u m m a r i z e dt h em e t h o do f c u d a p a r a l l e lc o m p u t a t i o no nh a r d w a r ed i s p o s e ds o m ep h y s i c a lc o m p u t a t i o n d e t a i l s o ft h es y s t e mr e l a t i v et oc u d a s of a r , io p t i m i z e dt h ee x i s t e dc l o t hp h y s i c m a t h e m a t i c a lm o d e l ，ig e tt h e a c c e p t a b l ei n t e r a c t i v er e s u l t sb yu s i n gt h en e w l yd e v e l o p e dc u d ap r o g r a m m i n g l a n g u a g ea n dg p u h a r d - w a r et op e r f o r mh i g hi m m e n s i t yc o m p u t a t i o nt a s k ss u c ha s i n t e g r a t i o na n df o r c ea n a l y s i s a l s oc o m b i n gt h eu s eo fc + + t op e r f o r mt h ec l o t h c o n f i g u r a t i o n ，c o l l i s i o nd e t e c t i o na n dr e s p o n s e k e yw o r d s ：k n i t w e a r , m a s ss p r i n g ，e n e r g ye q u a t i o n , g p ua c c e l e r a t i o n c l o t hs i m u l a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导- 卜进行的研究工作和取得的研究成果， 除了文中特别加以标注垌i 致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得苤注盘堂或其他教育机构的学位或证1 5 而使刚过的材料。与我一同一1 ： 作的同志对本研究所做的任何贡献均已往论文中作了明确的说明并表示了谢意。 学位论文作者签名：刎促忽签字日期： 伽。胁易月争日 学位论文版权使用授权书 本学位论文作者完全了解叁盗盘堂有关保留、使用学位论文的规定。特授权 苤鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检索，并采川影印、缩 印或扫描等复制手段保存、汇编以供奄阅和借阅。同意学校向国家有关部门或机构送交论文 的复印件和磁盘。 ( 保密的学位论文在解密后适刚本授权说明) 学位论文作者签名：刎认荔己导9 帝签名： 训辛乞 j 签字日期：伊7 年月争日 签字日期： ，7 年月争e l 第一章绪论 1 1 研究背景及意义 第一章绪论弟一早三：百比 随着近年来计算机图形硬件的飞速发展，有越来越多的实时仿真系统被开发 出来，以满足人们对更逼真的虚拟场景的需求。这其中比较成功的一类仿真系统 就是布料仿真系统。在现实环境中，布料是一种非常常见的材料，无论何时何地 的人们都会身着形形色色的服装：还有户外的迎风飘扬的旗帜，家里的窗帘以及 台桌布等，所有这些都是真实世界必不可少的一部分。计算机图像学领域的科学 家和技术人员进行了大量的研究和开发，取得了众多突破性成果。 布料仿真的一个重要应用领域为三维服装设计，+ 它将改变传统的服装设计过 程，可让人们在衣服做好之前看到服装的式样和试穿后的形态，可以对各种布料 及薄性材料进行仿真，并能设置材料的质地、图案、尺寸和环境( 光源、重力、 风源、风速、风向) 以及材料的动力学约束。在虚拟现实场景中，需要逼真地显 示织物的装饰效果，模拟模特服装表演等。高效的布料仿真是不可缺少的。虚拟 现实环境等应用中有实时交互行为，因此对用于这些应用的布料仿真系统应该有 足够高的计算效率来满足实时交互的需要，并且布料模型还需要有足够的复杂度 以提供足够的画面表现。 布料仿真是计算机动画与仿真的一个重要组成部分。推动计算机动画发展的 一个重要原因是电影电视特技的需要，计算机动画已形成一个巨大的产业，并有 进一步壮大的趋势。随着计算机硬件性能价格比的快速提高，商用动画软件公司 及时地推出了动画软件的微机版本。因此动画的发展推动了布料仿真技术的发 展。 布料仿真还可以应用到游戏中，真实快速的仿真效果将为绚丽的游戏效果增 色不少。在游戏中，由于要保证游戏的运行速度，游戏制作者并不需要精确的模 拟布料仿真的细节，只需要为玩家们提供具有视觉真实感的布料仿真效果，例如 游戏场景中的窗帘、桌布以及随风飘动的战旗等。 布料的模型有许多种类，然而在计算机图像领域用得最多也是最早的一个模 型是把纺织( w o v f f 1 ) 布料看成是各向同构的线性弹性片。这些模型或者是显式 连续的 1 】或者是对一些连续曲面的离散化逼近【2 1 。对这些模型后来的改进和扩展 主要集中在加速计算时间【3 1 ，仿真布料压力状态下的稳定行为【4 1 ，改进的弯曲模 型【5 】【6 】和稳定的碰撞处理【3 】 7 】【8 】上。 第一章绪论 同时，由于编织n 蛐布科是由一些离散的纺线组成的，另一| 人们提出来。对纺线的几何建模由p e i r c e ”开始。他推导出了一系列自 程来对编织物中的纺线的穿越进行建模，并把这些纺线当成不可拉伸自 待。k a w a b a t ae ta l 【l o 惶出了在普通编织物中的纺线穿越的捆束模型 t l u s sm o d e l ) 同时也建立了一套测量布料被拉伸、剪切、弯曲后曲 统。编织物中的纺线穿越节，也被建模成一对曲线i ”i 。n a d l e re ta l i ”蝴 模型，在高层次上把布料作为连续片来对待，在微观层次把布料作为一 触的正交曲线对的集合来看待，微观层款结构的反馈驱动高层次的仿j 被建模成样条线，r 。e m i o n i ”为编织物中的样条线建立了一些基本方 用控制点间的弹簧来保持长度。e b e r h a r d te ta l 1 4 1 把编织物建模共 k a w a b a t a 测量试验所推导出来的压力曲线的连续片。 在布料仿真问题上，大量研宄者进行了广泛的研究，在仿真的速e 稳定性等方面取得了很大的进展，但在布料仿真的真实感和交互性上 非常满意，为此通常有两种主要的改进思路，分别就是优化算法和充f 计算资源。因此我们在进行软件方面算法优化的同时一个不可忽略自 当前图形硬件的高速发展。图形硬件已经远远不只是在硬件上实现固目 水线，当前的可编程图形硬件完全可以实现图形学以外的通用计算。 值得一提的是n v d i a 和微软两家公司都为硬件加速虚拟仿真上b 贡献，基于c g 着色语言，人们也可以把传统的c p u 物理计算放在图 执行，从而设计出比以前更大规模的实时布料系统。 图卜i 基于p h y s i c s 布料仿真- - 1 1 】 第一章绪论 由于编织布料的相对复杂性，所以编织布料在过去没有被研究得报充分。近 来却越来越引起人们的研究魁趣。人们不再满足于宏观的纹理贴国，而需要更深 入细节的物理仿真。所咀本文的重点也就是放在把质子弹簧模型用在编织布料 上，布料在几何结构上不仅仅是简单的薄片结构，而是立体编织节结构。且本布 科仿真系统的绝大部分物理计算过程都是在g p u 上使用c u d a 运算执行，提升 了系统仿真的精细度。 一 图卜3 基于p h y s i c s 布料仿真三 第一章绪论 1 2 研究内容和创新点 本文以质子弹簧物理模型和b 样条曲线绘制为基础，对中等规模的毛线编 织物进行实时仿真，取得了可接受的精细度和帧速率。所研究的内容主要涉及下 以几部分： 一、比较和分析毛线编织物仿真中学术界流行的两大物理模型：质子弹簧模 型( m a s s s p r i n g ) 和基于能量分析的约束拉格朗日方程( c o n s t r a i n e dl a g r a n g i a n d y n a m i c s ) 模型。最后选取质子基于弹簧模型的布料系统对编织布料进行模拟。 二、对整个系统在外力作用下随时间演变进行积分迭代运算。使用的三种积 分方法是显式欧拉方法( e x p l i c i te u l e rm e t h o d ) 、v e r l e t 积分以及龙格一库塔方法； 积分过程分为两大步，第一步计算质点系统受力情况，第二步更新位置和速度。 三、对质子系统与规则表面进行碰撞检测，再执行碰撞反馈，模拟布料悬垂 效果和布料与地面、墙面、球面碰撞。碰撞检测主要分为“点三角形”碰撞和 “边边”碰撞两类；同时对碰撞检测利用包围盒树和表面曲率的方法进行优化。 四、在o p e n g l 环境中，执行质子点鼠标拾取，模拟用户自定义力施加在质 子弹簧上的效果。 五、在c u d a 平台上进行线程级的大规模并行计算，生成网格中的编织节基 本结构顶点数据，并返回给o p e n g l 顶点缓冲对象( v b o ) 。讨论了线程在内核 级和全局级的g p u 内存访问冲突解决方法。 在本文中创新点如下： 1 采用c u d a 进行大量通用数值计算，并成功进行布料仿真的受力和积分 的硬件并行计算，使仿真规模( 粒度) 提高4 倍左右。 2 基于布料的质子点网格，由g p u 生成有光滑曲度的毛线结构，顶点数据 可返回给o p e n g l 。 3 基于层级树的碰撞检测预处理，优化碰撞检测的规模。 1 3 论文结构 第一章，介绍了本文的课题研究背景及意义，提出了本文的研究内容和创新 点，并简要介绍了论文的主要结构。 第二章，重点比较了在编织布料模拟仿真中常用的能量方程和质子弹簧两种 模型的基本原理和各自的优势和劣势。着重介绍了质子弹簧系统结构，受力和运 动方程。 第三章，说明了三种布料模型的数值积分方法和过程，重点分析了4 阶1 1 第一章绪论 龙格库塔( r u n g e k u t t a ) 积分方法，并比较了各算法的效率。 第四章，论述了布料碰撞的基本类型和原理，重点讨论了碰撞检测优化算法， 即层级树划分和表面曲率判断碰撞检测。说明碰撞反馈的处理，并给出了碰撞检 测的核心流程。 第五章，描述了毛线布料网格级的微观结构，采用b 样条线来模拟毛线的 相互穿越结构，即基本r ，l 环。 第六章，介绍c u d a 并行运算平台，描述了将c p u 实现的算法在g p u 上 实现的流程，比较了受力分析模块的c p u 算法和g p u 算法的耗时加速比。 第二章拉格朗日艟量方程与质子弹簧模型 第二章拉格朗日能量方程与质子弹簧模型 布料仿真系统的实现会涉及到力学，科学计算，图形学，井行计算等学科知 识。本文所实现的仿真系统主要由五大模块组成，分别是初始化模块、主循环模 块、用户交互界面、c u d a 核运算横块、o p c n g l 绘制模块。其中主循环和c u d a 核运算实现本章所要讨论的质子弹簧模型，驱动仿真系统的绘制模块。 以下就分别介绍拉格朗日能量方程模型与质子弹簧模型的基本原理因为他 们的物理理论模型是仿真系统的核心和灵魂，最好对两者进行简要对比分析。 2 1 基于拉格朗日能量方程的物理仿真模型原理 布料模型是基于组成它的单根毛线。为了不失通用性，我们假设编织节是由 单根毛线构成。毛线是由控制点q r 妯所描述的直径恒定为r 的开放立方b 样 条曲线。通常，下标i j 在样条线分段数范围内。而下标k l 在控制点效范围内。 对单根毛线来说，曲线被描述硪y ( s ) 2 以o ) “，j 【o ，_ v 】且n = m - 3 样条分段 黼 s 1 0 c k i n e t l ek j t a t 、一i + o r q 、一f o 粥糕龋燃 嬲嚣疆黼徽 数。ql s l 是b 样条线的与控制点k 有关的基函数。 图2 - 1 三种常见的编织物毛线穿越样式 1 4 类似的在参数点s 处毛线的的速度是呲印2 上乜。为方便起见，限制 于特定的样条段i 的曲线是被记为”( s ) ，s c o ，l 】( 且v ( 曲为速度) 每条样条线段都 有固定的弧线长度k 。毛线每单位长度具有质量“，且质量是按照函数 “例2 “”“o ，顺着弧线分布的。分数段常函数按弧线长度赋予各段以质量，然后 在参数空间均匀分布质量。 黼 第二章拉格朝日能量方程与质子弹簧模型 使用约束状态下的拉格朗日运动学方程来对毛线的时间演变进行建模。参考 可咀对拉格朗日力学有个更详细的了解。r c m i o n 武a l 有其在样条曲线上 的应用有相关介绍。此外，布料的刚性是通过约束来加强的。最终的结果就是这 样形式的线性微分方程( d a e ) ： f m q = 一v p 聊) 一l d ) + ，( 2 一1 ) 【“q ) = o ( 2 2 ) 其中m 为密度矩阵，e ( q ) 为位置能量项的总和，d 为所有“阻尼能”项的 总和，f 为外力。且c ( q ) 为常函数向量。 、 r _ 。露 ，一 ，岫砖| _ 矗。 -一5 ： k 、f 、t 、】i 】k 1 、过j 、n 、 图2 2 毛线线模致l3 】 2 1 1 毛线内属性 r 2 3 1 为了运用拉格郎日力学就得计算旦d t ( w r ( 口”。通过展开方程2 - 3 右边的积 为了运用拉格郎日力学就得计算 。 。通过展开方程右边的积 分项，m v q t ( q ) 可控重写为岣，帆2 r m o 地( 啪( 5 ) d5 。由于这取决于弧 长“马址和基函数。对 绚关于t 求导即可产生，i 也即方程( 2 - 1 ) 的左边部分。 弯曲：弯曲抗力被定义成与曲率的二次方成正比的弯曲能量密度函数： 置掣= r o ) 2 d s 其中 屯0 ) = 为样条段i 在s 处的无符号曲率 ( 2 _ 4 ) 是 腿小。? 峥 毛 珊 第二章拉格朗日能量方程与质子弹簧模型 恒定性：由于同布料相比所具有的对拉伸的高抗力，在此把毛线定义成不可 拉申。理想状态下在无限小层级上这是一约束。为确保不能因添加了过多的约束 而使系统锁定。最终，在每个样条段上定义一约束 c p = i - - 1j ：。1 i i y i ( s ) l 缸 ( 2 - 5 ) 这个约束是为了使分段的总长度保持不变，但它没必要使弧线内部的质量均 匀分布。只要总体长度不变，无限小的长度却可以变化而不带来太大的危害。为 了防止这样，这里引进了些能量项： 矽= 肛峄，出 ( 2 6 ) 其中k 是硬度系数。这一项并不需要特别的硬，因为有长度约束，它仅仅需 要抵抗局部质量的拉申和压缩。比如，在一条垂直悬挂的毛线中k 仅需要支撑单 个样条段的重量，而不是需要k 能够使第一个分段支撑起整个毛线的重量。 2 1 2 毛线间碰撞 毛线间的碰撞由这一项能量能定义： 错：够( 鼽掣脚 ( 2 _ 7 ) 其中i ，j 使得li - j l l ，f i d ) 被定义为d 一1 时，f 【d ) 一0 ，d l 时f ( d ) - 0 ，且d 一0 时，坟d ) 一。 可定义， 朋，= 瞄删 ( 2 8 ) 此碰撞模型要比最近点模型在物理上和计算上都更加健壮。此外，这个定义 方法也可以应对任意布料的自碰撞，正如在折叠和捆束中所看到的一样。 第二章拉格朗日能量方程与质子弹簧模型 2 1 3 阻尼与摩擦 编织布料中的阻尼与摩擦是很复杂的，他们有严重的滞后效应。编织物的互 锁结构形成了较大的接触区域，对于由短纤维组成的毛线来说，毛线问的直接接 触点加上纤维束的扭合，即“毛绒”，能够抵抗毛线间的相对运动。目前有三个 具有实际用途的阻尼模型。 质量均衡阻尼是一种吸收运动的经典方法，且它也是最基本的阻尼力构成部 分。阻尼按以下能量项均匀地分布于毛线中。 矽耐= m j ：v f ( s ) r v ( s ) j ( 2 - 9 ) 由于假定毛线的密度是恒定的，质量依赖被有效地放入k 珈b 柏中。在实际仿真 中，k # o b s a 却通常是不使用的，且依赖于以下两阻尼模型来对布料的运动进行阻 尼。 接触阻尼：毛线间的接触阻尼项d 舻用来阻尼毛线间的刚性接触力和近似 滑动摩擦。对其定义为： 掣z r ( n 1 2 - ( 五筏) 2 d s d s 7 其中k d t - 0 控制着切线方向的阻尼，v ，i ，2 觚，j ( s ，s ) 2 _ ( s ) 一v ( j ) 为相对速 度；1 3 0 ：n t j ( s ，s ) 为碰撞方向n i j ( s ，s ) 2y ，( s ) 一y is ) 的法向值。这项积分只是在估 计毛线将要相互碰撞时才求取积分值的，估计法为方程( 2 8 ) 。 非刚体运动阻尼：定义毛绒特性的吸收效果是一个相当难的问题。即不能显 式地定义他，但又不能忽略它，因为需要模拟的布料的重要特性之一。这里，有 一个在实际中运用得很好的简单模型，发展更高级的模型留给将来工作。 为了抵抗周围毛线段的相对运动，可对非刚体运动进行阻尼 1 6 】在r i v e r sa n d j a m e s 【1 7 】中布料被撕裂成固定的相互交叠的区域，在每一时间步，每片区域的质 晏( 耐o ) ，1 ，o ) ) 心，角运量，惯性矩都要计算。每片区域中的毛线都按公式，p j 。 来 阻尼，其中酗( s ) 为点s 的期望刚性运动。参数口【u ，l j 控制着阻尼的强度，“s ) 为包含点s 的固定区域的数量。 在由毛线初始阶段定义的参数化静态区域上使用二阶段过虑器，首先加重阻 尼两毛线环的小区域，然后阻尼更大的区域( 见图2 3 ) 。 第二章拉格朗日能量方程与质子弹簧模型 蒸溅 # 性m 月十e m# 性月较太区域 图2 3 非刚性速度阻尼过虑作用区域 第一阶段被设计用于阻尼掉毛线环问的局部运动，每二阶段阻尼拉申、剪切 和弯曲力。 2 1 4 额外的约束和联结 为了防止编织布料自动解散，毛线的末端通常打成死结或者牵引着通过好几 个节环依靠摩擦力保持固定。 通过“粘”毛线的末端到另一条毛线上达到了同样的效果。物理方法就是通 过以下约束达到，即针对特定选择的s l 和s 2 ：c g l u e = y ( s 1 ) 一y ( s 2 ) 。同样的，当布 料需要被钉起来时，以下形式的向量约束被添加进来： 尊“= r 0 。) 一r 。避免使用过多的强制约束是很有必要的，因为它会导致过分 约束的或者接近奇异的系统，降低毛线力学特性。 综台使用这两种方法来近似物体的摩擦。把接触看成显式表面。并通过以下 能量项来定义反力： 矿吨： 燃 ) 2 ，( * ( s ) ) c 矗l b2 1 l 它同相应的阻尼力一道产生舍力。( 同毛线问碰撞阻尼( 2 1 0 ) 相似) 。此 外，对于有距离项的物体( 比如一条掉落在平板上的毛巾) ，可采用一速度过滤 器和一法向脉冲，这样就可咀解决相互穿透的问题。同时，在摩擦上也给一近似 脉冲( 参照 7 ) 。 第二章拉格朗日能量方程与质子弹簧模型 22 质子弹簧模型基本原理 2 2 1 质子弹簧基本结构 质子弹簧模型把布料作为节点网格来看待，布料的质量都集中在这个中心节 点上。此网格结构由一系列的线性弹簧连接而成，这些线性弹簧使系统保持稳定 不至于布料被扯开。到目前为止，有各种各样类型的弹簧和结构被学术界提出来， 不同的结构产生 图2 - 4 质子弹簧网格口习 本文采用的质子弹簧模型结构由以下三种弹簧组成： 结构弹簧：这类弹簧连接四周邻近的节点，但不连接对角的节点作用是布 料保持片状。 囟 第二章拉格朗日能量方程与质子弹簧模型 图2 7 弯曲弹簧连接结构 2 2 2 质子弹簧受力分析 以上介绍了质点弹簧模型中质点的连接方式，布料仿真的实质是要计算 出屏幕每一帧每个质点的位置和速度。质点的位置受布料内部弹簧的弹力( 包括 结构弹簧力，剪切弹簧力，弯曲弹簧力) 和织物外部受力( 如重力、约束反力、 阻尼力、空气阻力、用户定义的力等) 的影响，确定屏幕每一帧各质点的位置、 速度等信息 考虑系统的简单和高效性，基于本文所实现的系统对单个质子主要受下以几 种类型的力： 一、弹簧内力： 假设质点j 是通过弹簧与质点i 相连接的一个质点，则质点i 所受该弹簧的 拉( 推) 力可由虎克定律计算得到： 耻吲一乞尚卜础z 卅一l ok ( x , 刮- x j ) ( 2 - 1 2 ) 其中，是连接质点i 和j 弹簧的弹性系数，l “o 是该弹簧的原长，是 某时刻该弹簧的矢量，x i 和x j 是该时刻质点i 和质点j 的位置。对于质点i 和 j 之间的弹簧阻尼力( 对质点i 的作用) 定义如下： f 0 = k ；j j v ) ( 2 1 3 ) 其中，k 是与质点i 相连接的质点总数。 以上公式对三种类型的弹簧都适用，所以，一个质点所受的弹簧内力之和即 为三种类型弹簧对质点作用力向量的合。 第二章拉格朗日能量方程与质子弹簧模型 民刚( x ，f ) = k ，+ 只 。咖+ 兄咖 ( 2 - 1 4 ) 二、 外力： 在布料仿真中，为了模拟布料质点的运动及与周围环境障碍物所发生的碰 撞，往往还要考虑重力、惩罚力、阻尼力、空气阻力等自然世界里真实存在的外 力，也需要考虑系统设计者定义的力。即： 。，( x ，t ) = g + 。砂+ 瓦慨+ e 。，o + 瓦。 ( 2 1 5 ) 下面分别详细介绍质点受到的各种外力： ( 1 ) 重力( g r a v i t y ) 在我们的模型中，我们用规则的网格描述布模型，因此，我们认为每个质点 有相同的质量，该质量等于布的总质量除质点的数量。则每个质点所受重力g 为： g = m i g ( 2 1 6 ) 式中m i 为单个质量的重量，g 为重力加速度，是个常量，一般取9 8 。 ( 2 ) 约束反力( p e n a l t yf o r c e ) 约束反力也称反碰撞力，布料与外界物体及其自身的碰撞是碰撞检测的主要 因素。如果不对质点的运动加以约束，就会发生布料与外界物体之间相互穿透现 象。为此，本模型采用约束反力的方法处理它们：当检测到质点与即将穿越某规 p 则表面时时，加入一个约束反力1 彤n a t y ，将质点拉回到正确的表面一侧。对质点 x 和碰撞发生点x 0 ，有： = p 烈。小纠r ) 发生碰撞 不发生碰撞 ( 2 1 7 ) 其中为c p 反碰撞系数，系数越大，碰撞时所产生的反碰撞力越大。表示 矿hyy l ia ， a o 点处的单位法向量，忖。一以0 表示质点x 与碰撞发生点x 0 之间沿方向“乩的 距离分量。 ( 3 ) 阻尼力( d a m p i n gf o r c e ) 第二章拉格朗日能量方程与质子弹簧模型 为了减少质点运动过程中受力引起过度振荡，引入了阻尼力。在动态的布仿 真中，适当的阻尼力对维持系统的稳定性是非常重要的。例如，为了防止两质点 间出现不规则的振动，一个弹簧拉力必须伴随一个稳定的阻尼力。质点运动的越 快，阻尼力越大，可以避免质点过度振荡所导致的布料不真实拉长变形的现象。 通常最简单的阻尼模型如下： 瓦m p i n g = 一白v ( 2 1 8 ) 其中f d a 唧i n 。为阻尼力，为阻尼系数，为一个非负的标量。这个公式的意义是， 所有具有速度的质点都受到阻力的影响，这个阻力与运动速度的方向相反，阻力 大小与速度大小c d 成正比。 这是一个具有实际物理意义的阻尼模型，可以描述一切在粘性介质中低速运 动的阻尼性质。但是，对于布料在空气中运动所受到的影响应该特别考虑；这里 所要的阻尼仅仅指布料内部的能量消耗。直接使用这个阻尼模型也能得到一些好 的效果，比如布料的运动变得比较的平稳等等。但是，一些不好的效果也是显而 易见的：这个阻尼将使整个布料的运动变慢。并且，当阻尼系数c d 较大时，布 料的运动会变得僵硬。 因此，需要对上述模型进行改进。由于实验需要的是表示布料内部的能量消 耗的阻尼模型，可以考虑让弹簧来承担这个消耗项，即让弹簧在运动过程中产生 能量消耗，这样，朱淮冰等【1 8 】提出如下的阻尼模型： 瓦咖= 一c 0 ( v j v ) ( 2 1 9 ) 这里阻尼力是连接质点i 和质点j 之间的弹簧作用在质点i 上的阻尼力，和两 个相连质点的速度差成正比，其中q d ，为阻尼系数。k 和_ 分别为两质点p i 和p j 的速度。这样，质点i 上作用的总的阻尼力就计算如下： = 一吒( v j - v , ) ( f ，j ) e ( 2 2 0 ) 其中e 是所有有连接关系的弹簧集合，其余变量意义如上所述。这个阻尼模 型是目前布料动画文献上广为采用的阻尼模型，我们系统的速度阻尼力也是采用 的以上阻尼模型。在应用上取得了良好的表现，可以有效的提高算法的稳定性， 并增加布料运动的真实感，且计算简便。 第二章拉格朗日能量方程与质子弹簧模型 ( 4 ) 空气阻力( a e r o d y n a m i cf o r c e ) 要实现真实的布料仿真，空气阻力f a e r o 是其中的一个重要因素，本系统在 g p u 实现时考虑的质点数目较多，布料面片较多，计算量也较大，因此把该空 气阻力合并到速度阻尼力上一并计算，节省较多计算资源。 ( 5 ) 用户定义的力( u s e r - d e f i n e df o r c e ) f u s e r 表示用户定义的力，当仿真的时候，为了实现用户交互的效果，可以 为质点人为定义作用力，例如鼠标拉力等，本文实现的时候考虑到这种情况，并 作了用户接口，可以拾取一个或两个质点，实现拖拉布料。 f 。= c m d m ( 2 2 1 ) 其中，c m 为常系数，为3 d 视图中用户鼠标拖动的距离 以上主要讨论了质点在仿真过程所受到的力，在每个时间步长里，都需要对 所有粒子重新进行受力分析，然后让粒子在新的加速度下运动。 因此，当粒子由于碰到硬物而突然改变方向时，容易产生运动上的不连续。通过 在原有模型中加入阻尼系数可以减缓这种运动上的不连续。粒子间的摩擦力，外 界环境的粘滞力都可以用这个阻尼系数来模拟。阻尼力较大，粒子运动较为缓慢， 但是更容易到达平衡状态。阻尼力较小，粒子运动快，容易产生布料穿透硬物的 情况。阻尼力过小还会导致一种极端情况，当大量粒子一起拉着少量位置固定的 粒子的时候，粒子间的距离越来越远，最终导致整个系统“崩溃”。在宏观上表现 为一大块布料，固定住两个相邻角，让它自然下垂，这时候布料就容易撕裂。 经过以上受力分析，基于牛顿第二定律f - - m a ，和相应的数值积分方法，就可 以在一定时间间隔密度下对系统进行仿真演进。至于具体的受力的数值求法和积 分过程请见下节。 2 3 两种物理模型的比较 第二章拉格朗日能量方程与质子弹簧模型 表2 1 两种物理模型特性对照表 特性名称 能量方程质子弹簧 几何空间三维立体纺线网格片 点密度密松 多元二阶o d e 微分 方程类型 显式积分方程 方程 计算量 大中 模型结构 复杂简洁 宏观近似，微观不可 模型仿真效果 宏、微观精确 见 总休来讲基于能量分析的方法对毛线运动的仿真更精确更自然，针对同等规 模的布料，基于能量的方法要比质子弹簧的方法计算规模更巨大。就目前的硬件 水平来说，能量的方法即使通过g p u 加速也远不能实现实时计算，而质子弹簧 的方法在多核c p u 计算上就可以实现实时交互。 通过比较二种方法的计算模型可知，计算量的差别主要两个方面。第一，实 现细节层面不一样。第二，力的求解复杂度不一样。针对细节层面，我们可以看 到，质子弹簧的方法只是把( u ，v ) 点作为最小的受力分析点，我们知道，一个 毛线节由四边形的( u ，v ) 点来控制，而一个( u ，v ) 点又被邻近的多个毛线 节所共享，所以一个毛线节近似最终等于对应了一个( u ，v ) 点，也即质子点。 而在能量的方法中，我们看到，一个毛线节被分成若干段，这些段又被离散化为 参数点，最终的受力分析的基本点就是针对这些参数点的，所以其点阵的规模之 大是相比质子弹簧是可想而知的。 针对求解复杂度，很显然，质子弹簧模型中质子点所受的力只和该质子与 相邻质子的距离相关，且显式可求解，其算法复杂度为o ( n ) 。而能量模型中， 参数点的受力是能量的梯度，且能量的求解需要通过二次积分的方法，最终通过 求解拉格朗日方程组的方法，得到参数点的位置和速度。其算法复杂度为o ( n 2 ) 。 基于以上两原因，才导致了两方法在计算时间上的极大差异。 通过对两种物理模型原理的介绍，我们可以得出它们之间的差异和各自的优 缺点。具体比较项目见表2 1 。从比较结果我们认为，就目前普通p c 硬件的计 算能力来说，普通规模的布料能量方程方法仿真很难实现实时。而基于g p u 硬 件实现质子弹簧模型的实时仿真是完全可能的，且目前已经有了许多在g p u 上 基于c g 语言开发成功的布料仿真系统，但使用最新的c u d a 语言开发的布料 模拟目前还非常少见。最终我们选择质子弹簧物理模型，将弹簧和质子状态数据 第二章拉格朗日能量方程与质子弹簧模型 结构组织为一维线性数组，方便使用c u d a 并行编程语言实现了。且为了表现 毛线的微观结构，我们引入了微观结构的绘制方法，即用b 样条曲线来描述毛线 的编织结构，取得可观的效果，这也是本文的创新处之一。 第三章质子弹簧数值积分过程 第三章质子弹簧数值积分过程 在对布料的各个质点进行受力分析后，还需要对模型进行积分求解，常用 的求解方法有很多种，从物理角度来分有基于力的模型和基于能量的模型。基于 质子弹簧力的模型，根据牛顿第二定律a = f m ，计算出质点p i 的加速度a i 后，列 出偏微分方程，通过数值方法来计算质点在各个时刻的位置和速度。基于能量方 程的方法与基于力的方法原理基本一致，只不过能量是用力矩来计算，而非力， 最终目的是使整块布料的“能量最小化”，此时布料达到平衡状态。 从数值积分角度来分，主要分为三大类：显式的、隐式和将两者混合使用的 混合方法。混合方法将微分方程分离成线性和非线性两部分，分别采用显式和隐 式方法解决，从而能够减少计算工作。 现有的数值积分方法很多，常尉的方法有显式欧拉方法( e x p l i c i te u l e r m e t h o d ) 、v e r l e t 积分以及龙格一库塔方法等，下面将着重介绍这三种方法。 3 1 显式欧拉方法 显式欧拉方法( e x p l i c i te u l e rm e t h o d ) 是最容易实现的数值积分方法之 一。令h 为时间步长。对于初始条件x ( o ) t = x o ，x 在下一时刻t o + h 的值为x ( t o + h ) ， 欧拉方法对于x ( t o + h ) 的计算公式为： x ( t o + j j l ) = x o + i l x f 0 ) ( 3 - 1 ) 显式欧拉方法计算简单，但不够精确、稳定性差，要求时间步长足够小。为 了考察该方法产生误差的大小，首先观察一下一个平滑连续函数x ( t ) 的泰勒级数 展开式： z ( t o + h 一( 伊) + 万h 2 诋) + + 等参+ ( 3 2 ) 可以看出，欧拉积分实际上是取自泰勒级数的前两项，因此，除非从二阶导 数开始以后各项均为0 ，否则欧拉积分方法总会带来舍去误差( 或称截断误差) 。 第三章质子弹簧数值积分过程 该误差项主要是舍去部分中的第一项：( 五2 2 ) 王( 乇) ，于是我们可以将误差记为 o ( h 2 ) 这说明显式欧拉方法是一阶方法。只要h 取得适当小，就能将误差控制在所 期望的允许值之内，当然其代价是计算量的增加和计算效率的损失。 3 2v e rie t 积分法 v e r l e t 积分法的核心思想是用位置偏移来代替速度，在时间步长at 固定的前 提下，v e r l e t 积分法的积分方程如下所示： l 蕾- - 薯- + ( 铲薯) + z 竺 1 ：葺 聊 。3 3 ， 上式中，玉。为质点i 在时刻t 的位置；薯为质点i 在t 一t 时刻的位置；丘质 点当前所受外办的合力( 重力，用户力等) ；m 为质点的质量。这样，每个质点 存储的两个变量变为：当前位置和上一时间步的位置，每次更新位置后，交换 五，x t 的值，保存质点在上一帧的位置。 虽然用x t 一蕾代替v i 并不完全准确，但对于视觉真实性要求不是非常高的应 用，如游戏，这个策略完全可以模拟出真实的布料运动效果。由于该方法不需要 显式的计算速度，因此，。可以通过直接移动质点的位置来计算弹簧内力对运动的 影响，而这并不会影响下一帧积分算法的运行。实验证明：v e r l e t 积分法与e u l e r 积分法相比，具有相同的计算速度，但v e r l e t 积分法却具有更高的精确度，v e r l e t 积分法的局部误差为o ( h 4 ) ，但它的全局误差为o ( h 2 ) ，其中h 是积分的时间步长， e u l e r 积分法的误差为o ( h ) 。因此，v e r l e t 积分法是布料积分算法中一个极为有 效的方法。 3 3 龙格一库塔( r u n g e - k u t t a ) 方法 r t m g e k u t t a 方法在工程上已经使用很久，是一种很有效的计算方法。该方 法在1 9 世纪末由德国科学家c r u n g e 和m m k u a t t 提出的。后来经历了不同程 度的改进和发展。目前较为广泛使用的是四阶龙格一库塔方法( 上面所提到的显 式欧拉方法实际上是二阶龙格一库塔方法) ，又称经典凡叨r u n g e - k u t a t 方法。该 方法的误差项为d ( 厅5 ) ，因此时间步长的取值可以更大一些，以提高计算效率。 第三章质子弹簧数值积分过程 同中点方法一样，这样做的代价是在一个时间步长内要进行多次迭代运算。四阶 龙格库塔方法的思想如下： 对于j = f ( x ，) ，在已知t 时刻的状态，情况下，要求得t + h 时刻的状态x ， 引入四个参数毛，如，屯一，则： 也= 厂( r + 笔岛，r + 兰) 屯= 厂o + 宝如，r + 害) 丸= f ( x + 屯，t + h ) x f + = x + 鲁( 毛+ 2 如+ 2 屯+ 屯) ( 3 - 4 ) 根据该思想，假设质点i 在t 时刻的位置矢量和速度矢量分别为，毫，受力 为，在什h 时刻的位置矢量和速度矢量分别为t + h ，丐，爱力为 t + h 。再引 ，f -vo f + 一， 入四个虚拟时刻状态k l ，l ( 2 ，k 3 ，k 4 ，对应的受力分别为- ，g ， k l ，- ，k 3 ，对应的状 ，七2，七4 态变量为( 蕾“，毫) ，( t 船，毫舵) ，( 墨 ，毫好) ，x i k 4 毫) 。则四阶r u n g e k u t t a 算法可描 述如下： 利用力计算函数求出k l 状态质点受力1 ； j g k 2 + 告譬彳z 叫- + z ，矩二z 求出k 2 状态质点受力2 ； 3 e k 3 = + 告譬，叫- + z 舰z 求出k 3 状态质点受力3 ； 矿叫- + 冬譬膏叫- + z ，竹：z 求出k 4 状态质点受力4 ； 毫“= 毫+ _ h ( 彳1 + 2 f 2 + 2 f 3 + ，；。4 ) ； o m ； 葺帕= + 导( 毫l + 2 毫2 + 2 毫3 + 毫4 ) ； 第三章质子弹簧数值积分过程 3 4 质子弹簧数值积分过程 给定各质点位置及速度初始值 各质点受力清零 l 计算各质点受合力及其微分 上 l计算各质点新的位置和速度 碰撞检测和反馈处理 更新各质点位置和速度值 图3 1 质子弹簧模型求解流程图 为了更好的组织数据流程，方便实验相关参数的设