（计算机软件与理论专业论文）织物模拟中实时碰撞检测方法的研究.pdf

大连理工大学硕士学位论文 摘要 名莫一直备受关注，成为计算机图形学的研究热点。 其应用涉及计算机辅助设计与制造，虚拟手术，电子游戏，服装设计，虚拟现实等诸多 领域。织物建模是织物动态仿真的基础，选择合适的模型对织物模拟的效果和效率有着 决定性的影响，碰撞检测和响应是织物模拟中另一个重要问题。因此，本文对织物模拟 的建模技术和织物的碰撞检测方法进行了讨论和研究。 本文首先采用了质点一弹簧模型对织物进行仿真，利用牛顿经典力学理论对其进行 动力学分析并得到微分方程。通过对欧拉法，中点法，龙格一库塔，v e r i e r 等数值求解 方法的性能和特点进行比较分析，选择快速且简单v e r i e r 方法进行求解，实验表明该方 法速度较快同时具有较高的稳定性。 其次，本文在当织物发生局部形变时，给出了一种改进的质点一弹簧模型，并提出“力 的传播深度这一概念来确定参与计算的质点数量，对织物的边缘质点受力，端点质点 受力和中间质点受力分别进行了讨论。针对不同的应用，通过调整“力的传播深度 来 满足速度和精度的要求。在织物局部形变过程中该模型在保证模拟精度的前提下减少了 参与计算的质点数量，从而减少计算时间，实验结果表明在不减少精度的前提下提高了 运算速度。 为了避免质点一弹簧模型模拟过程中发生不真实的过度拉伸形变，本文介绍了距离 调整和速度调整两种不同的方法，而由于在我们的仿真过程中，我们采用的v e r l e t 积分， 只调整质点的位置，不涉及质点速度，因此我们利用了位置调整法来解决织物的超弹性 现象。 最后，本文利用层次包围盒方法来处理织物的碰撞检测，分别为织物和场景中其他 物体构造a a b b 层次包围盒树，从而将它们之间的碰撞问题，转化为两棵a a b b 层次 包围盒树的遍历和判交问题，解决了织物的碰撞检测和自碰撞检测问题。发生碰撞后， 利用自底向上的方法来更新织物的层次包围盒，在碰撞响应阶段，引用了物理学上的恢 复系数来处理刚体与织物之间的碰撞响应问题，并给出了碰撞响应阶段的推理表达式。 实验结果表明，本文的织物仿真系统能够提供较好的实时性和模拟效果。 关键词：虚拟现实；织物仿真；质点一弹簧模型；碰撞检测 大连理工大学硕士学位论文 r e s e a r c h o fr e a l - t i m ec o l l i s i o nd e t e c t i o no fc l o t hs i m u l a t i o n a b s tr a c t i ng r a p h i c sf i e l d ，c l o t hs i m u l a t i o nb e c o m e sh o t s p o ti nc o m p u t e rg r a p h i c s 1 1 1 ea p p l i c a t i o n r e f e r st om a n yf i e l d ss u c ha sc a d ，v i r t u a ls u r g e o n ，g a r m e n td e s i g na n ds oo n c l o t hm o d e l i n g i st h eb a s eo fc l o t hs i m u l a t i o n , c h o o s i n ga p p r o p r i a t em o d e lh a sg r e a ta f f e c to ns i m u l a t i o n r e s u l t sa n de f j f i c i e n c y 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 ei sa n o t h e ri m p o r t a n tp r o b l e m s ot h i s p a p e rm a k e sd i s c u s s i o na n dr e s e a r c ho nc l o t hs i m u l a t i o na n dc o l l i s i o nd e t e c t i o n f i r s tw eu s em a s s - s p r i n gm o d e lt os i m u l a t ec l o t h ，a p p l yn e w t o ns e c o n dl a wt oa n a l y z e a n dg e tm o t i v a t i o ne q u a t i o n v i ac o m p a r i s o na m o n ge u l e rm e t h o d , m i d - p o i n tm e t h o d ， r u n g e k u t t am e t h o da n dv e r l e tm e t h o d ，w ec h o o s ef a s ta n ds i m p l ev e r l e tm e t h o d ，a n d e x p e r i m e n t ss h o wt h a tv e r l e tm e t h o di sf a s ta n dh a sg o o ds t a b i l i t y s e c o n d ，w h e nl o c a ld e f o r m a t i o nh a p p e n si nc l o t h , t h i sp a p e rp u t sf o r w a r da ni m p r o v e d m o d e lb a s e do nm a s s - s p r i n gm o d e la n du s et h ec o n c e p t t r a n s m i t t i n gd e p t ho ff o r c e t o c o n t r o lt h ec o u n t so fv e r t e xc o m p u t e d w ed i s c u s si nt h r e es i t u a t i o n sa c c o r d i n gt op o s i t i o no f v e r t e xf o r c e d ：e d g ev e r t e xf o r c e d ，i n n e rv e r t e xf o r c e da n dt e r m i n a lv e r t e xf o r c e d i nd i f f e r e n t a p p l i c a t i o n sw e c a l la d j u s t t r a n s m i t t i n gd e p t ho ff o r c e t om a k ec o m p r o m i s eb e t w e e ns p e e d a n da c c u r a c y t l l i sm o d e lc a l ld e c r e a s ec o u n t so fv e r t e xc o m p u t e da n df u r t h e rd e c r e a s e c o m p u t i n gt i m eo nt h ep r e m i s eo fs i m u l a t i o na c c u r a c y e x p e r i m e n tr e s u l t sm a k eg o o de f f e c t s t h a tt h es y s t e m ss p e e di si m p r o v e do nt h ep r e m i s eo fs i m u l a t i o na c c u r a c v i no r d e rt oa v o i d “s u p e r - e l a s t i c i t y ”p h e n o m e n o nd u r i n gc l o t hs i m u l a t i o n w ei n t r o d u c et w o m e t h o d s ：p o s i t i o na d j u s t m e n ta n ds p e e da d j u s t m e n t b e c a u s ev e r l e tm e t h o dw eu s ej u s t a d j u s t sv e r t e x sp o s i t i o n ，s ow eu s ep o s i t i o na d j u s t m e n tm e t h o dt os o l v et h ep r o b l e m l a s t t h i sp a p e ru s e sa a b bb o u n d i n gv o l u m et od e a lw i t hc o l l i s i o no fc l o t h w ec o n s t r u c t a a b bh i e r a r c h i c a lb o u n d i n gv o l u m et r e ef o rc l o t ha n do t h e ro b j e c t s ，s oc o l l i s i o nb e t w e e n c l o t ha n do b j e c t sc a nb et r a n s f e r r e dt ot h et r a v e r s ea n di n t e r a c t i o nb e t w e e nt w ot r e e s 粉e n c o l l i s i o nh a p p e n s ，u p d a t ea a b bv o l u m ef r o mb o t t o mt ot o p t h ep h y s i c sc o n c e p t i o no f r e s i s t a n c ee o e f f i c i e n ti su s e dt od e a lw i t hc o l l i s i o nr e s p o n s e o fw h i c ht h er e a s o n i n gp r o c e s s a n dt h em e t h o du s e dt ou p d a t et h er e a l t i m es y s t e mi sa l s op r o p o s e d e x p e r i m e n t ss h o wt h i s c l o t hs i m u l a t i o ns y s t e mc a ns a t i s f yr e q u i s i t i o n so fp r e c i s i o na n dr e a l - t i m em o d e l i n g k e yw o r d s ：v i r t u a lr e a l i t y ；c l o t hs i m u l a t i o n ；m a s s s p i n gm o d e l ；c o l l i s i o nd e t e c t i o n 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：，丛堑搓拯主塞吐垡撞捡趔友洼数珏窥 作者签名：堡盈日期：塑墨年生月盟日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 作者签名： 导师签名： 日期： 塑塞年坠月j 里日 日期：皇竺量年j 三一月2 l e t 大连理工大学硕士学位论文 1绪论 1 1 研究背景和现实意义 从2 0 世纪8 0 年代以来，随着计算机硬件技术的蓬勃发展和宽带网的迅速普及，虚 拟现实和计算机动画技术成为面向2 1 世纪亟待发展的新兴学科，而对自然界中各种物 体的动态模拟成为虚拟现实和计算机动画领域中的热点问题。模拟仿真技术是指遵循相 似原理( 几何，环境及性能相似) ，用模型( 物理模型或数学模型) 代替实际系统进行实验 和研究【l 】。其基本方法是建立合适的织物力学结构模型，然后利用力学理论进行推导， 从而预测出该织物的三维悬垂效果。现实世界中，织物与人们生活息息相关，由于它具 有高度变形的特点，如何在计算机上有效和逼真地模拟织物的运动一直是计算机图形学 研究的一个极具挑战性的课题。 二维的服装c a d 系统已经广泛地应用于服装设计领域。同时，日益发展的电子商 务也要求研究出快速、逼真的织物模拟算法和研制出合适的织物模拟软件，以帮助服装 企业高效地设计和生产，并把这些产品放到因特网上，使网上购物成为可能【2 】。电子游 戏也是织物动感模拟应用的重要领域，相信拥有生动界面的产品会更有竞争力。此外， 利用织物模拟算法，可以模拟旗帜、跳伞、空中漂浮物等的运动【2 】。 碰撞检测是织物模拟中另一个非常重要的问题，它是基于现实生活中一个普遍存在 的事实：两个不可穿透的对象不可能共享相同的空间区域，其任务是对模型之间的空间 位置关系进行判断，确定模型的空间位置是否有重叠，并在发现重叠时实时地自动报告 重叠的部位。柔性物体在复杂的虚拟环境中进行动画模拟时，与环境中其它物体( 刚体 或非刚体) 的碰撞检测问题在虚拟现实应用中极具普遍性。所以在一个虚拟场景中，为 了模拟的真实性我们必须避免织物和环境中的其他物体相互穿透，为了给出真实的物理 现象或反映，我们不仅要判断物体之间是否发生碰撞，而且还要在发生碰撞的情况下精 确的定位发生碰撞的位置。例如在虚拟试衣系统中，服装面片与人体躯干的碰撞检测问 题。因此，实时且精确的碰撞检测对于增强虚拟环境的真实性和沉浸感具有重要作用。 1 2 国内外研究现状 基于物理的建模是一种具有潜在优势的三维造型和运动模拟技术，尽管计算复杂度 高，但由于能够逼真模拟真实效果，因而得以广泛研究。基于物理特性的布料造型技术 首先对模拟对象进行三角形或矩形的网格剖分。对质点的物理描述一般从受力和能量角 度出发，通过引入质量、力、能量等物理量，将布料各个部分的运动，看成在各种力的 作用下质点运动的结果。采用基于力学的布料模拟技术从质点的空间运动方程入手，通 织物模拟中实时碰撞检澳4 方法的研究 过确定时间序列上的质点的空间位置，找到质点随时间变化的运动轨迹，来模拟布料的 行为状态。这方面的研究工作有： t e r z o p o u l o s 等人p 4 j 应用弹性力学中的薄板弹性变形方程，把布料的变形描述成布 料内部组织抵抗形变产生的弹性力、外界作用力和阻尼力共同作用结果，提出了弹性变 形模型，并且采用了半隐式数值求解方法。 t h a l m a n n s 副领导的m i r a l a b 也发展了弹性变形模型用于虚拟演员的服装模拟和3 d 时装辅助设计，并且对布料的碰撞检测及其优化问题也进行了讨论。 b r e e n 等人【6 ，7 】研究了不同布料的力学特性，提出了布料模拟中质点系统的概念。质 点系统使用由弹簧相互连接的一组质点来描述布料的结构和状态，用系统能量最小化方 法求解各个质点的位置。 p r o v o t i s , 9 】采用经典的质点弹簧模型模拟受约束条件下的柔性布料。布料被离散为 规则的四边形网格，网格交点为质点，质点与质点之间用弹簧相连，运用牛顿运动定律， 建立质点系统的运动方程。该模型计算简单，效率高，速度快，甚至能达到实时效果。 不足之处是模型不够精确，无法真实表现织物的物理性能，对大规模的布料仿真计算效 率较低。 b a r a f f t l o l 研究工作的重点在微分方程的求解方法上。他采用隐式欧拉方法求解方程， 使时间积分步长增大，减少了整个仿真过程的计算次数，系统收敛速度快。隐式迭代方 法比显示求解更适合于柔性布料的动态仿真与模拟，但隐式迭代法需要求解巨型稀疏线 性方程组，计算复杂且耗时，很难达到实时性要求，对计算机的硬件要求很高。 基于质点一弹簧物理模型的布料仿真，在数值方法方面已经有很多研究成果。2 0 0 1 年，v a s s i l e v 建立了基于速度的过程，即改变粒子速度而不是粒子的位置，从而使弹簧 不会被过度拉伸。2 0 0 2 年，b r i d s o 也提出了一种相似的方法，利用作用在粒子上防止弹 簧产生过度伸长现象的推力来达到目的。1 9 9 9 年，d e s b m i l 【1 1 】提出了隐式方法的近似形 式，使用了一个用于质点一弹簧系统的近似的能够求逆的线性系统矩阵，这样做的结果 是使用简单的矩阵向量进行乘法运算并减少了每个步长的计算时间，其缺点是矩阵的规 模随着粒子数的增加而呈平方增长趋势。y a n g 1 2 】对d e s b r u n 公式进行了改进，进一步简 化了系统。d e s b m n 模型和k a n g 模型都是通过降低对象的物理精确性而减少运算时间。 2 0 0 0 年，v o l m o 提出了一个不降低模拟质量的改进，他在求解线性系统的系统矩阵时进 行了优化。2 0 0 0 至2 0 0 1 年，e b e r h a r d t ，e t z m u s s 和h a u t h 也对布料仿真的数值方法进行 了研究，提出了很精确的仿真算法，其中i m e x 方法( 显式隐式混合方法) 便是其中的一 种。2 0 0 5 年s e u n g w o oo h 等提出用一种新的隐式积分方法进行布料模拟，该方法不用 引入额外的阻尼力即可达到稳定的效果。2 0 0 4 年k i m m e r l e 1 3 】提出了一种用于可变形物 大连理工大学硕士学位论文 体的随机碰撞检测方法，大大提高了碰撞检测的效率。2 0 0 3 年f u h r m a n n 掣1 4 】提出了一 种快速的交互式布料模拟技术，并且在自碰撞检测方面做出了重要贡献。 以上都是利用已有的织物模型，微软研究院与浙大c a d & c g 实验室合作研究了一 种新的织物模型半刚性样条模型【2 】。该方法在处理窗帘等悬垂物体时具有明显的优势， 但是无法应用到已有的模型中。 1 3 本文结构 本文以织物为研究对象，利用经典的质点一弹簧模型对其仿真，并在模型的基础上 进行了织物实时碰撞检测的研究和讨论。主要包括以下内容：织物模拟的基础理论，对 织物建立质点一弹簧模型和进行动力学分析，利用数值积分方法对所建的动力学方程求 解来模拟织物的形态，最后介绍了在织物虚拟环境中碰撞检测的问题。 本文章节安排组织如下： 第一章介绍了织物模拟的研究背景及其发展历史和当前国内外该领域的研究现状。 第二章介绍了经典的质点一弹簧模型理论，对模型受内力和外力情况进行分析，建 立了织物模拟的动力学方程并介绍求解织物动力学方程的数值积分方法，通过比较各种 数值积分方法的比较，选择了合适的方法来求解微分方程并给出了算法流程。 第三章在织物发生局部形变时提出了一种改进模型，对织物发生局部形变时进行了 详细的分析，提出了“力的传播深度 这一概念来控制和确定参与计算的质点，针对受 力质点位置的不同分别讨论了“力的传播深度 的定义方式，给出了改进后模型的算法， 最后对织物模拟中“超弹性”效应进行了处理。 第四章介绍了织物模拟中的重要问题碰撞检测，介绍了利用层次包围盒a a b b 方法 来对织物进行碰撞检测，介绍了织物的自碰撞检测方法和基本几何元素的碰撞检测，最 后讨论了织物检测到碰撞后的碰撞响应。 第五章给出了系统的实现和和对实验结果的分析。 最后给出结论和展望，对本文的研究工作进行了总结性论述，指出了系统中的一些 缺陷和不足，最后指出了今后进一步的工作和对未来的发展进行了展望。 织物模拟中实时碰撞检测方法的研究 2 质点一弹簧模型理论 2 1 织物模拟中的建模方法 织物建模是研究的基础，许多计算机图形学研究者和纺织学者从最简单的织物形状 和运动形式出发，利用不同的方法从不同角度对织物仿真技术进行了广泛的研究，根据 其模拟过程所采用的方法，织物建模技术主要可分为3 类：几何模型，物理模型和混合 模型。 2 2 1几何模型 早期由于硬件环境的限制，计算量非常大的基于物理的建模方法很难实现，因此几 何方法得以广泛采用。几何方法不是根据动力学表现织物的运动特性，而是用几何方程 表示织物的一些几何特性，例如折叠、褶皱等【1 5 】。1 9 8 6 年，美国贝尔实验室的j e r r yw e i l 提出了一种基于几何的织物造型方法【1 6 】，他把织物悬挂在一些约束点上，基于悬链线计 算出织物自由悬挂时的形状。w e i l 之后a g u i 等提出了一种表示袖子的几何方法，他们 用一系列圆环表示袖子，利用强迫相邻粒子间的距离为初始设定距离来生成褶皱。h i n d s 等也提出了一种针对制衣生产自动化的衣料的几何方法，这个方法把织物定义成不同的 碎片，每个碎片有唯一的边界，曲面细节通过几何插值生成。n g 等提出的几何方法用 一系列由两个层组成的交叉部件表示织物，用正弦曲线生成褶皱【1 7 1 。 几何法的优点是效率极高，计算开销非常地小。它的缺点也很明显，表示的真实感 不够，更为糟糕的是，每种方法都只适用很小的特定范围，不能表示动态的织物形态。 2 2 2 物理模型 近几年，研究者们更多地用基于物理的方法去模拟织物，他们提出了各种物理模型 来对织物进行变形仿真模拟。基于物理的建模通常通过引入质量、力、能量等物理量， 将织物各个部分的运动看成各种力的作用下质点运动的结果【2 】。对各种物理模型进行介 绍如下。 ( 1 ) 质点网格模型 这种织物变形的物理仿真模型由f e y n m a n ! 瞎】提出。f e y n m a n 算法得到的是布在重力 等外力作用下自然下垂时，达到稳态的图形。f e y n m a n 的出发点是当织物的总能量达到 最小值时，才能达到稳定。在应用中，这种模型不如质点一弹簧模型逼真，复杂度较高， 并且表现织物的能力也较弱，可以说该模型现在应用价值不大。 ( 2 ) 粒子模型 4 大连理工大学硕士学位论文 该模型由b r e e n 6 1 等提出，他将织物的经线和纬线的交点看作一个粒子。整块织物 是相应粒子的集合。在悬垂过程中，粒子与粒子之间以及粒子和周围环境之间存在着相 互的物理作用。与其它物理模型比较，从离散介质的角度看，粒子模型是最接近织物本 质的一个模型，各个能量表达式依靠实验确定，因而它的模拟比较逼真。但其缺点也很 明显：计算量庞大；确定粒子间相互作用的能量表达式通过复杂的实验确定；表达式的 确定很难说是完全准确客观的，因此如何反映织物材料特征还有必要进一步研究。 ( 3 ) 质点一弹簧模型 x p r o v o t 8 】建立了一个经典的质点一弹簧模型。他将织物设想为一个质点的集合， 质点之间的相互关系归结为质点问的弹簧作用。弹簧分三类：结构弹簧、剪切弹簧和柔 性弹簧，各个质点的运动符合牛顿定律。质点一弹簧模型简单易用，算法容易实现，计 算效率较高，因而应用较广。但实际上，该模型对织物材料特性表述简单、不完全，反 映材料特性比较困难。从理论上说该模型完全可以统一在同一个表达形式下，而且对材 料特性参数也可以作更多灵活统一的表达，使等效比拟更真实。这个工作有待进一步进 行，实现这一点，将有易于算法的计算机实现，使用者也只需要通过表达参数的调整就 可以达到多种多样的模拟效果。本文采用的就是基于质点一弹簧模型。 ( 4 ) 弹性变形模型 从连续介质力学的角度考虑物体的变形，t c r z o p o u l o s 3 】等提出了基于物理的弹性变 形模型。弹性变形模型成功地模拟了织物等一系列变形曲面。但由于其采用的有限差分， 所以要通过将非线性的常微分方程转化为线性的代数方程组，求解巨型稀疏线性方程方 能得出结果，由于计算量非常大，从而阻碍了这种方法在实际中的应用和推广。 ( 5 ) 波传播模型 a 0 n o 【1 9 1 应用弹性理论和d a l e m b e r t 原理建立了一个褶皱传播模型。在此模型中， 织物被看作传播褶皱的介质模型中也可以考虑各向异性和粘弹性。由于模型只是模拟 褶皱在布匹中的传播，而不是模拟织物的悬垂等现象，所以其应用范围非常有限。因方 程不复杂，故计算效率较高。 ( 6 ) 空气动力模型 以往模拟织物在风中的动态效果，都是预先设定风力在织物上的分布，但这样不能 处理风力场和织物运动的相互作用。与此不同，l i n 9 1 2 0 j 等提出一个空气动力学模型，该 模型涉及的流体是无旋、无粘、不可压缩的流体。空气动力学模型使得织物在流体中的 运动仿真更逼真。但是它的应用范围仅限于模拟织物在流场中的变形，计算量是极其巨 大的。 ( 7 ) 有限元模型 织物模拟中实时碰撞检测方法的研究 从宏观角度把织物看作连续的介质，静态变形用有限元方法模拟也就是自然的工程 思想。jrc o l l i e r l 2 ”等使用由薄膜单元和板弯曲单元叠加成的平面壳单元计算织物的悬 垂；lg 锄等建立自己的本构关系，使用通常的扁壳单元计算织物的悬垂；有限元模型 从连续介质的本质上计算织物的变形，该模型更真实，而且其本构关系的表达没有粒子 模型复杂，计算效率较高。这种方法存在的问题是：要求非线性变形的理论描述必须准 确，单元的选取一定要适当；由于对不同织物材料特性描述的不准确，必定带来结果的 不准确：不能满足实时的要求。 2 2 3 混合模型 纯物理方法的计算量非常大，在模型规模比较大时要取得实时效果极其困难。而几 何法等一些不需要求解动力学方程的方法计算非常简便。因此，为了得到实时的织物模 拟效果，很多人考虑采用物理方法与几何方法相结合的算法，这样既得到了物理方法的 真实感，又可使计算开销降低。一般的做法是，采用一个粗疏的网格作物理计算，然后 用几何方法或者纹理等方法表现细节，或者，把织物分成几个部分，不同部分采用不同 的算法。 r u d o m m 捌首先采用几何与物理相结合的方法来模拟织物。他提出计算性的几何方 法，生成了一系列3 d 的多边形，从而给出一块悬挂于几个固定点的织物形状的大致估 计。k u n i i t 2 3 】提出了一个采用奇异性理论模拟衣服及褶皱的技术，该技术是基于几何方 法和基于物理方法的混合。o s l l i t a 和m a l ( i n o u c l l i 【2 4 j 提出用几何方法在粗疏的粒子系统上 表现褶皱等细节。h b v m t 2 5 j 贝i j 用纹理技术表现细节以得到具有真实感的画面。 虽然如上所述，混合建模技术取得了一些成果，但无论是从织物模拟范围而言，还 是从几何技术与物理技术相结合的角度而言，这种建模技术都仅仅是初级阶段，远没有 达到人们所预期的目标。 2 2 质点一弹簧模型概述 当前织物的特性已经通过很多种方法得到描述和模拟。其中，用质点一弹簧模型描 述织物行为被证明是非常有效的。这个模型基于物理学的规律，即物体在受到力的作用 时将如何表现。这些力包括重力、空气或者风的阻力和摩擦力。控制织物行为的最基本 的法则是牛顿第二运动规律，它描述了物体的加速度，作用于物体上的力以及物体的质 量之间的关系。由于可以很方便的应用物理学定律将织物的运动状态描述为受力之后的 形变，因此，质点一弹簧模型在织物模拟的众多方法中作为一种行之有效的造型方法。 在质点一弹簧模型中，模型被视为由质点和弹簧组成的一种非连续的结构：每一个 质点和每一条弹簧，都将得到分别的处理。根据织物的特性及其在真实世界中的表现， 大连理工大学硕士学位论文 质点一弹簧模型可以较好地模拟出织物的固有特性。织物中的线在一定限度内可以被拉 长或者放松，因此可以用弹簧来近似模拟；织物上的点可以被认为是一个质点，每一个 质点都有一个3 d 位置、方向和速度，这三个矢量可以通过作用于质点上的所有作用力 计算得出其具体数值。质点和弹簧一起形成了一组顶点和矩形网格( 也可以是三角形网 格) 。这些顶点和矩形构成整块织物的形状，顶点之间的张力是模拟织物的基本。通过 模拟织物内部的作用力，使得模拟不同类型的织物成为可能，同时，织物的形态也会受 到外部作用力的影响，织物内部的张力加上外部作用力将使织物发生形变。通过使用这 样一个模型，当织物上一个质点的平衡被破坏时，因为所有的质点都通过弹簧相连，所 以扰乱将通过弹簧传递到其他质点。在质点一弹簧模型中，代表不同织物的弹簧的弹性 系数有很大区别。因而可以通过变换弹簧的弹性系数，模拟不同材质织物的不同形态。 2 3 织物的质点一弹簧模型描述 x p r o v o t 8 】提出的质点一弹簧模型首先把织物划成若干网格，每个网格的节点都是 一个模型的质点，每个质点通过弹簧与其临近的质点相连，假设这些弹簧没有质量且长 度不为零。其中弹簧被分为三类：结构弹簧，剪切弹簧，弯曲弹簧。结构弹簧是为了保 持质点间初始状态时的距离。剪切弹簧是为了防止织物在自身平面过度和不真实的变 形，而给织物的一个剪切刚性。弯曲弹簧是为了防止织物弯曲。三种弹簧产生的力分别 定义为，k 、瓦哪、k 。具体构成如图2 1 所示。 己：椿气 ( a ) 弹旋矮点攒穗( 1 哆端构搏瑟( c ) 翦切弹鬻( d ) 弯曲弹瑟 图2 1 质点一弹簧模型 f i g 2 1m a s s s p r i n gm o d e l 在采用质点一弹簧模型时，可用无向图中的顶点代表布料离散后的质点，与顶点相 连的边代表质点问的弹簧。该无向图可表示为对称阵，对应第f 行( 或列) 中元素的和即 为与第f 个质点相连的弹簧数量，为表示方便，将该行中不为零的元素集合定义为必，) = ( 订，讫，功，从而定义了与其相关联的质点。由前面质点一弹簧模型的定义可看出，质点 一弹簧系统组成的图不是一个完全连通图，存在大量稀疏的边，若直接存储该矩阵显然 会浪费大量存储空间，因此在许多应用中常采用邻接表来存储质点和弹簧的数据，这样 织物模拟中实时碰撞检测方法的研究 可以不用区分面模型和体模型，同时可以处理由于所模拟对象的结构或质量不均匀而引 起的模型中弹簧和质点的分布不均匀的复杂情况，从而保证了建模的通用性。但对于本 文所研究的布料面模型，由于我们已经假设质点和弹簧的分布相当规则，不存在由于布 料密度不均匀而引起的质点和弹簧分布的不均匀性，因此很容易对所有质点和弹簧进行 有规律地编号，从而使问题进一步得到简化。 2 4 质点一弹簧模型的动力学分析 2 4 1 质点一弹簧点模型的内力分析 在一个给定时间步a t 内，任意一个弹簧质点的从t 。时刻起的位移户( ，) 可以看成匀加 速运动，运动轨迹方程如公式( 2 1 ) 。 声o ) = 户( ，o ) + 哥o o 弦+ 去舀，2 ( 2 1 ) 其中户( r o ) 、哥( f 。) 、云分别是质点的初始位置，初始速度和加速度。加速度云可以 看作是随时间变化的动态系统质点的运动，由n e w t o n 第二定律确定，如公式( 2 2 ) 。 m a 一：所学：瓦鼬( 声，f ) + 瓦删( 户，r ) ( 2 2 ) 2 所万2 ，砌【，f ) + ，i n t 聊耐【， lz z ， 式中兄舭( 户，f ) 表示质点所受外力，瓦删( 声，d 表示，位移声是时间f 的函数。 ( 1 ) 质点弹力 在弹簧质点模型中，惟一的内力是弹簧的弹性变形力。本文利用h o o k c 定律来计算弹 簧的任意质点所受的弹性变形力磊恤，如公式( 2 3 ) 。 = 删+ 瓦。+ 磊a i o n ( 2 3 ) 其中，各类弹簧施加弹力计算如公式( 2 4 ) ，( 2 5 ) ，( 2 6 ) 。 k = 一口盯( 0 霉- e ) ( 2 4 ) i i - a = l 或m k = 一岛( 幅一ei l ) ( 2 5 ) i # - a = m l l 篼w + l 瓦洳= 一磊( 1 l 置- ei i ) ( 2 6 ) l i - a = 2 或2 m 其中，岛，锄分别为结构弹簧，剪切弹簧，弯曲弹簧形变系数。i i 霉一霉。为形 变后质点f 句之间的距离，乇为质点i ，歹没有发生形变的距离。 由于现实中的织物的弹性系数并不是线性的，是根据不同的变形程度，弹性系数呈 大连理工大学硕士学位论文 曲线上升的，因此本文对于各种织物的三种弹簧发生形变的不同阶段，根据k a w a b a t a e v a l u a t i o ns y s t e m 提供的织物各种弹性系数随形变的变化曲线，进行了采样，然后将采 样值根据本系统中三种弹簧的不同形变长度区间构造分段函数，用来实时计算弹簧对质 点的弹力，进一步提升了织物内力的仿真效果。 ( 2 ) 阻尼力 质点弹簧模型可以被看成是一个震动系统，在现实中任何震动系统都会受到阻尼力 的作用，在阻尼力与恢复力的作用下的震动形成了阻尼振动。由于织物上的质点运动速 度不大，所以质点的阻力根速度v ( t o ) 成反比，如公式( 2 7 ) 。 2 5 k 肋幄= 一万( f o ) ( 2 7 ) ，幽。唧智2 一，何【b j l 么， 其中7 是阻尼系数，铲( 岛) 可以通过哥( ，o ) = v ( t o 一f ) + 五( f o - a t ) a t 得出，由此可知质 点运动得越快，阻尼力越大，以此避免质点过度振荡所导致的织物不真实地拉长变形的 现象，以及避免了的弹簧质点的长时间振荡。 2 4 2 质点一弹簧模型的外力分析 ( 1 ) 重力 任意质点脚重力的计算，如公式( 2 8 ) 。 名咖= m ( 2 8 ) ( 2 ) 摩擦力 当织物发生位移时，与之接触的周围其他物体对织物产生摩擦力，由于最大静摩擦 力系数与滑动摩擦力系数相差很小，本文使用滑动摩擦力描述织物与物体之间的摩 擦力露商。，如公式( 2 9 ) 。 r 幽= 一(29n,u ) ，箭c 妇。= l z j 其中霄为垂直于表面的压力，为摩擦系数。 ( 3 ) 空气阻力 空气阻力是织物动态模拟中不可回避的一种外力，也是一种决定织物动态模拟形变 的一种外力，计算方法如公式( 2 1 0 ) 。 瓦一= 丢c p s c l 耐吲： 其中，c 是空气阻力系数，可按照风速阻力系数选定；p 是空气密度， 值；s 是质点迎风面积【2 6 1 。 ( 2 1 0 ) 通常为确定 织物模拟中实时碰撞检测方法的研究 2 5 数值积分方法 2 5 1织物模拟中数值积分方法概述 粒子系统将织物表示为质点的集合。织物的表面形状由相邻粒子间的几何关系来表 示，力学行为由粒子间的相互作用力表示，它取决于粒子的相对位置和速度的变化。通 过对该系统建立普通微分方程，用数值积分法对其求解可实现织物的仿真。现有的数值 积分方法很多，选择积分方法时，性能是需要首先考虑的问题1 2 7 1 。 适用于布料模拟的数值方法总的来说可归结为两大类：显式的和隐式的。也有人提 出了混合方法，将微分方程分离成线形和非线形两部分，分别用显性和隐性方法来求解， 从而能够相应减少计算工作。下面分别对显式积分，隐式积分和混合方法进行简单的介 绍。 ( 1 ) 显式数值积分( e x p l i c i tn u m e r i c a li n t e g r a t i o n ) 强调真实感，系统时间步长要小， 每步需要作的工作少，但由于时间步长小，导致迭代次数多。 ( 2 ) 隐式数值积分( i m p l i c i tn u m e r i c a li n t e g r a t i o n ) 可以使用较大时间步长，减少迭代 次数，能够产生精确的效果，并保证系统的稳定性，能够快速地收敛于平衡状态，但是 隐式解法的实现涉及求解巨型稀疏线形方程组，计算的复杂性和工作量远远高于同阶的 显示方法，要达到真正理想的实时效果，对硬件性能提出较高的要求。 ( 3 ) 混合方法( i m p l i c i t e x p l i c i ts c h e m e s ) 综合显式和隐式积分的优点，扬长避短，但 仅适用于能够将微分方程分离成线形和非线形的系统。 2 5 2 织物模拟中常用的数值积分方法 ( 1 ) 隐式积分 隐式积分认为粒子的位置关系是有联系的，这些粒子作为一个系统在同一个时间步 长内同时求解。理论上讲，隐式求解法在织物动感模拟中能使系统保持稳定性，同时能 快速使系统趋于平衡，因此对于织物模拟的多数情况下它们都显示出高效性。然而隐式 法的实现涉及求解巨型稀疏线性方程组，计算的复杂性和工作量远远超过同阶的显式方 法，并需对系统状态及算法所需的状态进行存储，要达到真正理想的实时效果，对计算 机的硬件性能要求很高。在实践中，隐式法存在着局限性。另外隐式方法很难正确的进 行编码也是它存在的问题，这也是通常人们会选择显示积分方法的原因。 ( 2 ) 显式欧拉法 欧拉法是实时模拟的常用数值求解方法，其思想是用差商代替了微商，用一种近似 的方法来进行数值计算。 设一阶微分方程的初值问题如( 2 11 ) 。 大连理工大学硕士学位论文 j y 7 = 厂( x 9 ( 2 1 1 ) i 厶11 j 【y ( x o ) = y o 式中：f ( x ，y ) 是已知函数，y 。是给定初试值。求该初值问题的数值解法，就是寻求 解函数y ( x ) 在一系列离散点x l x 2 x n x n + l 上的近似函数值y l y ( x 1 ) ， y 2 y ( x 2 ) ，儿y ( x 。) ，y 剃y ( + 1 ) ，式中；h = k l 一是等步长，( n = o ，1 ，2 ) 。 令y ，( x ) y ( x + h ；- ) - 一y ( x ) ，则有：y ( x + h ；- ) - 一y ( x ) 厂( x ，y ) ，取x - x n ，则有： 月刀 y ( x 打+ 1 ) y ( x 。) + h f ( x ，y ( x 。”。 当n = o 时，由于y o = y ( x o ) 已知，有：y ( x 1 ) 留y o + h f ( x o ，y o ) = y l 。 一当n = l 时，将y l 代入，有：y ( x 2 ) y 2 = y l + h f ( x l ，y 1 ) 。 以此类推可得公式( 2 1 2 ) 。 y ( 矗“) 儿+ l = y 。+ h f ( x 。，y 。) ( 2 1 2 ) 下面用泰勒展开来讨论显欧拉公式的局部截断误差。 1 2 将y ( x 州) 在i n 处作泰勒展开，则有：y ( 毛+ 1 ) = 灭而) + 砂( ) + 鲁y 。( ) + 。 二 而y ( x 州) = y ( 矗) + h f ( 矗，y ( x 。) ) = y ( x 。) + h y 7 ( x 。) ，其中元+ l 是当以为准确值( 即 儿= y ( x 。) ) 时得到的y ( 矗+ 。) 的近似值。 l 2 则局部截断误差为：】 ：，+ l = y ( x 州) 一只= 冬y ( x n ) + 。 二 在弹簧质点模型中，应用显式欧拉法有公式( 2 13 ) 。 i 口o + ，) = f ( ，) 1 l , 1 ，o + ，) = ，o ) + a t 口o + r ) ( 2 1 3 ) l p ( f + f ) = p o ) + a t v ( t + ，) 其中是质点的质量，p ，a ，f 分别是质点的位置，速度，加速度和所受合力， a t 是时问步长。显式欧拉方法计算简单，但不够精确稳定性差，要求时间步长足够小。 由上述分析可以看出，欧拉积分实际上是取自泰勒级数的前两项，因此，除非从二 阶导数开始以后各项均为0 ，否则欧拉积分方法总会带来舍入误差( 或称截断误差) 。该 z 2 误差项主要是舍去部分中的第一项冬y ( 矗) ，因此我们可以将误差记为o ( 办2 ) ，这说明 么 欧拉方法是一阶方法。只要h 取得适当小，就能将误差控制在所期望的范围内，同时将 导致计算量的增加和效率的降低。可以说欧拉方法是最简单，易于实现，单步计算速度 织物模拟中实时碰撞检测方法的研究 非常快。在一个计算步中每个粒子的状态都是独立计算的，计算的并行性也很好。但是， 根据线形微分方程理论，当弹簧原长降为o 时，就退化成线形方程了，4 r 存在一个最 大的临界值瓦，一旦4r 超过瓦，方程就会病态而失稳。 ( 3 ) 显式中点法 在方程( 2 1 1 ) 中用向后差商代替微商有：y ( x ) - y _ ( x 一- h ) 厂( x ，y ) ，取x - ：x n + 1 得： y ( 矗+ 1 ) y ( 以) - t - h f o n + ly ( 矗+ 1 ) ) ， 令以y ( x 。) ，y 槲y ( 矗+ i ) ，可得欧拉公式 儿“= 儿+ h f ( 矗+ ，y 州) ，该式右端含有未知的y 州，不能直接使用，必须先用显示公式 预测出第一个以。，再用公式迭代得公式( 2 1 4 ) 。 蒜o 。嚣+ 抓h f ( x n + l 一如，c 脚 2 ， c 2 m ， 【y 等 = 虬瑞) 1 一。 。 下面用泰勒展开来讨论显欧拉公式的局部截断误差瓦+ ，的首项为一冬y ( x 。) ，即这 也是一种一阶方法。 比较显示中点法和欧拉方法的局部截断误差，可以看出将两种方法做算术平均即可 消除