基于物理的布料仿真在最近二十年里一直都是计算机图形学领域的热点研究问题。而在最近十年,随着布料仿真技术的快速发展,基于物理的布料动画在电影、游戏与在线虚拟购物等领域得到了越来越广泛的应用,并展现出了越来越高的商业价值。近年来,随着虚拟试衣行业的崛起,工业界对高质量高效率的服装布料仿真的需求越来越大。由于布料具有复杂的物理特性,既有弹性也有塑形、既可以自由变形又无法过度拉伸、既可以是针织结构也可以是纺织结构,所以高质量高效率的布料仿真在计算机图形学领域是一个非常有挑战性的研究问题。高质量的布料仿真对布料的物理模型,数值时间积分方法与求解,碰撞处理等每一个步骤都有非常高的要求。任何一个环节出现问题都会极大的影响最终的布料效果。另外,布料仿真的效率也越来越关键。快速的布料仿真可以极大地降低动画电影中布料动画的制作成本。同时,游戏与虚拟试衣等需要进行实时交互的应用则提出了实时布料仿真的需求。通常情况下,为了得到最优的布料效果,需要在仿真的质量与效率之间寻找一种平衡。本文的研究目标是高质量高效率的实时布料仿真。针对基于物理的布料仿真中的若干关键问题,本文针对性地进行了研究,提出了相对应的方法,既提高了布料仿真的质量,也提高了布料仿真的效率。本文重点研究了在高质量的布料仿真中非线性问题的求解方法,碰撞处理中的高质量高效率的连续碰撞检测算法与碰撞响应方法,以及对布料的形变控制后处理算法,并取得了以下研究成果:·非线性布料仿真中高效并行的非线性Multigrid算法。提出了一种基于GPU并行计算加速的非线性Multigrid方法,并将该方法应用在非线性的高分辨率布料仿真中。该方法的基础是一种创新的非线性Full Multigrid(FMG)方法。为了把非线性引入到FMG中,本文提出:首先在不同的较低分辨率层级上进行子问题求解,并把对应的结果作为一个不同频率的下降方向应用在最高分辨率层级的非线性优化问题上。本文证明了非线性FMG方法在多种条件下可以确保收敛,并且通过实验与相应的统计数据体现了这种非线性带来的优势。另外,本文还提出了一种简单高效的自适应求解方法来降低在高精度变量处的计算量。与一般的线性迭代求解方法相比,非线性FMG方法为传统牛顿法与Projective Dynamics提供了更好的收敛性和更加高效的性能。实验表明,本文提出的方法高效、精确、在大步长情况下稳定、而且易于在GPU上进行并行化加速。同时,该方法的性能针对不同的网格分辨率有很好的线性性能扩展性。·基于伯恩施坦符号分类的快速精确的连续碰撞检测算法。利用伯恩斯坦基与贝泽尔曲线的性质,本文把三角形网格之间的连续碰撞检测问题简化成判断一系列多项式符号的问题,从而提出了一种基于精确几何算术计算的精确连续碰撞检测算法,来快速地进行碰撞测试判断。与之前的同类精确连续碰撞检测方法相比[1],本文的精确连续碰撞检测方法在速度上要快10-25倍。通过基于物理的布料仿真与有限元仿真实验,本文测试了该方法在CPU与GPU上的性能。·基于浮点数误差上界的高效连续碰撞检测算法。提出了一种简单高效的方法来计算浮点数算术表达式的舍入误差上界,并把该方法应用于前一章所介绍的基于伯恩斯坦符号分类的连续碰撞检测算法中,使其可以充分的利用CPU与GPU等浮点数硬件的计算性能。通过计算一系列关键变量的舍入误差上界,本文提出的方法可以准确地判断浮点数表达式的符号,并确保浮点数连续碰撞检测方法的正确性。与之前的同类浮点数连续碰撞检测方法相比,该方法在确保没有遗漏碰撞的前提下可以减少90-95%的误判碰撞。在基于物理的布料仿真与有限元仿真中,该方法的性能比前一章所介绍的精确方法快5-15倍,同时也有助于提高布料仿真的整体性能与稳定性。·基于半定规划的应变张力控制与非线性碰撞响应算法。本文通过把应变张力约束与碰撞约束表示成一系列的线性矩阵不等式与线性多项式不等式,提出了一个基于半定规划方法的应变张力控制与碰撞响应算法。在对三角形网格进行张力控制时,该方法通过引入一个附加的顶点把三角形转换成四面体,可以有效地防止三角形的翻转,同时加快应变张力控制的收敛性。在对三角形布料网格进行碰撞响应时,该方法引入了一个行列式约束,可以确保每一个碰撞在一次迭代处理之后被解决,提高了碰撞处理的收敛速度与效率。