基于物理的布料仿真(Physically-based Cloth Simulation)研究的是如何在计算机虚拟世界中模拟出布料在现实世界中的运动形态,是近几十年来计算机图形学领域的热门研究课题之一。随着计算机图形学和计算机硬件的快速发展,布料仿真在计算机游戏、影视制作、电子商务等领域被广泛应用。在保证仿真质量的前提下,如何提高仿真系统的效率一直是基于物理的布料仿真领域的重要研究任务之一。其中,碰撞处理作为仿真系统中的重要步骤,是仿真系统能否真实还原现实世界的关键,同时也是仿真系统的时间瓶颈。因此,高效的碰撞处理算法将会有效改善整个布料仿真系统的效率,具有重要的现实意义。此外,GPU等并行硬件的诞生和发展也为探索快速布料仿真算法提供了新的研究方向。本文围绕如何提高布料仿真流程的效率,针对关于碰撞处理的算法进行了较为深入的研究。本文重点探索了碰撞检测中的自碰撞剔除算法和基于GPU的碰撞响应算法,并提出了一套新的基于GPU的布料仿真系统。本文研究的主要内容可概括如下:·提出了一种基于双锥测试的自碰撞剔除算法。自碰撞剔除,即在碰撞检测开始时首先剔除掉布料网格中一定不会发生自相交的三角形对,以减轻后续精确碰撞检测的计算负担。最常用的自碰撞剔除方法为基于法向锥测试的剔除方法。但是,该方法在轮廓边测试阶段通常需要将轮廓边投影到某个平面中,然后判断任意两条投影后的边是否相交,相对比较耗时。针对此问题,在原有轮廓边测试的基础上,本文提出了一种新的使用切向锥和双锥测试定理的轮廓边测试策略。该策略在保证不会遗漏碰撞的前提下,提高了轮廓边测试的速度。基于此策略,本文提出了针对单个网格的自碰撞判断条件,并将此通用的判断条件加入到基于包围盒层次结构的自碰撞剔除算法中。此外,基于单个网格的判断条件和包围盒层次结构的特性,本文提出了新的包围盒测试树的遍历策略,可以减少多余的包围盒测试树节点的测试数量。实验表明,基于双锥测试的自碰撞剔除算法可以得到准确的剔除结果,同时较其他传统算法也有不同程度的加速。·提出了一种基于非投影法向锥测试的自碰撞剔除算法。上一方法虽然对原始的法向锥测试法进行了改进,但其仍需对轮廓边进行投影以及判断投影后的轮廓边是否相交。针对此问题,本文继续对轮廓边测试进行改进,首先提出了二维平面中新的轮廓边测试方法,将轮廓边测试转化为星形多边形的判断;之后,根据星形多边形判断中所使用的公式,本文将二维平面中所涉及的顶点计算扩展到其对应的三维非投影的轮廓边端点中,可以得到同样准确的轮廓边测试结果。基于此非投影的轮廓边测试法,本文构建了非投影的法向锥测试法,并与包围盒层次结构相结合共同构成了完整的自碰撞剔除算法。与上一方法相比,此方法不需要进行任何投影计算和轮廓边的相交测试,大大提高了自碰撞剔除的速率。此外,本文还将非投影法向锥测试法扩展到了连续碰撞检测中,以进行更准确的碰撞检测。实验表明,无论是在离散还是连续碰撞检测中,非投影的法向锥测试法都具有明显的性能优势,提高了整个碰撞检测的效率。·提出了一种基于GPU的碰撞响应算法和基于GPU的布料仿真系统。在碰撞响应过程中,多个碰撞对通常被组织成若干个Impact Zone,每个Impact Zone的处理可以被转化为带约束的非线性优化问题的求解。针对如何在GPU上快速求解此非线性优化问题,本文提出了一个新的非线性求解器。该求解器除使用梯度下降法外,还加入雅可比预处理器和切比雪夫加速法以提高收敛速率。与前人的方法相比,本求解器具有更好的稳定性和收敛速率,且更适用于GPU并行。通过使用此求解器,基于GPU的碰撞响应算法可以做到多个Impact Zone并行处理,同时每个Impact Zone内的顶点位置并行进行更新。除此之外,本文将此Impact Zone的求解器与其他基于GPU的布料仿真算法结合,构造了一套基于GPU的布料仿真系统I-Cloth。本系统可以在一定程度上实现用户与仿真布料的实时交互。实验表明,本文的非线性求解器具有更好的稳定性和收敛速率,仿真系统具有更好的性能表现。