11.5 Shape-preserving warping⧉
You have a 2-D shape, such as a cartoon arm, a fish, a letterform, or a triangulated photo cut-out, and a couple of handles: vertices the user pins or drags. The job from Chapter 11.1, Warping was to turn that sparse motion into a dense warp of the whole shape, and the tools there did it by interpolating positions: least-squares-fit an affine or a thin-plate spline through the moved handles, evaluate it everywhere. Drag a handle a little and it works fine. Drag it far, say by swinging the wrist of the arm up over the shoulder, and the result betrays the method. The arm does not bend like an arm; it shears into a parallelogram, stretches thin, and the silhouette caves in (Figure 11.5.1, left). Nothing is mathematically wrong: the interpolant did exactly what you asked, finding the smoothest field consistent with the handles. The trouble is that smoothest field consistent with the handles is not what you wanted. You wanted the field that deforms least like a stretch and most like a rotation, because real limbs swing, they do not telescope.
Plain interpolation has no notion of rigidity. It treats a $2\times$ stretch and a $45°$ rotation as equally "smooth" ways to move a region. Shape-preserving deformation adds a regularizer that breaks the tie: each small neighborhood of the shape should transform as close to a rotation + translation (a rigid motion) as possible. Rotation is free of charge, but stretch and shear cost energy. Minimize that and a dragged handle propagates as bending, not distortion. The chapter turns on a rigidity prior: of all the ways to satisfy the handles, prefer the one in which the local shape is preserved.
A free-form warp that only interpolates handle positions will happily shear, stretch, and collapse a shape, because position-interpolation has no opinion about how a region deforms, only about where its anchors land. To make a deformation look physical you add a regularizer that measures, at every point, how far the local transformation is from a rigid motion (a rotation + translation) and minimizes it. Rotation is left free (a limb may swing any amount); only the stretch/shear part is charged. The recurring move (fit the constraints, but regularize toward a prior about the world) is the same one behind Poisson editing (regularize toward a gradient field), content-aware retargeting (regularize toward leaving salient regions rigid), and morphable models (regularize toward a learned shape basis). Here the prior is the most generic physical one there is: things rotate freely but resist stretching.
11.5.1 Why plain interpolation shears: the rigidity gap⧉
Recall the free-form warp of Chapter 11.1, Warping. Sparse handles $\mathbf{p}_j \mapsto \mathbf{p}'_j$ define a deformation $f$ by minimizing a smoothness energy (least-squares affine, or the thin-plate-spline bending energy $\int \|\nabla^2 f\|^2$) subject to $f(\mathbf{p}_j)=\mathbf{p}'_j$. The minimizer is the smoothest map through the constraints. And "smooth" here means low second derivative: it dislikes sharp changes in the field, but it is perfectly content with a uniform stretch or a uniform shear, because those have zero second derivative everywhere. So when one handle is dragged far from another, the cheapest smooth way to connect them is often a big affine shear of the region between. That is exactly the unnatural squashing you see.
The diagnosis points straight at the cure. The local behavior of a warp at a point is captured by its Jacobian $J=\partial f/\partial \mathbf{x}$, a little $2\times2$ matrix. Polar-decompose it, $J = R\,S$, into a rotation $R$ and a symmetric stretch $S$. A rigid motion has $S=I$ (no stretch, no shear); anything else has $S \neq I$. Plain interpolation never looks at $S$. Shape-preserving warping makes $\|S - I\|^2$, the deviation of the local transformation from a pure rotation, the thing you pay for, summed over the shape. Rotation $R$ is whatever it needs to be and is never penalized. This is the rigidity gap that the rest of the chapter closes, two ways: a direct nonlinear solve (ARAP), and a weighting scheme that decides how handles blend (skinning / BBW).
The same rigidity prior drives moving-least-squares (MLS) image deformation, the closed-form cousin of ARAP that powers handle-based photo warping: for each output point, fit the best rigid (or similarity) transform of the nearby handles and apply it, so a dragged handle bends the picture instead of shearing it. On a real photograph the effect is immediate (Figure 11.5.3), and overlaying the deformation on a regular grid makes the underlying warp field legible (Figure 11.5.4).
11.5.2 As-rigid-as-possible (ARAP) manipulation⧉
The cleanest realization of the rigidity prior is as-rigid-as-possible deformation, introduced for interactive 2-D shape manipulation by Igarashi, Moscovich and Hughes (2005) and developed into the standard surface-editing tool by Sorkine and Alexa (2007). Triangulate the shape (or take its mesh). Each vertex $i$ has a rest position $\mathbf{p}_i$ and an unknown deformed position $\mathbf{p}'_i$; the handles fix some of the $\mathbf{p}'_i$. Around each vertex (or each triangle) sits a small cell: the vertex and its one-ring of neighbors. The ARAP idea: a deformation is good if, cell by cell, the deformed cell looks like the rest cell after a single rigid rotation $R_i$. Concretely, the energy sums over cells the squared failure of each edge to be just a rotation of its rest self,
with $R_i$ constrained to be a pure rotation. The bracket is the key: it does not ask the deformed edge to equal the rest edge (that would forbid all motion), only to equal a rotation of it. Pure rotation of a cell costs zero; stretch and shear are precisely what the squared norm charges. That is $\|S-I\|^2$ from the previous section, discretized onto edges.
Minimizing $E$ jointly over the positions $\mathbf{p}'$ and the rotations $\{R_i\}$ is nonlinear (rotations live on a curved set), but it splits into two easy halves that you alternate, a textbook block-coordinate descent:
- Local step (rotations). Hold the positions $\mathbf{p}'$ fixed. Each cell's best rotation $R_i$ is found independently and in closed form: form the cross-covariance between rest edges and deformed edges, take its SVD, and read off the rotation (the orthogonal Procrustes / Kabsch solution). Per cell, a $2\times2$ SVD, which is trivial and parallel.
- Global step (positions). Hold the rotations $\{R_i\}$ fixed. Now $E$ is quadratic in $\mathbf{p}'$, so its minimizer is a single sparse linear solve: a Poisson-like system $L\,\mathbf{p}' = \mathbf{b}$ whose left side $L$ is the (cotangent-weighted) Laplacian of the mesh and whose right side $\mathbf{b}$ packs the rotated rest edges. With fixed rest geometry, weights and constrained vertex set, the constrained matrix can be factored once and reused across global steps. Changing that structure may require a new factorization. That is what makes ARAP run interactively.
Exact alternating minimization decreases the stated energy, but need not find its global minimum. Warm starts often help interactive editing; iteration count depends on the deformation and stopping criterion. Neither ARAP nor local rigid MLS guarantees an injective warp, absence of self-intersection, or preserved areas. Check those separately when required.
In the local SVD step, enforce determinant +1 so the fitted orthogonal map is a rotation rather than a reflection. State the discretization and weight assumptions: nonnegative edge weights make the displayed sum directly a weighted least-squares energy.
11.5.3 Linear blend skinning and why the weights decide everything⧉
ARAP solves a system per drag. The other great family avoids the solve entirely and instead precomputes how each handle's motion spreads, then at runtime just blends, the approach behind real-time character animation. This is linear blend skinning (LBS, also "skeletal subspace deformation"). Attach a few handles to the shape (skeleton bones, a cage, or scattered control points), each with its own transformation $T_j$ (a rotation+translation the user or animator drives). Give every point $\mathbf{x}$ of the shape a set of weights $w_j(\mathbf{x})$ saying how much it belongs to handle $j$, and move it by the weighted blend of the handle transforms:
It is one matrix-blend per point, fast, perfect for games. And it is entirely at the mercy of the weights. The whole quality of the deformation lives in the field $w_j(\mathbf{x})$, because the transforms are just blended; nothing else has a say. Pick the weights badly and you get the notorious skinning artifacts: the candy-wrapper collapse when a joint twists (because two opposite rotations average to a degenerate one across a sharp weight boundary), and leaks where a weight that should be local bleeds across the body so that bending one elbow tugs the other arm. Good weights must be, all at once: smooth (no creases at boundaries), local (a handle influences only nearby geometry), non-negative and summing to one (a partition of unity, so the blend is a proper interpolation), and shape-aware (respecting the parts of the shape, not just Euclidean distance: the two hands of a figure are close in space but far along the body).
Hand-painting weights with all those properties is impractical, which is the problem the next section solves automatically. The relationship to ARAP is direct: ARAP solves for a rigidity-optimal deformation each frame (a per-edit optimization whose result depends on the constraints and convergence), while skinning bakes the deformation into a fixed weight field and only blends at runtime (instant, but only as good as the weights). They are the two ends of the same spectrum: solve at runtime, or precompute the weights.
Even nonnegative weights summing to one do not make blended rotations a rotation. Equal blending of rotations by +90° and −90° collapses a 2-D point to the rotation center. Good weights reduce unwanted influence; they do not remove this algebraic limitation of linear blend skinning.
11.5.4 Bounded biharmonic weights (BBW)⧉
Jacobson, Baran, Popović and Sorkine (2011) gave skinning the weight field it had been missing: bounded biharmonic weights. The recipe is, once again, minimize an energy subject to constraints, and the energy is chosen so its solution is automatically smooth and well-spread. For each handle $j$, find the weight field $w_j(\mathbf{x})$ over the shape's interior that minimizes the Laplacian (biharmonic) energy
(the same bending energy that makes thin-plate splines smooth) subject to three constraints that supply every property the previous section demanded:
- Interpolation: $w_j = 1$ at handle $j$ and $w_j = 0$ at every other handle (each handle owns its own location).
- Bounds: $0 \le w_j(\mathbf{x}) \le 1$ everywhere (this is the bounded in the name), and it is what forbids the weights from over- and under-shooting and so kills the leaks and ringing that an unconstrained biharmonic solve would produce.
- Partition of unity: $\sum_j w_j(\mathbf{x}) = 1$, enforced so the blend is a valid interpolation.
Minimizing a quadratic (the Laplacian energy) under linear inequality constraints (the bounds) is a convex quadratic program, solved once per shape; locality comes for free because the bounded biharmonic solution naturally decays away from each handle and, crucially, respects the shape's domain: it spreads through the geometry, not across the empty gap between two limbs, reducing influence across empty gaps between nearby limbs. Influence can still travel through connected parts of the domain (Figure 11.5.8). The output is a clean set of weights that you drop straight into the LBS blend of the previous section, turning fragile skinning into reliable deformation. It is the workhorse behind handle-, cage-, and skeleton-based deformation in modern modeling tools.
11.5.5 ARAP interpolation: rigid-as-possible morphing between two poses⧉
The same rigidity prior answers a different question: "how should a shape move between two given poses?" This is the morphing problem of Chapter 11.3, Morphing, now with a rigidity constraint. Given pose A and pose B of the same shape (the arm down vs. the arm raised), the naive in-between at parameter $t$ linearly interpolates each vertex, $\mathbf{p}_i(t) = (1-t)\,\mathbf{p}_i^A + t\,\mathbf{p}_i^B$. And it fails in a now-familiar way: averaging the endpoints of a link that rotated between the poses cuts a chord across the rotation arc, so the link comes out shorter in the middle. The arm foreshortens and collapses halfway through: the forearm shrinks and the elbow caves in, because straight-line interpolation of rotated coordinates does not preserve length (Figure 11.5.9).
Alexa, Cohen-Or and Levin (2000) fixed this with as-rigid-as-possible shape interpolation: instead of interpolating the coordinates, interpolate the local transformations, and interpolate their rotation part as an angle, not as a matrix average. Decompose each cell's A→B transform into rotation and stretch ($J = R\,S$), then at time $t$ build the in-between transform from the rotation taken $t$ of the way around (a true rotation by $t\theta$, which preserves length) and the stretch interpolated linearly, and reassemble a consistent set of vertex positions by the same global linear solve as ARAP manipulation. Interpolating rotations avoids the shrinkage of a direct matrix blend, but the global reconstruction compromises among local transforms and need not preserve every edge length, passing cleanly through A at $t=0$ and B at $t=1$. This is morphing's missing rigidity: Chapter 11.3, Morphing, aligned features and blended; here we additionally insist the motion between the aligned poses be as rigid as possible, so the in-betweens look like a real object turning rather than a rubber sheet sagging.
11.5.6 Moving least squares: the simpler cousin⧉
ARAP needs a mesh and a per-frame solve. When you want shape-preserving deformation with no mesh at all, just a handful of scattered control points dragged over an image, there is a lighter-weight option: moving least squares (MLS) rigid deformation, due to Schaefer, McPhail and Warren (2006). For each output point $\mathbf{x}$ independently, fit the best transformation taking the handles' rest positions to their dragged positions, but weighted so that handles near $\mathbf{x}$ dominate the fit: typically $w_j = 1/\|\mathbf{p}_j - \mathbf{x}\|^{2\alpha}$. Because the weights change with $\mathbf{x}$, the fit is local: nearby it tracks the close handles, far away it relaxes. Restrict the fitted transform to be rigid (rotation + translation, no scale or shear), solvable in closed form per point, no global system, and you get a smooth, mesh-free warp that bends rather than shears, evaluated independently at every pixel. It is the method shown standing in for ARAP in Figure 11.5.1: cheaper and meshless, at the cost of ARAP's global consistency and detail-preservation. MLS is the right tool for interactive image warping (drag points on a photo, "liquify" with rigidity); ARAP is the right tool when you have a mesh and want the cleanest possible result.
11.5.7 Recap and significance optional⧉
Three ideas outlast this chapter. First, interpolating positions is not enough: a warp with no notion of rigidity will shear, stretch and collapse a shape, and the usual cure is a regularizer that charges for the stretch and shear part of the local motion while leaving rotation free. Second, that regularizer appears in two guises: ARAP, which solves for a deformation or pose interpolation by alternating a local per-cell rotation step with a global sparse linear solve; and linear blend skinning, which blends precomputed handle transforms, fast but only as good as its weights, which is why bounded biharmonic weights (smooth, local, nonnegative and summing to one) matter. Third, the same prior reframes morphing: as-rigid-as-possible interpolation keeps limbs close to their true length where a linear blend would foreshorten them. Neither method guarantees a fold-free result for every handle placement.
The reach is broad. Every interactive "puppet warp" and rig-free image deformation is one of these methods; character skinning in games and film is LBS with good weights; and the rigidity prior is one instance of a recurring pattern (fit the constraints, regularize toward a prior about the world) that also drives content-aware retargeting (Chapter 10.9, Seam optimization, where the prior is "keep salient regions undistorted"), Poisson editing (prior: match a gradient field), and morphable models (Chapter 11.4, Morphable models, prior: stay in a learned shape basis). Shape-preserving warping is where that pattern meets the most universal physical prior of all: things rotate freely, but they resist being stretched.
Recap: big lessons of this chapter
A free-form warp that only interpolates handle positions will happily shear, stretch, and collapse a shape, because position-interpolation has no opinion about how a region deforms, only about where its anchors land. To make a deformation look physical you add a regularizer that measures, at every point, how far the local transformation is from a rigid motion (a rotation + translation) and minimizes it. Rotation is left free (a limb may swing any amount); only the stretch/shear part is charged. The recurring move (fit the constraints, but regularize toward a prior about the world) is the same one behind Poisson editing (regularize toward a gradient field), content-aware retargeting (regularize toward leaving salient regions rigid), and morphable models (regularize toward a learned shape basis). Here the prior is the most generic physical one there is: things rotate freely but resist stretching.