Large steps in cloth simulation

David BaraffAndrew Witkin

article1998SIGGRAPH2,145 citations

Physically based animation of garments on moving characters has historically been computationally expensive. Because real fabrics strongly resist stretching while bending and shearing easily, the underlying mathematical equations are extremely stiff. Prior simulation systems largely relied on explicit time-stepping methods, which become numerically unstable unless restricted to tiny time increments. This instability severely limited the mesh resolution and visual realism achievable within practical production schedules.

The article demonstrates that combining an implicit integration method with direct particle constraint enforcement enables fast, robust, and stable cloth simulation using large time steps. The approach models fabric as a triangular mesh to eliminate topological constraints, deriving stretch, shear, and bend behaviors alongside a unified formulation for internal damping. To advance the simulation, the system generates a large, sparse linear system at each step. It solves this system using a modified conjugate gradient solver that directly maintains particle constraints across every iteration without relying on penalty functions or auxiliary multiplier variables. The workflow also integrates an adaptive time-stepping controller that monitors stretch deformations to proactively catch numerical instability, alongside an instantaneous position alteration technique to resolve geometric intersections smoothly.

The evaluation demonstrates substantial performance gains over traditional approaches. Simulations consistently advanced using large time steps, averaging only two to three steps per 30 Hz animation frame. The solver required relatively few iterations to converge—taking only 50 to 100 iterations for an 18,000-variable system—and scaled at roughly O(n^1.5), slightly better than expected theoretical bounds. Benchmarks showed draped meshes calculating in roughly two to three seconds per frame and complex garments with thousands of nodes rendering in 8 to 38 seconds per frame, compared to tens of minutes per frame reported in earlier explicit systems. Furthermore, running time proved exceptionally robust against material stiffness, varying by less than 5% across a 10,000-fold increase in fabric bending resistance.

These findings indicate that production pipelines can simulate high-resolution, realistically folding clothing on animated characters at a fraction of previous computational costs and turnaround times. The approach removes the need to artificially reduce fabric stiffness to gain simulation stability, avoiding unnatural, rubbery visual artifacts. Organizations producing digital animation can leverage this implicit formulation to significantly reduce rendering overhead, accelerate iteration cycles for technical artists, and achieve higher fidelity garments without specialized hardware.

For practical deployment, graphics pipelines should implement this coupled implicit solver and modified conjugate gradient architecture when simulating stiff deformable surfaces. Dynamic step sizing based on stretch thresholds should be configured to preserve stability without manual tuning. Further development should address the main current limitations: while cloth-solid collisions are resolved exactly, cloth-cloth contacts still rely on penalty spring approximations, and static friction between contacting cloth surfaces remains an open challenge.

cloth simulation computational efficiency contracts Cloth Particle Simulation

Baraff et al (1998).pdf

Paper: Elastically deformable models, D. Terzopoulos et al. (1987). Introduces foundational physically based deformable models for graphics and animation that set up the explicit integration formulations the source paper aims to replace with implicit methods.

No sufficiently relevant recommendations were found.

Topics

cloth simulation computational efficiency contracts multiplier penalty function sparse linear systems numerical solution

Keywords

Cloth Particle Simulation Forces Equation Force Cloth Simulation Particles Step Large

1 Introduction
1.1 Specific Contributions
1.2 Previous Work
2 Simulation Overview
2.1 Notation and Geometry
2.2 Energy and Forces
2.3 Sparse Matrices
2.4 Constraints
3 Implicit Integration
4 Forces
4.1 Forces and Force Derivatives
4.2 Stretch Forces
4.3 Shear and Bend Forces
4.4 Additional Forces
4.5 Damping
5 Constraints
Reduced Coordinates
Penalty Methods
Lagrange Multipliers
5.1 Mass Modification
5.2 Implementation
5.3 The Modified Conjugate Gradient Method
5.4 Determining the Constraint Forces
6 Collisions
6.1 Constraint Initiation
6.2 Position Alteration
7 Adaptive Time Stepping
8 Results
9 Acknowledgments
References

Knowls

Knowl 1 — Modified Conjugate Gradient Method for Constrained Linear Systems
algorithm
To solve the large, sparse, symmetric linear system arising in implicitly integrated cloth dynamics while directly maintaining kinematic velocity constraints, a modified preconditioned conjugate gradient procedure (modified-pcg) is used. The solver enforces the invariant that for every particle $i$ , the velocity change $\Delta \mathbf{v}_i$ along constrained directions remains exactly equal to the target constraint velocity change $\mathbf{z}_i$ at every iteration, while the unconstrained components of the residual $\mathbf{r} = \mathbf{b} - \mathbf{A}\Delta \mathbf{v}$ are iteratively driven to zero.
procedure modified-pcg(A, b, P, z, filter, epsilon)
    Input: Symmetric positive definite matrix $A \in \mathbb{R}^{3n \times 3n}$ , right-hand side $b \in \mathbb{R}^{3n}$ , diagonal preconditioner $P \in \mathbb{R}^{3n \times 3n}$ , constraint vector $z \in \mathbb{R}^{3n}$ , directional projection operator filter, tolerance $\epsilon > 0$
    Output: Solution vector $\Delta v \in \mathbb{R}^{3n}$ exactly satisfying constrained components
    \Delta v = z
    \delta_0 = filter(b)^T * P * filter(b)
    r = filter(b - A * \Delta v)
    c = filter(P^{-1} * r)
    \delta_new = r^T * c
    while \delta_new > \epsilon^2 * \delta_0 do
        q = filter(A * c)
        \alpha = \delta_new / (c^T * q)
        \Delta v = \Delta v + \alpha * c
        r = r - \alpha * q
        s = P^{-1} * r
        \delta_old = \delta_new
        \delta_new = r^T * s
        c = filter(s + (\delta_new / \delta_old) * c)
    return \Delta v
The operator $\text{filter}(\mathbf{a})$ applies directional projection block-wise: $(\text{filter}(\mathbf{a}))_i = \mathbf{S}_i \mathbf{a}_i$ , where $\mathbf{S}_i \in \mathbb{R}^{3 \times 3}$ filters out components in prohibited directions for particle $i$ . The diagonal preconditioner $\mathbf{P}$ is defined by $P_{ii} = 1 / A_{ii}$ . Filtering the search direction $\mathbf{c}$ ensures that increments to $\Delta \mathbf{v}$ never alter the constrained components. The method converges in $O(n^{0.5})$ iterations for typical cloth meshes, with each iteration requiring $O(n)$ work for sparse matrix-vector multiplication.
Knowl 2 — Linearized Implicit Backward Euler Integration for Cloth Dynamics
equation
For a cloth system of $n$ particles with positions $\mathbf{x} \in \mathbb{R}^{3n}$ , velocities $\mathbf{v} = \dot{\mathbf{x}} \in \mathbb{R}^{3n}$ , diagonal mass matrix $\mathbf{M} \in \mathbb{R}^{3n \times 3n}$ , and net force $\mathbf{f}(\mathbf{x}, \mathbf{v}) \in \mathbb{R}^{3n}$ , the backward Euler step over a time step $h > 0$ from state $(\mathbf{x}_0, \mathbf{v}_0)$ with initial force $\mathbf{f}_0 = \mathbf{f}(\mathbf{x}_0, \mathbf{v}_0)$ determines the velocity change $\Delta \mathbf{v} = \mathbf{v}(t_0 + h) - \mathbf{v}_0$ via a first-order Taylor expansion of $\mathbf{f}$ :

$\left( \mathbf{M} - h \frac{\partial \mathbf{f}}{\partial \mathbf{v}} - h^2 \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \right) \Delta \mathbf{v} = h \left( \mathbf{f}_0 + h \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \mathbf{v}_0 \right)$

where $\frac{\partial \mathbf{f}}{\partial \mathbf{x}} \in \mathbb{R}^{3n \times 3n}$ is the stiffness matrix and $\frac{\partial \mathbf{f}}{\partial \mathbf{v}} \in \mathbb{R}^{3n \times 3n}$ is the damping Jacobian evaluated at $(\mathbf{x}_0, \mathbf{v}_0)$ . Once $\Delta \mathbf{v}$ is obtained, the particle positions are advanced as:

$\Delta \mathbf{x} = h(\mathbf{v}_0 + \Delta \mathbf{v})$

Left-multiplying by $\mathbf{M}$ yields a symmetric positive definite system matrix $\mathbf{A} = \mathbf{M} - h \frac{\partial \mathbf{f}}{\partial \mathbf{v}} - h^2 \frac{\partial \mathbf{f}}{\partial \mathbf{x}}$ , which enables the use of iterative conjugate gradient solvers on large, sparse, irregular meshes.
Knowl 3 — Condition-Based Internal Cloth Forces and Derivatives
model/method
Internal cloth forces are derived by formulating vector constraint conditions $\mathbf{C}(\mathbf{x}) \in \mathbb{R}^m$ that vanish when the material is in its rest state. The deformation energy associated with condition $\mathbf{C}$ is:

$E_C(\mathbf{x}) = \frac{k}{2} \mathbf{C}(\mathbf{x})^T \mathbf{C}(\mathbf{x})$

where $k > 0$ is a stiffness parameter. For each particle $i$ upon which $\mathbf{C}(\mathbf{x})$ depends, the resulting internal force $\mathbf{f}_i \in \mathbb{R}^3$ is:

$\mathbf{f}_i = -\frac{\partial E_C}{\partial \mathbf{x}_i} = -k \left( \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_i} \right)^T \mathbf{C}(\mathbf{x})$

where $\frac{\partial \mathbf{C}}{\partial \mathbf{x}_i} \in \mathbb{R}^{m \times 3}$ . The force derivative (stiffness matrix block) $\mathbf{K}_{ij} = \frac{\partial \mathbf{f}_i}{\partial \mathbf{x}_j} \in \mathbb{R}^{3 \times 3}$ for particle pair $(i, j)$ is:

$\mathbf{K}_{ij} = -k \left( \left( \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_i} \right)^T \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_j} + \sum_{l=1}^m \frac{\partial^2 C_l(\mathbf{x})}{\partial \mathbf{x}_i \partial \mathbf{x}_j} C_l(\mathbf{x}) \right)$

Because $\mathbf{K}_{ij} = -\frac{\partial^2 E_C}{\partial \mathbf{x}_i \partial \mathbf{x}_j} = \mathbf{K}_{ji}^T$ , the full stiffness matrix $\mathbf{K} = \frac{\partial \mathbf{f}}{\partial \mathbf{x}}$ is symmetric.
Knowl 4 — Continuous Stretch, Shear, and Bend Energy Conditions on Triangular Meshes
model/method
For a triangular cloth mesh where each particle $i$ has world coordinates $\mathbf{x}_i \in \mathbb{R}^3$ and planar reference coordinates $(u_i, v_i) \in \mathbb{R}^2$ , internal deformation forces are parameterized by three conditions:
1. Stretch Condition (per triangle): For a triangle with particles $i, j, k$ and reference area $a = \frac{1}{2}|(u_j - u_i)(v_k - v_i) - (u_k - u_i)(v_j - v_i)|$ , the spatial derivatives $\mathbf{w}_u = \frac{\partial \mathbf{w}}{\partial u}$ and $\mathbf{w}_v = \frac{\partial \mathbf{w}}{\partial v}$ of the piecewise linear mapping $\mathbf{w}(u, v)$ from plane coordinates to world space are computed via:
$\begin{pmatrix} \mathbf{w}_u & \mathbf{w}_v \end{pmatrix} = \begin{pmatrix} \mathbf{x}_j - \mathbf{x}_i & \mathbf{x}_k - \mathbf{x}_i \end{pmatrix} \begin{pmatrix} u_j - u_i & u_k - u_i \\ v_j - v_i & v_k - v_i \end{pmatrix}^{-1}$

The stretch condition vector is quadratic in energy and linear in spatial derivatives:

$\mathbf{C}_{\text{stretch}}(\mathbf{x}) = a \begin{pmatrix} \|\mathbf{w}_u(\mathbf{x})\| - b_u \\ \|\mathbf{w}_v(\mathbf{x})\| - b_v \end{pmatrix}$

where $b_u, b_v$ are target stretch ratios (set to 1 for rest, or altered to create anisotropic shrinkage, cuffs, or wrinkles).
1. Shear Condition (per triangle): Measures in-plane shearing:
$C_{\text{shear}}(\mathbf{x}) = a \,\mathbf{w}_u(\mathbf{x})^T \mathbf{w}_v(\mathbf{x})$
1. Bend Condition (per shared edge): For two adjacent triangles with unit normals $\mathbf{n}_1, \mathbf{n}_2 \in \mathbb{R}^3$ and common unit edge vector $\mathbf{e} \in \mathbb{R}^3$ , the dihedral angle $\theta$ satisfies $\sin\theta = (\mathbf{n}_1 \times \mathbf{n}_2) \cdot \mathbf{e}$ and $\cos\theta = \mathbf{n}_1 \cdot \mathbf{n}_2$ . The bend condition is $C_{\text{bend}}(\mathbf{x}) = \theta$ . For anisotropic bending with stiffnesses $k_u, k_v$ , edge stiffness is weighted by $\frac{k_u (\Delta u)^2 + k_v (\Delta v)^2}{(\Delta u)^2 + (\Delta v)^2}$ where $\Delta u = u_i - u_j$ and $\Delta v = v_i - v_j$ .
Knowl 5 — Condition-Based Damping Forces and Symmetrized Jacobians
model/method
To damp specific modes of deformation (stretch, shear, and bend) without penalizing rigid-body motions, damping forces are defined along the gradient of the condition function $\mathbf{C}(\mathbf{x}) \in \mathbb{R}^m$ . The damping force $\mathbf{d}_i \in \mathbb{R}^3$ acting on particle $i$ is:

$\mathbf{d}_i = -k_d \left( \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_i} \right)^T \dot{\mathbf{C}}(\mathbf{x})$

where $k_d > 0$ is the damping coefficient and $\dot{\mathbf{C}}(\mathbf{x}) = \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}} \mathbf{v} = \sum_j \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_j} \mathbf{v}_j$ .

The derivative of the damping force with respect to velocity is symmetric:

$\frac{\partial \mathbf{d}_i}{\partial \mathbf{v}_j} = -k_d \left( \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_i} \right)^T \frac{\partial \mathbf{C}(\mathbf{x})}{\partial \mathbf{x}_j}$

The position derivative $\frac{\partial \mathbf{d}_i}{\partial \mathbf{x}_j} = -k_d \left( \sum_{l=1}^m \frac{\partial^2 C_l}{\partial \mathbf{x}_i \partial \mathbf{x}_j} \dot{C}_l + \left(\frac{\partial \mathbf{C}}{\partial \mathbf{x}_i}\right)^T \frac{\partial \dot{\mathbf{C}}}{\partial \mathbf{x}_j} \right)$ contains an unsymmetric second term $\left(\frac{\partial \mathbf{C}}{\partial \mathbf{x}_i}\right)^T \left(\frac{\partial \dot{\mathbf{C}}}{\partial \mathbf{x}_j}\right)$ . Omitting this term yields the symmetric approximation $\frac{\partial \mathbf{d}_i}{\partial \mathbf{x}_j} \approx -k_d \sum_{l=1}^m \frac{\partial^2 C_l}{\partial \mathbf{x}_i \partial \mathbf{x}_j} \dot{C}_l$ , which preserves the symmetry of the global implicit system matrix without introducing instability.
Knowl 6 — Position Alteration for Collision Resolution in Implicit Integration
model/method
When a cloth particle collides with an obstacle or interpenetrates, moving the particle position after a step causes visual artifacts and local instabilities because neighboring particles are not alerted to the shift. To resolve penetrations instantaneously within an implicit time step, an explicit position correction offset $\mathbf{y} \in \mathbb{R}^{3n}$ is added to the kinematic update equation:

$\Delta \mathbf{x} = h(\mathbf{v}_0 + \Delta \mathbf{v}) + \mathbf{y}$

Propagating this modification through the first-order Taylor expansion of forces modifies the right-hand side of the symmetric linear system:

$\left( \mathbf{M} - h \frac{\partial \mathbf{f}}{\partial \mathbf{v}} - h^2 \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \right) \Delta \mathbf{v} = h \left( \mathbf{f}_0 + h \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \mathbf{v}_0 + \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \mathbf{y} \right)$

where $\mathbf{y}_i \in \mathbb{R}^3$ is non-zero only for particles being shifted. The term $\frac{\partial \mathbf{f}}{\partial \mathbf{x}} \mathbf{y}$ automatically communicates the displacement to adjacent particles via the force gradient, eliminating instability and visual jitter without requiring additional solver steps.
Knowl 7 — Directional Projection Matrices for Individual Particle Constraints
definition
Kinematic constraints on an individual cloth particle $i$ are represented by a $3 \times 3$ projection matrix $\mathbf{S}_i$ parameterized by its remaining degrees of freedom ( $\text{ndof}(i)$ ):

$\mathbf{S}_i = \begin{cases} \mathbf{I} & \text{if } \text{ndof}(i) = 3 \text{ (unconstrained)} \\ \mathbf{I} - \mathbf{p}_i \mathbf{p}_i^T & \text{if } \text{ndof}(i) = 2 \text{ (constrained along unit normal } \mathbf{p}_i) \\ \mathbf{I} - \mathbf{p}_i \mathbf{p}_i^T - \mathbf{q}_i \mathbf{q}_i^T & \text{if } \text{ndof}(i) = 1 \text{ (constrained along orthogonal unit vectors } \mathbf{p}_i, \mathbf{q}_i) \\ \mathbf{0} & \text{if } \text{ndof}(i) = 0 \text{ (completely fixed)} \end{cases}$

The global block-diagonal matrix $\mathbf{W} \in \mathbb{R}^{3n \times 3n}$ replaces the inverse mass matrix $\mathbf{M}^{-1}$ with diagonal blocks $\mathbf{W}_{ii} = \frac{1}{m_i} \mathbf{S}_i$ . For any 3D vector $\mathbf{a}_i$ , the operation $\mathbf{S}_i \mathbf{a}_i$ projects out components along prohibited acceleration directions.
Knowl 8 — Contact Force Extraction and Friction/Release Transitions
model/method
When solving the constrained system $\mathbf{A} \Delta \mathbf{v} = \mathbf{b}$ with the modified conjugate gradient method, the constraint force $\mathbf{e}_i \in \mathbb{R}^3$ exerted on particle $i$ is obtained from the unfiltered residual:

$\mathbf{e} = \mathbf{A} \Delta \mathbf{v} - \mathbf{b}$

For unconstrained particles, $\mathbf{e}_i \approx \mathbf{0}$ , while for constrained particles $\mathbf{e}_i$ equals the force necessary to enforce the prescribed velocity change $\mathbf{z}_i$ .

Contact constraints between cloth particles and solid surfaces use $\mathbf{e}_i$ to govern state transitions:
- Contact Release: When the normal component of $\mathbf{e}_i$ against the surface changes from repulsive (pushing away from the surface) to attractive (pulling toward the surface), the contact constraint is removed.
- Friction and Sliding: If a particle is locked tangentially on a surface ( $ext{ndof}(i) = 0$ ), the tangential force magnitude is compared against the normal force. If the ratio exceeds the static friction coefficient, the constraint is switched to a sliding contact ( $ext{ndof}(i) = 2$ ), and a dissipative tangential damping force proportional to the normal force is applied opposite the sliding direction.
Knowl 9 — Stretch-Based Adaptive Time Stepping for Cloth Simulation
algorithm
Adaptive time-step control prevents numerical divergence by monitoring in-plane stretch metrics rather than integration truncation error, exploiting the fact that cloth instability is caused by the stiff stretch terms.
procedure adaptive-step(x0, v0, h, h_max)
    Input: Current state (x0, v0), trial step size h, maximum allowable step size h_max
    Output: Updated state (x1, v1) and next step size h_next
    while true do
        Solve implicit backward Euler linear system with step size h to obtain \Delta v
        \Delta x = h * (v0 + \Delta v)
        x_candidate = x0 + \Delta x
        is_stable = true
        for each triangle in mesh do
            Compute derivatives w_u, w_v for x_candidate
            if ||w_u|| or ||w_v|| changes drastically relative to rest stretch then
                is_stable = false
                break
        if is_stable then
            x1 = x_candidate
            v1 = v0 + \Delta v
            if consecutive successes >= 2 then
                h_next = min(h_max, 2 * h)
            else
                h_next = h
            return (x1, v1), h_next
        else
            h = h / 2
            Increment failure counter (retry wait limit up to 40 steps)
If any triangle exhibits a drastic stretch change in $u$ or $v$ , the proposed step is rejected, $h$ is halved, and the step is recomputed.

Knowl 10 — Performance and Computational Breakdown of Implicit Cloth Simulation

data/table

Simulations of diverse cloth benchmarks and animated garments were evaluated on an SGI Octane R10000 195 MHz processor to measure frame execution times, step sizes, and task breakdowns.

Figure / Garment	Cloth Verts / Tris	Solid Verts / Tris	Time/Frame (s)	Step Min/Max (ms)	Frames / Steps	EVAL (%)	CG (%)	C/C (%)	C/S (%)
1 (Draping on cylinder)	2,602 / 4,942	322 / 640	2.23	16.5 / 33	75 / 80	25.7	50.4	18.3	1.4
2 (Fixed sheet)	2,602 / 4,942	322 / 640	3.06	16.5 / 33	75 / 80	17.9	63.6	15.3	0.2
3 (Shirt, twisting figure)	6,450 / 12,654	9,941 / 18,110	7.32	16.5 / 33	50 / 52	18.9	37.9	30.9	2.6
4 (Shirt, walking man)	6,450 / 12,654	9,941 / 18,110	14.5	2.5 / 20	430 / 748	16.7	29.9	46.1	2.2
4 (Pants, walking man)	8,757 / 17,352	9,941 / 18,110	38.5	0.625 / 20	430 / 1214	16.4	35.7	42.5	1.7
5 (Short skirt, dancer)	2,153 / 4,020	7,630 / 14,008	3.68	5 / 20	393 / 715	18.1	30.0	44.5	1.5
5 (Blouse, dancer)	5,108 / 10,016	7,630 / 14,008	16.7	5 / 20	393 / 701	11.2	26.0	57.7	1.3
6 (Long skirt, dancer)	4,530 / 8,844	7,630 / 14,008	10.2	10 / 20	393 / 670	20.1	36.8	29.7	2.6
6 (Blouse, dancer)	5,188 / 10,194	7,630 / 14,008	16.6	1.25 / 20	393 / 753	13.2	30.9	50.2	1.4

The total CPU time is categorized into four main components:

EVAL: Evaluating internal forces and assembling the linear system ( $11.2\% - 25.7\%$ ).
CG: Solving the linear system with modified PCG ( $26.0\% - 63.6\%$ ).
C/C: Cloth-cloth collision detection and penalty spring application ( $15.3\% - 57.7\%$ ).
C/S: Cloth-solid collision detection ( $0.2\% - 2.6\%$ ).

Unaccounted overhead (geometry transformations, memory allocation) accounts for roughly $5\%$ . The simulator averages 2 to 3 steps per animation frame at 30 Hz.

Knowl 11 — Runtime Insensitivity to Material Stiffness and Empirical O(n^1.5) Scaling
empirical result
The implicit integration and modified conjugate gradient approach demonstrates two scaling properties in cloth simulation:
- Stiffness Insensitivity: Scaling the bending stiffness across four orders of magnitude (multiplying baseline stiffness by factors of $0.1$ , $1.0$ , $10$ , $100$ , and $1{,}000$ , representing a total range of $10{,}000\times$ ) in a 2,602-node draping test produced a running time variation of under $5\%$ .
- Spatial Resolution Scaling: In benchmark draping tests across varying mesh resolutions on an SGI Octane R10000 195 MHz processor, running times scaled slightly better than $O(n^{1.5})$ $O (n^{1.5})$ with respect to particle count $n$ $n$ :
  - 500 particles: $0.23\text{ s/frame}$
  - 899 particles: $0.46\text{ s/frame}$
  - 2,602 particles: $2.23\text{ s/frame}$
  - 7,359 particles: $10.3\text{ s/frame}$
This $O(n^{1.5})$ scaling matches the theoretical convergence rate of preconditioned conjugate gradients on two-dimensional surface discretizations.

Coverage note — Standard bounding box hierarchy collision detection algorithms, interactive user-controlled mouse forces, and aerodynamic drag were omitted as they follow standard formulations.

References

1.D. Baraff. Dynamic Simulation of Non-penetrating Rigid Bodies. PhD thesis, Cornell University, May 1992.
2.D. Baraff. Fast contact force computation for nonpenetrating rigid bodies. Computer Graphics (Proc. SIGGRAPH), 28:23–34, 1994.
3.D.E. Breen, D.H. House, and M.J. Wozny. Predicting the drape of woven cloth using interacting particles. Computer Graphics (Proc. SIGGRAPH), pages 365–372, 1994.
4.M. Carignan, Y. Yang, N. Magenenat-Thalmann, and D. Thalmann. Dressing animated synthetic actors with complex deformable clothes. Computer Graphics (Proc. SIGGRAPH), pages 99–104, 1992.
5.B. Eberhardt, A. Weber, and W. Strasser. A fast, flexible, particle-system model for cloth draping. IEEE Computer Graphics and Applications, 16:52–59, 1996.
6.G. Golub and C. Van Loan. Matrix Computations. John Hopkins University Press, 1983.
7.M. Kass. An Introduction To Physically Based Modeling, chapter Introduction to Continuum Dynamics for Computer Graphics. SIGGRAPH Course Notes, ACM SIGGRAPH, 1995.
8.M. Kass and G. Miller. Rapid, stable fluid dynamics for computer graphics. Computer Graphics (Proc. SIGGRAPH), pages 49–58, 1990.
9.H.N. Ng and R.L. Grimsdale. Computer graphics techniques for modeling cloth. IEEE Computer Graphics and Applications, 16:28–41, 1996.
10.H. Okabe, H. Imaoka, T. Tomiha, and H. Niwaya. Three dimensional apparel cad system. Computer Graphics (Proc. SIGGRAPH), pages 105–110, 1992.
11.J.C. Platt and A.H. Barr. Constraint methods for flexible models. In Computer Graphics (Proc. SIGGRAPH), volume 22, pages 279–288. ACM, July 1988.
12.W.H. Press, B.P. Flannery, S.A. Teukolsky, and W.T. Vetterling. Numerical Recipes. Cambridge University Press, 1986.
13.X. Provot. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Graphics Interface, pages 147–155, 1995.
14.J. Shewchuk. An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMU-CS-TR-94-125, Carnegie Mellon University, 1994. (See also http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.ps.).
15.D. Terzopoulos and K. Fleischer. Deformable models. Visual Computer, 4:306–331, 1988.
16.D. Terzopoulos and K. Fleischer. Modeling inelastic deformation: Viscoelasticity, plasticity, fracture. In Computer Graphics (Proc. SIGGRAPH), volume 22, pages 269–278. ACM, August 1988.
17.D. Terzopoulos, J.C. Platt, and A.H. Barr. Elastically deformable models. Computer Graphics (Proc. SIGGRAPH), 21:205–214, 1987.
18.D. Terzopoulos and H. Qin. Dynamics nurbs with geometric constraints for interactive sculpting. ACM Transactions on Graphics, 13:103–136, 1994.
19.X. Tu. Artificial Animals for Computer Animation: Biomechanics, Locomotion, Perception and Behavior. PhD thesis, University of Toronto, May 1996.
20.P. Volino, M. Courchesne, and N. Magnenat Thalmann. Versatile and efficient techniques for simulating cloth and other deformable objects. Computer Graphics (Proc. SIGGRAPH), pages 137–144, 1995.
21.P. Volino, N. Magnenat Thalmann, S. Jianhua, and D. Thalmann. An evolving system for simulating clothes on virtual actors. IEEE Computer Graphics and Applications, 16:42–51, 1996.

Citation

MLA

Baraff, D., and A. Witkin. “Large Steps in Cloth Simulation”. Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '98, 1998, pp. 43–54, https://doi.org/10.1145/280814.280821.

APA

Baraff, D., & Witkin, A. (1998). Large steps in cloth simulation. Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '98, 43–54. https://doi.org/10.1145/280814.280821

Chicago

Baraff, D., and A. Witkin. 1998. “Large Steps in Cloth Simulation”. Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '98, 43–54. https://doi.org/10.1145/280814.280821.

Harvard

Baraff, D. and Witkin, A. (1998) “Large steps in cloth simulation”, Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98. ACM Press, pp. 43–54. Available at: https://doi.org/10.1145/280814.280821.

Vancouver

1. Baraff D, Witkin A (1998) Large steps in cloth simulation. In: Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98. ACM Press, pp 43–54

BibTeX

@inproceedings{Baraff_1998, series={SIGGRAPH ’98}, title={Large steps in cloth simulation}, url={http://dx.doi.org/10.1145/280814.280821}, DOI={10.1145/280814.280821}, booktitle={Proceedings of the 25th annual conference on Computer graphics and interactive techniques  - SIGGRAPH ’98}, publisher={ACM Press}, author={Baraff, David and Witkin, Andrew}, year={1998}, pages={43–54}, collection={SIGGRAPH ’98} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Large steps in cloth simulation

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Modified Conjugate Gradient Method for Constrained Linear Systems

Knowl 2 — Linearized Implicit Backward Euler Integration for Cloth Dynamics

Knowl 3 — Condition-Based Internal Cloth Forces and Derivatives

Knowl 4 — Continuous Stretch, Shear, and Bend Energy Conditions on Triangular Meshes

Knowl 5 — Condition-Based Damping Forces and Symmetrized Jacobians

Knowl 6 — Position Alteration for Collision Resolution in Implicit Integration

Knowl 7 — Directional Projection Matrices for Individual Particle Constraints

Knowl 8 — Contact Force Extraction and Friction/Release Transitions

Knowl 9 — Stretch-Based Adaptive Time Stepping for Cloth Simulation

Knowl 10 — Performance and Computational Breakdown of Implicit Cloth Simulation

Knowl 11 — Runtime Insensitivity to Material Stiffness and Empirical O(n^1.5) Scaling

References

Citation

BibTeX

Access the Paper