（计算机应用技术专业论文）柔性物体仿真中冲突检测与响应技术的研究.pdf

摘要 摘要 最近几年，柔性物体仿真成了人们感兴趣的研究课题，其中的一个难点是冲 突检测与响应问题。这不仅仅是因为它会影响织物的真实感显示，而且，冲突检 测与响应往往是柔性物体仿真中的瓶颈，它般要占总计算时间的一半以上。因 此，如何获得简单而有效的冲突检测与响应算法成为了人们的研究重点。 本文首先从研究柔性物体仿真中冲突检测与响应技术的基本问题入手，然 后，提出了一种柔性物体与刚体以及柔性物体自身的冲突检测与响应算法，并且 充分利用图形学、计算几何等学科的理论束提高算法的效率。最后，在微机上实 现了该算法，并对结果进行了简单分析。 在上述研究的基础上，文中对冲突检测与响应技术中的难点：冲突处理的 致性、多重冲突等问题进行了一定的探讨，提出了个人的看法并介绍了其他人在 这方面的研究。 关键词：柔性物体仿真冲突检测冲突响应 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，t h es i m u l a t i o no ff l e x i b l eo b j e c th a sb e e na ni n t e r e s t i n gr e s e a r c h t o p i c ，t h e r e i n t o ，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 ni s s u e o nt h eo n eh a n d ，i tm a y e x a c ta ni m p a c to nt h ed i s p l a yo fr e a l i s m o nt h eo t h e rh a n d ，i ti su s u a l l yt h eb o t t l e n e c k o ft h es i m u l a t i o no ff l e x i b l eo b j e c t ，w h i c ha c c o u n tf o rm o r et h a n5 0p e r c e n to fe n t i r e t i m e t h e r e f o r e ，h o wt os e c u r es i m p l ea n de f f i c i e n tc 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 a l g o r i t h mh a sb e c o m e ar e s e a r c he m p h a s i s f i r s t l y ，t h i sp a p e rr e s e a r c h e s t h eb a s i c p r o b l e m s o fc o l l i s i o nd e t e c t i o na n d r e s p o n s ei nt h es i m u l a t i o no f f l e x i b l eo b j e c t ，a n dt h e np r e s e n t sac o l l i s i o nd e t e c t i o na n d r e s p o n s ea l g o r i t h mb e t w e e nf l e x i b l eo b j e c ta n dr i g i do b j e c ta n db e t w e e nf l e x i b l e o b j e c ta n df l e x i b l eo b j e c t t h e r e f o r e ，w eg r e a t l yi m p r o v et h ee f f i c i e n c yo fa l g o r i t h m b yu t i l i z i n gt h et h e o r yi fc o m p u t e rg r a p h i c sa n dc o m p u t a t i o n a lg e o m e t r y f i n a l l y , w e i m p l e m e n t t h ea l g o r i t h ma n dm a k ea s i m p l ea n a l y s i so f r e s u l t s a f t e rt h ea b o v es t u d y ，t h i sp a p e rd i s c u s s e st h ei s s u eo fc o l l i s i o nd e t e c t i o na n d r e s p o n s e ，f o re x a m p l e ，c o l l i s i o nc o n s i s t e n c y , m u l t i c o l l i s i o ne t c ，p r e s e n t s a u t h o r s o p i n i o n sa n dj n t r o d u c e so t h e r r e l a t e dr e s e a r c h k e y w o r d ：f l e x i b l e o b j e c t s i m u l a t i o nc o l l i s i o nd e t e c t i o nc o l l i s i o n r e s p o n s e 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容外，论文中不 包含他人已经发表或撰写的研究成果：也不包含为获得西安电子科技大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所作过的 任何贡献均已在论文中作了明确的说明并表示了致谢。 本人签名：i 墨遭皇受 同期：z p o j ，旷 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期问论文工作的知以产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用复印、影印、缩印或其它手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：j 长口疑峙r 期： 。；陟 导师签名：善蛆 日期：兰竺生l j ，丝 第一章绪论 ! 第一章绪论 1 1 柔性物体仿真的研究现状 最近几年，柔性物体仿真成了人们感兴趣的研究课题。柔性物体仿真不仅包 括人体衣服的动画，还包括旗帜、窗帘、桌布等的动画。柔性物体仿真的一个特 殊应用领域为时装设计，它将改变传统的服装设计过程，让人们在衣服做好之前 就可看到服装的式样和试穿后的形念。 在图形学领域，关于柔性物体特性的研究，可以追溯到5 0 年代，但出于当 时的计算机硬件根本就不支持柔性物体的处理，故早期的计算机绘图仅限于绘制 和模拟刚性物体。随着计算机硬件和计算机图形学的快速发展以及c a d c a m 应 用领域的不断拓展，对柔性物体模拟的研究逐渐吸引了大量学者的注意力。8 0 年 代中期，j n i s s e l s o n “。在g r a p h i c si n t e r f a c e 和c o m p u t e rg r a p h i c s 上提出的 “c o m p u t e rg r a p h i c sa n d t h ef a s h i o ni n d u s t r y ”以及“c o m p u t e r g r a p h i c si nf a s h i o n ” 的两篇论文开创了对柔性物体走向时装工业的新局面。 8 0 年代术，许多学者运用几何、物理、混合三种技术对柔性物体进行了大量 的研究。总体来晚：几何技术不考虑服装的物理属性，只采用相应的几何变形来 模拟服装，其特点是运算速度快，但难以描述服装的内在特性，仿真效果较差； 物理技术对服装进行三角、网格或粒子划分，然后对服装进行能量、受力分析， 该方法能较真实地模拟柔性物体的特性，但运算速度较慢；混合技术综合了几何 技术和物理技术的优点，通常采用几何技术确定服装的粗略外型，然后使用物理 技术来处理其结构。由于物理技术不但能反映柔性物体的外形特征，而且能对柔 性物体的内部结构进行深入分析，可得到比较真实的模拟效果，因此，在迸一步 的研究过程中，该技术逐渐成为研究柔性物体的主流。著名学者c f e y n m a n 。“、 d 。t e r z o p o u l o s ”3 和d e b r e e n ”3 等人先后分别提出了柔性物体的能量、力学和粒子 三种典型模型，奠定了人们运用物理技术对柔性物体进行研究的模型基础。 进入9 0 年代，基于物理技术的柔性物体研究模型和算法更是层出不穷，大量 学者在三大研究模型的基础上对柔性物体的建模、变形约束、冲突检测与处理提 出了大量的研究模型并实现了相关的算法。再加上许多商家和基会组织的参与， 形成了不少柔性物体方面的产品。 采用物理技术对柔性物体进行模拟仿真的基本思想是：首先将柔性对象分层， 然后再将层划分为相应的网格( 三角形、四边形等) 或粒子，在此基础上，运用 不同的公式集来表示网格或粒子的状态( 位置、形状、能量、受力等) ，并采用相 应的公式计算其不同时刻的新状态值，最后通过冲突检溅、自检测方法处理服装 !柔性物体仿真中冲突检测与响应技术的研究 的特性，以达到预期的模拟效果。 在物理技术领域。近期的研究通常基于以下三类：能量模型、力学模型和粒子 系统模型。能量模型对网格的顶点运用能量公式进行计算，并在特定的顶点上获 得一个最小能量状态，并依次推算出柔性物体的整体外形。该类模型主要适用于 柔性物体的静态模拟。该方面的典型代表有：o k a b e 工作组”1 、n g 工作组”1 等。 力学模型对网格的顶点运用力学公式进行分析，并对网格进行变形处理，再进行 数字化集成获得各个时刻的位置及变形信息。这个模型可适用于柔性物体的动态 模拟。浚方面的典型代表有：a o n o ”、t h a i m a n n s 工作组1 等。粒子模型将网格的 顶点看成粒子，对服装的模拟分两阶段，即速度分析阶段和能量分析阶段。该方 面的典型代表是：j e f f l a n d e r “、x p r o v o t 1 等。 1 2 冲突检测与响应 冲突检测与响应在柔性物体的仿真中是一个至关重要的问题。在一些系统中 l “，冲突检测的计算花费将占总计算时i l 白j 的5 0 以上。在实时应用以及对柔性物 体的快速模拟中，都需要一个有效的冲突检测与响应算法。 冲突检测与响应问题不仅应用于真实感御和衣服的仿真中，用于判断衣服与 人体或与场景中其它障碍物之间的交互作用，而且还应用于机器人的路径规划和 学习、飞行员和宇航员的培训、交互式动画系统等很多方面。尤其是在电脑动画 和电脑游戏中，冲突检测与响应显得尤为重要。比如在著名的电脑游戏古墓丽 影中，由于冲突问题没有解决好，游戏中的主角劳拉在靠墙行走时，她的身体 会嵌入到墙壁中。与此类似，若是我们在真实感衣服仿真中没有解决好冲突问题， 也会发生衣服嵌入人体躯干的情况。冲突检测与响应问题的解决对于我们的真实 感衣服仿真至关重要，因为它直接影响到仿真的速度和仿真结果的真实感。 冲突就是两个或多个物体的体积不能同时占有相同空间的事实。当物体间发 生冲突时，它们之问的交互力使得它们会对另外的物体产生排斥作用。交互力包 括两种力，其一是排斥力，它使得物体削不会相互穿透：其二是摩擦力，它可以 阻止物体问沿着彼此滑动。 从机械模拟的观点来看，冲突问题包括以下两个方面。 冲突检测：发现两个物体间是否有几何接触。 冲突响应：使用排斥力和摩擦力的结果，使物体间不能互相穿透。 这两个问题在本质上是不同的：前者基本上是几何问题，而后者与具体的建模 方法有关。 1 2 1 冲突检测 在定义一个好的冲突检测算法之前，有许多问题需要被解决。 第一章绪论 1 复杂性 在柔性物体的冲突检测中，除了检测柔性物体与其周围物体是否发生穿透外， 由于柔性物体的柔软形变，不同部分之间的运动没有严格的约束，因此必须也对 柔性物体的不同部分进行冲突检测，就是自冲突检测。 自冲突检测( s e l f c o l l i s i o n ) 。没有它，布会穿透自己； 它冲突检测( h i tc o l l i s i o n ) 。没有它。布会穿透其它物体： 由于柔性物体随运动易变的特性，柔性物体一般被离散化成成千上万个多边 形网格。因此，冲突检测和自冲突检测就归结为寻找每对点一多边形或每对边一边 之间是否发生穿透。由于必须对每个点一多边形或边一边对进行检测，计算量庞大。 必须采取措施来避免这种情况的发生。 2 本质 冲突检测由两个问题组成：其一是检测物体间是否相互穿透，即干涉检测 ( i n t e r f e r e n c ed e t e c t i o n ) ：其二是检测两个物体削的距离是否小于个极限值，即 邻近检测( p r o x i m i t y d e t e c t i o n ) 。 1 _ 2 2 冲突响应 冲突响应就是如何防止物体闯相互穿越现象的发生。 对于柔体物体的冲突响应，现有的算法主要是采用构造人工势场的方法。这 种方法在障碍物周围设置一个斥力场，当柔性物体与障碍物的距离足够近时，会 受到斥力场的作用，避免发生冲突。 一般来讲，采用构造人工势场的方法能够成功地防止冲突，避免穿越现象发 生。但是，由于斥力场是人为设置的，在仿真过程中不可避免地会出现一些不自 然的响应。例如当布与障碍物的距离非常近时，由斥力场产生的斥力会很大，则 布看起来象是“弹离”了障碍物的表面，并且有可能造成系统不稳定。另外，由 于斥力场的存在，布在到达稳态时，将会“浮于”障碍物的表面，而不与物体产 生接触。这使得在某些情况下会使产生的图形在真实感上有所欠缺。如搭在方桌 上的台布，在直角形的桌沿会出现圆角的情况。 还有些人采用动量守恒的方法进行冲突响应，当布粒子与障碍物发生冲突时， 根据动量守恒定律，粒子会向相反的方向运动，所以这种方法同样会使布看起来 象是“弹离”了障碍物的表面，影响仿真结果的真实感。 1 3 冲突检测与响应问题的研究现状 冲突检测与响应问题开始并未作为一个专门的问题来研究，最早是涉及运动 和空间的布局问题。例如运动空间的干涉检测和装配中的干涉问题，这些问题主 要用求交解决。随着应用的需求、新技术、如机器入学和几何建模技术的发展给 4 柔性物体仿真中冲突检测与响应技术的研究 冲突检测与修正问题提出了新的要求和内容。冲突检测与响应也逐渐吸引更多的 人进行研究。 1 3 1 冲突检测 在过去，许多冲突检测与响应算法已经被设计【l ”，这些算法中，有的能适用 于特定的应用，而有的只有理论上的价值。其中，有些算法可以直接或经改进后 运用到柔性物体的模拟仿真上来。 对于柔性物体来说，必须检测每一个小面片或粒子的冲突，而且必须采耿措 施来避免引进额外的硬度，因此，柔性物体间的冲突检测相比刚体之间的冲突检 测来说要复杂的多。在这方面，几个方法也己经被建议。 对于随时阳j 变化的参数曲面，h e r z e n 1 4j 等人使用分层算法首先发现在大的边 界体之间的冲突，然后进一步细化到具体物体问的冲突检测。另个被经常使用 来建模布料的方法是有限元模型和节点分析法。但是，这个方法计算量很大，速 度上不能令人满意。b a r a f f 和w i t k i n 1 5 j 使用多面体近似法来模拟柔性物体的冲突 检测。如果这个模型非常精练，它能产生合理的结果。但是，即使使用一致性技 术柬减少多边形一多边形对之间的相交测试，这个算法花费的时问仍比线性时间 多。s n y d e r t 6 等人使用间隔算术、优化过程以及别的许多数学方法，提出了种 适用于任何曲面类型的通用的冲突检测算法。尽管有如此多的优点，这个算法非 常满，不适合于实时模拟。 132 冲突响应 b a r a f r 平口w i t k i n 1 2 j 使用一个基于约束的方法，v o l i n oe ta 1 i 7 j 为冲突的粒子重 新设置位置、速度和加速度，而v o l i n o t t 7 i 1 0 p r o v o t ”j 为处理多个冲突提出了新的方 法。 1 4 冲突检测与响应问题的复杂性 冲突检测与响应问题的复杂性表现在： 运动轨迹的复杂性：运动轨迹实际上有两种情况：轨迹( t r a j e c t o r y ) 和路径 ( p a t h ) 。轨迹是由时间参数定义的，它的实际位置一般受到物理规律或运动方程 的约束。对轨迹进行插值运算时，物理参数( 如速度和加速度) 可以作为端点的插 值条件。物体在运动之前轨迹是不存在的。路径本身的定义是与时间无关的，例 如一条公路，它不以运动规律定义，而是一种客观存在。然而当物体沿已有的路 径运动时，物体在某个时刻在路径上的位置则是由物体的运动规律决定。两者的 区别可能导致复杂程度不同的算法。其次，运动轨迹的复杂性还体现在物体的运 动轨迹不仅是二维空间曲线，而且含有三维空间曲线。复杂运动轨迹的描述有时 比较困难。 第一章绪论 运动物体的复杂性：运动物体的复杂性是指物体形状的复杂性，表达形式的 复杂性( 如数学描述和数据结构) ，如果变形物体还包含受力后的变形描述，非常 犍确地表示运动物体可以导致检测方法的耗时，特别是实时检测时，对检测时闻 要求很短，复杂的数学模型根本不能检测。运动物体的复杂性还导致含有时间参 数的描述难以定义。对于四维物体，由于三维物体( x ，y ，z ) 本身的复杂，导致四 维物体( x ，y ，z ，t ) 的复杂性。 运动方式的复杂性：物体的运动方式指物体相对于自己的坐标系的运动。最 简单的运动方式时平移和旋转。运动坐标系沿轨迹运动，物体相对该坐标系静止。 当物体运动过程中相对坐标系也运动时，宜接描述物体表面就很困难。运动方式 还牵扯到整体运动和部分运动( 带关节) 。整体运动指运动物体作为一个不可分割 的整体，各部分统一行动，而部分运动是每个部分在同一时问沿自己的轨迹进行 运动。 采用静态冲突检测方法时，需要将时间离散化，那么离散的步长d t 如何选取， d t 选取过大，会出现漏检情况，发生穿越；d t 选取过小，计算量将大大增加，检 测效率下降，不适合实时检测。 求交算法的复杂性：冲突检测与修正算法的基础是求交。求交算法依赖于物 体的建模和测试方法。平面求交解决多面体类物体的检测，参数曲面求交解决曲 面粪的检测。求交的精度和效率是关键指标，但同时又是一对矛盾。在实时检测 系统中，检测效率是关键。在许多场合没有必要采用非常精确的物体描述进行冲 突检测，这既是为了提高检测效率，也是出于实际应用的安全余量的考虑。对物 体进行适当的放大或简化可大大地提高检测效率。几何逼近程度在于冗余空问的 大小，冗余空闯越小，逼近程度越高，检测的准确性也越高。 l 。5 本文的研究工作 本文首先研究了柔性物体仿真中冲突检测与响应阍题所用到的基本技术，这 些技术具有通用性，即可被应用到任何的模拟环境。然后，结合本项目组其它同 学的研究成果以及实际的模拟环境，提出了柔性物体与融体以及柔性物体自身的 冲突检测与响应算法，重点是柔性物体的自冲突检测与响应算法。在柔性物体的 自冲突检测与响应算法中，首先利用物体表面的曲率排除了大部分虚假的“冲突”。 接着，使用健壮的几何冲突算法和排斥力方法来完全避免冲突。最后。本文对柔 性物体仿真中的一些复杂问题，提出了自己的看法或介绍了其他人在这方面的研 究。概括起来，本文主要有以下几方面的工作： l 、分析了柔性物体仿真中冲突检测与响应问题所用到的基本技术。 2 、提出了柔往物体与刚体的冲突检测与响应算法。 一6 柔性物体仿真中冲突检测与响应技术的研究 3 、提出了柔住物体的自冲突检测与响应算法。 4 、实现了上述算法。并对结果进行了分析。 5 、对柔性物体仿真中冲突检测与响应技术的难点闯题做了进一步探讨。 本文得到了陕西省自然科学基会( 0 0 0 x 0 0 2 ) 的支持。 第二章基础研究 第三章基础研究 2 1 柔性物体建模 柔性物体没有固定的形状，当它处于运动状态或接近于其它物体时会改变其 表露的特征。这类物体包括人体飘肉、繁状物体、织物、水滴等，在图形学的应 用中。已经开发出了几种柔性物体的建模方法。比较典型的有下面几种。 2 ，l ，l 毫颠密度函数法 该方法利用柔性物体在变形过程中保持其体积或面积不变的思想将柔性物体 的表面定义为： f ( x ，y ，z ) = b k e 一7 = 0 ( 2 1 ) 女 其中： 疗= + y ；+ ：，是某个特定的临界值，参数a 。用来调整单个柔性物 体的数量，参数b 。的正负使柔性物体的外形产生“凹”形或“凸”形，在瞧赛值 级上。数值化寻根技术用来给坐标交叉值定位。此时。单个物体的剖面部分按圆 或椭圆柬建模，当两个剖蕊部分彼此靠近，则它们趋于一种柔性形状。因此，柔 性物体的结构依赖于两个物体分离的程度。用三维高斯密度函数来表示柔性物体 的示例如下： - aa 图2 1 ( a ) 高斯密度函数圈2 i ( b ) 用高斯密度函数构造的柔性物体表面 高斯密度函数法适用予建立柔性物体的总体表面。 2 1 2 分段函数法 该方法在柔性物体的变形区域分段设置不同的函数，用来描述柔性物体在彼 此接近或柔性物体与其它物体接触时的粘滞形态。如分段函数： 竹，：f 一筹+ 筹十万r 3 r * o r d 其中：r 为柔性物体的半径、d 为柔性物体与近邻物体间的距离， ( 2 2 ) 如此可描述柔性 柔性物体仿真中冲突检测与响应技术的研究 物体在接近其它物体时的变形情况。r h r 2 ，r 3 分别为柔性物体的半径调整参量， d l , d 2 ，d 3 分别为柔性物体的距离调整参量。该分段函数可形成如人臂肌肉的柔性物 体形状。如图2 2 所示： 汐夕影 圈22 ( a ) 手臂弯曲造型图2 2 ( b ) 手臂伸展造型 以上分段函数只是给出了描述柔性物体的一种形式，在模拟仿真一种特定材 料时，应采用特定的分段函数以求接近柔性物体的实际外形。当然上述的分段函 数可以被定义为两段以上的多段函数。 分段函数法适用于建立柔性物体的局部连接表面。 2 1 3 多边形网格法 柔性物体的建模方法大多是基于多边形网格模型，例如，表示成由大量的三 角形和四边形组成的形体，从而形成立体的三维效果。其中每个平面片都由顶点和 边组成，由多个平面片彼此连接可形成封闭的多边形形体，由此构成的形体可进 行拉伸、缩放、定位、平滑过渡等操作。 由丁二角形具有良好的稳定性，任意二角形的顶点、边都存在丁同一个平面中，使得三 角性网格成为描述柔性物体最有效的近似方法。三角形的法向量、受力分析、顶点的加速度、 述度、位置都比较容易确定，冈此，将柔性物体划分为三角形后再进行处理大人简化了仿真 过程。 如图2 3 所示：三角形的三个顶点可分别表示为 p l 、 p ：) 、f p ， ；三条边分 别表示为：p p ：= 仍卜- 扣。) 、p ：p ，= 见) 一 p ：) 、丽= f p 。卜眠 三角形的法 向量可表示为：二= p i p 2 石石。由此，可以推算出三角形的面积： s = 捌而面卜一 其中：边石i 和p l p 3 的夹角。可通过两条相邻的边向量计算出来。 ( 2 3 ) 第二章基础研究一9 法向盛 p 2 ( 顶点) 图2 3 三角形之间的关系图 因此，由柔性物体表面三维空间点集，通过三角剖分的方法重新建立物体表 面是计算几何的一个基本问题，它实际上是在物体表面进行三角形剖分。目前它 在计算机三维重建领域、计算机数字图象处理、复杂物体的模拟、动念模拟方面 有者广泛的应用，大致可以分为映射法和自动网格生成法两类。 2 2 求交算法 出于柔性物体以及场景中的其它物体经常用多边形网格来表示。因此，判断 柔性物体是否冲突的最简单方法是在每一个时间步长结束时，判断所有的多边形 网格之问是否相交。如果相交，则求出相应的交点，以进行相应的冲突处理。这 种处理方法只适合于时问步长很小的模拟环境，它一般可归结为点一面求交运算 和边一边求交运算。 2 2 1 点与平面区域的求交计算 设点坐标为p ( 工，y ，z ) ，平面方程为戤+ 砂+ 盯+ d = 0 。则点到平面的距离为 d ：! 竺兰丝堡圭垡!( 2 4 ) 口2 + b 2 + c 2 若d s i z e a g g r e g a t e o b j b ) t h e n s w a p ( o b j a ，o b g b ) ：i fn o te l e m e n t a r y ( o b j b t h q l ：f o ro b jf r o mf i r s t e l e 啦e n t o b j b t oe n d o f l i s td o ：t e s t c o l l i s i o n ( o b j a ，o b j ) ：e l s et e s t e l e m e n t a r y c o l l i s i o n ( o b j a ，o b j b 口n d 乘性物体仿真中冲突检测与响应技术的研究 因此，我们可以通过在一个曲面区域内或两个相邻的曲面区域间用曲率测试代 替边界盒测试来将曲率准则合并进分层算法中。 4 4 几何相交测试 当发现两个正在冲突的边界体后，我们需要测试这两个边界体所代表的三角 形对之间是否发生冲突，这个测试可分解为点一三角形冲突测试和边一边冲突测 试。 设f 。是布料在仿真过程中一个没有冲突发生的时刻，k ，f o + ，】是时间间隔。 我们假设布料的每一个结点在【f o ，f 0 + a t 】内具有恒定的速度。如果知道布料每一个 结点在t 。时刻的位置和速度，就能够计算出在，0 + 出时刻的位置。然后，冲突检测 算法能找出在这个时间间隔发生的所有冲突。 1 、“点一三角形”冲突 设j p ( ，) 是一个运动的点，爿( f ) ，曰( f ) ，c ( ，) 是运动三角形的三个顶点。旷，瓦，元，丘 分别是它们在【f o ，f 。+ a r i d l y 7 间隔内的恒定速度。因此，我们可以得出： 一( f ) = a ( t o ) + f 吒，b ( r ) = b ( t o ) + f ，c ( ，) = c ( t o ) + i v , 如果发生冲突，那么点p ( ，) 将属于三角形a b c ( t ) 。这能用下面的关系式表示 出来： jr p o ，t o + 出j ， 并且jz ，v i o ，l i + v l ， 使得a p ( t ) = u a b ( t ) + v a c ( t )( 4 i ) 不幸的是，这个向量方程是一个非线性方程。为了解出这个方程，另一个条件 必须被使用，那就是：点p 在三角形a b c 所属的平面上。由于叉乘 n ( t ) = a b ( t ) a t ( t ) 正交于三角形a b c 所属的平面，那么，在冲突发生的时刻， 下面的关系式将成立： a p ( t ) n ( t ) = 0 这个新的关系式尽管不是充分条件，但是必要的。它仅仅意味着，点爿，8 ，c 和 j p 是共面的。然而，由于它允许用一种很简单的方式来决定冲突时间，因此，它 是非常有用的。贾( f ) 是关于的二次方的函数，i 芦( d 是f 的一次方，因此，它们 的点乘产生一个能被很容易解决的三次方函数。我们可以得到三个，值，但是，只 有在【，0 ，。+ f 】间隔内的t 值才对应着一个冲突。 如果这个方程系统有不止一个解，那么，我们仅仅考虑的冲突是最早发生的一 个，例如，对应着最小f 值的一个。 2 、“边一边”冲突 设a b ( t ) 是第一条边，c d ( t ) 是另一条边。当且仅当下面的条件满足，冲突才 第西章柔性物体的自冲突检测与响应算法 会发生。 3 te l f o ，t o 十f j 并且j ，v f 0 ，i 】，使u a b ( t ) = v c d ( t ) ( 4 ，2 ) 像上面一样，这是一个非线性系统。为了发现t 的值而不用解上面的方程，另 个关系必须被使用。即，在冲突时刻，四个点爿，e c ，d 将属于同一个平面，可 以如下式所示： ( a g ( t ) c d ( 功a c ( t ) = 0 ( 4 3 ) 这个关系式也是一个三次方程，在将，值代入方程( 4 2 ) 后，我们能够解出“和 v ，然后，我们就能检测出一个冲突是否发生。 4 5 布料的自冲突响应 稚料的自冲突响应对于布的真实感显示至关重要。我们算法的主要思想是将 能主动防止冲突的几何方法和快速的( 非刚性的) 排斥力方法结合起来。在我们 的工作中，对于静态接触，采用基于排斥力的处理方式；而对于高速冲突，采用 基于脉冲的处理方式。我们用排斥力的方式处理布料仿真中大多数的静态接触， 因此，这种方式必须是有效而简单的。对于未能处理的冲突，我们用昂贵但健壮 的基于脉