Blog XPBD Cloth with WebGPU

XPBD Cloth with WebGPU

12 Sept 2026

§ Demo

Controls: Space to pause, S to toggle sphere movement, R to reset.
Click and drag to rotate; hold shift to pan, alt to zoom.

A quick weekend project for me to learn WebGPU. This was inspired by a homework assignment in CSCE 451 — Computer Animation at Texas A&M taught by Dr. Shinjiro Sueda.

§ Methodology

Fig. 1: A cloth can be represented in this framework using discrete particles connected via springs. In our case, we have springs that connect to their horizontal, vertical, and diagonal neighbours Additionally, there are springs that skip across or vertically, these are called "bending" springs.

If we have $NM$ particles assembled in a $N \times M$ grid that are connected using the scheme in Fig. 1, then we expect to have $6NM-5(N+M)+2 \in \mathcal{O}(NM)$ constraints that we need to solve. (Specifically, we have $N(M-1) + M(N-1)$ horizontal and vertical springs, $2(N-1)(M-1)$ diagonal springs, $N(M-2) + M(N-2)$ bending springs.)

There are multiple ways we can solve this system of constraints. One way is to set up a linear system $A\dot{\mathbf{x}} = \mathbf{b}$ (see my notes from when I took this course in 2022) and using some solver to find the updated velocity $\dot{\mathbf{x}},$ however, this is slow with solvers like LDLT taking at worst $\mathcal{O}(n^3)$ – typically $n^2$ – time with $n \in \mathcal{O}(NM)$ . Another way is to use XPBD as described in Alg. 1 below, from which we can easily observe that it takes $\mathcal{O}(NM)$ time.

XPBD

# Input:
# - Simulation timestep $h$ , and gravity $\mathbf{g}.$
# - Particles with position $\mathbf{p}_i$ , predicted position $\mathbf{x}_i$ , velocity $\mathbf{v}_i$ , mass $\mathbf{m}_i > 0$ , and damping coefficient $d_i.$
# - Constraints (springs) which connect particles $j$ and $k$ , a rest length $L_i$ , compliance (or reciprocal of spring constant) $\alpha_i$ , the accumulated Lagrange multiplier $\lambda_i$ .
# Integrate
for all particles $i$ $i$ do
- $\bm{f}_i$ $\leftarrow$ $m_i \mathbf{g} - d_i \mathbf{v}_i$ # Sum forces acting on particle $i$ (gravity + damping)
- $\bm{v}_i$ $\leftarrow$ $\bm{v}_i + hm_i^{-1}\mathbf{f}_i$ # Integrate force
- $\bm{p}_i$ $\leftarrow$ $\mathbf{x}_i$
- $\bm{x}_i$ $\leftarrow$ $\bm{x}_i + h\mathbf{v}_i$ # Integrate velocity
# Solve Constraints
for all spring constraints $i$ $i$ do
- $\lambda_i$ $\leftarrow$ 0
for $\mathrm{pass} \in \{0, \dots, N\}$ $pass \in {0, \dots, N}$ do
- for all spring constraints $i$ $i$ connecting particles $j$ $j$ and $k$ $k$ do
  - # Compute Constraint
  - $\Delta \mathbf{x}_i$ $\leftarrow$ $\mathbf{x}_j - \mathbf{x}_k$
  - $C_i$ $\leftarrow$ $\|\Delta \mathbf{x}_i\| - L_i$
  - $\nabla C_i$ $\leftarrow$ $\frac{\Delta\mathbf{x}_i}{\|\Delta\mathbf{x}_i\|}$
  - $\tilde{\alpha}$ $\leftarrow$ $\alpha h^{-2}$
  - # Compute Lagrange multiplier
  - $\Delta\lambda_i$ $\leftarrow$ $-(C_i + \lambda_i\tilde{\alpha})$ / $(m_j^{-1} + m_k^{-1} + \tilde{\alpha})$
  - $\lambda_i$ $\leftarrow$ $\lambda_i + \Delta\lambda_i$
  - # Apply accumulated impulse
  - $\mathbf{x}_j$ $\leftarrow$ $\mathbf{x}_j - \lambda_i m_j^{-1}\nabla C_i$
  - $\mathbf{x}_k$ $\leftarrow$ $\mathbf{x}_k + \lambda_i m_k^{-1}\nabla C_i$
# Update
for all particles $i$ $i$ do
- $\mathbf{v}_i$ $\leftarrow$ $h^{-1}(\mathbf{x}_i - \mathbf{p}_i)$

The loops involving particles are trivially parallelizable, as the integration and update steps only depend on the properties of the current particle.

Special consideration needs to be taken for solving the constraints, because XPBD uses the Gauss-Seidel method which immediately uses the values in each iteration. This is an issue because if we naïvely try to solve all the constraints in parallel then we will have resource contention due to conflicting reads and writes to a particle's predicted position.

One way to solve this is to use graph coloring; we can construct a conflict graph using each constraint as a vertex in the graph and constraints which affect the same particle are connected via an edge.

Because this cloth does not change in topology, we can do greedy graph coloring when we construct the constraints. For each vertex, we maintain a set of colors used by the constraints connected to it. Then, whenever we add a new constraint we take the union of the color sets of each particle connected to it, and we assign the constraint the first unused color. (For the graphs generated using springs as defined in Fig. 1, this greedy coloring finds a $\Delta - 1$ coloring where $\Delta = 12$ for $N, M \geq 5.$ )

Then it's a simple modification to the constraint solver loop in the XPBD algorithm:

# Solve Constraints
for all spring constraints $i$ $i$ do
- $\lambda_i$ $\leftarrow$ 0
- $\gamma_i$ $\leftarrow$ $\texttt{GraphColor(i)}$
for $\mathrm{pass} \in \{0, \dots, N\}$ $pass \in {0, \dots, N}$ do
- for all graph colors $\gamma$ $γ$ do
  - for all spring constraints $i$ $i$ connecting particles $j$ $j$ and $k$ $k$ do
    - if $\gamma_i$ $γ_{i}$ <> $\gamma$ $γ$ then
      - continue
    - # Otherwise, solve constraints as described in Alg. 1

Now, all of the loops in XPBD can be trivially written with compute shaders. The details behind the WebGPU implementation and WGSL shaders aren't particularly interesting; it is pretty straight-forward with setting up the relevant buffers, bindings, and pipelines.