布料模拟属于计算机图形学领域的研究课题，其技术成果被广泛应用于动画、游戏、影视和设计等场景。布料模拟算法通常将布料运动和变形的过程离散化为一系列时间步，通过物理规律建立和求解动力学系统，得到布料在每一时刻的物理状态，从而生成模拟动画。布料模拟算法不仅需要保证模拟结果具有一定的真实感，还要能够高效地完成求解计算过程。本文提出了一种隐式摩擦投影动力学图形处理器（Graphics Processing Unit，GPU）并行算法。该算法采用雅可比迭代法和高斯—赛德尔迭代法实现了隐式摩擦投影动力学全局求解的并行化，解决了中央处理器（Central Processing Unit，CPU）实现中使用的直接求解法难以并行加速的问题。本文将约束矩阵的对角元素与非对角元素分开存储，然后将全局线性系统右端项进行拆分重组，将与约束矩阵非对角元素相关子项计算合并到同一GPU内核执行，提高了求解算法中的代数运算对于GPU并行架构的适应性。本文提出了基于高斯—赛德尔迭代法和切比雪夫加速的隐式摩擦求解算法，该算法能够快速收敛到布料碰撞和摩擦视觉效果合理的解，有效解决了逐次超松弛迭代法在布料碰撞情形下不收敛的问题。本文实现的隐式摩擦投影动力学GPU并行算法，在不考虑自碰撞的布料模拟测试用例上能够得到与CPU实现相近的模拟结果，并将求解迭代的计算速度提高到CPU实现的3.3~10.4倍。本文提出了一种基于GPU和隐式摩擦投影动力学的布料自碰撞模拟算法。该算法采用点面碰撞检测和碰撞法向修正对布料自碰撞检测进行了改进，并对局部求解阶段的自碰撞接触力逐层计算更新，以及全局求解阶段的线性系统求解进行了GPU并行实现。本文提出外层求解迭代与内层线性迭代相结合的隐式摩擦布料自碰撞系统求解算法，解决了考虑布料自碰撞因素后全局步骤使用单步线性迭代无法快速收敛，而使用直接求解法不能有效利用GPU并行优势导致计算效率过低的问题，有效地将全局线性系统求解的耗时控制在合理范围。本算法在布料自碰撞模拟测试用例上能够给出视觉效果合理的近似结果，并将求解迭代的计算速度提升为CPU实现的1.4~2.0倍，对隐式摩擦投影动力学布料自碰撞模拟提供了一套可行的GPU并行实现方案。
Cloth simulation is a research topic in computer graphics, and its technical achievements are widely used in animation, games, films, design, etc. Cloth simulation algorithms usually discretize the duration of cloth movement and deformation into a series of time steps, and then build and solve a dynamic system through physics laws, to obtain the physical state of the cloth at each moment and generate a cloth animation. Cloth simulation algorithms should consider both the realism of the simulation results and the efficiency of the solving calculation.In this paper, a graphics processing unit (GPU) parallel algorithm of implicit friction Projective Dynamics is proposed. The algorithm uses the Jacobi and Gauss-Seidel iterative methods to achieve the parallelization of the global solve of implicit friction Projective Dynamics, which solves the problem that the direct method used in the central processing unit (CPU) implementation is difficult to be accelerated in parallel. In this paper, the diagonal and non-diagonal elements of the constraint matrix are stored separately, and the right-hand side term of the global linear system is split and reorganized, and the calculations of the sub-items related to the non-diagonal elements of the constraint matrix are merged into the same GPU kernel, which improves the adaptability of algebraic operations in the algorithm to GPU parallel architectures. This paper proposes an implicit friction solving algorithm based on Gauss-Seidel iterative method and Chebyshev acceleration, which can quickly converge to a solution with reasonable visual effects on cloth collision and friction, and solve the problem that the successive over-relaxation fails to converge when cloth collision happens. By experiment, in the cloth simulation cases that ignore self-collision, the GPU parallel algorithm of implicit friction Projective Dynamics implemented in this paper can obtain results similar to that of the CPU implementation, and the calculation speed of the solve iteration is 3.3~10.4 times that of the CPU implementation.This paper proposes a cloth self-collision simulation algorithm based on GPU and implicit friction Projective Dynamics. The algorithm uses vertex-face collision detection and contact normal correction to refine the cloth self-collision detection, and implements the layer-by-layer udpate of self-collision contact force in the local step and the linear solve in the global step in parallel on GPU. To solve the problem that a single linear iteration in the global solve cannot converge quickly in the case of cloth self-collision, and that direct method can't be easily accelerated on GPU, a solving algorithm with an outer solve iteration and an inner linear iteration is proposed for the implicit friction cloth self-collision system, which controls the time cost of the global solve within a reasonable range. By experiment, the algorithm can obtain a visually plausible approximate solution in the cases of cloth self-collision, and increase the calculation speed of solve iteration to 1.4~2.0 times that of the CPU implementation, which provides a feasible GPU parallel implementation for cloth self-collision simulation based on implicit friction Projective Dynamics.
