<H1>5 Constraints</H1>
        In this section, we describe how constraints are imposed on individual cloth particles. The constraints we discuss in this section are either automatically determined by the user (such as geometric attachment constraints on a particle) or are contact constraints (generated by the system) between a solid object and a particle. The techniques we describe in this section could be used for multi-particle constraints; however, constraints that share particle would need to be merged. Thus, a set of four-particle constraints (such as vertex/triangle or edge/edge contacts in the cloth) might merge to form a single constraint on arbitrarily many particles, which would be expensive to maintain. Because of this, we handle cloth/cloth contacts with strong springs (easily dealt with, given the simulator’s underlying implicit integration base) and “position alteration,” a technique described in section 6. At any given step of the simulation, a cloth particle is either completely unconstrained (though subject to forces), or the particle may be constrained in either one, two or three dimensions. Given the differential nature of our formulation, it is the particle’s acceleration, or equivalently, the change in the particle’s velocity, that is constrained. If the particle is constrained in all three dimensions, then we are explicitly setting the particle’s velocity (at the next step). If the constraint is in two or one dimensions, we are constraining the particle’s velocity along either two or one mutually orthogonal axes. Before describing our constraint method, we discuss several other possible enforcement mechanisms and explain why we chose not to use them.
      
      
        Reduced Coordinates
        An obvious and quite exact method for constraining a particle is to reduce the number of coordinates describing the particle’s position and velocity. A completely constrained particle would have no coordinates, while a particle with one dimension of constraint would have two coordinates. This is possible—but it complicates the system immensely. If we change the number of coordinates per particle, we alter the size of the derivative matrices in equation (6), as well as the sparsity pattern (this happens when a particle changes from having no coordinates to some coordinates, or vice versa). Given the transient nature of contact constraints between cloth and solids, this is most unappealing. The computation of the derivative matrices’ entries is also greatly complicated, because we must now introduce extra Jacobian matrices that relate a particle’s reduced coordinates to its motion in world-space. Finally, correct constraint-release behavior between cloth and solid objects is difficult to achieve using a reduced coordinate formulation. Considering all of this, we immediately rejected this method of constraints.
      
      
        Penalty Methods
        We could constrain particles through the use of strong energy functions—essentially, stiff springs that attempt to prevent illegal particle motions. Since our entire formulation is geared to handle stiffness, the usual objections to enforcing constraints with springs—very stiff equations—do not carry as much weight. We tried this for a time, and found it to be a not unreasonable constraint enforcement mechanism. However, penalty methods do not enforce constraints exactly, and they do add some additional stiffness to the system. Since the mechanism we describe enforces constraints exactly, and adds no extra stiffness, we turned away from penalty methods except in the case of cloth/cloth interactions.
      
      
        Lagrange Multipliers
        We could introduce additional constraint forces—that is, Lagrange multipliers—into our system to satisfy the constraints. This involves augmenting the linear system of equation (6) with extra variables (the multipliers) and extra equations (the constraint conditions). Unfortunately, this turns a positive definite system into an indefinite system, which means that iterative methods such as CG will need to square the system first, thereby doubling the running time and degrading the numerical conditionining of the linear system. Additionally, an iterative method will generally not enforce the constraints exactly without a large number of iterations. (A direct method for solving the augmented system would, however, avoid this problem.) Again, the constraint method we describe steps past these difficulties, so we turned away from using Lagrange multipliers.
      
      
        <H2>5.1 Mass Modification</H2>
        The idea behind our constraint enforcement mechanism is described quite simply, although the actual implementation is somewhat more complicated, to maximize performance. A dynamic simulation usually requires knowledge of the inverse mass of objects; for example, note the appearance of M −1 , and not M in equation (6). In the case of a single particle, we write x  ̈ i = m 1 i f i to describe a particle’s acceleration. When inverse mass is used, it becomes trivial to enforce constraints by altering the mass. Suppose for example that we want to keep particle i’s velocity from changing. If we take 1/m i to be zero, we give the particle an infinite mass, making it ignore all forces exerted on it. Complete control over a particle’s acceleration is thus taken care of by storing a value of zero for the particle’s inverse mass. What if we wish to constrain the particle’s acceleration in only one or two dimensions? Although we normally think of a particle’s mass as a scalar, we need not always do so. Suppose we write ẍ i = 1/m 0 i 1/m 0 i 0 0 f i . Now ẍ i 0 0 0 must lie in the xy plane; no acceleration in the z direction is possible. Note than an unconstrained particle can be considered to have the 3 × 3 inverse mass matrix 1 I, with I the identity matrix. m i Of course, we are not restricted to coordinate-aligned constraints. More generally, given a unit vector p ∈ IR 3 , a particle is prevented from accelerating along p by using an inverse mass matrix 1 (I − m i pp T ); this follows from the fact that (I − pp T )p = 0. Similarly, given two mutually orthogonal unit vectors p and q, we prevent a particle from accelerating in either the p or q direction by using the inverse mass matrix 1 (I − pp T − qq T ). m i By allowing constrained particles to have these sorts of inverse masses, we can build constraints directly into equation (6). We will create a modified version W of M −1 ; W will be a block-diagonal matrix, with off-diagonal blocks being zero, and diagonal blocks defined as follows: let ndof(i) indicate the number of degrees of freedom particle i has, and let particle i’s prohibited directions be p i (if ndof(i) = 2) or p i and q i (if ndof(i) = 1) with p i and q i mutually orthogonal unit vectors. W’s diagonal blocks are W ii = m 1 i S i where
        48
        SIGGRAPH 98, Orlando, July 19–24
        C OMPUTER G RAPHICS Proceedings, Annual Conference Series, 1998
        
          13
           S i =         I 0 (I (I − − p p i i p p i i T T ) − q i q i T ) if if if ndof(i) ndof(i) ndof(i) ndof(i) = = = = 1 2 3 0.
        
        We are not limited to constraining particles to have zero accelerations in certain directions; rather, we control exactly what the change in velocity is along the constrained directions. For every particle i, let z i be the change in velocity we wish to enforce in the particle’s constrained direction(s). (This implies we can choose any value of z i for a completely constrained particle, since all directions are constrained; an unconstrained particle must have z i = 0 since it has no constrained directions.) Using W and z, we rewrite equation (6) to directly enforce constraints. If we solve
        
          14
          I − hW ∂v ∂f − h 2 W ∂x ∂f v = hW f 0 + h ∂x ∂f v 0 + z
        
        for v, we will obtain a v which is consistent with our constraints. Completely constrained particles will have v i = z i , while partially constrained particles will have a v i whose component in the constrained direction(s) is equal to z i .
      
      
        <H2>5.2 Implementation</H2>
        We initially implemented constraints using equation (14) and found that it worked exactly as advertised. For very small test systems, we solved equation (14) using a direct method (Gaussian elimination) without any problems. For larger systems, we planned to use the iterative, sparsity-exploiting CG method, which immediately presents us with a problem: equation (14) is not a symmetric linear system. (For that matter, neither is equation (6) unless all particles have the same mass.) CG methods, however, require symmetric matrices. 6 We could apply a CG method to the unsymmetric matrix of equation (14) by use of the “normal equations”; but this involves multiplying the matrix of equation (14) with its transpose which doubles the cost of each iteration while squaring the condition number of the system [ 14 ]
—a less than desirable plan. We decided that using a CG method to solve the unsymmetric problem was not acceptable. Note that without constraints, applying a CG method to equation (6) is not difficult, because we can transform this equation to 6 In fact, they work best on positive definite symmetric matrices. The matrices we ultimately hand to our CG method are positive definite. a symmetric (and positive definite) system by left-multiplying the entire equation by M: the system
        
          15
          M − h ∂v ∂f − h 2 ∂x ∂f v = h f 0 + h ∂x ∂f v 0
        
        is symmetric and has the same solution v as equation (6). Unfortunately, we cannot apply the same transformation to equation (14), because W is singular—the filtering blocks in equation (13) are rank deficient—so we cannot multiply through by W −1 . The solution to the problem of asymmetry is to modify the CG method so that it can operate on equation (15), while procedurally applying the constraints inherent in the matrix W at each iteration. The modified method will need to know about the particles’ constraints and the vector z. Let us define the symmetric positive definite matrix A by
        
          16
          A = M − h ∂f − h 2 ∂f ∂v ∂x
        
        and the vector b and residual vector r as ∂f b = h f 0 + h ∂x v 0 and r = A v − b. Given A, b, constraints on the particles, and z, our modified CG method will try to find v that satisfies two conditions: • For each particle i, the component of r i in the particle’s unconstrained direction(s) will be made equal to zero (assuming the method is run for sufficiently many iterations). • For each particle i, the component of v i in the particle’s constrained direction(s) will be exactly z i (no matter how many iterations are taken). Note that these two conditions imply that unconstrained particles have r i close to zero, while completely constrained particles have v i = z i . Thus in the case when no particles are constrained, our modified CG method should produce the same result as the regular CG method.
      
      
        <H2>5.3 The Modified Conjugate Gradient Method</H2>
        The CG method (technically, the preconditioned CG method) takes a symmetric positive semi-definite matrix A, a symmetric positive definite preconditioning matrix P of the same dimension as A, a vector b and iteratively solves A v = b. The iteration stops when b − A v is less than b where is a user-defined tolerance value. The preconditioning matrix P, which must be easily invertible, speeds convergence to the extent that P −1 approximates A. We wholeheartedly refer the reader to Shewchuk 
[ 14 ] for information on the CG method. We derive our modified conjugate gradient method by observing that the effect of the matrix W in equation (14) is to filter out velocity changes in the constrained directions. Our idea then is to define an invariant— for all i, the component of v i in the constrained direction(s) of particle i is equal to z i —and then establish and maintain the invariant at each iteration, by defining a filtering procedure filter. The role of filter is to take a vector a and perform the same filtering operation (see equation (13)) as multiplying by W, but leaving out the scaling by 1/m i : procedure filter(a) for i = 1 to n a i = S i a i return a
        49
        SIGGRAPH 98, Orlando, July 19–24
        C OMPUTER G RAPHICS Proceedings, Annual Conference Series, 1998
        Using filter, we define the modified CG method modified-pcg as follows:
        1 procedure modified-pcg 2 v = z 3 δ 0 = filter(b) T P filter(b) 4 r = filter(b − A v) 5 c = filter(P −1 r) 6 δ new = r T c 7 while δ new &gt; 2 δ 0 8 q = filter(Ac) 9 α = δ new /(c T q) 10 v = v + αc 11 r = r − αq 12 s = P −1 r 13 δ old = δ new 14 δ new = r T s 15 c = filter(s + δ new c) δ old Line 2 of the procedure establishes our invariant. Lines 5 and 15 maintain the invariant by filtering c before adding it to v. The unmodified conjugate gradient method establishes a stopping criterion based on b T Pb. Since our constrained formulation ignores certain components of b, our stopping criterion should as well, so we add filtering to line 3. The vector r measures the solution error b − A v, and should not include error due to the constraints; hence we add filtering at lines 4 and 8. (Note that removing the calls to filter and changing line 2 to v = 0 yields the standard preconditioned conjugate gradient method.) We use a simple preconditioner P by making P be a diagonal matrix with P ii = 1/A ii so products involving P −1 are trivially computed. More elaborate preconditioners could be used, though we doubt there is a large speedup to be gained. Matrix-vector products with A are of course implemented in sparse matrix-vector fashion, using the data structures defined in section 2.3. Given modified-pcg, obvious questions are “does it work?” followed by “how does it compare with the unmodified CG method?” Proofs about CG methods are difficult in general; in practice, our method always converges, which answers the first question. Prior to implementing modified-pcg, we used a penalty method and applied the standard CG method to equation (15). When we began using procedure modified-pcg, we did not notice any substantial change in the number of iterations required by the method. Empirically, we conclude that the two methods have similar convergence behavior. Result in section 8 indicate that the running time is close to O(n 1.5 ), which is what unmodified CG would be expected to deliver on this sort of problem [ 14 ].
      
      
        <H2>5.4 Determining the Constraint Forces</H2>
        For contact constraints (between cloth and solid objects) we need to know what the actual force of constraint is, in order to determine when to terminate a constraint. Additionally, we need to know the constraint force actually exerted in order to model frictional forces properly. Fortunately, it is easy to add one more step to modified-pcg to determine the constraint force. When modified-pcg terminates, the residual error e = A v − b has the property that e i need not be close to zero if particle i is constrained. In fact, e i is exactly the extra constraint force that must have been supplied to enforce the constraint. Thus, we can compute constraint forces at the end of modified-pcg by performing one last matrixvector product to compute A v − b. (The vector r in modified-pcg is equal to filter(A v − b), so the extra matrix-vector product to compute e really is necessary.) The particles’ accelerations are inherently dependent on one another through the matrix A of equation (16). This means that the correct approach to determing constraint release is combinatoric, as in Baraff [ 2 ]. We reject this approach as impractical given the dimension of A. Instead, we allow contacts to release when the constraint force between a particle and a solid switches from a repulsive force to an attractive one. In practice, this has proven to work well. Friction presents a similar problem. When cloth contacts a solid, we lock the particle onto the surface, if the relative tangential velocity is low. We monitor the constraint force, and if the tangential force exceeds some fraction of the normal force, we allow the particle to slide on the surface. For high sliding velocities, we apply a dissipative tangential force, opposite the relative sliding direction, proportional to the normal force.
      
      
        