A Survey on Position-Based Simulation Methods in Computer Graphics 计算机图形学中基于位置的模拟方法概览
Jan Bender , Matthias Müller , Miguel A. Otaduy , Matthias Teschner and Miles Macklin Jan Bender , Matthias Müller , Miguel A. Otaduy , Matthias Teschner 和 Miles Macklin Graduate School CE, TU Darmstadt 达姆施塔特工业大学 CE 研究生院 NVIDIA PhysX Research 英伟达™ PhysX 研究 URJC Madrid 马德里城市青年活动中心 University of Freiburg 弗莱堡大学
Abstract 摘要
The dynamic simulation of mechanical effects has a long history in computer graphics. The classical methods in this field discretize Newton's second law in a variety of Lagrangian or Eulerian ways, and formulate forces appropriate for each mechanical effect: joints for rigid bodies; stretching, shearing, or bending for deformable bodies; and pressure, or viscosity for fluids, to mention just a few. In the last years the class of position-based methods has become popular in the graphics community. These kinds of methods are fast, stable and controllable which make them well-suited for use in interactive environments. Position-based methods are not as accurate as force-based methods in general but they provide visual plausibility. Therefore, the main application areas of these approaches are virtual reality, computer games and special effects in movies. 机械效应的动态模拟在计算机制图领域有着悠久的历史。该领域的经典方法以各种拉格朗日或欧拉方式将牛顿第二定律离散化，并为每种机械效应制定适当的力：刚体的关节；可变形体的拉伸、剪切或弯曲；以及流体的压力或粘度等。最近几年，基于位置的方法在图形学领域大受欢迎。这类方法快速、稳定、可控，非常适合在交互环境中使用。一般来说，基于位置的方法不如基于力的方法精确，但它们提供了视觉上的可信度。因此，这些方法的主要应用领域是虚拟现实、电脑游戏和电影特效。
This state-of-the-art report covers the large variety of position-based methods that were developed in the field of physically-based simulation. We will introduce the concept of position-based dynamics, present dynamic simulation based on shape matching and discuss data-driven upsampling approaches. Furthermore, we will present several applications for these methods. 这份最新报告涵盖了物理仿真领域开发的各种基于位置的方法。我们将介绍基于位置的动力学概念，介绍基于形状匹配的动态模拟，并讨论数据驱动的上采样方法。此外，我们还将介绍这些方法的若干应用。
Keywords: 关键词：
Categories and Subject Descriptors (according to ACM CCS): Computer Graphics [I.3.7]: Three-Dimensional Graphics and Realism-Animation 类别和主题描述符（根据 ACM CCS）：计算机图形学[I.3.7]：三维图形和逼真-动画
1. Introduction 1.导言
The simulation of solid objects such as rigid bodies, soft bodies or cloth has been an important and active research topic in computer graphics for more than 30 years. The field was introduced to graphics by Terzopoulos and his colleagues in the late eighties [TPBF87a]. Since then, a large body of work has been published and the list is growing rapidly. There exists a variety of survey papers [GM97, MTV05,NMK* 06, MSJT08,BETC12] which document this development. However, due to the shear number of papers, it has become difficult to cover the entire field in one survey. 30 多年来，实体物体（如刚体、软体或布料）的模拟一直是计算机图形学中一个重要而活跃的研究课题。80 年代末，Terzopoulos 和他的同事将这一领域引入图形学领域 [TPBF87a]。从那时起，大量研究成果陆续发表，而且数量还在迅速增加。有许多调查论文[GM97, MTV05,NMK* 06, MSJT08,BETC12] 都记录了这一发展。然而，由于论文数量庞大，很难在一份调查报告中涵盖整个领域。
In this state-of-the-art report we focus on a special class of simulation methods, namely position-based approaches. These methods were originally developed for the simulation of solids. However, some recent works demonstrated that the position-based concepts can even be used to simulate flu- ids. Classical dynamics simulation methods formulate the change of momentum of a system as a function of applied forces, and evolve positions through numerical integration of accelerations and velocities. Position-based approaches, instead, compute positions directly, based on the solution to a quasi-static problem. 在这份最新报告中，我们将重点讨论一类特殊的模拟方法，即基于位置的方法。这些方法最初是为模拟固体而开发的。然而，最近的一些研究表明，基于位置的概念甚至可以用于模拟流体。经典动力学模拟方法将系统的动量变化表述为外力的函数，并通过加速度和速度的数值积分来演化位置。而基于位置的方法则是根据准静态问题的解决方案直接计算位置。
Physical simulation is a well studied problem in the computational sciences and therefore, many of the well established methods have been adopted in graphics such as the Finite Element Method (FEM) [OH99], the Finite Differences Method [TPBF87b], the Finite Volume Method [TBHF03], the boundary element method [JP99] or particle-based approaches [DSB99, THMG04]. The main goal of computer simulations in computational physics and chemistry is to replace real-world experiments and thus, to be as accurate as possible. In contrast, the main applications of physically based simulation methods in computer graphics are special 物理模拟是计算科学中一个研究得很透彻的问题，因此，许多成熟的方法已被图形学所采用，如有限元法（FEM）[OH99]、有限差分法[TPBF87b]、有限体积法[TBHF03]、边界元法[JP99]或基于粒子的方法[DSB99, THMG04]。计算物理和化学中计算机模拟的主要目标是取代真实世界的实验，因此要尽可能精确。相比之下，基于物理的模拟方法在计算机图形学中的主要应用是特殊的
effects in movies and commercials and more recently, computer games and other interactive systems. Here, speed and controllability are the most important factors and all that is required in terms of accuracy is visual plausibility. This is especially true for real-time applications. 在电影和商业广告中，以及最近在电脑游戏和其他互动系统中，都可以看到这种特效。在这种情况下，速度和可控性是最重要的因素，而对精确度的要求只是视觉上的可信度。这一点在实时应用中尤为明显。
Position-based methods are tailored particularly for use in interactive environments. They provide a high level of control and are stable even when simple and fast explicit time integration schemes are used. Due to their simplicity, robustness and speed these approaches have recently become very popular in computer graphics and in the game industry. 基于位置的方法特别适合在互动环境中使用。它们提供了高水平的控制，即使在使用简单快速的显式时间积分方案时也很稳定。由于其简单性、稳健性和快速性，这些方法最近在计算机制图和游戏行业非常流行。
In this state-of-the-art report, we focus the discussion on several geometrically motivated methods, in particular those that directly manipulate the positions of the simulated bodies. We start with a description of position-based dynamics methods, which compute equilibrium positions by iteratively resolving geometric constraints. Then, we cover shape matching methods, and we conclude with data-driven upsampling methods, which compute positions as a function of data from precaptured deformation examples. 在这份最新报告中，我们将重点讨论几种基于几何原理的方法，特别是那些直接操纵模拟体位置的方法。我们首先介绍基于位置的动力学方法，这种方法通过迭代解决几何约束来计算平衡位置。然后，我们将介绍形状匹配方法，最后介绍数据驱动的上采样方法，该方法将位置作为预先捕获的变形示例数据的函数进行计算。
Collision detection is an important part of any simulation system. However, an adequate discussion of this topic is beyond the scope of this report. Therefore, we refer the reader to the surveys of Lin and Gottschalk [LG98] and the one of Teschner et al. [TKH* 05 碰撞检测是任何模拟系统的重要组成部分。然而，对这一主题的充分讨论超出了本报告的范围。因此，我们建议读者参阅 Lin 和 Gottschalk [LG98] 以及 Teschner 等人 [TKH* 05] 的研究报告。
2. Background 2.背景情况
The most popular approaches for the simulation of dynamic systems in computer graphics are force based. Internal and external forces are accumulated from which accelerations are computed based on Newton's second law of motion. A time integration method is then used to update the velocities and finally the positions of the object. A few simulation methods (most rigid body simulators) use impulse based dynamics and directly manipulate velocities. In contrast, geometry-based methods omit the velocity layer as well and immediately work on the positions. The main advantage of a position-based approach is its controllability. Overshooting problems of explicit integration schemes in force based systems can be avoided. In addition, collision constraints can be handled easily and penetrations can be resolved completely by projecting points to valid locations. 计算机图形学中最常用的动态系统仿真方法是基于力的仿真。根据牛顿第二运动定律计算出加速度，并将内力和外力累积起来。然后使用时间积分法更新速度，最后更新物体的位置。少数模拟方法（大多数刚体模拟器）使用基于脉冲的动力学方法，并直接操作速度。相比之下，基于几何的方法则省略了速度层，直接处理位置。基于位置的方法的主要优势在于其可控性。在基于力的系统中，可以避免显式积分方案的过冲问题。此外，还可以轻松处理碰撞约束，并通过将点投影到有效位置来完全解决穿透问题。
Among the force based approaches, one of the simplest methods is to represent and simulate solids with mass-spring networks. A mass spring system consists of a set of point masses that are connected by springs. The physics of such a system is straightforward and a simulator is easy to implement. However, there are some significant drawbacks of the simple method. 在基于力的方法中，最简单的方法之一是用质量弹簧网络来表示和模拟固体。质量弹簧系统由一组通过弹簧连接的点质量组成。这种系统的物理原理简单明了，模拟器也很容易实现。然而，这种简单的方法也有一些明显的缺点。
The behavior of the object depends on the way the spring network is set up. 对象的行为取决于弹簧网络的设置方式。
It can be difficult to tune the spring constants to get the desired behavior. 要调整弹簧常数以获得所需的性能可能比较困难。
Mass spring networks cannot capture volumetric effects directly such as volume conservation or prevention of volume inversions. 质量弹簧网络无法直接捕捉体积效应，如体积守恒或防止体积倒置。
The Finite Element Method solves all of the above problems because it considers the entire volume of a solid instead of replacing it with a finite number of point masses. Here, the object is discretized by splitting the volume into a number of elements with finite size. This discretization yields a mesh as in the mass spring approach in which the vertices play the role of the mass points and the elements, typically tetrahedra, can be viewed as generalized springs acting on multiple points at the same time. In both cases, forces at the mass points or mesh vertices are computed due to their velocities and the actual deformation of the mesh. 有限元法可以解决上述所有问题，因为它考虑的是固体的整个体积，而不是用有限个点质量来代替。在这种方法中，物体被离散化，体积被分割成若干具有有限尺寸的元素。这种离散化方法产生的网格与质量弹簧方法中的网格相同，其中顶点扮演质量点的角色，而元素（通常为四面体）则可视为同时作用于多个点的通用弹簧。在这两种情况下，质量点或网格顶点上的力都是根据其速度和网格的实际变形计算得出的。
3. Position-Based Dynamics 3.基于位置的动态
In this section we present Position-Based Dynamics, an approach which omits the velocity and acceleration layer and immediately works on the positions [MHHR07]. We will first describe the basic idea and the simulation algorithm of PBD. Then we will focus specifically on how to solve the system of constraints that describe the object to be simulated. After this we will provide a list of constraints that can be used to simulate a variety of materials such as soft bodies, cloth or even fluids with PBD. We will also discuss the relation of PBD to strain limiting methods, how to include damping and ways to parallelize the simulation algorithm. 在本节中，我们将介绍 "基于位置的动力学"（Position-Based Dynamics），这是一种省略了速度和加速度层而直接基于位置的方法[MHHR07]。我们将首先介绍 PBD 的基本思想和模拟算法。然后，我们将特别关注如何求解描述待模拟对象的约束系统。之后，我们将提供一份约束条件列表，这些约束条件可用于使用 PBD 模拟软体、布料甚至流体等各种材料。我们还将讨论 PBD 与应变限制方法的关系、如何加入阻尼以及仿真算法并行化的方法。
3.1. Overview 3.1.概述
The objects to be simulated are represented by a set of particles and a set of constraints. Each particle has three attributes, namely 要模拟的对象由一组 粒子和一组 约束来表示。每个粒子 都有三个属性，即
mass
position
velocity
A constraint is defined by the five attributes 一个约束 由五个属性定义
cardinality
scalar constraint function 标量约束函数
set of indices 指数集
stiffness parameter 刚度参数
unilateral or bilateral 单边或双边
type
Constraint with type bilateral is satisfied if . If its type is unilateral then it is satisfied if . The stiffness parameter defines the strength of the constraint in a range from zero to one. 如果 ，则类型为双边的约束条件 得到满足。如果其类型为单边，则在 时满足。刚度参数 定义了约束的强度，范围从 0 到 1。
Given this data and a time step , the simulation proceeds as described by Algorithm 1. Since the algorithm simulates a system which is second order in time, both the positions and the velocities of the particles need to be specified in (1)(3) before the simulation loop starts. Lines (5)-(6) perform a simple explicit forward Euler integration step on the velocities and the positions. The new locations are not assigned to the positions directly but are only used as predictions. Non-permanent external constraints such as collision constraints are generated at the beginning of each time step from scratch in line (7). Here the original and the predicted positions are used in order to perform continuous collision detection. The solver (8)-(10) then iteratively corrects the predicted positions such that they satisfy the external as well as the internal constraints. Finally, the corrected positions are used to update the positions and the velocities. It is essential here to update the velocities along with the positions. If this is not done, the simulation does not produce the correct behavior of a second order system. As you can see, the integration scheme used here is very similar to the Verlet method. It is also closely related to Jos Stam's Nucleus solver [Sta09] which also uses a set of contraints to describe the objects to be simulated. The main difference is that Nucleus solves the constraints for velocities, not positions. 给定这些数据和时间步长 后，模拟将按照算法 1 所描述的方式进行。由于该算法模拟的系统在时间上是二阶的，因此在模拟循环开始之前，需要在(1)(3)中指定粒子的位置和速度。第(5)-(6)行对速度和位置进行简单的显式欧拉积分。新位置 并不直接分配给位置，而只是作为预测值使用。在第(7)行中，非永久性外部约束（如碰撞约束）在每个时间步开始时从零开始生成。这里使用原始位置和预测位置来执行连续碰撞检测。然后，求解器 (8)-(10) 对预测位置进行迭代修正，使其满足 外部和 内部约束条件。最后，修正后的位置 用于更新位置和速度。在更新位置的同时更新速度至关重要。如果不这样做，模拟就不会产生二阶系统的正确行为。正如您所看到的，这里使用的积分方案与 Verlet 方法非常相似。它还与 Jos Stam 的 Nucleus 求解器[Sta09]密切相关，后者也使用一组约束条件来描述要模拟的对象。主要区别在于 Nucleus 求解的是速度约束，而不是位置约束。
3.2. The System to be Solved 3.2.待解系统
The goal of the solver step (8)-(10) is to correct the predicted positions of the particles such that they satisfy all constraints. The problem that needs to be solved comprises of a set of equations for the unknown position components, where is now the total number of constraints. This system does not need to be symmetric. If the system is over-determined (underdetermined). In addition to the asymmetry, the equations are in general non-linear. The function of a simple distance constraint yields a non-linear equation. What complicates things even further is the fact that collisions produce inequalities rather than equalities. Solving a non-symmetric, non-linear system with equalities and inequalities is a tough problem. 求解步骤(8)-(10)的目标是修正粒子的预测位置 ，使其满足所有约束条件。需要求解的问题包括一组 未知位置分量的 等式，其中 现在是约束条件的总数。这个系统不需要对称。如果 ，则该系统为过确定（欠确定）系统。除了不对称外，方程一般也是非线性的。简单的距离约束函数 会产生一个非线性方程。使问题更加复杂的是，碰撞会产生不等式而不是等式。解决一个非对称、非线性的等式和不等式系统是一个棘手的问题。
Let be the concatenation and let all the constraint functions take the concatenated vector as input while only using the subset of coordinates they are defined for. We can now write the system to be solved as 让 成为连接向量 ，让所有的约束函数 将连接向量 作为输入，同时只使用它们所定义的坐标子集。现在我们可以将待求解的系统写成
where the symbol denotes either or . NewtonRaphson iteration is a method to solve non-linear symmetric systems with equalities only. The process starts with a first guess of a solution. Each constraint function is then linearized in the neighborhood of the current solution using 其中，符号 表示 或 。牛顿-拉夫逊迭代法是一种只求解等式的非线性对称系统的方法。该过程从对解法的第一次猜测开始。然后，在当前解的邻域内对每个约束函数进行线性化处理。
This yields a linear system for the global correction vector 这就产生了全局校正矢量的线性系统
where is the dimensional vector containing the derivatives of the function w.r.t. all its parameters, i.e. the components of . It is also the -th row of the linear system. Both, the rows and the right hand side scalars are constant because they are evaluated at the location before the system is solved. When and only equalities are present, the system can be solved by any linear solver, e.g. a preconditioned conjugate gradient method. Once it is solved for the current solution is updated as . A new linear system is generated by evaluating and at the new location after which the process repeats. 其中 是 维向量，包含函数 与其所有参数相关的导数，即 的 分量。它也是线性系统的 -th row。行 和右侧标量 都是常数，因为它们是在求解系统之前在 处求值的。当 且只存在等式时，该系统可以用任何线性求解器求解，如预处理共轭梯度法。一旦求解出 ，当前解就会更新为 。在新位置对 和 求值，生成新的线性系统，然后重复上述过程。
If the resulting matrix of the linear system is nonsymmetric and not invertible. Goldenthal et al. [GHF*07] solve this problem by using the pseudo-inverse of the system matrix which yields the best solution in the least-squares sense. Still, handling inequalities is not possible directly. 如果 ，线性系统的结果矩阵是非对称的，不可反演。Goldenthal 等人[GHF*07]通过使用系统矩阵的伪逆来解决这个问题，从而得到最小二乘意义上的最佳解。不过，直接处理不等式仍然是不可能的。
3.3. The Non-Linear Gauss-Seidel Solver 3.3.非线性高斯-赛德尔求解器
In the position-based dynamics approach, non-linear GaussSeidel is used. It solves each constraint equation separately. Each constraint yields a single scalar equation for all the particle positions associated with it. The subsystem is therefore highly under-determined. PBD solves this problem as follows. Again, given we want to find a correction such that . It is important to notice that 在基于位置的动力学方法中，使用了非线性高斯赛德尔（GaussSeidel）。它分别求解每个约束方程。每个约束都会产生一个与之相关的所有粒子位置的标量方程 。因此，子系统的确定性很低。PBD 解决这一问题的方法如下。同样，在给定 的情况下，我们希望找到一个修正方程 ，使得 。需要注意的是
PBD also linearizes the constraint function but individually for each constraint. The constraint equation is approximated by PBD 也对约束函数进行线性化处理，但对每个约束条件单独处理。约束方程近似为
The problem of the system being under-determined is solved by restricting to be in the direction of which conserves the linear and angular momenta. This means that only one scalar - a Lagrange multiplier - has to be found such that the correction 通过限制 在 的方向上，从而保持线性和角矩，解决了系统未充分确定的问题。这意味着只需找到一个标量 （拉格朗日乘数），就可以修正
solves Equation (1). This yields the following formula for the correction vector of a single particle 解方程 (1)。由此得出单个粒子的修正矢量公式如下
where 其中
and 和
As mentioned above, this solver linearizes the constraint functions. However, in contrast to the Newton-Raphson method, the linearization happens individually per constraint. Solving the linearized constraint function of a single distance constraint for instance yields the correct result in a single step. Because the positions are immediately updated after a constraint is processed, these updates will influence the linearization of the next constraint because the linearization depends on the actual positions. Asymmetry does not pose a problem because each constraint produces one scalar equation for one unknown Lagrange multiplier . Inequalities are handled trivially by first checking whether . If this is the case, the constraint is simply skipped. 如上所述，该求解器将约束函数线性化。不过，与牛顿-拉夫逊方法不同的是，线性化是针对每个约束条件单独进行的。例如，求解单个距离约束的线性化约束函数，只需一步就能得到正确结果。由于在处理完一个约束条件后，位置会立即更新，这些更新会影响下一个约束条件的线性化，因为线性化取决于实际位置。不对称不会造成问题，因为每个约束条件都会产生一个未知拉格朗日乘数的标量方程 。处理不等式的方法很简单，首先检查 。如果是，则跳过该约束。
The fact that each constraint is linearized individually before its projection makes the solver more stable than a global approach in which the linearizations are kept fixed for the entire global solve of a Newton iteration. Liu et al. [LBOK13] pointed out that PBD can be interpreted as a heuristic variant of the variational implicit Euler method taking the inertial term out of the solve and into the integration step of the simulation. 与牛顿迭代的整个全局求解中保持线性化固定的全局方法相比，在投影之前对每个约束条件进行单独线性化的事实使求解器更加稳定。Liu 等人[LBOK13]指出，PBD 可以解释为变式隐式欧拉法的启发式变体，将惯性项从求解中取出，放入模拟的积分步骤中。
We have not considered the stiffness of the constraint so far. There are several ways to incorporate it. The simplest variant is to multiply the corrections by . However, for multiple iteration loops of the solver, the effect of is non-linear. The remaining error for a single distance constraint after solver iterations is . To get a linear relationship we multiply the corrections not by directly but by . With this transformation the error becomes and, thus, becomes linearly dependent on and independent of as desired. However, the resulting material stiffness is still dependent on the time step of the simulation. Real time environments typically use 到目前为止，我们还没有考虑约束的刚度 。有几种方法可以将其考虑在内。最简单的方法是用 乘以修正值 。然而，对于求解器的多次迭代循环， 的影响是非线性的。 求解器迭代后，单个距离约束的剩余误差为 。为了得到线性关系，我们不直接用 乘以修正值，而是用 乘以修正值。通过这种转换，误差变为 ，因此与 成线性关系，而与 无关。不过，由此得出的材料刚度仍取决于模拟的时间步长。实时环境通常使用
Figure 1: Projection of the constraint . The corrections are weighted according to the inverse masses . 图 1：约束投影 。修正 根据反质量加权 。
fixed time steps in which case this dependency is not problematic. 在这种情况下，这种依赖性就不成问题了。
3.4. Constraint Examples 3.4.约束示例
In the following we will introduce different constraint examples. For better readability we define . 下面我们将介绍不同的约束示例。为了提高可读性，我们定义 。
3.4.1. Stretching 3.4.1.拉伸
To give an example, let us consider the distance constraint function . The derivatives with respect to the points are and with . The scaling factor is, thus, and the final corrections 举例来说，让我们考虑距离约束函数 。与点有关的导数为 和 ，与 。因此，缩放因子 为 ，最终修正值为
which are the formulas proposed in [Jak01] for the projection of distance constraints (see Figure 1). They pop up as a special case of the general constraint projection method. 是 [Jak01] 中提出的距离约束投影公式（见图 1）。它们是一般约束投影法的特例。
3.4.2. Bending 3.4.2.弯曲
In cloth simulation it is important to simulate bending in addition to stretching resistance. To this end, for each pair of adjacent triangles and a bilateral bending constraint is added with constraint function 在布料模拟中，除了拉伸阻力外，模拟弯曲也很重要。为此，我们为每对相邻三角形 和 添加了一个双边弯曲约束，约束函数为
and stiffness . The scalar is the initial dihedral angle between the two triangles and is a global user parameter defining the bending stiffness of the cloth (see Figure 2). The advantage of this bending term over adding a distance constraint between points and is that it is independent of stretching. This is because the term is independent of edge lengths. 和刚度 。标量 是两个三角形之间的初始二面角，而 是一个全局用户参数，用于定义布的弯曲刚度（见图 2）。与在 和 两点之间添加距离约束相比，该弯曲项的优势在于与拉伸无关。这是因为弯曲项与边缘长度无关。
3.4.3. Triangle Collisions 3.4.3.三角形碰撞
Self collisions within cloth can be handled by additional unilateral constraints. For vertex moving through a triangle 布内的自碰撞可通过额外的单边约束来处理。对于通过三角形移动的顶点
Figure 2: For bending resistance, the constraint function is used. The actual dihedral angle is measured as the angle between the normals of the two triangles. 图 2：对于抗弯强度，使用了约束函数 。实际的二面角 是以两个三角形的法线之间的夹角来测量的。
Figure 3: Constraint function . makes sure that stays above the triangle by the cloth thickness . 图 3：约束函数 。 确保 通过布的厚度 保持在三角形 的上方。
, the constraint function reads ，约束函数为
where is the cloth thickness. If the vertex enters from below with respect to the triangle normal, the constraint function has to be 其中 是布的厚度。如果顶点从三角形法线的下方进入，则约束函数必须为
3.4.4. Volume Conservation 3.4.4.体积保持
For tetrahedral meshes it is useful to have a constraint that conserves the volume of single tetrahedron. Such a constraint has the form 对于四面体网格来说，有一个保持单个四面体体积的约束条件是非常有用的。这种约束的形式为
where and are the four corners of the tetrahedron and is its rest volume. In a similar way, the area of a triangle can be kept constant by introducing 其中 和 是四面体的四个角， 是四面体的静止体积。同样，三角形的面积也可以通过引入
3.4.5. Cloth Balloons 3.4.5.布气球
For closed triangle meshes, overpressure inside the mesh as shown in Figure 5 can easily be modeled with an equality constraint concerning all vertices of the mesh: 对于封闭三角形网格，如图 5 所示，网格内的过压可以通过网格的所有 顶点的相等约束轻松建模：
Here and are the three indices of the vertices belonging to triangle . The sum computes the actual volume of the closed mesh. It is compared against the original volume times the overpressure factor . This constraint function yields the gradients 这里 和 是属于三角形 的三个顶点的索引。和计算封闭网格的实际体积。将其与原始体积 乘以超压系数 进行比较。此约束函数产生梯度
.
These gradients have to be scaled by the scaling factor given in Equation (3.3) and weighted by the masses according to Equation (2) to get the final projection offsets . 这些梯度必须按公式 (3.3) 给出的比例因子进行缩放，并根据公式 (2) 按质量加权，才能得到最终的投影偏移 。
Figure 5: Simulation of overpressure inside a character. 图 5：模拟字符内部的超压。
3.4.6. Fluids 3.4.6.流体
It is also possible to simulate fluids in the PBD framework even though it has been used almost exclusively for the simulation of deformable objects. We mention fluids simply as an item in the list of possible constraints because all that is needed to simulate liquids and gases is a specialized constraint. 尽管 PBD 框架几乎只用于模拟可变形物体，但它也可以模拟流体。我们只是将流体作为可能的约束条件列表中的一项，因为模拟液体和气体所需的只是一个专门的约束条件。
A straightforward approach would be to model the fluid as a system of particles constrained to maintain a minimum distance from each other, however this leads to granular-like behavior and will typically fail to reach hydrostatic equilibrium when coming to rest. An alternative method is presented by Macklin and Müller [MM13] where fluid incompressibility is enforced using density constraints. Borrowing the concept of a density estimator from Smoothed Particle Hydrodynamics (SPH) [Mon94, Mon92], a density constraint is constructed for each particle in the system as follows 一种直接的方法是将流体建模为一个颗粒系统，约束其相互之间保持最小距离，但这会导致类似颗粒的行为，并且在静止时通常无法达到流体静力学平衡。Macklin 和 Müller 提出了另一种方法[MM13]，即使用密度约束来强制流体的不可压缩性。借用平滑粒子流体力学（SPH）[Mon94, Mon92]中的密度估算器概念，为系统中的每个粒子构建了密度约束 ，如下所示
where is the fluid rest density and is the density at a particle, defined as the sum of smooth kernels [MCG03] centered at the particle's neighbor positions 其中 是流体静止密度， 是粒子处的密度，定义为以粒子邻近位置为中心的平滑核[MCG03]之和
Note that here each particle's mass is assumed to be one, and the rest density adjusted accordingly. In order to solve these density constraints using position-based dynamics, the derivative of the constraint function (3) with respect to each particle's position is required. This can be calculated using the gradient of SPH kernels 需要注意的是，这里假定每个粒子的质量为一，并相应调整静态密度。为了使用基于位置的动力学方法解决这些密度约束，需要得到约束函数 (3) 相对于每个粒子位置的导数。这可以用 SPH 核的梯度来计算
Figure 4: The image shows a mesh that is simulated using stretching and bending constraints. The top row shows and . The bottom row shows and . 图 4：图中显示的是使用拉伸和弯曲约束进行模拟的网格。上行显示 和 。下行显示 和 。
Then, by taking advantage of symmetry in the SPH smoothing kernel , the corrective change in position due to the particle's own density constraint, and the density constraints of its neighbors is given by 然后，利用 SPH 平滑核 中的对称性，粒子自身密度约束及其邻近密度约束导致的位置修正变化由以下公式给出
where is the per-constraint scaling factor (see section 3.3). Figure 6 shows a real-time water simulation using this method. 其中 是每个约束的比例因子（见第 3.3 节）。图 6 显示了使用这种方法进行的实时水模拟。
Figure 6: wave pool scene consisting of fluid particles simulated in frame on the GPU. Incompressibility is enforced using density constraints solved using positionbased dynamics. 图 6： 波浪池场景，由 流体粒子组成，在 GPU 上以 帧模拟。不可压缩性是通过使用基于位置的动力学求解的密度约束来实现的。
3.5. Strain Limiting 3.5.应变限制
Strain limiting is an important topic in the field of cloth simulation. The reason is that the low solver iteration counts used in real-time applications yield stretchy cloth. Since most cloth types are perceived by the human eye as completely inextensible, it is important to make simulated cloth inextensible in order to avoid disturbing visual artifacts [GHF* . 应变限制是布料模拟领域的一个重要课题。其原因在于，实时应用中使用的求解器迭代次数较低，会产生拉伸布料。由于大多数布料类型在人眼看来是完全不可拉伸的，因此必须使模拟布料不可拉伸，以避免干扰视觉效果 [GHF* 。
A strain limiting method makes sure that the overall stretch of the cloth stays below a certain threshold. In force based simulations, strain limiting is a separate pass which is executed before or after the regular cloth solver. In most cases, this pass moves the positions of vertices directly, even in force based simulations. Therefore, most strain limiting methods fall under the category of position-based methods. 应变限制方法可确保布的整体拉伸保持在某个阈值以下。在基于力的模拟中，应变限制是在常规布线求解器之前或之后执行的一个单独过程。在大多数情况下，这一过程会直接移动顶点的位置，即使在基于力的模拟中也是如此。因此，大多数应变限制方法都属于基于位置的方法。
A straightforward way of limiting strain is to iterate through all edges of a cloth mesh and project the adjacent particles of overstretched edges as shown in Figure 1 so that the stretch of the edge does not exceed the stretch limit. Provot [Pro95] was among the first to use this method in the context of cloth simulation. He performs a single iteration through all cloth edges after a force based solver. Desbrun et al. [DSB99] and Bridson et al. [BMF03] later used the same post solver strain limiter but with multiple iterations through all edges. Due to its simplicity, this method is still one of the most popular strain limiting methods used in cloth simulations . 限制应变的直接方法是遍历布网格的所有边缘，并如图 1 所示投影出过度拉伸边缘的相邻粒子，使边缘的拉伸不超过拉伸极限。Provot [Pro95] 是最早在布料模拟中使用这种方法的人之一。他使用基于力的求解器对所有布边进行一次迭代。Desbrun 等人 [DSB99] 和 Bridson 等人 [BMF03] 后来使用了相同的后求解应变限制器，但对所有边缘进行了多次迭代。由于其简单性，这种方法仍然是布模拟中最常用的应变限制方法之一。
The method is very similar to position-based cloth simulation. The main difference is that the strain limiting pass described above does not influence the velocities. These are updated by the force-based solver. In contrast, position-based cloth simulation derives the new velocities from the projec- 该方法与基于位置的布模拟非常相似。主要区别在于上述应变限制通道不会影响速度。速度由基于力的求解器更新。相比之下，基于位置的布面模拟则是通过预测布面的应变来获得新的速度。
tions, making an additional solver pass obsolete. Therefore, every position-based strain limiting method used in force based simulations can directly be used in a PBD solver. 因此，额外的求解器就显得不合时宜了。因此，在基于力的模拟中使用的每一种基于位置的应变限制方法都可以直接用于 PBD 求解器。
The result of projecting along edges depends on the structure of the mesh. To reduce this artifact, Wang et al. [WOR10] propose to limit the principal strains of the 2D deformation field within each triangle. The 2D deformation field can be determined by considering the 2D coordinates of the vertices of a triangle within the planes of the rest and current triangle configurations. Wang et al. compute the principal strains of the 2D deformation gradient, clamp them and construct a new 2D transformation using the clamped strains. With this new transformation they correct the current positions of the triangle vertices. As before, to limit strain globally, they iterate through all triangles multiple times in a Gauss-Seidel fashion. 沿边缘投影的结果取决于网格的结构。为了减少这种假象，Wang 等人[WOR10]建议限制每个三角形内二维变形场的主应变。二维变形场可通过考虑三角形顶点在其余和当前三角形配置平面内的二维坐标来确定。Wang 等人计算出二维变形梯度的主应变，将其夹紧，并利用夹紧的应变构建新的二维变换。通过这种新的变换，他们修正了三角形顶点的当前位置。与之前一样，为了限制全局应变，他们以高斯-赛德尔方式多次遍历所有三角形。
Due to the relatively slow convergence rate of a GaussSeidel solver, high iteration counts are necessary to limit the strain globally which slows down the simulation. The two main methods to improve the convergence rate are the use of a global Newton-Raphson solver as proposed by Goldenthal et al. [GHF*07] or to perform Gauss-Seidel iterations on a hierarchy of meshes as proposed in [Mü108], [WOR10] and [SKBK13]. However, these methods complicate the implementation and even though their convergence rate is higher, a single iteration can be significantly more expensive than a simple Gauss-Seidel iteration. 由于高斯-塞德尔求解器的收敛速度相对较慢，因此需要高迭代次数来限制全局应变，从而减慢模拟速度。提高收敛速度的两种主要方法是使用 Goldenthal 等人提出的全局牛顿-拉斐森求解器[GHF*07]，或在网格层次上进行高斯-赛德尔迭代，如[Mü108]、[WOR10]和[SKBK13]中提出的方法。不过，这些方法的实现比较复杂，而且即使收敛率较高，单次迭代的成本也会大大高于简单的高斯-赛德尔迭代。
Recently, Kim et al. [KCM12] found a surprisingly simple and robust technique they call Long Range Attachments (LRA) to prevent cloth from getting stretched globally with low iteration counts. Their method exploits the fact that stretching artifacts almost always appear when cloth is attached. In this case, instead of only applying attachment constraints to the subset of the vertices near the region where the cloth is attached and relying on error propagation of the solver for all other vertices, they apply unilateral attachment constraints to all the vertices by attaching each vertex to one or more attachment point directly. The rest lengths of these long range attachments can either be set to the Euclidean distance in the rest state or via measuring geodesic lengths along the cloth. Figure 7 demonstrates the method on a single rope attached at one end. The method allows the simulation of a piece of cloth with vertices at interactive rates as shown in Figure 8. 最近，Kim 等人[KCM12]发现了一种令人惊讶的简单而稳健的技术，他们称之为 "远距离附着 (LRA)"，可以在低迭代次数的情况下防止布料在全局范围内被拉伸。他们的方法利用了一个事实，即拉伸假象几乎总是出现在布被附着时。在这种情况下，他们不再只对靠近布匹附着区域的顶点子集应用附着约束，而是通过将每个顶点直接附着到一个或多个附着点，对所有顶点应用单边附着约束。这些远距离附着点的静止长度可以设置为静止状态下的欧几里得距离，也可以通过测量沿布的大地测量长度来设置。图 7 演示了该方法在单根绳索一端的应用。如图 8 所示，该方法允许以交互式速率模拟一块带有 个顶点的布。
A similar approach was recently proposed by Müller et al. [MKC12] to guarantee zero stretch in a single pass for the case of attached ropes. This approach allows the simulation of thousands of hair strands in real time (Figure 10). Figure 9 visualizes the basic idea. Particle is attached. To satisfy the first distance constraint, particle is moved towards such that their mutual distance is . Particle is then moved towards the new position of and similarly along the chain until the last particle is reached. After this single pass, all the distance constraints are satisfied. This 最近，Müller 等人[MKC12]提出了一种类似的方法，以确保在连接绳索的情况下一次通过时拉伸为零。这种方法可以实时模拟数千根发丝（图 10）。图 9 展示了基本思路。附带粒子 。为了满足第一个距离约束条件，粒子 被移向 ，使它们之间的相互距离为 。然后将粒子 移向 的新位置，并沿着链条进行类似的移动，直到到达最后一个粒子。经过这一次移动后，所有的距离约束都得到了满足。这
Figure 7: The Long Range Attachments (LRA) method used to simulate an inextensible rope attached at one end. Each particle is constrained or remain inside a sphere centered at the attachment point (red) whose radius is the initial distance from the particle to the attachment. For each configuration, target positions are shown in green when particles need to be projected. Particles inside the constraint spheres are allowed to move freely. 图 7：远距离附着（LRA）方法用于模拟一端附着在物体上的不可伸展的绳索。每个粒子都被限制在一个以附着点（红色）为中心的球体内，该球体的半径是粒子到附着点的初始距离。对于每种配置，当粒子需要投射时，目标位置显示为绿色。约束球内的粒子可以自由移动。
Figure 8: Simulation of a piece of cloth with vertices at on a GPU using LRA. 图 8：使用 LRA 在 GPU 上模拟一块带有 顶点的布， 。
method is called Follow The Leader (FTL). While LRA guarantees zero stretch of all the particles w.r.t. the attachment points, the constraint between consecutive particles can still remain overstretched. On the other hand, in contrast to LRA which is momentum conserving, FTL introduces unphysical behavior. Not projecting distance constraints symmetrically means that a system is simulated for which each particle has infinitely more mass than its successor. To compensate for this behavior, the authors replace the PBD velocity update by 这种方法被称为 "跟随领导者（FTL）"。虽然 LRA 可以保证所有粒子在附着点上的拉伸为零，但连续粒子之间的约束仍有可能过度拉伸。另一方面，与动量守恒的 LRA 相比，FTL 引入了非物理行为。不对称地投影距离约束意味着在模拟的系统中，每个粒子的质量都无限地大于其后续粒子的质量。为了补偿这种行为，作者将 PBD 速度更新 替换为
where is the position correction applied to particle 其中 是应用于粒子的位置修正
and a scaling factor do influence damping. While this modification of DFTL (dynamic FTL) hides the un-physical behavior of FTL, it introduces a certain amount of damping which is acceptable for the simulation of hair and fur as the author's results show. 和 缩放因子确实会影响阻尼。虽然这种对 DFTL（动态超光速）的修改掩盖了超光速的非物理行为，但它引入了一定量的阻尼，正如作者的结果所显示的那样，这种阻尼对于头发和毛皮的模拟是可以接受的。
Figure 9: Follow The Leader (FTL) projection. Starting from the attachment down, each particle is moved directly towards its predecessor such that their mutual distance constraint is satisfied. 图 9：跟随领导者（FTL）投影。从附着点向下开始，每个粒子直接向其前身移动，以满足它们之间的相互距离约束。
3.6. Wrinkle Meshes 3.6.皱褶网格
In cloth simulations, reducing the mesh resolution not only reduces the cost of a single solver iteration but also the number of iterations required to get visually pleasing results. In [MC10] the authors proposed a way to reduce the resolution of the dynamic mesh without losing too much visual detail. The most significant detail in cloth simulations are small wrinkles. The method is based on the observation that global dynamic behavior of the cloth and wrinkle formation can be separated. Therefore, expensive dynamic simulation including collision handling is performed on a lowresolution mesh. The wrinkle formation is handled on a high resolution mesh that is attached to the dynamic mesh (see Figures 11 and 12). Since wrinkles do not oscillate, it is sufficient to use a static solver with a low iteration count on the high-resolution mesh. 在布仿真中，降低网格分辨率不仅可以减少单次求解器迭代的成本，还可以减少迭代次数，从而获得视觉上令人满意的结果。在 [MC10] 中，作者提出了一种在不损失太多视觉细节的情况下降低动态网格分辨率的方法。布料仿真中最重要的细节是小褶皱。该方法基于这样一种观点，即布料的全局动态行为和褶皱的形成是可以分开的。因此，昂贵的动态模拟包括碰撞处理都是在低分辨率网格上进行的。褶皱的形成是在附加到动态网格的高分辨率网格上处理的（见图 11 和图 12）。由于皱纹不会摆动，因此只需在高分辨率网格上使用迭代次数较少的静态求解器即可。
Figure 11: Basic idea of wrinkle meshes. The high resolution wrinkle mesh (white vertices) follows the low-resolution dynamic mesh (black vertices) by restricting the white vertices to remain within a certain distance (gray discs) to the dynamic mesh. 图 11：皱褶网格的基本概念。高分辨率皱纹网格（白色顶点）跟随低分辨率动态网格（黑色顶点），限制白色顶点与动态网格保持一定距离（灰色圆盘）。
Figure 12: Visualization of the wrinkle mesh (solid) and the underlying dynamic mesh (wireframe). 图 12：皱纹网格（实体）和底层动态网格（线框）的可视化。
Figure 13 shows the constraints defined on the highresolution mesh to make it form wrinkles and follow the dynamic mesh. The attachment constraints makes sure that the vertices of the wrinkle mesh stay close to their attachment points on the dynamic mesh. If the dynamic mesh has outside/inside information, a one-sided constraint can be used which makes sure that the wrinkle vertices stay on the outside of the dynamic mesh, thus avoiding penetrations with other objects. The stretching and bending constraints are responsible for wrinkle formation. 图 13 显示了在高分辨率网格上定义的约束条件，这些约束条件可使网格形成皱纹并跟随动态网格。附着约束确保皱纹网格的顶点紧贴动态网格上的附着点。如果动态网格有外侧/内侧信息，则可以使用单侧约束，确保皱纹顶点位于动态网格的外侧，从而避免与其他物体发生穿透。拉伸和弯曲约束负责皱纹的形成。
Figure 13: Static constraints on a wrinkle mesh: Attachment constraint (top left), one sided attachment constraint (top right), stretch constraint (bottom left) and bending constraint (bottom right). 图 13：皱纹网格上的静态约束：附着约束（左上）、单面附着约束（右上）、拉伸约束（左下）和弯曲约束（右下）。
3.7. Damping 3.7.阻尼
The quality of dynamic simulations can generally be improved by the incorporation of an appropriate damping scheme. As a positive effect, damping can improve the stability by reducing temporal oscillations of the point positions of an object. This enables the use of larger time steps 一般来说，采用适当的阻尼方案可以提高动态模拟的质量。作为一种积极的效果，阻尼可以减少物体点位置的时间振荡，从而提高稳定性。这样就可以使用更大的时间步长
Figure 10: Dynamic FTL allows the simulation of every hair strand in real time. From left to right: 47k hair strands simulated at 25 fps including rendering and hair-hair repulsion. Long hair composed of particles at . Curly hair using visualization post-processing. 图 10：动态超光速可实时模拟每根发丝。从左到右：以 25 fps 的速度模拟了 47k 根头发，包括渲染和头发与头发之间的排斥力。由 个粒子组成的长发， 。使用可视化后期处理的卷发。
which increases the performance of a dynamic simulation. On the other hand, damping changes the dynamic motion of the simulated objects. The resulting effects can be either desired, e.g. reduced oscillations of a deformable solid, or disturbing, e.g. changes of the linear or angular momentum of the entire object. 从而提高动态模拟的性能。另一方面，阻尼会改变模拟对象的动态运动。由此产生的效果既可以是理想的，例如减少可变形固体的振荡，也可以是干扰性的，例如改变整个物体的线动量或角动量。
Generally, a damping term can be incorporated into the motion equation of an object where denotes the vector of all first time derivatives of positions. If the user-defined matrix is diagonal, absolute velocities of the points are damped, which sometimes is referred to as point damping. If appropriately computed, such point damping forces result in an improved numerical stability by reducing the acceleration of a point. Such characteristics are desired in some settings, e.g. in the context of friction. In the general case, however, the overall slow-down of an object, caused by point damping forces, is not desired. Point damping forces are, e.g., used in [TF88] or in [PB88], where point damping is used for dynamic simulations with geometric constraints such as point-to-nail. 一般来说，可以在物体的运动方程中加入阻尼项 ，其中 表示位置的所有第一次导数向量。如果用户定义的矩阵 是对角线，则点的绝对速度会受到阻尼，有时称为点阻尼。如果计算得当，这种点阻尼力可通过减小点的加速度来提高数值稳定性。在某些情况下，例如在摩擦的情况下，这种特性是理想的。但在一般情况下，点阻尼力导致的物体整体减速并不理想。例如，[TF88] 或 [PB88] 中就使用了点阻尼力，其中点阻尼用于具有几何约束（如点对钉）的动态模拟。
In order to preserve linear and angular momentum of deformable objects, symmetric damping forces, usually referred to as spring damping forces, can be used. Such forces can be represented by non-diagonal entries in the matrix C. Damping forces are, e.g., described by Baraff and Witkin [BW98] or Nealen et al. [NMK* 06]. These forces can also be applied to position-based methods. However, as the approaches of Baraff and Witkin and Nealen et al. rely on topological information of the object geometry, they cannot be applied to meshless techniques such as shape matching. 为了保持可变形物体的线性动量和角动量，可以使用对称阻尼力，通常称为弹簧阻尼力。这种力可以用矩阵 C 中的非对角项来表示。阻尼力由 Baraff 和 Witkin [BW98] 或 Nealen 等人 [NMK* 06] 等人描述。这些力也可应用于基于位置的方法。然而，由于 Baraff 和 Witkin 以及 Nealen 等人的方法依赖于物体几何形状的拓扑信息，因此无法应用于无网格技术，如形状匹配。
Point and spring damping can be used to reduce current velocities or relative velocities. However, it is generally more appropriate to consider predicted velocities or relative velocities for the next time step. 点阻尼和弹簧阻尼可用于降低当前速度或相对速度。不过，一般来说，考虑下一时间步的预测速度或相对速度更为合适。
An interesting damping alternative has been presented in [SGT09]. Here, the idea of symmetric, momentumconserving forces is extended to meshless representations. Global symmetric damping forces are computed with respect to the center of mass of an object. While such forces conserve the linear momentum, the preservation of the angular momentum is guaranteed by force projection onto relative positions or by torque elimination using Linear Programming. The approach presented in [SGT09] iteratively computes damping forces. The paper, however, also shows the convergence of the iterative process and how the solution can be computed directly without performing iterations. Therefore, the approach is an efficient alternative to compute damping forces for arbitrary position-based deformation models with or without connectivity information. The approach can be used to damp oscillations globally or locally for user-defined clusters. SGT09] 提出了一种有趣的阻尼替代方案。在这里，对称、动量守恒力的概念扩展到了无网格表示法。全局对称阻尼力是相对于物体质心计算的。虽然这种力能保持线性动量，但角动量的保持是通过力投影到相对位置或使用线性规划消除扭矩来保证的。SGT09] 提出的方法是迭代计算阻尼力。不过，该论文还展示了迭代过程的收敛性，以及如何在不进行迭代的情况下直接计算解。因此，无论是否有连接信息，该方法都是计算基于位置的任意变形模型阻尼力的有效替代方法。该方法可用于全局或局部阻尼振动，适用于用户定义的集群。
3.8. Parallelization 3.8.并行化
Parallelization of the PBD approach is an important topic since multi-core systems and massively parallel GPUs are ubiquitous today. PBD 方法的并行化是一个重要课题，因为多核系统和大规模并行 GPU 如今已无处不在。
In a single CPU implementation, the solver processes the constraints one by one in a Gauss-Seidel-type fashion. Thereby, after each constraint projection, the positions of affected particles are immediately updated. In a parallel implementation, the constraints are processed in parallel by multiple threads. If two constraints affecting the same particle are handled by two different threads simultaneously, they are not allowed to immediately update the particle's position because writing to the same position simultaneously leads to race conditions making the process unpredictable. A solution to circumvent this problem is to use atomic operations. Such operations are guaranteed not to be interrupted. However, atomics can slow down parallel execution significantly. 在单 CPU 实现中，求解器以高斯-赛德尔方式逐一处理约束条件。因此，每次约束投影后，受影响粒子的位置都会立即更新。在并行执行中，约束条件由多个线程并行处理。如果由两个不同的线程同时处理影响同一粒子的两个约束条件，它们就不能立即更新粒子的位置，因为同时写入同一位置会导致竞赛条件，使处理过程变得不可预测。规避这一问题的解决方案是使用原子操作。这种操作可以保证不被中断。不过，原子操作会大大降低并行执行的速度。
To avoid these issues, a parallel implementation of PBD needs to split the constraints into groups or phases. In each phase, none of the constraints are allowed to share a common particle. With this restriction, the constraints in the first phase can be processed in parallel without conflicts. Then, after a global synchronization, the next phase can be processed. This cycle is repeated until all constraints are processed. 为了避免这些问题，PBD 的并行执行需要将约束条件分成若干组或若干阶段。在每个阶段中，不允许任何约束条件共享一个共同粒子。有了这一限制，第一阶段的约束条件就可以并行处理，而不会发生冲突。然后，在全局同步后，可以处理下一阶段。如此循环往复，直到处理完所有约束条件。
As an example, if particles are connected in a serial chain, the constraints . can be processed in phase 1 and the constraints . in phase 2. This specific example corresponds to the Red-Black Gauss Seidel scheme, where there are two sets (colors) of constraints. For more general types of constraint such as the stretch, shear and bending constraints of cloth, more phases are needed. In this general case, splitting constraints into phases corresponds to the graph coloring problem, where each constraint corresponds to a node of the graph and two constraints are connected by an edge if they affect one or more common particles. The minimum number of colors determines how many phases are needed in the parallel execution of PBD. Keeping the number of phases small is not the only optimization criterion. The sets also need to have similar sizes for good load balancing. 举例来说，如果 粒子以串行链的形式连接，则可以在第 1 阶段处理 . 约束条件，在第 2 阶段处理 . 约束条件。这个具体例子对应于红黑高斯塞德尔方案，其中有两组（颜色）约束。对于更一般的约束类型，如布的拉伸、剪切和弯曲约束，则需要更多阶段。在这种一般情况下，将约束条件划分为不同阶段就相当于图着色问题，其中每个约束条件对应图中的一个节点，如果两个约束条件影响到一个或多个共同粒子，则它们通过边相连。颜色的最少数量决定了 PBD 并行执行时需要多少个阶段。保持较少的阶段数并不是唯一的优化标准。为了实现良好的负载平衡，各集合还需要具有相似的大小。
3.9. Discussion 3.9.讨论情况
Position-based dynamics is fast, easy to implement and controllable. Furthermore, it avoids the overshooting problems of force-based simulation models when using an explicit time integration scheme. The method can handle arbitrary bilateral and unilateral constraints as long as the gradient of the constraint function can be determined. Therefore, this method is very flexible and has already been used to simulate cloth, deformable solids and fluids. 基于位置的动力学快速、易于实施和控制。此外，在使用显式时间积分方案时，它还避免了基于力的模拟模型的过冲问题。只要能确定约束函数的梯度，该方法就能处理任意的双边和单边约束。因此，该方法非常灵活，已被用于模拟布料、可变形固体和流体。
However, position-based dynamics also has some disadvantages. The stiffness of the model does not only depend on the user-defined stiffness parameter but also on the time step size and the number of solver iterations. Although the dependency can be reduced as described in Section 3.3, it cannot be completely removed. Therefore, it is difficult to adjust parameters independently. Decoupling these parameters as well as adaptive time stepping are open problems and important topics for future work. Another drawback is that position-based dynamics is not convergent, i.e. the simulation does not converge to a certain solution with mesh refinement. Hence, the usage of adaptive meshes is another open problem. 不过，基于位置的动力学也有一些缺点。模型的刚度不仅取决于用户定义的刚度参数，还取决于时间步长和求解器迭代次数。虽然如第 3.3 节所述，这种依赖性可以减小，但无法完全消除。因此，很难独立调整参数。将这些参数解耦以及自适应时间步进都是有待解决的问题，也是未来工作的重要主题。另一个缺点是基于位置的动力学不收敛，即仿真不会随着网格细化而收敛到某个解。因此，使用自适应网格是另一个有待解决的问题。
4. Shape Matching 4.形状匹配
The geometrically motivated concept of shape matching to simulate deformable objects was introduced by Müller et al. [MHTG05]. Shape matching is a meshless approach which is able to simulate visually plausible elastic and plastic deformations (see Figure 14). This approach is easy to implement, very efficient and unconditionally stable. Müller 等人[MHTG05]提出了以几何为动机的形状匹配概念来模拟可变形物体。形状匹配是一种无网格方法，能够模拟视觉上可信的弹性和塑性变形（见图 14）。这种方法易于实现、非常高效且无条件稳定。
The basic idea of simulating elastic behavior with shape matching is shown in Figure 15. For the simulation the initial configuration of the deformable object must be stored. Since no connectivity information is needed, this configuration is defined by the initial positions . In each time step the positions and velocities of the particles are updated without 利用形状匹配模拟弹性行为的基本思路如图 15 所示。模拟时必须存储可变形物体的初始配置。由于不需要连接信息，该配置由初始位置 定义。在每个时间步中，粒子的位置和速度都会被更新，而不需要任何连接信息。
Figure 15: The initial shape with the vertex positions is matched to the deformed configuration to obtain goal positions . The deformed shape is pulled towards these goal positions to simulate elastic behavior. 图 15：将顶点位置为 的初始形状与变形配置 进行匹配，得到目标位置 。将变形形状拉向这些目标位置，以模拟弹性行为。
considering any internal constraints between the particles. Only external forces and collision response are taken into account. Instead of using internal constraints, goal positions are determined by matching the initial shape with the deformed configuration. Then, each particle is pulled towards its goal position. 考虑粒子之间的任何内部约束。只考虑外力和碰撞反应。不使用内部约束，而是通过匹配初始形状和变形配置来确定目标位置。然后，每个粒子都被拉向其目标位置。
In the following we first describe how the goal positions are determined. Then we show how large deformations can be simulated using region-based shape matching and introduce fast summation techniques for this approach. In the end the concept of oriented particles and different extensions of the shape matching method are presented. 下面我们首先介绍如何确定目标位置。然后，我们展示了如何使用基于区域的形状匹配来模拟大变形，并介绍了这种方法的快速求和技术。最后，我们将介绍定向粒子的概念和形状匹配方法的不同扩展。
4.1. Goal Positions 4.1.目标位置
In order to obtain goal positions for the deformed shape the best rigid transformation is determined which matches the set of initial positions and the set of deformed positions . The corresponding rotation matrix and the translational vectors and are determined by minimizing 为了获得变形形状的目标位置，需要确定与初始位置集 和变形位置集 相匹配的最佳刚性变换。相应的旋转矩阵 以及平移矢量 和 是通过最小化来确定的。
where are the weights of the individual points. The optimal translation vectors are given by the center of mass of the initial shape and the center of mass of the deformed shape: 其中 是各个点的权重。最佳平移向量由初始形状的质心和变形形状的质心给出：
If we minimize the term with and , we get the optimal linear transformation of the initial and the deformed shape. This transformation is determined by: 如果我们将 与 和 项最小化，就可以得到初始形状和变形形状的最佳线性变换 。这种变换由以下因素决定
In our case we are only interested in the rotational part of this transformation. Since is symmetric, it contains no rotation. Therefore, we only need to extract the rotational part of to get the optimal rotation for shape matching. 在我们的例子中，我们只对这种变换的旋转部分感兴趣。由于 是对称的，因此不包含旋转。因此，我们只需提取 的旋转部分，就能得到用于形状匹配的最佳旋转 。
Figure 14: Robust and volume-conserving deformations using shape matching. Armadillos (32442 particles total), 20 ducks and 20 tori (21280 particles total) and 20 balls (7640 particles total) were simulated in real-time on a GPU. 图 14：利用形状匹配实现稳健的体积保护变形。在 GPU 上实时模拟了犰狳（共 32442 个粒子）、20 只鸭子和 20 个 tori（共 21280 个粒子）以及 20 个球（共 7640 个粒子）。
This can be done by a polar decomposition of the transformation matrix where is a symmetric matrix. 这可以通过变换矩阵的极性分解 来实现，其中 是对称矩阵。
Finally, the goal positions are determined by 最后，确定目标位置的方法是
where . These goal positions are used to compute position corrections: 其中 。这些目标位置用于计算位置修正：
where is a user-defined stiffness parameter which defines how far the particles are pulled to their goal positions. 其中 是用户自定义的刚度参数，用于定义粒子被拉到目标位置的距离。
Shape matching can be seen as a form of constraint projection which can directly be integrated in the position-based dynamics algorithm. By performing shape matching in line (9) of Algorithm 1 it can be easily combined with other position-based constraint. 形状匹配可以看作是一种约束投影，可以直接集成到基于位置的动力学算法中。通过在算法 1 的第 (9) 行中执行形状匹配，可以很容易地与其他基于位置的约束相结合。
4.2. Region-Based Shape Matching 4.2.基于区域的形状匹配
The shape matching algorithm described above allows only for small deviations from the initial shape. For the simulation of large deformations the concept of region-based shape matching became popular, see e.g. [MHTG05, RJ07, DBB11]. The idea is to perform shape matching on several overlapping regions of the original shape. In each region we can have a small deviation from the corresponding part of the initial shape which results in a large deformation over all regions. 上述形状匹配算法只允许与初始形状有微小偏差。为了模拟大变形，基于区域的形状匹配概念开始流行起来，参见 [MHTG05, RJ07, DBB11]。其原理是对原始形状的多个重叠区域进行形状匹配。在每个区域中，我们都可以与初始形状的相应部分产生微小偏差，从而在所有区域中产生较大变形。
Diziol et al. [DBB11] propose to define a region for each particle of the model where the -th region contains all particles in the -ring of the -th particle in the original mesh of the model. Shape matching is a meshless method but Diziol et al. require a mesh to define the shape matching regions. Rivers and James [RJ07] use a regular lattice instead to define their regions. No matter which kind of regions are used, Diziol 等人[DBB11]建议为模型中的每个粒子定义一个区域，其中 -th 区域包含模型原始网格中 -th 粒子的 -ring 中的所有粒子。形状匹配是一种无网格方法，但 Diziol 等人需要网格来定义形状匹配区域。里弗斯和詹姆斯[RJ07]则使用规则网格来定义他们的区域。无论使用哪种区域、
Figure 16: The stiffness of the model depends on the region size. Smaller regions (top) allow larger deformations than larger regions (bottom). The hexagons in the left images represent the overlapping regions of the model. The right images show the goal positions after one particle is moved away. 图 16：模型的刚度取决于区域大小。较小的区域（上图）比较大的区域（下图）允许更大的变形。左图中的六边形代表模型的重叠区域。右图显示了一个粒子移动后的目标位置。
the stiffness of the model depends on the size of the overlapping regions (see Figure 16). Enlarging the regions results in a more global shape matching and therefore the stiffness of the simulated model is increased. 模型的刚度取决于重叠区域的大小（见图 16）。扩大重叠区域会使整体形状更加匹配，从而提高模拟模型的刚度。
In region-based shape matching a particle is part of multiple regions. In the following we denote the set of regions to which a particle belongs by . Since particles can belong to more than one region, Rivers and James [RJ07] proposed to use modified particle masses for shape matching. This ensures that a particle which is part of many regions has not more influence than others. The optimal translation vectors for a region are determined by 在基于区域的形状匹配中，一个粒子属于多个区域。在下文中，我们用 表示粒子 所属的区域集。由于粒子可能属于多个区域，Rivers 和 James [RJ07] 建议使用修正的粒子质量 进行形状匹配。这确保了属于多个区域的粒子不会比其他粒子有更大的影响力。区域 的最佳平移向量由以下因素决定
where is the effective region mass which can be precomputed. The optimal rotation matrix is computed 其中 是有效区域质量，可以预先计算。计算最佳旋转矩阵
by extracting the rotational part of the following matrix: 的旋转部分：
In this form the first term depends on the particles of the region while the second term depends on the region . This isolation of the dependencies is required for fast summation techniques (see below). 在这种形式下，第一项取决于区域内的粒子 ，而第二项则取决于区域 。快速求和技术（见下文）需要这种依赖关系的隔离。
After performing shape matching for all regions, we get multiple goal positions for each particle. The final goal position for a particle is determined by blending the goal positions of the corresponding regions: 在对所有区域进行形状匹配后，我们会得到每个粒子的多个目标位置。粒子的最终目标位置由相应区域的目标位置混合确定：
4.3. Fast Summation Techniques 4.3.快速求和技术
In the case of region-based shape matching the stiffness increases with growing region size . However, at the same time the computation of the optimal translation and the transformation matrix becomes a bottleneck since large sums have to be computed for each region. For a mesh with the dimension and regions, operations are required with the naive approach. 在基于区域的形状匹配中，刚度会随着区域大小的增加而增加 。但同时，最优平移 和变换矩阵 的计算成为瓶颈，因为每个区域都需要计算大量的和。对于尺寸为 和 区域的网格，采用传统方法需要进行 运算。
4.3.1. Regular Lattices 4.3.1.正则表格
Rivers and James demonstrated in [RJ07] how the number of operations for computing the sums can be reduced to for regular lattices . Their optimization is closely related to the concept of summed-area tables [Cro84]. In their approach they compute the summation for a set of particles just once and reuse it for all regions that contain this set. This reduces redundant computations significantly for a system with large overlapping regions. The fast summation of Rivers and James is based on the usage of cubical regions. These cubical regions can be subdivided in twodimensional plate regions which can again be subdivided in one-dimensional bar regions. The region summation is performed in three passes. In the first pass the sum for each bar is determined. The results are used to compute the sums for the plates which are again used to obtain the final region sum. Each pass requires operations. However, the region sum can even be determined in constant time if we take into account that the sum of two neighboring bars, plates or cubes only differs by one element. Lattice shape matching can be performed in linear time if the sums in Equations (6) and (7) are evaluated using the fast summation technique described above. 里弗斯和詹姆斯在 [RJ07] 中证明了对于正则表格 ，如何将计算求和的操作次数减少到 。他们的优化方法与求和面积表的概念密切相关 [Cro84]。在他们的方法中，对一组粒子只计算一次求和，并在包含这组粒子的所有区域重复使用。这就大大减少了具有大量重叠区域的系统的冗余计算。里弗斯和詹姆斯的快速求和方法基于立方体区域的使用。这些立方体区域可细分为二维板块区域，而二维板块区域又可细分为一维条形区域。区域求和分三次进行。在第一道工序中，确定每根棒材的总和。计算结果用于计算板块的总和，而板块的总和又用于获得最终的区域总和。每次运算需要 。不过，如果考虑到相邻两根条形、板块或立方体的总和只相差一个元素，区域总和甚至可以在恒定时间内确定。如果使用上述快速求和技术对等式(6)和(7)中的和进行评估，晶格形状匹配可以在线性时间内完成。
The FastLSM method of Rivers and James has several limitations. To handle regions where the lattice is not regular, e.g. on the boundary, several sums are defined in a preprocessing step for the corresponding node. In the case of fracturing the definition of these sums must be performed at run-time which is expensive to compute. Small features need a fine sampling to obtain realistic results. Since a regular lattice is used, a fine sampling yields an explosion of the computational costs. FastLSM does not support a varying region size to simulate inhomogeneous material. 里弗斯和詹姆斯的 FastLSM 方法有几个局限性。为了处理晶格不规则的区域，例如边界，需要在预处理步骤中为相应节点定义几个和。在压裂情况下，这些和的定义必须在运行时进行，计算成本很高。小特征需要精细采样才能获得真实的结果。由于使用的是规则网格，精细采样会导致计算成本激增。FastLSM 不支持改变区域大小来模拟不均匀材料。
4.3.2. Adaptive Lattices 4.3.2.自适应网格
Steinemann et al. [SOG08] introduce an adaptive shape matching method which is based on lattice shape matching to overcome these limitations. A fast summation is realized by an octree-based sampling and an interval-based definition of the shape matching regions. The hierarchical simulation model is created by starting with a coarse cubic lattice and then performing an octree subdivision. The subdivision process can be controlled by a user-defined criterion. At the end of the process a simulation node is placed at the center of each leaf cell and a virtual node at the center of each nonleaf cell. A virtual node stores the sum of all its descendant simulation nodes. Steinemann 等人[SOG08]引入了一种基于晶格形状匹配的自适应形状匹配方法，以克服这些限制。通过对形状匹配区域进行基于八度的采样和基于区间的定义，实现了快速求和。分层仿真模型的创建是从粗立方晶格开始，然后进行八叉细分。细分过程可由用户定义的标准控制。细分过程结束后，在每个叶单元的中心放置一个模拟节点，在每个非叶单元的中心放置一个虚拟节点。虚拟节点存储其所有后代模拟节点的总和。
The fast summation for the hierarchical model is performed by an interval-based method which requires operations per region. For each simulation node a shape matching region is defined by a region width . To perform a fast summation, all summation nodes of the region are determined in a pre-processing step. First, for each node of the octree the interval of minimum and maximum distances of all descendant leaves of to are determined. Then, during a top-down traversal each node where the maximum distance is smaller than the region width is added to region . If the descendant leaf nodes are contained only partially in region , the current node must be refined. Only in this case the traversal continues. 分层模型的快速求和采用基于区间的方法，每个区域需要 运算。对于每个模拟节点 ，通过区域宽度 定义一个形状匹配区域。为了进行快速求和，需要在预处理步骤中确定 区域的所有求和节点。首先，对于八叉树的每个节点 ，确定 的所有子叶到 的最小和最大距离间隔。然后，在自顶向下遍历过程中，将最大距离小于区域宽度的每个节点 添加到区域 中。如果子叶节点仅部分包含在区域 中，则必须对当前节点进行细化。只有在这种情况下，遍历才会继续。
The top-down traversal assigns summation nodes to each region. A fast summation can now be performed in two steps. In the first step the sums of all nodes in the hierarchy are determined. This is done by first computing the sums for the simulation nodes which are the leaf nodes of the hierarchy, and then updating the sums of the virtual nodes in a bottom-up fashion. The second step sums up the values of the summation nodes for each region. For a roughly balanced octree the computation of the sums takes time where is the number of simulation nodes. Hence, the adaptive shape matching method requires linear time when using the described fast summation technique to evaluate Equations (6) and (7). 自上而下的遍历会为每个区域分配 求和节点。现在可以分两步进行快速求和。第一步，确定层次结构中所有节点的总和。首先计算作为层次结构叶节点的模拟节点的总和，然后以自下而上的方式更新虚拟节点的总和。第二步是计算每个区域的求和节点值。对于一个大致平衡的八叉树，求和计算需要花费 时间，其中 是模拟节点的数量。因此，在使用所述快速求和技术评估公式 (6) 和 (7) 时，自适应形状匹配方法需要线性时间。
4.3.3. Triangle Meshes 4.3.3.三角形网格
In contrast to Rivers and James, Diziol et al. [DBB11] only use the surface mesh of a volumetric model to simulate its deformation. Therefore, no interior elements are required for the simulation which reduces the computational costs. Diziol et al. introduce a fast summation technique for arbitrary triangle meshes to compute the large sums of the region-based approach efficiently. This technique only 与 Rivers 和 James 不同，Diziol 等人[DBB11]只使用体积模型的表面网格来模拟其变形。因此，模拟不需要内部元素，从而降低了计算成本。Diziol 等人引入了一种针对任意三角形网格的快速求和技术 ，以高效计算基于区域方法的大和。该技术只需
Figure 17: Fast summation technique for arbitrary triangle meshes [DBB11]. First the prefix sums for the disjoint paths are determined. Then the region sum is computed by adding the difference of the intersection interval for each path. 图 17：任意三角形网格的快速求和技术[DBB11]。首先确定相交路径的前缀和。然后将每条路径的相交区间之差相加，计算出区域和。
requires operations instead of and can be performed very efficiently in parallel. 需要 操作，而不是 ，可以非常高效地并行执行。
The fast summation technique of Diziol et al. is based on a subdivision of all particles of the mesh in disjoint paths. A path is a set of vertices which are connected by edges. The paths are determined in a precomputation step. The goal of the path construction algorithm is that each region is intersected by a minimum number of paths. To determine the optimal path layout is computationally expensive. Therefore, a heuristic is used to find a good path layout. Starting with a single vertex, adjacent vertices are added to a path until the path length exceeds a maximum size or cannot be extended any further. The heuristic tries to avoid gaps by choosing vertices which have neighbors that are already part of a path. To obtain paths which are as parallel as possible we add the vertex which is closest to a plane passing through the starting vertex of the current path, e.g. the xy-plane. Diziol 等人的快速求和技术基于将网格中的所有粒子细分为互不相交的路径。路径 是一组由边连接的顶点 。路径在预计算步骤中确定。路径构建算法的目标是每个区域被最少的路径交叉。确定最佳路径布局的计算成本很高。因此，我们采用启发式方法来寻找良好的路径布局。从单个顶点开始，将相邻顶点添加到路径中，直到路径长度超过最大值或无法继续扩展。启发式试图通过选择那些邻近顶点已经是路径一部分的顶点来避免空隙。为了获得尽可能平行的路径，我们会添加最靠近通过当前路径起始顶点的平面（如 xy 平面）的顶点。
The fast summation is split in two phases (see Figure 17). In the first phase the prefix sum for each path is computed with : 快速求和分为两个阶段（见图 17）。在第一阶段，通过 计算每条路径 的前缀和：
Since the prefix sums for all paths are independent of each other, they can be computed in parallel. The sums for a region are computed by first setting and . Then for each path which intersects the region in the interval , the following terms are added: 由于所有路径的前缀和是相互独立的，因此可以并行计算。在计算 区域的和时，首先设置 和 。然后，对于在区间 中与该区域相交的每条路径 ，都要加上以下项：
The final translational vector and the affine matrix are determined by and respectively. 最终的平移向量和仿射矩阵分别由 和 确定。
4.4. Oriented Particles 4.4.定向粒子
For a small number of particles or particles that are close to co-linear or co-planar (as in Figure 18), the matrix in Equation (5) becomes ill-conditioned and the polar decomposition needed to obtain the optimal rotation tends to be numerically unstable. 对于粒子数量较少或接近共线或共平面的粒子（如图 18），方程 (5) 中的矩阵 就会变得条件不良，而获得最佳旋转所需的极性分解在数值上往往不稳定。
To solve this problem, Müller et al. [MC11] proposed to use oriented particles. By adding orientation information to particles, the polar decomposition becomes stable even for single particles. The moment matrix of a single spherical particle with orientation and finite radius at the origin is well defined and can be computed via an integral over its volume as 为了解决这个问题，Müller 等人[MC11]建议使用定向粒子。通过为粒子添加方向信息，即使是单个粒子，极性分解也变得稳定。具有取向 和原点有限半径 的单个球形粒子的力矩矩阵定义明确，可通过对其体积的积分计算如下
where is the volume of a sphere of radius . Since is an orthonormal matrix, always has full rank and an optimal condition number of 1 . For an ellipsoid with radii and we get 其中 是半径为 的球体的体积。由于 是正交矩阵，因此 总是全秩的，最佳条件数为 1。对于半径为 和 的椭球体，我们可以得到
However, the moment matrices of the individual particles cannot simply be added because each one is computed relative to the origin. We need the moment matrix of particle relative to the position . 但是，单个粒子的矩阵不能简单地相加，因为每个矩阵都是相对于原点计算的。我们需要粒子 相对于位置 的力矩矩阵。
Fortunately, this problem can be fixed easily. As we saw above, the equation for computing the moment matrix 幸运的是，这个问题很容易解决。如上所述，计算矩阵的方程为
can be re-written as 可改写为
where and are the centers of mass of the initial and the deformed shape, respectively (see Equation (4)). 其中 和 分别为初始形状和变形形状的质心（见公式 (4)）。
Therefore, shifting the evaluation from the origin to the position yields 因此，将评估从原点移至 的位置，可以得到
Equation (9) now generalizes to 方程 (9) 现在概括为
As you can see, the last form looks like Equation (9) but with all the individual particle moment matrices added in the sum. 如您所见，最后的形式与公式 (9) 类似，但在总和中加入了所有粒子矩阵。
In addition to position and velocity , oriented particles carry a rotation which can be defined as an orthonormal matrix as above or a unit quaternion . They also carry the angular velocity . In the prediction step of position-based dynamics, these two quantities have to be integrated as well: 除了位置 和速度 外，定向粒子还携带旋转，旋转可定义为上述正交矩阵 或单位四元数 。它们还携带角速度 。在基于位置的动力学预测步骤中，也必须对这两个量进行积分：
For stability reasons, should directly be set to if . 出于稳定性考虑，如果 .
After the prediction step, the solver iterates multiple times through all shape match constraints in a Gauss-Seidel type fashion as before. To simulate objects represented by a mesh of linked particles, Müller and Chentanez [MC11] define one shape matching group per particle. A group contains the corresponding particle and all the particles connected to it via a single edge. The positions of the particles in a group are updated as in regular shape matching by pulling them towards the goal positions while the orientation of the center particle only is replaced by the optimal rotation of shape matching. 在预测步骤之后，求解器会以高斯-赛德尔方式对所有形状匹配约束条件进行多次迭代。Müller 和 Chentanez [MC11]对每个粒子定义了一个形状匹配组，以模拟由连接粒子组成的网格所代表的物体。一个组包含相应的粒子和通过单条边与之相连的所有粒子。组内粒子的位置更新与常规形状匹配一样，都是通过将粒子拉向目标位置来实现的，而中心粒子的方向则由形状匹配的最佳旋转来代替。
After the solver has modified the predicted state , the current state is updated using the integration scheme 在求解器修改了预测状态 之后，将使用积分方案更新当前状态
where axis() returns the normalized direction of a quaternion and angle() its angle. Again, for stability reasons, should be set to zero directly if . There are two rotations, and transforming into . It is important to always choose the shorter one, i.e. if use , where is the real part of the quaternion. As in traditional PBD for translation, changing the rotational quantity in the solver also affects its time derivate through the integration step creating the required second order effect. 其中 axis() 返回四元数的归一化方向，angle() 返回四元数的角度。同样，出于稳定性考虑，如果 ， 应直接设置为零。有两种旋转方式， 和 将 转换为 。重要的是始终选择较短的那个，即如果 使用 ，其中 是四元数的实部。与传统 PBD 的平移一样，在求解器中改变旋转量 也会通过积分步骤影响其时间导数 ，从而产生所需的二阶效应。
The orientation information of particles cannot only be used to stabilize shape matching but also to move a visual mesh along with the physical mesh. With position and orientation, each particle defines a full rigid transformation at every point in time. This allows the use of traditional linear blend skinning with particles replacing skeletal bones. 粒子的方向信息不仅可用于稳定形状匹配，还可用于随着物理网格移动可视网格。有了位置和方向信息，每个粒子都能在每个时间点上定义完整的刚性变换。这样就可以使用传统的线性混合蒙皮，用粒子代替骨骼。
An additional advantage of having orientation information is that ellipsoids can be used as collision volumes for particles. This allows a more accurate approximation of the object geometry than with the same number of spherical primitives (see Figure 19). 拥有方向信息的另一个好处是，椭圆体可用作粒子的碰撞体积。与相同数量的球形基元相比，这样可以更精确地近似物体的几何形状（见图 19）。
4.5. Extensions 4.5.扩展
There exist several extensions for shape matching. In the following we will introduce volume conservation and plastic deformation. 形状匹配有几种扩展方法。下面我们将介绍体积守恒和塑性变形。
Figure 18: This underwater scene demonstrates the ability of the oriented particle approach to handle sparse meshes such as the one-dimensional branches of the plants or the fins of the lion fish. 图 18：这个水下场景展示了定向粒子方法处理稀疏网格的能力，例如植物的一维分支或狮子鱼的鱼鳍。
Figure 19: The rotation information of oriented particles cannot only be used to stabilize shape matching, it also allows the use of ellipsoids as collision primitives. The figure shows how the same mesh is approximated much more accurately with ellipsoids (right) than with the same number of spheres (left). 图 19：定向粒子的旋转信息不仅可用于稳定形状匹配，还可将椭球体用作碰撞基元。图中显示了使用椭球体（右图）比使用相同数量的球体（左图）更精确地近似相同的网格。
4.5.1. Volume Conservation 4.5.1.体积保持
The conservation of volume plays an important role in the dynamic simulation of deformable bodies [HJCW06, ISF07, DBB09]. Since most soft biological tissues are incompressible, this is an essential extension in the field of medical simulation. However, it is also used in the field of shape modeling [vFTS06] since volume conserving deformations appear more realistic. 体积守恒在可变形体的动态模拟中发挥着重要作用 [HJCW06, ISF07, DBB09]。由于大多数生物软组织都是不可压缩的，因此这是医学模拟领域的一个重要扩展。然而，它也用于形状建模领域[vFTS06]，因为体积守恒变形看起来更逼真。
In the following we introduce the position-based approach for volume conservation of Diziol et al. [DBB11]. This method considers only the surface of a simulated object and 下面我们将介绍 Diziol 等人[DBB11]提出的基于位置的体积守恒方法。这种方法仅考虑模拟物体的表面，而
does not require interior particles which reduces the computational effort. The volume of a volumetric 3D shape can be determined by using the divergence theorem as proposed in [Mir96] and [HJCW06]: 不需要内部粒子，从而减少了计算量。体积三维形状 的体积 可以通过 [Mir96] 和 [HJCW06] 中提出的发散定理来确定：
where is the boundary of the shape and is the surface normal. If the boundary is given as triangle mesh, the integral can be written as sum over all triangles : 其中 是形状的边界， 是表面法线。如果边界是三角形网格，积分可以写成所有三角形的总和 ：
where is the area and and are the vertex indices of the -th triangle. Now we can define a volume constraint and compute a corresponding position correction (see Section 3): 其中 是面积， 和 是 -th 三角形的顶点索引。现在我们可以定义一个体积约束 并计算相应的位置修正（见第 3 节）：
The weights are used to realize a local volume conservation (see below). The gradient can be approximated by 权重 用于实现局部体积守恒（见下文）。梯度近似值为
where is the sum of the area weighted normals of all triangles which contain particle . 其中 是包含粒子的所有三角形的面积加权法线之和 。
The weights in Equation (12) are chosen as follows: 公式 (12) 中的权重选择如下：
where and are the weights for local and global volume conservation, respectively, and the user-defined value is used to blend between both. The vector contains the position change of the -th particle in the shape matching step. Hence, strongly deformed particles participate more in volume correction. The weight of a colliding particle is set to zero in order to ensure that a collision constraint is not violated during the position correction for the volume conservation. Finally, the weights are smoothed by a Laplacian filter. 其中 和 分别是局部体积守恒和全局体积守恒的权重，用户自定义值 用于两者之间的混合。向量 包含 -th 粒子在形状匹配步骤中的位置变化。因此，强变形粒子参与体积修正的程度更高。碰撞粒子的权重设置为零，以确保在位置修正过程中不违反碰撞约束，从而实现体积守恒。最后，使用拉普拉斯滤波器对权重进行平滑处理。
Diziol et al. also propose another definition for the local weights . To propagate volume changes through the object, they first determine pairs of opposing particles in a preprocessing step by intersecting the geometry with multiple rays. For each particle one particle on the opposite side of the volumetric body is stored. Then they choose a local weight which does not only depend on the position change of a particle but also on the distance changes of the corresponding particle pairs: Diziol 等人还为局部权重提出了另一种定义 。为了在物体中传播体积变化，他们首先在预处理步骤中通过多条射线与几何体相交来确定成对的粒子。对于每个粒子 ，都会存储体积体另一侧的一个粒子 。然后，他们选择一个局部权重，该权重不仅取决于粒子的位置变化 ，还取决于相应粒子对的距离变化 ：
where is a user-defined stiffness parameter and is used to define the influence of the distance changes. 其中 是用户定义的刚度参数， 用于定义距离变化的影响。
Figure 20: Four spheres with different volume conservation squeezed by a plate. Left to right: global conservation, local conservation with distance constraints, local conservation without distance constraints and no volume conservation. The maximum volume loss was and respectively. 图 20：四个具有不同体积守恒性的球体被平板挤压。从左到右依次为：整体守恒、有距离限制的局部守恒、无距离限制的局部守恒和无体积守恒。最大体积损失分别为 和 。
Analogous to the positions correction we perform a velocity correction to fulfill the constraint . This leads to a divergence free velocity field. 与位置修正类似，我们进行速度修正，以满足 的约束条件。这将产生一个无发散的速度场。
In Figure 20 different configurations for the presented volume conservation method are compared with each other. 图 20 比较了所介绍的体积守恒方法的不同配置。
4.5.2. Plastic Deformation 4.5.2.塑性变形
Shape matching can be extended in order to simulate plastic deformations [MHTG05]. If we perform a polar decomposition for the linear transformation matrix (see Equation (5)), we get a rotational part and a symmetric part . The matrix represents a deformation in the unrotated reference frame. Hence, for each region we can store the plastic deformation state in a matrix which is initialized with the identity matrix I. As proposed by Goktekin et al. [GBO04], we use two parameters and to control the plastic behavior of the material. If the condition is fulfilled for the deformation matrix of the current time step, the plastic deformation state is updated as follows: 形状匹配可以扩展到模拟塑性变形 [MHTG05]。如果我们对线性变换矩阵 进行极性分解 （见公式 (5)），就会得到旋转部分 和对称部分 。矩阵 表示未旋转参照系中的变形。因此，对于每个区域，我们可以将塑性变形状态存储在一个矩阵 中，该矩阵的初始化值为同位矩阵 I。根据 Goktekin 等人的建议[GBO04]，我们使用两个参数 和 来控制材料的塑性行为。如果当前时间步的变形矩阵 满足条件 ，塑性变形状态将按如下方式更新：
After this update, is divided by in order to conserve the volume. The plastic state is integrated in the shape matching process by deforming the reference shape in Equation (5). This is done by replacing the definition of 更新后， 除以 以保留体积。塑性状态 通过对方程 (5) 中的参考形状进行变形，将塑性状态整合到形状匹配过程中。具体做法是将
Figure 21: A stiff cloth model with 32467 triangles is simulated using multi-resolution shape matching with five hierarchy levels. 图 21：使用五级多分辨率形状匹配技术模拟了一个有 32467 个三角形的硬布模型。
(see Section 4.1) with (见第 4.1 节）与
Note that the plasticity can be bound by the condition where is the threshold for the maximum plastic deformation. If this condition is fulfilled, we use . 请注意，塑性可以通过条件 来约束，其中 是最大塑性变形的阈值。如果满足这一条件，我们就可以使用 。
4.6. Cloth Simulation 4.6.布料模拟
Stumpp et al. [SSBT08] present a region-based shape matching approach for the simulation of cloth. In their work they define a region for each triangle in the model. But instead of using the triangles directly as regions for shape matching, overlapping regions are defined. The region of a triangle is defined by the outer corners of its adjacent triangles. These overlapping regions enable the bending resistance of the cloth model. Since the model of Stumpp et al. uses regions with only three vertices, the stiffness of high resolution models is too low for realistic results. Therefore, they introduce so-called fiber clusters to increase the stretching stiffness. These one-dimensional regions are determined in a pre-processing step by subdividing the mesh into multiple edge strips. During the simulation each strip is traversed in both directions to obtain additional goal positions. The resulting displacements are translated so that they sum up to 0 to preserve the momentum of the model. The final goal positions are blended with the goal positions of the triangular regions. Stumpp 等人[SSBT08]提出了一种基于区域的布料仿真形状匹配方法。在他们的工作中，他们为模型中的每个三角形定义了一个区域。但他们并没有直接将三角形作为形状匹配的区域，而是定义了重叠区域。一个三角形的区域由其相邻三角形的外角定义。这些重叠区域可实现布料模型的抗弯强度。由于 Stumpp 等人的模型只使用了三个顶点的区域，高分辨率模型的刚度太低，无法获得真实的结果。因此，他们引入了所谓的纤维簇来增加拉伸刚度。这些一维区域是在预处理步骤中通过将网格细分为多个边缘条来确定的。在模拟过程中，每个条带都会向两个方向移动，以获得额外的目标位置。由此产生的位移将被平移，使其总和为 0，以保持模型的动量。最终的目标位置与三角形区域的目标位置相混合。
The usage of fiber clusters increases the stiffness of the cloth model. However, this effect is limited and for highresolution models the stiffness is still too low to achieve a realistic cloth behavior. Bender et al. [BWD13] solve this problem by the introduction of multi-resolution shape matching (see Figure 21) which is based on the idea of multi- 纤维簇的使用增加了布模型的刚度。然而，这种效果是有限的，对于高分辨率模型来说，刚度仍然太低，无法实现逼真的布面效果。Bender 等人[BWD13]通过引入多分辨率形状匹配（见图 21）解决了这一问题。
Figure 22: shape matching. The initial configuration of a triangle in (left) is matched to the deformed configuration (middle) by projecting the deformed triangle into and computing the optimal translation and rotation to get goal positions (right). 图 22： 形状匹配。通过将变形三角形投影到 ，并计算最佳平移和旋转以获得目标位置（右图），将 中三角形的初始配置（左图）与变形配置（中图）进行匹配。
grid solvers [Hac85]. A shape matching region is defined for each edge and each triangle in a cloth model. To increase the influence of these simple regions and therefore the stretching and shearing stiffness of the model, shape matching is performed on different resolution levels. Multi-resolution shape matching enables the robust simulation of stiff cloth models in linear time. 网格求解器 [Hac85]。布模型中的每条边缘和每个三角形都定义了一个形状匹配区域。为了增加这些简单区域的影响，从而提高模型的拉伸和剪切刚度，形状匹配在不同的分辨率水平上进行。多分辨率形状匹配可以在线性时间内对硬布模型进行稳健模拟。
In the following we first describe 2D shape matching for triangular regions and then introduce multi-resolution shape matching. 下面我们首先介绍三角形区域的二维形状匹配，然后介绍多分辨率形状匹配。
For a cloth simulation with triangular regions, shape matching is performed per triangle in the two-dimensional space of the triangle plane. First the optimal translation vectors of the regions are computed by evaluating Equation (6). Then, for each triangle with the vertices and and the normal a projection matrix is determined: 对于带有三角形区域的布料模拟，每个三角形都要在三角形平面的二维空间内进行形状匹配。首先，通过公式 (6) 计算出区域的最佳平移向量。然后，为每个三角形的顶点 和 以及法线 确定投影矩阵：
with 与
The matrix is used to project the vectors and in Equation (5) to get a 2D version of the matrix : 矩阵 用于投影方程 (5) 中的矢量 和 ，从而得到二维版本的矩阵 ：
where can be precomputed. The optimal rotation for shape matching is obtained by performing a polar decomposition [SD92] for the resulting matrix . This rotation matrix is used to compute goal positions for the particles and the corresponding 2D position changes : 其中 可以预先计算。通过对得到的矩阵 进行 极分解[SD92]，可获得形状匹配的最佳旋转。该旋转矩阵用于计算 粒子的目标位置 以及相应的二维位置变化 ：
Finally, the vectors are transformed to world space by and the particle positions are updated. This process is shown in Figure 22. 最后，通过 将矢量 转换到世界空间，并更新粒子位置。这一过程如图 22 所示。
In a simulation with multi-resolution shape matching [BWD13] two intergrid transfer operators are required to couple the different meshes in the multi-resolution hierarchy. The restriction operator transfers values from level to the next coarser level and the prolongation operator transfers values in the opposite direction. These operators can be defined by barycentric coordinates [GW06]. In each simulation step first the positions of the finest mesh are updated by time integration. For non-nested models the positions of the coarser meshes are interpolated using the restriction operator. Then multi-resolution shape matching is performed in a V-cycle as described by Algorithm 2. 在多分辨率形状匹配仿真[BWD13]中，需要两个网格间转移算子来连接多分辨率层次结构中的不同网格。限制算子 将数值从层次 转移到下一个更粗的层次 ，而延长算子 则以相反的方向转移数值。这些算子可以用巴里中心坐标[GW06]来定义。在每个模拟步骤中，首先通过时间积分更新最细网格的位置。对于非嵌套模型，使用限制算子对较粗网格的位置进行内插。然后按照算法 2 所描述的 V 循环进行多分辨率形状匹配。
In the restriction phase the hierarchy is traversed from the finest to the coarsest mesh performing a shape matching step on each level and projecting the resulting position differences to the next coarser level with the restriction operator. In the prolongation phase the hierarchy is traversed in the opposite direction. On each level a shape matching step is performed and the position differences are interpolated and added to the next finer level. Since only position differences are propagated between the levels, fine details are conserved on finer levels. However, fine details could get lost if the original shape matching method is used on the coarse levels of the hierarchy. Wrinkles on a fine resolution cause a compression of elements on a coarser level. Shape matching reduces this compression and thus eliminates fine details. Therefore, Bender et al. [BWD13] propose a modified computation of the goal positions on the coarse levels of the hierarchy so that shape matching only prevents stretching on these levels but not a compression. 在限制阶段，层次结构从最细的网格到最粗的网格进行遍历，在每个层次上执行形状匹配步骤，并使用限制算子将产生的位置差异 投影到下一个更粗的层次。在延长阶段，层次结构以相反的方向遍历。在每个层级上执行形状匹配步骤，并将位置差值插值并添加到下一个更细的层级。由于在层级之间只传播位置差异，因此在更细的层级上可以保留精细细节。但是，如果在层次结构的较粗层次上使用原始的形状匹配方法，则可能会丢失精细细节。精细分辨率上的褶皱会压缩较粗层次上的元素。形状匹配可以减少这种压缩，从而消除精细细节。因此，本德尔等人[BWD13]提出了一种修改后的分层粗级目标位置计算方法，这样形状匹配只能防止这些级别上的拉伸，而不能防止压缩。
4.7. Parallelization 4.7.并行化
In Section 4.3 we presented different fast summation techniques for shape matching. The one of Diziol et al. [DBB11] is best suited for a parallel implementation on the GPU. In the following the GPU implementation of this technique with CUDA is described in detail. For such an implementation memory access and memory layouts play an important role as well as the number of kernel calls. 在第 4.3 节中，我们介绍了不同的形状匹配快速求和技术。Diziol 等人的技术[DBB11]最适合在 GPU 上并行实施。下文将详细介绍使用 CUDA 在 GPU 上实现该技术。对于这种实现方式，内存访问和内存布局以及内核调用次数都起着重要作用。
Since each kernel call introduces a computational overhead, the particles of all objects in a simulation are packed into one single array. This array is ordered according to the path layout which is used for the fast summation (see Section 4.3). Since the array contains the paths one after another, a segmented prefix sum [SHZO07] can be used to determine the prefix sums of all paths at once. To avoid numerical problems due to the 32 bit floating-point arithmetics on the GPU, the path length is limited to 512. The resulting prefix sums are stored in texture memory to benefit from the texture cache when the translational vectors and the affine matrices are determined (see Equation (8)). 由于每次内核调用都会带来计算开销，因此模拟中所有对象的粒子都被打包到一个数组中。该数组根据用于快速求和的路径布局排序（见第 4.3 节）。由于数组中的路径一个接一个，因此可以使用分段前缀和[SHZO07]来一次性确定所有路径的前缀和。为了避免 GPU 上的 32 位浮点运算造成的数值问题，路径长度限制为 512。得到的前缀和存储在纹理内存中，以便在确定平移向量和仿射矩阵时从纹理缓存中获益（见公式 (8)）。
The volume conservation introduced in Section 4.5.1 can also be performed efficiently on the GPU. This is done by evaluating the volume integral (see Equation (10)), the integral which is required to obtain a divergence free velocity field and the weights for the local volume conservation in parallel. Both integrals can be written as sums over the vertices (see Equation (11)). Hence, the integrals as well as the weights can be computed by a segmented sum reduction. Finally, the smoothing of the weights by a Laplacian filter can be performed in parallel using the fast summation technique as described above. 第 4.5.1 节中介绍的体积守恒也可以在 GPU 上高效执行。具体方法是并行计算体积积分（见公式 (10)）、获得无发散速度场所需的积分以及局部体积守恒的权值。这两个积分都可以写成顶点上的和（见公式 (11)）。因此，可以通过分段求和来计算积分和权重。最后，通过拉普拉斯滤波器对权重进行平滑处理，可以使用上述快速求和技术并行执行。
The multi-resolution approach described in Section 4.6 can be implemented on the GPU as follows. Shape matching on each level of the hierarchy is performed by computing the goal positions per element in parallel in a first step. The results are stored for each element. In a second step shape matching is completed by summing up the contributions of all elements containing a vertex to get a final goal position for the vertex. The restriction and the prolongation of the results can be performed efficiently using the sparse matrix data structure of Weber et al. [WBS*13]. This implementation allows to simulate the deformation of a cloth model with more than 200k triangles on the finest level in on a GeForce GTX 470. 第 4.6 节所述的多分辨率方法可以在 GPU 上实现，具体如下。第一步，通过并行计算每个元素的目标位置，在层次结构的每个层级上进行形状匹配。每个元素的结果都会被存储起来。第二步，将包含顶点的所有元素的贡献值相加，得到顶点的最终目标位置，从而完成形状匹配。利用韦伯等人的稀疏矩阵数据结构[WBS*13]，可以有效地对结果进行限制和延长。这种实现方式允许在 GeForce GTX 470 上以 的最细级别模拟超过 20 万个三角形的布料模型的变形。
4.8. Discussion 4.8.讨论情况
Shape matching is efficient, unconditionally stable and easy to implement. However, the shape matching algorithm can only handle small deformations. Therefore, the concept of region-based shape matching was introduced as well as corresponding fast summation techniques. Although this method is a meshless approach, many implementations use a mesh to define the required overlapping regions. Shape matching can even handle sparse structures by the usage of oriented particles. 形状匹配高效、无条件稳定且易于实现。然而，形状匹配算法只能处理较小的变形。因此，我们引入了基于区域的形状匹配概念以及相应的快速求和技术。虽然这种方法是一种无网格方法，但许多实施方法都使用网格来定义所需的重叠区域。通过使用定向粒子，形状匹配甚至可以处理稀疏结构。
We also want to discuss the drawbacks of shape matching. Being a geometric approach, only visually plausible results can be obtained. The stiffness of the model does not only depend on the user-defined stiffness parameter but also on the time step size and the region sizes or, in case of multiresolution shape matching, the number of hierarchy levels. 我们还想讨论一下形状匹配的缺点。作为一种几何方法，只能获得视觉上可信的结果。模型的刚度不仅取决于用户定义的刚度参数 ，还取决于时间步长和区域大小，或者在多分辨率形状匹配的情况下，取决于层次结构的数量。
Moreover, the physical behavior depends on the mesh geometry and does not converge to a certain solution as the mesh is refined. Hence, adaptive time stepping and the application of level-of-detail methods are open problems for further research. 此外，物理行为取决于网格的几何形状，并不会随着网格的细化而收敛到某个特定的解决方案。因此，自适应时间步进和细节级方法的应用是有待进一步研究的开放性问题。
5. Data-Driven Upsampling Methods 5.数据驱动的上采样方法
The behavior of solid objects can be accurately described using well-known mechanical models, but real-world materials display other inherent sources of complexity that largely limit the results of traditional models in computer animation. Complexity is produced, for example, by nonlinear or anisotropic behaviors, by heterogeneous properties, or by a wide frequency spectrum. These sources of complexity are typically addressed by designing complex nonlinear constitutive models to describe the mechanical behavior of diverse materials. However, these models require computationally expensive simulation algorithms, and their parameters are difficult and tedious to tune, particularly if the properties are heterogeneous. All in all, the animation of solid objects is limited by the domain of effects captured by the underlying physical models, but also by their parameterization accuracy. 固态物体的行为可以使用众所周知的机械模型进行精确描述，但现实世界中的材料显示出其他固有的复杂性来源，这在很大程度上限制了传统模型在计算机动画中的应用效果。例如，非线性或各向异性行为、异质特性或宽频谱都会产生复杂性。要解决这些复杂性问题，通常需要设计复杂的非线性结构模型来描述各种材料的机械行为。然而，这些模型需要计算成本高昂的模拟算法，其参数的调整也十分困难和繁琐，尤其是当材料特性是异质的时候。总而言之，实体物体的动画制作不仅受限于底层物理模型所捕捉的效应范围，还受限于其参数化的准确性。
Data-driven methods offer an alternative to complex constitutive models, as they turn the modeling metaphor into the knowledge of a system's response under several example conditions. This section describes geometric datadriven methods in computer animation. It formulates a twoscale representation of geometry and dynamics, describes the computation of detailed geometry as the interpolation of example data, and discusses several successful examples. 数据驱动方法将建模隐喻转化为系统在若干示例条件下的响应知识，为复杂的构成模型提供了一种替代方法。本节介绍计算机动画中的几何数据驱动方法。它提出了几何和动力学的双尺度表示法，描述了作为实例数据插值的详细几何计算，并讨论了几个成功的实例。
5.1. Two-Scale Geometry and Dynamics 5.1.双尺度几何与动力学
Let us consider the surface of a solid object (e.g., the cloth in Figure 23), with vertex positions . These positions can be decomposed into a low-resolution position and a fine-scale displacement , expressed in a local reference system for each vertex (i.e., with orientation ): 让我们考虑一个实体物体的表面（如图 23 中的布），其顶点位置 。这些位置可以分解为低分辨率的位置 和精细尺度的位移 ，以每个顶点的局部参考系表示（即带有方向 ）：
This definition of vertex positions essentially decomposes large-scale geometry (i.e., the overall shape of a solid object) from the small-scale deformation (i.e., wrinkles). 这种顶点位置定义实质上是将大尺度几何图形（即实体物体的整体形状）与小尺度变形（即皱纹）分解开来。
The large-scale and fine-scale geometry can be represented at different resolutions, connected through subdivision schemes. As shown in Figure 23 for a cloth object, a low-resolution feature mesh defines the large-scale deformation. A high-resolution smooth mesh is obtained by subdividing the feature mesh a user-defined number of times, and can be regarded as an upsampled version of the feature mesh. Finally, a high-resolution detail mesh is obtained by adding local displacements onto the smooth mesh. The smooth and detail meshes fully share the connectivity, thus trivially defining their correspondence. 大尺度和细尺度几何体可以通过细分方案以不同的分辨率表示。如图 23 中的布料对象所示，低分辨率的特征网格定义了大尺度变形。高分辨率平滑网格是将特征网格细分为用户定义的次数后得到的，可视为特征网格的上采样版本。最后，通过在平滑网格上添加局部位移，得到高分辨率的细节网格。平滑网格和细节网格完全共享连通性，因此可以定义它们之间的对应关系。
Once large-scale and fine-scale geometry are separated, they can be computed using different models. The choice of models can be made based on the following observations. First, for many objects such as the face or cloth, the most salient dynamic effects can be captured at a large scale. For example, Bickel et al. [BLB*08] and Ma et al. [MJC compute the large-scale face geometry from an actor's performance, using a single face scan and sparse mocap markers as input, and a linear deformation model. Wang et al. [WHRO10], Zurdo et al. [ZBO13], and Kavan et al. [KGBS11] compute the large-scale geometry of cloth using a low-resolution dynamics model with contact handling. 一旦大尺度和小尺度几何图形被分开，就可以使用不同的模型来计算它们。可以根据以下几点来选择模型。首先，对于许多物体，如脸或布，最显著的动态效果可以在大尺度上捕捉到。例如，Bickel 等人[BLB*08] 和 Ma 等人[MJC ]使用单次面部扫描和稀疏的 mocap 标记作为输入，并使用线性形变模型，从演员的表演中计算出大尺度的面部几何形状。Wang 等人[WHRO10]、Zurdo 等人[ZBO13]和 Kavan 等人[KGBS11]使用带接触处理的低分辨率动力学模型计算布匹的大尺度几何形状。
A second important observation is that plausible highresolution wrinkles can often be defined as a quasi-static function in a reduced low-resolution domain . All authors mentioned in the previous paragraph follow this observation to some extent. For the face, and due to the repetitive nature of facial expressions, tissue becomes weaker at certain locations, and expressive wrinkles appear in a deterministic fashion as a function of large-scale deformation, and indirectly as a function of muscle activations and facial bone configurations. For cloth, even though real wrinkles require a large number of degrees of freedom to capture their true diversity, plausible wrinkles can be defined in the reduced domain of large-scale deformation. We can formally write the dependency between high-resolution detail and the lowresolution configuration as , where the function is a position-based model. 第二个重要观察结果是，可信的高分辨率皱纹通常可以定义为缩小的低分辨率域中的准静态函数 。上一段提到的所有作者都在一定程度上遵循了这一观点。对于面部，由于面部表情的重复性，组织在某些位置会变得薄弱，表现性皱纹会以确定的方式出现，成为大尺度变形的函数，并间接成为肌肉激活和面部骨骼配置的函数。就布料而言，尽管真实的皱纹需要大量的自由度才能捕捉到其真实的多样性，但可信的皱纹可以在大尺度变形的缩小域中定义。我们可以将高分辨率细节 和低分辨率配置 之间的依赖关系正式写为 ，其中函数 是一个基于位置的模型。
The reduced-domain definition presents some limitations, which should be mentioned upfront. Fine-scale wrinkle dynamics cannot be captured, as wrinkles are defined quasistatically. And the model captures only a limited set out of all the possible wrinkles that a solid object might present. However, the power of data-driven methods is that the generic function makes use of data from real deformation examples; therefore, data-driven wrinkles preserve natural characteristics such as length, width, and consistency over time, and they appear plausible despite their limitations. 缩减域定义存在一些局限性，这一点应预先提及。由于皱纹是准静态定义的，因此无法捕捉到细尺度的皱纹动态。而且该模型只能捕捉到固体物体可能出现的所有皱纹中有限的一组。然而，数据驱动方法的强大之处在于，通用函数 使用了真实变形实例的数据；因此，数据驱动的皱纹保留了长度、宽度和随时间变化的一致性等自然特征，尽管有其局限性，但看起来还是可信的。
5.2. Data-Driven Geometric Detail 5.2.数据驱动的几何详图
At this point, we have a suitable setting to define a positionbased data-driven model. For data collection, we need to record example deformations (denoted by the subscript ), with vertex displacements and low-resolution configurations in correspondence. Then, we apply learning methods to design a data-driven approximation of the function , which can be formally defined as . 至此，我们有了一个合适的环境来定义基于位置的数据驱动模型。为了收集数据，我们需要记录示例变形（用下标表示 ），并将顶点位移 和低分辨率配置 对应起来。然后，我们应用学习方法设计一个数据驱动的近似函数 ，其形式定义为 。
A general and successful approach to define a data-driven approximation is through a linear combination of examplebased basis functions, 定义数据驱动的近似 的一种普遍而成功的方法是通过基于实例的基函数的线性组合、
Feature mesh (400 tris) 特征网格（400 三面体）
(25600 tris)
examples 例子
Figure 23: Data-driven animation of cloth wrinkles. On the left, a low-resolution feature mesh, a smooth mesh obtained by subdivision, and a high-resolution detail mesh. On the right, a schematic depiction of the data-driven wrinkle computation. The feature mesh is subdivided to obtain the smooth mesh, and then detailed wrinkles are added in a local reference frame by combining detail from examples. 图 23：数据驱动的布皱动画。左边是低分辨率的特征网格、通过细分得到的平滑网格和高分辨率的细节网格。右图是数据驱动的皱褶计算示意图。首先对特征网格进行细分，得到平滑网格，然后结合实例中的细节，在局部参考框架中添加细节皱纹。
Figure 24: Example of facial animation with the data-driven method of Bickel et al. [BLB* 08]. From left to right: large-scale deformation interpolating mocap markers, full result data-driven detail computation, the same result with full shading, and comparison to the real actor's face. 图 24：使用 Bickel 等人[BLB* 08]的数据驱动方法制作面部动画的示例。从左到右依次为：大尺度变形插值 mocap 标记、数据驱动细节计算的完整结果、全着色的相同结果以及与真实演员面部的对比。
with weights computed as a function of the lowresolution configuration . In the expression above, constitutes an example-based detail displacement, and represents the values associated with one vertex in the basis function. 权重 作为低分辨率配置 的函数计算。在上述表达式中， 构成基于示例的细节位移，代表 基函数中与一个顶点相关的值。
In the rest of this section, we discuss several examples of position-based data-driven deformation models, which differ in terms of the choice of low-resolution configuration, basis functions, or interpolation method. 在本节的其余部分，我们将讨论基于位置的数据驱动形变模型的几个示例，它们在低分辨率配置、基函数或插值方法的选择上有所不同。
Bickel et al. [BLB* 08 proposed a data-driven method to compute facial wrinkles as a function of large-scale deformation and a small set of example deformations, and later Zurdo et al. [ZBO13] followed a similar strategy for cloth animation. Figure 24 shows an example facial animation by Bickel et al., and Figure 25 an example cloth animation by Zurdo et al. Bickel 等人[BLB* 08 ]提出了一种数据驱动的方法，将面部皱纹作为大尺度变形和一小部分示例变形的函数来计算，后来 Zurdo 等人[ZBO13]对布料动画也采用了类似的策略。图 24 是 Bickel 等人的面部动画示例，图 25 是 Zurdo 等人的布料动画示例。
In their methods, the basis function combination in Equation (13) follows the weighted pose-space deformation (WPSD) approach [KM04]. In a nutshell, the basis functions 在他们的方法中，等式 (13) 中的基函数组合遵循加权姿态空间变形 (WPSD) 方法 [KM04]。简而言之，基函数
constitute local vertex displacements in example deformations, called poses, and the weights are convex weights for each of the poses. The weights of the poses are computed using scattered-data interpolation based on radial basis functions (RBFs) in pose space. In this case, the pose space is given by the large-scale deformation . 构成实例变形中的局部顶点位移，称为姿态，权重 是每个姿态的凸权重。姿势的权重是根据姿势空间中的径向基函数（RBF）使用散点数据插值计算得出的。在这种情况下，姿势空间由大尺度变形 给出。
As shown by Zurdo et al., pose weights can be computed through WPSD on the sparse vertices of the feature mesh, and then simply interpolated to the vertices of the detail mesh using subdivision weights. For the computation of pose weights on a given vertex, WPSD requires a local definition of the pose space . Both Bickel et al. and Zurdo et al. use a metric of local low-resolution strain, formed by concatenating the deformation of the 16 closest edges of the feature mesh, multiplied by fast-decaying weights. With RBF interpolation, the weight of each pose is computed as 如 Zurdo 等人所示，可以通过 WPSD 计算特征网格稀疏顶点的姿态权重，然后使用细分权重简单地插值到细节网格的顶点。为了计算给定顶点上的姿态权重，WPSD 需要对姿态空间进行局部定义 。Bickel 等人和 Zurdo 等人都使用了局部低分辨率应变度量，该度量由特征网格 16 个最近边缘的变形乘以快速衰减权值构成。通过 RBF 插值，每个姿态的权重计算公式为
The RBF weights are precomputed such that pose weights fulfill the Kronecker delta for the database of poses, i.e., is 0 if and 1 if , for poses and in the database. The function represents a specific type of RBF. Both Bickel et al. and Zurdo et al. use RBFs with global support , as they avoid complex tuning of support radii for unevenly sampled data . RBF 权重 是预先计算出来的，因此姿势权重符合姿势数据库的 Kronecker delta 值，即对于数据库中的姿势 和 ，如果 ，则 为 0；如果 ，则 为 1。函数 代表一种特定类型的 RBF。Bickel 等人和 Zurdo 等人都使用了具有全局支持的 RBF ，因为它们避免了对不均匀采样数据进行复杂的支持半径调整 。
The selection of poses starts with the generation of training data, which requires a database of synchronized feature and detail meshes. Zurdo et al. employ the TRACKS method [BMWG07] to precompute cloth simulations where the detail mesh tracks the motion of the feature mesh. In the training simulations, contact is solved both on the feature mesh and the detail mesh, and then the high-resolution information in the poses captures the response to contact. From all mesh pairs in the database, Zurdo et al. select only a small number of poses (typically 6), until the error between synthesized animations and the training dataset is below a certain threshold. The set of poses is grown in a greedy manner, adding each time the mesh pair with largest error between the training and synthesized configurations. 姿势的选择从生成训练数据开始，这需要一个同步特征网格和细节网格的数据库。Zurdo 等人采用 TRACKS 方法[BMWG07]预先计算布模拟，其中细节网格跟踪特征网格的运动。在训练模拟中，在特征网格和细节网格上同时解决接触问题，然后利用姿势中的高分辨率信息捕捉接触的响应。Zurdo 等人只从数据库中的所有网格对中选择少量姿势（通常为 6 个），直到合成动画与训练数据集之间的 误差低于某个阈值。姿势集以贪婪的方式增加，每次增加的网格对都是训练和合成配置之间误差最大的 。
5.2.2. Polynomial Displacement Maps 5.2.2.多项式位移图
Ma et al. [MJC08] designed Polynomial Displacement Maps (PDM), a method for data-driven computation of wrinkles in facial animation, following the computational strategy of Polynomial Texture Maps [MGW01]. Despite the computational differences, the method shares many similarities with the WPSD approach of Bickel et al. [BLB 08]. Ma 等人[MJC08]按照多项式纹理贴图[MGW01]的计算策略设计了多项式位移贴图（PDM），这是一种用于面部动画中皱纹的数据驱动计算方法。尽管计算方法不同，但该方法与 Bickel 等人的 WPSD 方法[BLB 08]有许多相似之处。
In the general data-driven framework described by Equation (13), the low-resolution configuration of PDM is defined as a two-dimensional local strain metric of the feature mesh, . In particular, this metric is obtained through principal component analysis of a five-dimensional vector formed by the local vertex offset and the in-plane strain of the feature mesh. Based on this low-resolution configuration, the weights in Equation (13) are defined based on biquadratic polynomials, . Finally, the detail position of each vertex in the detail mesh, , is defined as a scalar displacement in the local normal direction. 在公式（13）描述的一般数据驱动框架中，PDM 的低分辨率配置被定义为特征网格的二维局部应变度量 。具体而言，该指标是通过对由局部顶点偏移和特征网格面内应变形成的五维向量进行主成分分析而获得的。基于这种低分辨率配置，等式 (13) 中的权重是根据二次多项式定义的， 。最后，细节网格中每个顶点的细节位置 被定义为局部法线方向上的标量位移。
Due to the choice of biquadratic PDMs, the per-vertex displacements are computed through linear combination of six basis functions, which are stored in texture maps. Ma et al. compute the coefficients in these texture maps as the result of a least-squares problem that minimizes the fitting error over the training data. 由于选择了二次方 PDM，每个顶点的位移是通过六个基函数的线性组合计算出来的，这些基函数存储在纹理图中。Ma 等人将这些纹理图中的系数作为最小二乘问题的结果来计算，从而使训练数据的拟合误差最小化。
5.2.3. Physics-Inspired Upsampling 5.2.3.物理启发式升采样
Kavan et al. [KGBS11] proposed a data-driven method to compute cloth animations with detailed wrinkles at videogame frame rates. In their approach, high-resolution cloth positions are computed following a position-based data-driven method, but the data is learned from dynamic simulations with tracking of high-resolution and lowresolution geometry, similar to the approach by Zurdo et al. [ZBO13] described earlier. Kavan 等人[KGBS11]提出了一种数据驱动方法，用于以电子游戏帧速率计算带有细节褶皱的布料动画。在他们的方法中，高分辨率的布料位置是按照基于位置的数据驱动方法计算的，但数据是从跟踪高分辨率和低分辨率几何体的动态模拟中学习的，这与前面介绍的 Zurdo 等人的方法[ZBO13]类似。
In physics-inspired upsampling (PIU), the weights in Equation (13) correspond directly to the vertex positions of the feature mesh. The basis functions coefficients extend subdivision schemes, and are learned from a database of example deformations. 在物理启发上采样（PIU）中，等式（13）中的权重 直接对应于特征网格的顶点位置。基函数系数 扩展了细分方案，并从变形示例数据库中学习。
For the description of the method in more detail, let us define the low-resolution deformation as a vector that concatenates the vertex positions of the low-resolution feature mesh. We also define a matrix of upsampling basis functions, being each row of the basis function for one vertex coordinate. Finally, we define a vector that concatenates all vertex positions of the high-resolution detail mesh. Note that the method of Kavan et al. computes high-resolution positions directly, not local displacements as discussed earlier. With these definitions, the data-driven detail from Equation (13) can be rewritten as . 为了更详细地描述该方法，让我们将低分辨率变形 定义为一个向量，它串联了低分辨率特征网格的顶点位置。我们还定义了一个上采样基函数矩阵 ，其中 的每一行都是一个顶点坐标的基函数。最后，我们定义了一个矢量 ，用于连接高分辨率细节网格的所有顶点位置。请注意，Kavan 等人的方法是直接计算高分辨率位置，而不是前面讨论的局部位移。有了这些定义，公式 (13) 中的数据驱动细节可以重写为 。
Given the data captured in training simulations, expressed as example deformations of the feature mesh, , and the detail mesh, , Kavan et al. compute basis functions through an optimization problem 给定训练模拟中获取的数据（以特征网格 和细节网格 的实例变形表示），Kavan 等人通过优化问题计算基函数
The optimization must satisfy additional constraints. In particular, the basis functions B must constitute a partiton of unity, and the objective function includes a regularization term to prevent overfitting. 优化必须满足额外的约束条件。特别是，基函数 B 必须构成一个统一的部分，目标函数包括一个正则化项，以防止过度拟合。
As mentioned earlier, one of the limitations of pure position-based data-driven methods is that wrinkles are quasi-static functions of low-resolution deformations. In PIU, Kavan et al. add oscillatory modes to allow the simulation of traveling waves. 如前所述，纯位置数据驱动方法的局限之一是皱纹是低分辨率变形的准静态函数。在 PIU 中，Kavan 等人增加了振荡模式以模拟行波。
Figure 25: Top row: a low-resolution model of a dress, with only 381 triangles, defines the dynamics, the large-scale deformation, and response to contact. The dress is then subdivided to 24384 triangles for rendering. Bottom row: high-resolution wrinkles are interpolated from 6 example poses based on the large-scale deformation of the dress, using the data-driven method of Zurdo et al. [ZBO13]. 图 25：顶行：仅有 381 个三角形的低分辨率礼服模型，定义了动态、大尺度变形和接触响应。然后将裙子细分为 24384 个三角形进行渲染。最下面一行：使用 Zurdo 等人的数据驱动方法[ZBO13]，根据裙子的大尺度变形从 6 个示例姿势中插值出高分辨率皱纹。
5.3. Parallelization 5.3.并行化
One of the most attractive features of position-based datadriven methods is that they can be massively parallelized on GPUs. Taking as reference Equation (13), the multiplication of basis weights times the basis values follows the same procedure at all vertices of the detail mesh, but it can be executed in a completely independent manner on each vertex. Therefore, this multiplication is very well suited for parallel implementation on GPUs. In fact, it can be handled as a dense matrix-vector product. 基于位置的数据驱动方法最吸引人的特点之一是可以在 GPU 上大规模并行处理。以方程 (13) 为参照，在详细网格的所有顶点上，基权重乘以基值的乘法过程是相同的，但在每个顶点上可以完全独立地执行。因此，这种乘法非常适合在 GPU 上并行执行。事实上，它可以作为密集矩阵向量乘积来处理。
Moreover, the evaluation of weights can also be done independently for each basis. In the PIU method described above, the weights are trivially defined as the positions of vertices in the feature mesh, hence they do not need further evaluation. In the WPSD and PDM methods, on the other hand, these weights are computed as a function of lowresolution deformation. As shown by Zurdo et al. [ZBO13], the nonlinear weights at feature vertices can be evaluated easily on the CPU, and then interpolated to detail vertices using subdivision weights. This interpolation step is trivial to parallelize on SIMD architectures. 此外，权重的评估 也可以在每个基础上独立完成。在上文所述的 PIU 方法中，权重被明确定义为特征网格中顶点的位置，因此无需进一步评估。而在 WPSD 和 PDM 方法中，这些权重是作为低分辨率变形的函数来计算的。正如 Zurdo 等人的研究[ZBO13]所示，特征顶点的非线性权重可以在 CPU 上轻松评估，然后使用细分权重插值到细节顶点。这一插值步骤在 SIMD 架构上的并行化非常简单。
Thanks to the highly parallel nature of data-driven algorithms, existing implementations exhibit very high performance. For example, Zurdo et al. [ZBO13] simulate cloth with triangles at including contact handling on the feature mesh, Kavan et al. [KGBS11] simulate a cape with vertices at , and Bickel et al. [BLB* 08 animate a face with more than triangles at . 得益于数据驱动算法的高度并行性，现有的实现方法表现出非常高的性能。例如，Zurdo 等人[ZBO13]在 上模拟了带有 三角形的布料，包括特征网格上的接触处理；Kavan 等人[KGBS11]在 上模拟了带有 顶点的披风；Bickel 等人[BLB* 08 ]在 上模拟了带有超过 三角形的面的动画。
5.4. Discussion 5.4.讨论情况
The particular data-driven methods discussed here present different pros and cons. Among all methods, PIU is probably the fastest method, as it relies on simple matrix-vector multiplication. However, the result is limited to a linear operator, and wrinkles may appear smoothed. WPSD and PDM, on the other hand, allow nonlinear operators, and the combination of the input data is decided in a local manner. 本文讨论的特定数据驱动方法各有利弊。在所有方法中，PIU 可能是最快的方法，因为它依赖于简单的矩阵-向量乘法。不过，其结果仅限于线性算子，皱纹可能会被平滑。另一方面，WPSD 和 PDM 允许使用非线性算子，而且输入数据的组合是局部决定的。
With WPSD and PDM, the representation is more compact, thanks to the choice of low-resolution strain as interpolation domain. Low-resolution strain also has been used as a parameter space for cloth wrinkles in procedural models [RPC* 10], or in the Wrinkle Meshes method [MC10]. In the position-based Wrinkles Meshes method, described in Section 3.6, the low-resolution strain affects wrinkle modeling indirectly, as it influences the deformation of the highresolution cloth. Seiler et al. [SSH12] propose a different interpolation domain based on local contact data, as their work targets the animation of high-resolution effects due to contact interactions. 在 WPSD 和 PDM 中，由于选择了低分辨率应变作为插值域，因此表示更为紧凑。在程序模型[RPC* 10]或皱纹网格法[MC10]中，低分辨率应变也被用作布皱纹的参数空间。在第 3.6 节描述的基于位置的皱褶网格方法中，低分辨率应变间接影响了皱褶建模，因为它影响了高分辨率布的变形。Seiler 等人[SSH12]提出了一种基于局部接触数据的不同插值域，因为他们的工作目标是制作由接触相互作用引起的高分辨率效果动画。
One limitation of most data-driven methods is that wrinkles are defined as a quasi-static function of the feature mesh, hence they exhibit no dynamics. Kavan et al. [KGBS11] somewhat alleviate this problem by adding oscillatory modes, but the solution does not support all dynamic effects. The work of de Aguiar et al. [dASTH10] offers an interesting approach to data-driven simulation of dynamic effects, but it models low-resolution motion, not high-resolution details. 大多数数据驱动方法的一个局限是，皱纹被定义为特征网格的准静态函数，因此不表现出动态性。Kavan 等人的研究[KGBS11]通过添加振荡模式在一定程度上缓解了这一问题，但该解决方案并不支持所有动态效果。de Aguiar 等人的研究[dASTH10]为数据驱动的动态效果模拟提供了一种有趣的方法，但它模拟的是低分辨率运动，而不是高分辨率细节。
The data-driven cloth upsampling method of Feng et al. [FYK10] departs from those presented here. It not only defines fine-scale details in a data-driven manner, but also a Feng 等人[FYK10]的数据驱动的布上采样方法与本文介绍的方法有所不同。它不仅以数据驱动的方式定义了细微尺度的细节，而且还采用了一个
mid-scale transformation from a coarse cloth simulation. Its two deformation transformers, for fine-scale and mid-scale deformations, are learned using regression with rotationinvariant data. The method of Feng et al. produces highquality results if the training sequence captures the dynamics that will appear at runtime, but it will suffer larger errors otherwise. 中尺度变形。它的两个变形变换器（细尺度变形和中尺度变形）是通过旋转不变数据回归学习得到的。如果训练序列能捕捉到运行时会出现的动态，Feng 等人的方法就能产生高质量的结果，反之则会产生较大的误差。
This section has covered position-based data-driven methods for animating high-resolution effects on solids, but recent advances open the possibility to extend this paradigm also to fluids. The recent work of Kim et al. [KTT13] introduces a decomposition of liquid surface geometry into a low resolution surface plus high-resolution ripples, just like the one defined for solid surfaces in Section 5.1 above. However, for liquids, a quasi-static definition of high-resolution details is a particularly severe limitation. Kim et al. propose a model that decouples low-resolution and high-resolution dynamics, and they use the Wave model [Tes04] to synthesize high-resolution liquid ripples. We envision that such ripples could also be synthesized from precomputed data using a data-driven model. 本节介绍了基于位置的数据驱动方法，用于对固体产生高分辨率的动画效果，但最近的研究进展为将这一范例扩展到液体提供了可能。Kim 等人最近的研究[KTT13]将液体表面几何分解为低分辨率表面和高分辨率波纹，就像上文第 5.1 节为固体表面定义的一样。然而，对于液体来说，高分辨率细节的准静态定义是一个特别严重的限制。Kim 等人提出了一个解耦低分辨率和高分辨率动力学的模型，他们使用 Wave 模型[Tes04]合成了高分辨率的液体波纹。根据我们的设想，这种涟漪也可以使用数据驱动模型从预先计算的数据中合成。
6. Applications 6.应用
In this section we introduce different application areas of position-based methods. These methods are mainly used in interactive applications where performance, controllability and stability are more important than accuracy, like e.g. in [SGdA* 10,DB13]. But there exist also other works which use a position-based approach for stabilization. 在本节中，我们将介绍基于位置的方法的不同应用领域。这些方法主要用于交互式应用，在这些应用中，性能、可控性和稳定性比精度更为重要，如 [SGdA* 10,DB13] 等。但也有其他作品使用基于位置的方法来实现稳定。
One application area for position-based methods is interactive surgical simulation. In this area Wang et al. [WXX* 06] introduce a mass-spring model based on a surface mesh to simulate deformable bodies in real-time. Since such a model can neither preserve its volume nor resume its rest shape in the absence of external forces, the authors propose to couple the surface model with a rigid core by using spring forces. This rigid core is simulated using shape matching [MHTG05] which results in a fast and stable simulation. Kubiak et al. [KPGF07] present a simulation method for surgical threads which is based on the positionbased dynamics approach of Müller et al. [MHHR07]. Their method simulates the stiffness, bending and torsion of a thread and also provides feedback for a haptic device. For the simulation Kubiak et al. define distance constraints for stiffness and bending, torsion constraints, contact constraints and friction constraints. The presented method allows for an interactive and robust simulation of knots. 基于位置的方法的一个应用领域是交互式手术模拟。在这一领域，Wang 等人[WXX* 06]介绍了一种基于曲面网格的质量弹簧模型，用于实时模拟可变形体。由于这种模型在没有外力的情况下既不能保持体积，也不能恢复静止时的形状，因此作者建议利用弹簧力将表面模型与刚性核心耦合起来。这种刚性核心是通过形状匹配[MHTG05]来模拟的，从而实现了快速而稳定的模拟。Kubiak 等人[KPGF07]提出了一种基于 Müller 等人[MHHR07]基于位置的动力学方法的手术线模拟方法。他们的方法模拟了螺纹的刚度、弯曲和扭转，还为触觉设备提供了反馈。Kubiak 等人为模拟定义了刚度和弯曲的距离约束、扭转约束、接触约束和摩擦约束。所提出的方法可以对绳结进行交互式的稳健模拟。
The simulation of complex hairstyles using a shape matching approach is presented by Rungiiratananon et al. [RKN10]. Their approach is based on Lattice Shape Matching which was originally introduced by Rivers and James [RJ07]. For the simulation each hair strand is represented by a chain of particles which is subdivided in overlapping chain regions. After shape matching an additional position-based strain limiting is applied to each strand which moves the particles in the direction of their root. Different hair styles are realized by using appropriate initial configurations and by modifying the region sizes of a chain. Rungiiratananon 等人[RKN10]采用形状匹配方法对复杂发型进行了模拟。Rungiiratananon 等人[RKN10]介绍了使用形状匹配方法对复杂发型进行模拟的情况。他们的方法基于格子形状匹配，该方法最初由 Rivers 和 James[RJ07] 提出。在模拟过程中，每根发丝都由一个粒子链来表示，粒子链又被细分为多个重叠的粒子链区域。在形状匹配后，对每根发丝施加额外的基于位置的应变限制，使粒子沿其根部方向移动。通过使用适当的初始配置和修改链的区域大小，可以实现不同的发型。
O'Brien et al. [ODC11] use position-based dynamics for the physically plausible adaptation of motion-captured animations. In their work they use a vertex-based character skeleton and different constraints to preserve the skeleton structure, to define joint limits and to implement a center of mass control. In addition to the kinematic constraints, they define a couple of dynamics constraints which consider vertices in multiple frames. Dynamics constraints are used to enforce smooth acceleration and dynamical correctness. O'Brien 等人[ODC11]使用基于位置的动力学技术对动作捕捉动画进行物理上可信的适配。在他们的工作中，他们使用了基于顶点的角色骨架和不同的约束来保留骨架结构、定义关节限制和实现质量中心控制。除了运动学约束外，他们还定义了一些动态约束，这些约束考虑了多帧中的顶点。动态约束用于执行平滑加速和动态正确性。
Fierz et al. [FSAH12] introduce a position-based approach to stabilize a finite element simulation. When using an explicit time integration for a finite element simulation, the time step size is typically limited by the stiffness of the model and its spatial discretization. In each simulation step Fierz et al. use the Courant-Friedrichs-Lewy (CFL) condition to determine the maximum allowed time step size for each tetrahedral element in their volumetric simulation model. However, instead of using the time step size given by the CFL condition to perform a stable simulation step with an explicit integration scheme, they use a fixed size and mark all elements where the condition is not met. The marked elements are then simulated using a shape matching approach while for all other elements a linear finite element method is used for the simulation. Fierz 等人[FSAH12]介绍了一种基于位置的方法来稳定有限元模拟。在有限元模拟中使用显式时间积分时，时间步长通常会受到模型刚度及其空间离散度的限制。在每个模拟步骤中，Fierz 等人使用 Courant-Friedrichs-Lewy (CFL) 条件来确定其体积模拟模型中每个四面体元素的最大允许时间步长。不过，他们并没有使用 CFL 条件给出的时间步长来通过显式积分方案执行稳定的模拟步长，而是使用了一个固定的步长，并标记了所有不符合条件的元素。然后使用形状匹配方法对标记元素进行模拟，而对所有其他元素则使用线性有限元方法进行模拟。
7. Conclusion 7.结论
In this survey, we focused on a popular and practically relevant subset of approaches for dynamically deforming solids, namely on position-based approaches. Such geometrically motivated techniques are not force-driven and are particularly appropriate in interactive applications due to their versatility, robustness, controllability and efficiency. We explained general ideas of position-based methods, shapematching approaches and data-driven techniques. Various deformation aspects for 2D and 3D solids and efficient solution strategies were discussed with a particular focus on the benefits of position-based approaches compared to forcedriven techniques. 在本次调查中，我们重点研究了用于固体动态变形的一种流行且实用的方法子集，即基于位置的方法。这种以几何为动机的技术不是受力驱动的，由于其多功能性、鲁棒性、可控性和高效性，特别适用于交互式应用。我们解释了基于位置的方法、形状匹配方法和数据驱动技术的一般思路。我们还讨论了二维和三维实体的各种变形问题以及高效的求解策略，并特别强调了基于位置的方法与力驱动技术相比的优势。
References 参考资料
[BB08] BEnder J., BAYER D.: Parallel simulation of inextensible cloth. In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations (2008), pp. 47-56. 6 [BB08] BEnder J., BAYER D.：不可伸展布料的并行仿真。VRIPHYS 08：第五届虚拟现实交互与物理仿真研讨会（2008 年），第 47-56 页。6
[BETC12] Bender J., Erleben K., Trinkle J., Coumans E.: Interactive Simulation of Rigid Body Dynamics in Computer Graphics. In EG 2012 - State of the Art Reports (2012), Cani M.P., Ganovelli F., (Eds.), Eurographics Association, pp. 95-134. [BETC12] Bender J., Erleben K., Trinkle J., Coumans E.: Interactive Simulation of Rigid Body Dynamics in Computer Graphics.In EG 2012 - State of the Art Reports (2012), Cani M.P., Ganovelli F., (Eds.), Eurographics Association, pp.
[BLB*08] Bickel B., Lang M., Botsch M., Otaduy M. A., Gross M.: Pose-space animation and transfer of facial details. In Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2008), pp. 57-66. 18, 19, 20, 21 [BLB*08] Bickel B., Lang M., Botsch M., Otaduy M. A., Gross M.: Pose-space animation and transfer of facial details.In Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2008), pp.18, 19, 20, 21
[BMF03] BRIDSON R., MARINO S., FEDKIW R.: Simulation of clothing with folds and wrinkles,. In Proc. ACM/Eurographics Symposium on Computer Animation (2003), pp. 28-36. 6 [BMF03] BRIDSON R., MARINO S., FEDKIW R.: Simulation of clothing with folds and wrinkles,.In Proc.ACM/Eurographics Symposium on Computer Animation (2003), pp.6
[BMWG07] BERGOU M., MathUR S., WARDETZKY M., GRINSPUN E.: TRACKS: Toward directable thin shells. Proc. of ACM SIGGRAPH (2007). 20 [BMWG07] BERGOU M., MathUR S., WARDETZKY M., GRINSPUN E.: TRACKS: Toward directable thin shells.Proc. of ACM SIGGRAPH (2007).20
[BW98] BARAFF D., WITKIN A.: Large steps in cloth simulation. In Proceedings of Computer graphics and interactive techniques (1998), SIGGRAPH '98, ACM, pp. 43-54. 9 [BW98] BARAFF D.、WITKIN A.：布料模拟中的大步骤。In Proceedings of Computer Graphics and interactive techniques (1998), SIGGRAPH '98, ACM, pp.9
[BWD13] Bender J., Weber D., Diziol R.: Fast and stable cloth simulation based on multi-resolution shape matching. Computers & Graphics (2013). 16, 17 [BWD13] Bender J., Weber D., Diziol R.: 基于多分辨率形状匹配的快速稳定布料模拟。Computers & Graphics (2013).16, 17
[CBC*01] Carr J. C., Beatson R. K., Cherrie J. B., Mitchell T. J., Fright W. R., McCallum B. C., Evans T. R.: Reconstruction and representation of 3D objects with radial basis functions. In Proc. of ACM SIGGRAPH (2001), pp. 6776. 20 [CBC*01] Carr J. C., Beatson R. K., Cherrie J. B., Mitchell T. J., Fright W. R., McCallum B. C., Evans T. R.: Reconstruction and representation of 3D objects with radial basis functions.In Proc. of ACM SIGGRAPH (2001), pp.20
[Cro84] CROw F. C.: Summed-area tables for texture mapping. SIGGRAPH Comput. Graph. 18, 3 (Jan. 1984), 207-212. 12 [Cro84] CROw F. C.：用于纹理映射的求和面积表。SIGGRAPH Comput.Graph.18, 3 (Jan. 1984), 207-212.12
[dASTH10] DE Aguiar E., Sigal L., Treuille A., Hodgins J. K.: Stable spaces for real-time clothing. ACM Trans. Graph. 29, 4 (July 2010), 106:1-106:9. 21 [dASTH10] DE Aguiar E., Sigal L., Treuille A., Hodgins J. K.: Stable spaces for real-time clothing.ACM Trans.Graph.29, 4 (July 2010), 106:1-106:9.21
[DB13] DEul C., BENDER J.: Physically-Based Character Skinning. In VRIPHYS 13: 10th Workshop on Virtual Reality Interactions and Physical Simulations (Lille, France, 2013), Eurographics Association, pp. 25-34. 22 [DB13] DEul C., BENDER J.：基于物理的角色换肤。VRIPHYS 13：第 10 届虚拟现实交互与物理模拟研讨会（法国里尔，2013 年），欧洲图形学协会，第 25-34 页。22
[DBB09] Diziol R., BENDER J., BAYER D.: Volume conserving simulation of deformable bodies. In Short Paper Proceedings of Eurographics (Mar. 2009). 14 [DBB09] Diziol R., BENDER J., BAYER D.：可变形体的体积守恒模拟。欧洲图形学短论文集（2009 年 3 月）。14
[DBB11] DIZIOL R., BENDER J., BAYER D.: Robust real-time deformation of incompressible surface meshes. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2011), SCA '11, Eurographics Association. 11, [DBB11] DIZIOL R., BEND J., BAYER D.：不可压缩曲面网格的稳健实时变形。2011 年 ACM SIGGRAPH/Eurographics 计算机动画研讨会（2011 年）论文集》，SCA '11, 欧洲图形协会。11,
[DSB99] DESBRUN M., SCHRÖDER P., BARR A.: Interactive animation of structured deformable objects. In Proc. of SIGGRAPH 99 (1999), ACM, pp. 1-8. 1, 6 [DSB99] DESBRUN M., SCHRÖDER P., BARR A.: Interactive animation of structured deformable objects.In Proc. of SIGGRAPH 99 (1999), ACM, pp.1, 6
[FSAH12] Fierz B., Spillmann J., Aguinaga I., HardERS M.: Maintaining large time steps in explicit finite element simulations using shape matching. Visualization and Computer Graphics, IEEE Transactions on 18, 5 (may 2012), 717 -728. 22 [FSAH12] Fierz B., Spillmann J., Aguinaga I., HardERS M.: Maintaining large time steps in explicit finite element simulations using shape matching.Visualization and Computer Graphics, IEEE Transactions on 18, 5 (May 2012), 717 -728.22
[GBO04] Goktekin T. G., Bargteil A. W., O’Brien J. F.: A method for animating viscoelastic fluids. ACM Trans. Graph. 23, 3 (Aug. 2004), 463-468. 15 [GBO04] Goktekin T. G., Bargteil A. W., O'Brien J. F.: A method for animating viscoelastic fluids.ACM Trans.Graph.23, 3 (Aug. 2004), 463-468.15
[GHF*07] Goldenthal R., Harmon D., Fattal R., BERcovier M., Grinspun E.: Efficient simulation of inextensible cloth. ACM Trans. Graph. 26, 3 (2007), 49. 3, 6, 7 [GHF*07] Goldenthal R., Harmon D., Fattal R., BERcovier M., Grinspun E.: Efficient simulation of inextensible cloth.ACM Trans.Graph.26, 3 (2007), 49.3, 6, 7
[GM97] Gibson S. F., MiRTICH B.: A survey of deformable modeling in computer graphics. Tech. Rep. TR-97-19, Mitsubishi Electric Research Lab., 1997. 1 [GM97] Gibson S. F., MiRTICH B.: A survey of deformable modeling in computer graphics.Tech.TR-97-19, Mitsubishi Electric Research Lab., 1997.1
[GW06] Georgil J., WeStermann R.: A multigrid framework for real-time simulation of deformable bodies. Computer & Graphics 30 (2006), 408-415. 17 [GW06] Georgil J., WeStermann R.: A multigrid framework for real-time simulation of deformable bodies.Computer & Graphics 30 (2006), 408-415.17
[Hac85] HACKBUSCH W.: Multi-Grid methods and applications, vol. 4 of Springer Series in Computational Mathematics. Springer, 1985. 16 [Hac85] HACKBUSCH W.: Multi-Grid methods and applications, vol. 4 of Springer Series in Computational Mathematics.Springer, 1985.16
[HJCW06] Hong M., Jung S., Choi M., Welch S.: Fast volume preservation for a mass-spring system. IEEE Comput. Graph. Appl. 26 (2006), 83-91. 14, 15 [HJCW06] Hong M.、Jung S.、Choi M.、Welch S.：质量弹簧系统的快速体积保持。IEEE Comput.Graph.26 (2006), 83-91.14, 15
[ISF07] Irving G., Schroeder C., Fedkiw R.: Volume conserving finite element simulations of deformable models. ACM Trans. on Graphics 26, 3 (July 2007), 13:1-13:6. 14 [ISF07] Irving G., Schroeder C., Fedkiw R.: Volume conserving finite element simulations of deformable models.ACM Trans. on Graphics 26, 3 (July 2007), 13:1-13:6.14
[Jak01] JAKOBSEN T.: Advanced character physics. In Proceedings, Game Developer's Conference 2001 (2001). 4 [Jak01] JAKOBSEN T.: Advanced character physics.2001 年游戏开发者大会论文集》（2001 年）。4
[JP99] JAMES D. L., PAI D. K.: Artdefo: accurate real time deformable objects. In Proc. of SIGGRAPH 99 (1999), ACM, pp. 65-72. 1 [JP99] JAMES D. L., PAI D. K.: Artdefo: accurate real time deformable objects.In Proc. of SIGGRAPH 99 (1999), ACM, pp.1
[KCM12] Kim T.-Y., ChentaneZ N., MÜller M.: Long Range Attachments - A Method to Simulate Inextensible Clothing in Computer Games. In Eurographics/ ACM SIGGRAPH Symposium on Computer Animation (2012), Lee J., Kry P., (Eds.), Eurographics Association, pp. 305-310. 7 [KCM12] Kim T.-Y., ChentaneZ N., MÜller M.：Long Range Attachments - A Method to Simulate Inextensible Clothing in Computer Games.In Eurographics/ ACM SIGGRAPH Symposium on Computer Animation (2012), Lee J., Kry P., (Eds.), Eurographics Association, pp.7
[KGBS11] Kavan L., Gerszewski D., Bargteil A. W., SLOAN P.-P.: Physics-inspired upsampling for cloth simulation in games. Proc. of ACM SIGGRAPH (2011). 18, 20, 21 [KGBS11] Kavan L., Gerszewski D., Bargteil A. W., SLOAN P.-P.：游戏中布料模拟的物理启发上采样。Proc. of ACM SIGGRAPH (2011).18, 20, 21
[KM04] Kurihara T., MiYata N.: Modeling deformable human hands from medical images. In Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2004), pp. 357-366. 19 [KM04] Kurihara T., MiYata N.: Modeling deformable human hands from medical images.In Proc. of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2004), pp.19
[KNE10] Kelager M., Niebe S., Erleben K.: A Triangle Bending Constraint Model for Position-Based Dynamics. In VRIPHYS 10: 7th Workshop on Virtual Reality Interactions and Physical Simulations (2010), Erleben K., Bender J., Teschner M., (Eds.), Eurographics Association, pp. 31-37. 4 [KNE10] Kelager M., Niebe S., Erleben K.: A Triangle Bending Constraint Model for Position-Based Dynamics.In VRIPHYS 10: 7th Workshop on Virtual Reality Interactions and Physical Simulations (2010), Erleben K., Bender J., Teschner M., (Eds.), Eurographics Association, pp.4
[KPGF07] Kubiak B., Pietroni N., Ganovelli F., FratarCANGELI M.: A robust method for real-time thread simulation. In Proceedings of the 2007 ACM symposium on Virtual reality software and technology (2007), VRST '07, ACM, pp. 85-88. 22 [KPGF07] Kubiak B., Pietroni N., Ganovelli F., FratarCANGELI M.: A robust method for real-time thread simulation.In Proceedings of the 2007 ACM symposium on Virtual reality software and technology (2007), VRST '07, ACM, pp.22
[KTT13] Kim T., Tessendorf J., ThÜrey N.: Closest point turbulence for liquid surfaces. ACM Trans. Graph. 32, 2 (Apr. 2013), 15:1-15:13. 22 [KTT13] Kim T., Tessendorf J., ThÜrey N.: Closest point turbulence for liquid surfaces.ACM Trans.Graph.32, 2 (Apr. 2013), 15:1-15:13.22
[LBOK13] Liu T., Bargteil A. W., O'Brien J. F., Kavan L.: Fast simulation of mass-spring systems. ACM Transactions on Graphics 32, 6 (Nov. 2013), 209:1-7. Proceedings of ACM SIGGRAPH Asia 2013, Hong Kong. 4 [LBOK13] Liu T., Bargteil A. W., O'Brien J. F., Kavan L.: 质量弹簧系统的快速模拟。ACM Transactions on Graphics 32, 6 (Nov. 2013), 209:1-7.ACM SIGGRAPH Asia 2013论文集，香港。4
[LG98] Lin M. C., Gottschalk S.: Collision detection between geometric models: A survey. In In Proc. of IMA Conference on Mathematics of Surfaces (1998), pp. 37-56. 2 [LG98] Lin M. C., Gottschalk S.: Collision detection between geometric models：A survey.In Proc. of IMA Conference on Mathematics of Surfaces (1998), pp.2
[MC10] MÜller M., Chentanez N.: Wrinkle meshes. In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2010), SCA '10, Eurographics Association, pp. 85-92. 8, 21 [MC10] MÜller M., Chentanez N.: Wrinkle meshes.In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2010), SCA '10, Eurographics Association, pp.8, 21
[MC11] MÜller M., Chentanez N.: Solid simulation with oriented particles. ACM Trans. Graph. 30, 4 (July 2011), 92:192:10. 13, 14 [MC11] MÜller M., Chentanez N.: Solid simulation with oriented particles.ACM Trans.Graph.30, 4 (July 2011), 92:192:10.13, 14
[MCG03] MÜller M., Charypar D., Gross M.: Particlebased fluid simulation for interactive applications. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation (2003), SCA '03, Eurographics Association, pp. 154-159. 5 [MCG03] MÜller M., Charypar D., Gross M.: Particlebased fluid simulation for interactive applications.In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation (2003), SCA '03, Eurographics Association, pp.5
[MGW01] Malzbender T., Gelb D., Wolters H.: Polynomial texture maps. In Proceedings of ACM SIGGRAPH 2001 (Aug. 2001), Computer Graphics Proceedings, Annual Conference Series, pp. 519-528. 20 [MGW01] Malzbender T., Gelb D., Wolters H.: 多项式纹理贴图。In Proceedings of ACM SIGGRAPH 2001 (Aug. 2001), Computer Graphics Proceedings, Annual Conference Series, pp.20
[MHHR07] MÜller M., Heidelberger B., HenniX M., RATCLIFF J.: Position based dynamics. Journal of Visual Communication and Image Representation 18, 2 (2007), 109-118. 2, 22 [MHHR07] MÜller M.，Heidelberger B.，HenniX M.，RATCLIFF J.：基于位置的动力学。视觉传达与图像表征期刊》18，2（2007），109-118。2, 22
[MHTG05] MÜller M., Heidelberger B., Teschner M., GRoss M.: Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3 (2005), 471-478. 10, 11, 15, 22 [MHTG05] MÜller M.、Heidelberger B.、Teschner M.、GRoss M.：基于形状匹配的无网格变形。ACM Trans.Graph.24, 3 (2005), 471-478.10, 11, 15, 22
[Mir96] MIRTICH B.: Fast and accurate computation of polyhedral mass properties. J. Graph. Tools 1, 2 (Feb. 1996), 31-50. 15 [Mir96] MIRTICH B.：多面体质量特性的快速精确计算。J. Graph.Tools 1, 2 (Feb. 1996), 31-50.15
[MJC*08] Ma W.-C., Jones A., Chiang J.-Y., Hawkins T., Frederiksen S., Peers P., Vukovic M., Ouhyoung M., DEBEVEC P.: Facial performance synthesis using deformationdriven polynomial displacement maps. ACM Trans. Graph. (Proc. of ACM SIGGRAPH Asia) 27, 5 (2008). 18, 20 [MJC*08] Ma W.-C., Jones A., Chiang J.-Y., Hawkins T., Frederiksen S., Peers P., Vukovic M., Ouhyoung M., DEBEVEC P.：使用变形驱动多项式位移图的面部表现合成。ACM Trans.Graph.(Proc. of ACM SIGGRAPH Asia) 27, 5 (2008).18, 20
[MKC12] MÜller M., Kim T.-Y., Chentanez N.: Fast Simulation of Inextensible Hair and Fur. In VRIPHYS 12: 9th Workshop on Virtual Reality Interactions and Physical Simulations (2012), Eurographics Association. 7 [MKC12] MÜller M.、Kim T.-Y.、Chentanez N.：快速模拟不可伸展的头发和毛皮。VRIPHYS 12：第九届虚拟现实交互与物理仿真研讨会（2012），欧洲图形学协会。7
[MM13] MACKLIN M., MÜLler M.: Position based fluids. ACM Trans. Graph. 32, 4 (July 2013), 104:1-104:12. 5 [MM13] MACKLIN M., MÜLler M.: Position based fluids.ACM Trans.Graph.32, 4 (July 2013), 104:1-104:12.5
[Mon92] Monaghan J. J.: Smoothed particle hydrodynamics. Annual Review of Astronomy and Astrophysics 30, 1 (1992), 543574. 5 [Mon92] Monaghan J. J.: Smoothed particle hydrodynamics.Annual Review of Astronomy and Astrophysics 30, 1 (1992), 543574.5
[Mon94] Monaghan J. J.: Simulating free surface flows with sph. J. Comput. Phys. 110, 2 (Feb. 1994), 399-406. 5 [Mon94] Monaghan J. J.: Simulating free surface flows with sph.J. Comput.110, 2 (Feb. 1994), 399-406.5
[MSJT08] MÜller M., Stam J., JAmes D., ThÜrey N.: Real time physics: class notes. In ACM SIGGRAPH 2008 classes (2008), SIGGRAPH '08, ACM, pp. 88:1-88:90. 1 [MSJT08] MÜller M., Stam J., JAmes D., ThÜrey N.: Real time physics: class notes.In ACM SIGGRAPH 2008 classes (2008), SIGGRAPH '08, ACM, pp.1
[MTV05] Magnenat-Thalmann N., Volino P.: From early draping to haute couture models: 20 years of research. The Visual Computer 21 (2005), 506-519. 1 [MTV05] Magnenat-Thalmann N., Volino P.：从早期的悬垂到高级时装模特：20 年的研究。视觉计算机 21 (2005)，506-519。1
[Mü108] MÜlLER M.: Hierarchical Position Based Dynamics. In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations (2008), Faure F., Teschner M., (Eds.), Eurographics Association, pp. 1-10. 7 [Mü108] MÜlLER M.: Hierarchical Position Based Dynamics.In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations (2008), Faure F., Teschner M., (Eds.), Eurographics Association, pp.7
[NMK* 06] Nealen A., Müller M., Keiser R., BoXerman E., CARLSON M.: Physically based deformable models in computer graphics. Computer Graphics Forum 25, 4 (December 2006), 809-836. 1, 9 [NMK* 06] Nealen A., Müller M., Keiser R., BoXerman E., CARLSON M.: Physically based deformable models in computer graphics.Computer Graphics Forum 25, 4 (December 2006), 809-836.1, 9
[ODC11] O'Brien C., Dingliana J., Collins S.: Spacetime vertex constraints for dynamically-based adaptation of motion-captured animation. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2011), SCA '11, ACM, pp. 277-286. 22 [ODC11] O'Brien C., Dingliana J., Collins S.: Spacetime vertex constraints for dynamically-based adaptation of motion-captured animation.In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2011), SCA '11, ACM, pp.22
[OH99] O’BrIEn J. F., Hodgins J. K.: Graphical modeling and animation of brittle fracture. In SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1999), ACM Press/Addison-Wesley Publishing Co., pp. 137-146. 1 [OH99] O'BrIEn J. F., Hodgins J. K.: 脆性断裂的图形建模和动画。In SIGGRAPH '99：第 26 届计算机图形学与交互技术年会论文集》（美国纽约，1999 年），ACM 出版社/Addison-Wesley 出版公司，第 137-146 页。1
[PB88] PlATT J. C., BARR A. H.: Constraints methods for flexible objects. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques (1988), SIGGRAPH '88, ACM, pp. 279-288. 9 [PB88] PlATT J. C., BARR A. H.: 灵活对象的约束方法。In Proceedings of the 15th annual conference on Computer graphics and interactive techniques (1988), SIGGRAPH '88, ACM, pp.9
[Pro95] PROVOT X.: Deformation constraints in a mass-spring model to describe rigid cloth behavior. In In Graphics Interface (1995), Davis W. A., Prusinkiewicz P., (Eds.), Canadian HumanComputer Communications Society, pp. 147-154. 6 [Pro95] PROVOT X：描述刚性布行为的质量弹簧模型中的变形约束。In In Graphics Interface (1995), Davis W. A., Prusinkiewicz P., (Eds.), Canadian HumanComputer Communications Society, pp.6
[RJ07] RIVERS A. R., JAMES D. L.: FastLSM: fast lattice shape matching for robust real-time deformation. In SIGGRAPH '07: ACM SIGGRAPH 2007 papers (2007), ACM, p. 82. 11, 12, 22 [RJ07] RIVERS A. R., JAMES D. L.: FastLSM: fast lattice shape matching for robust real-time deformation.In SIGGRAPH '07: ACM SIGGRAPH 2007 papers (2007), ACM, p. 82.11, 12, 22
[RKN10] RungJiratananon W., KANAmori Y., NiShita T.: Chain shape matching for simulating complex hairstyles. Computer Graphics Forum 29, 8 (2010), 2438-2446. 22 [RKN10] RungJiratananon W.、KANAmori Y.、NiShita T.：用于模拟复杂发型的链形匹配。计算机图形论坛 29，8（2010），2438-2446。22
[SD92] ShoemaKe K., DUfF T.: Matrix animation and polar decomposition. In Proceedings of the conference on Graphics interface '92 (1992), Morgan Kaufmann Publishers Inc., pp. 258-264. 16 [SD92] ShoemaKe K., DUfF T.: Matrix animation and polar decomposition.In Proceedings of the conference on Graphics interface '92 (1992), Morgan Kaufmann Publishers Inc., pp.16
[SGdA*10] Stoll C., Gall J., De Aguiar E., Thrun S., THEOBALT C.: Video-based reconstruction of animatable human characters. ACM Trans. Graph. 29, 6 (Dec. 2010), 139:1-139:10. 22 [SGdA*10] Stoll C., Gall J., De Aguiar E., Thrun S., THEOBALT C.：基于视频的可动画人类角色重建。ACM Trans.Graph.29, 6 (Dec. 2010), 139:1-139:10.22
[SGT09] Schmedding R., Gissler M., Teschner M.: Optimized damping for dynamic simulations. In Spring Conference on Computer Graphics (2009), pp. 205-212. 9 [SGT09] Schmedding R., Gissler M., Teschner M.：动态模拟的优化阻尼。计算机图形学春季会议（2009 年），第 205-212 页。9
[SHZO07] Sengupta S., Harris M., Zhang Y., Owens J. D.: Scan primitives for GPU computing. In Proc. of the 22nd ACM SIGGRAPH/Eurographics Symp. on Grap. Hardware (2007), Eurographics Association, pp. 97-106. 17 [SHZO07] Sengupta S., Harris M., Zhang Y., Owens J. D.: GPU 计算的扫描原语。在第 22 届 ACM SIGGRAPH/Eurographics Symp.Hardware (2007), Eurographics Association, pp.17
[SKBK13] Schmitt N., Knuth M., Bender J., KuiJper A.: Multilevel Cloth Simulation using GPU Surface Sampling. In VRIPHYS 13: 10th Workshop on Virtual Reality Interactions and Physical Simulations (Lille, France, 2013), Eurographics Association, pp. 1-10. 7 [SKBK13] Schmitt N., Knuth M., Bender J., KuiJper A.: Multilevel Cloth Simulation using GPU Surface Sampling.VRIPHYS 13：第 10 届虚拟现实交互与物理仿真研讨会（法国里尔，2013 年），欧洲图形学协会，第 1-10 页。7
[SOG08] Steinemann D., Otaduy M. A., Gross M.: Fast adaptive shape matching deformations. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2008), SCA '08, Eurographics Association, pp. 8794. 12 [SOG08] Steinemann D., Otaduy M. A., Gross M.：快速自适应形状匹配变形。In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2008), SCA '08, Eurographics Association, pp.12
[SSBT08] Stumpp T., Spillmann J., Becker M., Teschner M.: A Geometric Deformation Model for Stable Cloth Simulation. In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations (2008), Faure F., Teschner M. (Eds.), Eurographics Association, pp. 39-46. 16 [SSBT08] Stumpp T., Spillmann J., Becker M., Teschner M.: A Geometric Deformation Model for Stable Cloth Simulation.In VRIPHYS 08: Fifth Workshop in Virtual Reality Interactions and Physical Simulations (2008), Faure F., Teschner M. (Eds.), Eurographics Association, pp.16
[SSH12] SeIler M., Spillmann J., Harders M.: Enriching coarse interactive elastic objects with high-resolution data-driven deformations. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2012), SCA '12, Eurographics Association, pp. 9-17. 21 [SSH12] SeIler M., Spillmann J., Harders M.: Enriching coarse interactive elastic objects with high-resolution data-driven deformations.ACM SIGGRAPH/Eurographics 计算机动画研讨会论文集（2012 年），SCA '12, Eurographics 协会，第 9-17 页。21
[Sta09] Stam J.: Nucleus: Towards a unified dynamics solver for computer graphics. IEEE International Conference on Computer-Aided Design and Computer Graphics (2009), 1-11. [Sta09] Stam J.: Nucleus：面向计算机图形学的统一动力学求解器。IEEE 计算机辅助设计和计算机图形国际会议（2009 年），1-11。
[TBhF03] Teran J., Blemker S., Hing V. N. T., Fedkiw R.: Finite volume methods for the simulation of skeletal muscle. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2003), Eurographics Association, pp. 68-74. 1 [TBhF03] Teran J., Blemker S., Hing V. N. T., Fedkiw R.: 骨骼肌模拟的有限体积方法。In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp.Anim.(2003), Eurographics Association, pp.1
[TF88] Terzopoulos D., Fleischer K.: Deformable models. The Visual Computer 4 (1988), 306-331. 9 [TF88] Terzopoulos D., Fleischer K.: Deformable models.视觉计算机 4 (1988)，306-331。9
[THmg04] Teschner M., Heidelberger B., Muller M., GROSS M.: A versatile and robust model for geometrically complex deformable solids. In Proceedings of the Computer Graphics International (Washington, DC, USA, 2004), CGI '04, IEEE Computer Society, pp. 312-319. 1 [THmg04] Teschner M., Heidelberger B., Muller M., GROSS M.: A versatile and robust model for geometricically complex deformable solids.In Proceedings of the Computer Graphics International (Washington, DC, USA, 2004), CGI '04, IEEE Computer Society, pp.1
[TKH*05] Teschner M., Kimmerle S., Heidelberger B. Zachmann G., Raghupathi L., Fuhrmann A., Cani M.P., Faure F., Magnenat-Thalmann N., Strasser W., [TKH*05] Teschner M., Kimmerle S., Heidelberger B. Zachmann G., Raghupathi L., Fuhrmann A., Cani M.P., Faure F., Magnenat-Thalmann N., Strasser W.、
Volino P.: Collision detection for deformable objects. Computer Graphics Forum 24, 1 (Mar. 2005), 61-81. 2 Volino P.：可变形物体的碰撞检测Computer Graphics Forum 24, 1 (Mar. 2005), 61-81.2
[TPBF87a] Terzopoulos D., Platt J., Barr A., Fleischer K.: Elastically deformable models. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques (1987), SIGGRAPH '87, ACM, pp. 205-214. 1 [TPBF87a] Terzopoulos D., Platt J., Barr A., Fleischer K.: Elastically deformable models.第 14 届计算机图形学与交互技术年会论文集 (1987)，SIGGRAPH '87，ACM，第 205-214 页。1
[TPBF87b] Terzopoulos D., Platt J., BARr A., Fleischer K.: Elastically deformable models. In Computer Graphics (Proceedings of SIGGRAPH 87) (1987), vol. 21, ACM, pp. 205-214. 1 [TPBF87b] Terzopoulos D.、Platt J.、BARr A.、Fleischer K.：弹性可变形模型。计算机图形学（SIGGRAPH 87论文集）（1987），第21卷，ACM，第205-214页。1
[vFTS06] von Funck W., Theisel H., SeIdel H.-P.: Vector field based shape deformations. ACM Trans. on Graphics 25, 3 (July 2006), 1118-1125. 14 [vFTS06] von Funck W., Theisel H., SeIdel H.-P：基于矢量场的形状变形。ACM Trans. on Graphics 25, 3 (July 2006), 1118-1125.14
[WBS*13] Weber D., Bender J., Schnoes M., Stork A., FELLNER D.: Efficient GPU data structures and methods to solve sparse linear systems in dynamics applications. Computer Graphics Forum 32, 1 (2013), 16-26. 17 [WBS*13] Weber D.、Bender J.、Schnoes M.、Stork A.、FELLNER D.：解决动力学应用中稀疏线性系统的高效 GPU 数据结构和方法。Computer Graphics Forum 32, 1 (2013), 16-26.17
[WHRO10] Wang H., Hecht F., Ramamoorthi R., O'BRIEN J.: Example-based wrinkle synthesis for clothing animation. ACM Trans. Graph. 29, 4 (July 2010), 107:1-107:8. 18 [WHRO10] Wang H., Hecht F., Ramamoorthi R., O'BRIEN J.: Example-based wrinkle synthesis for clothing animation.ACM Trans.Graph.29, 4 (July 2010), 107:1-107:8.18
[WOR10] Wang H., O’BRIEn J., Ramamoorthi R.: Multiresolution isotropic strain limiting. ACM Trans. Graph. 29, 6 (Dec. 2010), 156:1-156:10. 7 [WOR10] Wang H., O'BRIEn J., Ramamoorthi R.: Multiresolution isotropic strain limiting.ACM Trans.Graph.29, 6 (Dec. 2010), 156:1-156:10.7
[WXX*06] Wang Y., Xiong Y., Xu K., Tan K., Guo G.: A mass-spring model for surface mesh deformation based on shape matching. In Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia (2006), GRAPHITE '06, ACM, pp. 375-380. 22 [WXX*06] Wang Y., Xiong Y., Xu K., Tan K., Guo G.: A mass-spring model for surface mesh deformation based on shape matching.第四届澳大拉西亚和东南亚计算机图形学与交互技术国际会议（2006）论文集，GRAPHITE '06，ACM，第 375-380 页。22
[ZBO13] Zurdo J. S., BRITO J. P., OTAdUY M. A.: Animating wrinkles by example on non-skinned cloth. IEEE Transactions on Visualization and Computer Graphics 19, 1 (2013). 18, 19, 20, 21 [ZBO13] Zurdo J. S.、BRITO J. P.、OTAdUY M. A.：通过非皮肤布料上的皱纹实例制作动画。IEEE Visualization and Computer Graphics 19, 1 (2013).18, 19, 20, 21
