Geometry Processing

As-Rigid-As-Possible
Surface Modeling

An interactive surface editing tool that preserves local shape detail by optimizing per-vertex rigid transformations, implemented from scratch in C++ with Eigen.

C++ / EigenTwo weeksGeometruy Processing
Interactive ARAP deformation of a character mesh
Dragging a single handle: the surface bends naturally while local detail stays intact.

The problem

When deforming a 3D surface, users expect the mesh to behave like a physical material, bending and twisting smoothly without shearing or distorting local features. Naive Laplacian-based editing fails at this: large translations cause detail loss and unnatural stretching because there is no rotation field to propagate. This project implements the ARAP (As-Rigid-As-Possible) method of Sorkine and Alexa (SGP 2007) to fix exactly that.

But how exactly do we preserve local features? By making every small patch of the surface move as rigidly as it can. To make that precise, the mesh is covered in overlapping cells: the cell \(C_i\) for a vertex \(\mathbf{p}_i\) is its one-ring neighborhood: \(\mathbf{p}_i\), its directly connected neighbors \(N(i)\), and the edges \(\mathbf{e}_{ij} = \mathbf{p}_i - \mathbf{p}_j\) between them.

The cell Cᵢ: the one-ring around pᵢ
pi pj eij Ci every vertex owns one cell; neighboring cells overlap

When the user deforms the mesh, vertices are displaced to new positions \(\mathbf{p}'_i\), \(\mathbf{p}'_j\), and each edge becomes \(\mathbf{e}'_{ij}\). Let \(R_i\) be a rotation carrying the cell's rest edges onto its deformed ones. If the cell moved perfectly rigidly, a single rotation would explain every edge simultaneously:

Perfect rigidity
$$\mathbf{p}'_i - \mathbf{p}'_j = R_i(\mathbf{p}_i - \mathbf{p}_j), \qquad \forall j \in N(i)$$

Real edits bend and stretch, so no such rotation exists. The equation can't hold for every neighbor at once. Instead, we ask for the rotation that comes closest: the one minimizing the cell's rigidity energy,

Local rigidity energy of one cell
$$E(C_i, C'_i) = \sum_{j\in N(i)} w_{ij} \left\lVert(\mathbf{p}'_i - \mathbf{p}'_j) - R_i(\mathbf{p}_i - \mathbf{p}_j)\right\rVert^2$$

This is the failure of rigidity for one cell: each term measures how far a deformed edge is from being a pure rotation of its rest edge. Summing it over every vertex gives the total energy the method minimizes. Deformations that preserve local features are exactly the ones that keep every cell's term small:

Total ARAP energy
$$E(S') = \sum_i \sum_{j\in N(i)} w_{ij} \left\lVert(\mathbf{p}'_i - \mathbf{p}'_j) - R_i(\mathbf{p}_i - \mathbf{p}_j)\right\rVert^2$$

Solving it: alternate between rotations and positions

The unknowns come in pairs: the positions \(\mathbf{p}'\) depend on the rotations \(R_i\), and the best rotations depend on the positions. The classic escape is alternating minimization: freeze one set, solve for the other, and repeat.

Setup

Store the rest configuration

Build one-ring neighborhoods, compute cotangent weights from the original geometry, assemble the sparse Laplacian \(L\), and factor it once, since it never changes.

Constrain

User moves the handles

Anchored and dragged vertices take their user-given positions; everything else starts from wherever it currently is. This is the initial guess for \(\mathbf{p}'\).

Local step

Best rotation per cell

With positions frozen, find the \(R_i\) minimizing each cell's rigidity energy: a 3×3 covariance matrix and a small SVD per vertex.

Global step

Solve for positions

With rotations frozen, the optimal positions satisfy the sparse linear system \(L\mathbf{p}' = \mathbf{b}\). Repeat local/global 2-5 times, and each pass provably never increases the energy.

Cotangent weights
$$w_{ij} = \frac{1}{2}(\cot\alpha_{ij} + \cot\beta_{ij})$$

\(\alpha_{ij}\) and \(\beta_{ij}\) are the two angles opposite edge \((i, j)\). These weights account for triangle shapes, so the result doesn't depend on how the surface happens to be triangulated. They're computed once from the rest pose, so the energy always measures rigidity relative to the original geometry.

Assembling the Laplacian
$$L_{ij} = \begin{cases} -w_{ij} & j \in N(i) \\[2pt] \displaystyle\sum_{n\in N(i)} w_{in} & j = i \\[2pt] 0 & \text{otherwise} \end{cases} \qquad\Longrightarrow\qquad L\,\mathbf{p}' = \mathbf{b}$$

Each edge writes a symmetric pair of off-diagonal entries \(L_{ij} = L_{ji} = -w_{ij}\), and each diagonal entry collects its row's weights. Because cells are one-rings, a vertex only touches its immediate neighbors, so nearly every entry of \(L\) is zero, which is what makes the system fast to solve. When the user anchors a vertex, its row is replaced with the identity row and its known position moves into \(\mathbf{b}\): the anchor drops out of the optimization and stays pinned.

Local step: the best rotation from the covariance matrix
$$S_i = \sum_j w_{ij}\,\mathbf{e}_{ij}\mathbf{e}_{ij}^{\prime T} = U_i\Sigma_iV_i^T \quad\Longrightarrow\quad R_i = V_iU_i^T$$

The best rotation for each cell falls out of the SVD of a small 3×3 covariance matrix \(S_i\), with a sign check on \(\det(V_iU_i^T)\) to rule out reflections. Rotation estimation uses Eigen's JacobiSVD per vertex.

Anatomy of the covariance matrix S₁
Ri rotates every rest edge onto its deformed twin pi eij Rest cell: edges eij p′i e′ij residual → energy Deformed cell: e′ij vs. ghost Rieij for each neighbor j × = eij e′ijT 3×3 Σj wij Si covariance of the cell SVD: Si = UΣVT Ri = VUT

Reading the diagram: each neighbor pairs a rest edge \(\mathbf{e}_{ij}\) (left) with its deformed counterpart \(\mathbf{e}'_{ij}\) (right, one pair highlighted). Their outer product is a 3×3 matrix that "votes" for the transform carrying one onto the other; the cotangent-weighted sum of all votes is the covariance \(S_i\). Its SVD strips away stretch and shear, leaving the pure rotation \(R_i\). The dashed ghost on the right shows the rest edges under \(R_i\) alone, and the small dotted gaps between ghost and actual edges are the non-rigid residuals the ARAP energy penalizes.

Global step: the right-hand side
$$\mathbf{b}_i = \sum_{j\in N(i)} \frac{w_{ij}}{2}\,(R_i + R_j)(\mathbf{p}_i - \mathbf{p}_j)$$

Setting \(\partial E/\partial \mathbf{p}' = 0\) with the rotations held fixed produces the Laplacian on the left and this vector on the right: each rest edge, rotated by the average of the two rotations that claim it (every edge belongs to two overlapping cells). The prefactored SimplicialLDLT Cholesky solve then recovers all three coordinate columns of \(\mathbf{p}'\) by back-substitution, with no refactoring ever, which is what keeps dragging interactive.

Key properties

Detail preservation

Local rotations capture bending and twisting, preventing the detail washout that plagues linear methods under large deformations.

Edge length fidelity

The optimization naturally resists stretching, so relative edge length error stays very low unless constraints force it.

No rig required

Physically plausible deformation from positional constraints alone, with no skeleton, weights, or setup needed.

C++EigenSimplicialLDLTJacobiSVDCotangent LaplacianSparse Cholesky