<H1>2 Simulation Overview</H1>
        In this section, we give a brief overview of our simulator’s architecture and introduce some notation. The next section derives the linear system used to step the simulator forward implicitly while section 4 describes the specifics of the internal forces and their derivatives that form the linear system. Section 5 describes how constraints are maintained (once established), with a discussion in section 6 on collision detection and constraint initialization. Section 7 describes our adaptive step-size control, and we conclude in section 8 with some simulation results.
      
      
        <H2>2.1 Notation and Geometry</H2>
        Our simulator models cloth as a triangular mesh of particles. Given a mesh of n particles, the position in world-space of the ith particle is x i ∈ IR 3 . The geometric state of all the particles is simply x ∈ IR 3n . The same component notation applies to forces: a force f ∈ IR 3n acting on the cloth exerts a force f i on the ith particle. Real-world cloth is cut from flat sheets of material and tends to resist deformations away from this initial flat state (creases and pleats not withstanding). We capture the rest state of cloth by assigning each particle an unchanging coordinate (u i , v i ) in the plane. 3 Section 4 makes use of these planar coordinates. Collisions between cloth and solid objects are handled by preventing cloth particles from interpenetrating solid objects. Our current implementation models solid objects as triangularly faced polyhedra. Each face has an associated thickness and an orientation; particles found to be sufficiently near a face, and on the wrong side, are deemed to have collided with that face, and become subject to a contact constraint. (If relative velocities are extremely high, this simple test may miss some collisions. In this case, analytically checking for intersection between previous and current positions can guarantee that no collisions are missed.) For cloth/cloth collisions, we detect both face-vertex collisions between cloth particles and triangles, as well as edge/edge collisions between portions of the cloth. As in the case of solids, close proximity or actual intersection of cloth with itself initiates contact handling.
        44
        SIGGRAPH 98, Orlando, July 19–24
        C OMPUTER G RAPHICS Proceedings, Annual Conference Series, 1998
      
      
        <H2>2.2 Energy and Forces</H2>
        The most critical forces in the system are the internal cloth forces which impart much of the cloth’s characteristic behavior. Breen et al. [ 3 ]
 describes the use of the Kawabata system of measurement for realistic determination of the in-plane shearing and out-of-plane bending forces in cloth. We call these two forces the shear and bend forces. We formulate the shear force on a per triangle basis, while the bend force is formulated on a per edge basis—between pairs of adjacent triangles. The strongest internal force—which we call the stretch force— resists in-plane stretching or compression, and is also formulated per triangle. Under normal conditions, cloth does not stretch appreciably under its own weight. This requires the stretch force to have a high coefficient of stiffness, and in fact, it is the stretch force that is most responsible for the stiffness of equation (1). A common practice in explicitly integrated cloth systems is to improve running time by decreasing the strength of the stretch force; however, this leads to “rubbery” or “bouncy” cloth. Our system uses a very stiff stretch force to combat this problem, without any detrimental effects on the run-time performance. While the shear and bend force stiffness coefficients depend on the material being simulated, the stretch coefficient is essentially the same (large) value for all simulations. (Of course, if stretchy cloth is specifically called for, the stretch coefficient can be made smaller.) Complementing the above three internal forces are three damping forces. In section 5, we formulate damping forces that subdue any oscillations having to do with, respectively, stretching, shearing, and bending motions of the cloth. The damping forces do not dissipate energy due to other modes of motion. Additional forces include air-drag, gravity, and user-generated generated mouse-forces (for interactive simulations). Cloth/cloth contacts generate strong repulsive linear-spring forces between cloth particles. Combining all forces into a net force vector f, the acceleration ẍ i of the ith particle is simply ẍ i = f i /m i , where m i is the ith particle’s mass. The mass m i is determined by summing one third the mass
        3 In general, each particle has a unique (u, v) coordinate; however, to accommodate pieces of cloth that have been topologically seamed together (such as a sleeve), particles lying on the seam must have multiple (u, v) coordinates. For these particles, we let the (u, v) coordinate depend on which triangle we are currently examining. The (u, v) coordinates are useful for texturing.
        of all triangles containing the ith particle. (A triangle’s mass is the product of the cloth’s density and the triangle’s fixed area in the uv coordinate system.) Defining the diagonal mass matrix M ∈ IR 3n×3n by diag(M) = (m 1 , m 1 , m 1 , m 2 , m 2 , m 2 , . . . , m n , m n , m n ), we can write simply that
        
          2
          ẍ = M −1 f(x, x).
        
      
      
        <H2>2.3 Sparse Matrices</H2>
        The use of an implicit integration method, described in the next section, generates large unbanded sparse linear systems. We solve these systems through a modified conjugate gradient (CG) iterative method, described in section 5. CG methods exploit sparsity quite easily, since they are based solely on matrix-vector multiplies, and require only rudimentary sparse storage techniques. The sparsity of the matrix generated by the implicit integrator is best represented in block-fashion: for a system with n particles, we deal with an n × n matrix, whose non-zero entries are represented as dense 3 × 3 matrices of scalars. The matrix is represented as an array of n rows; each row is a linked list of the non-zero elements of that row, to accommodate possible run-time changes in the sparsity pattern, due to cloth/cloth contact. The (dense) vectors that are multiplied against this matrix are stored simply as n element arrays of threecomponent vectors. The overall implementation of sparsity is completely straightforward.
      
      
        <H2>2.4 Constraints</H2>
        An individual particle’s position and velocity can be completely controlled in either one, two, or three dimensions. Particles can thus be attached to a fixed or moving point in space, or constrained to a fixed or moving surface or curve. Constraints are either user-defined (the time period that a constraint is active is user-controlled) or automatically generated, in the case of contact constraints between cloth and solids. During cloth/solid contacts, the particle may be attached to the surface, depending on the magnitudes of the frictional forces required; otherwise, the particle is constrained to remain on the surface, with sliding allowed. The mechanism for releasing a contact constraint, or switching between sliding or not sliding, is described in section 5. The constraint techniques we use on individual particles work just as well for collections of particles; thus, we could handle cloth/cloth intersections using the technique described in section 5, but the cost is potentially large. For that reason, we have chosen to deal with cloth/cloth contacts using penalty forces: whenever a particle is near a cloth triangle or is detected to have passed through a cloth triangle, we add a stiff spring with damping to pull the particle back to the correct side of the triangle. The implicit solver easily tolerates these stiff forces.
      
      
        