Spring forces and ARAP

This is a post comparing two techniques for mesh deformation: spring forces, and ARAP. I've written about as-rigid-as-possible deformation before, but I haven't written much about springs before. The spring forces solver run on an OpenGL Compute shader, while the ARAP solver runs on the CPU using Eigen/LibIGL.

In this post on attachment and rigidity, I brought up some artifacts that can occur when deforming a mesh using a skeleton. Here's an example:

For the record: The mesh I'm using has 5634 vertices, 11264 faces, and 17 bones. The plus-sign shape makes it very useful for deformation studies.

Similar artifacts happen with LBS and DQS:

The skinning method's rigidity is causing that drastic stretch artifact. In the last post, I also mentioned a few things I might try to remove the artifact. Let's start with ARAP. I'm using LibIGL's implementation with default parameters: Young's modulus is set to 1, and the maximum iteration count is 100.

ARAP has a preprocess phase for the selected boundary vertices (highlighted yellow). Any time the selected set changes, the preprocess is reprocessed. The solver runs separately. For the deformation above, compute time was ~400 ms, and solver time was 1100 ms.

Now let's look at the same kind of deformation, but used with spring forces. The techniques are rather different, but I'll use the same cap of 100 iterations. Note: ARAP runs and solves everything in one pass. The spring forces can run like this too, or I can set it to run one iteration per frame to show the change over time. I'll show both below.

There's no preprocess phase for the spring force solver. If I'm allowing the solver to run until complete, then the total compute time is under 5 ms. When I restrict the solver to running once per frame, the total compute time is closer to 12 ms. The additional time comes from frame-to-frame overhead - mostly updating and binding shader storage buffers. Even so, it's 12 ms compared to ARAP's total of 1500 ms: around 125x speedup.

So, the performance improvement is nice, and the runtime makes it almost suitable for real-time use. However, the techniques are quite different. ARAP is an energy minimization problem solved with a sparse linear system. It depends on the mesh's adjacency matrix and edge lengths at bind.

I've started by creating springs out of every mesh edge. Let's bust out Hooke's Law:

$$
\begin{equation}
F = -kx
\end{equation}
\label{eq:hookeslaw}
$$

where $F$ is the spring's force, $k$ is the spring constant that represents the spring's stiffness, and $x$ is the spring's displacement from rest position. The displacement's sign determines the force direction, and at 0 displacement, the spring exerts no force.

We can also compute the potential energy stored in a spring:

$$
\begin{equation}
U = \frac{1}{2}kx^2
\end{equation}
\label{eq:springpe}
$$

How does this relate to our mesh? If the mesh is a set of vertices and edges $M=(V,E)$, then we can compute the energy of any edge given a deformation $M'=(V',E)$:

$$
\begin{equation}
U(i,j) = \frac{1}{2}k (||V'(i)-V'(j)||-||(V(i)-V(j)||)^2
\end{equation}
\label{eq:edgepe}
$$

And the total potential energy in the mesh deformation:

$$
\begin{equation}
E(M') = \sum_{i,j \in E} U(i,j)
\end{equation}
\label{eq:meshenergy}
$$

Now things can get interesting. The edge's energy is a quadratic function of the displacement. The mesh's energy is a sum over the edge energies. A good way to reduce the mesh's energy is to redistribute large displacements across many adjacent edges. Because of that square power, it ends up being better to have many edges with a little displacement than to have only a few edges with large displacements.