Local Deformation for Interactive Shape Editing

A time-honored and common approach for localized deformation is the direct manipulation of high-level parameters. From the onset, a notion of locality is baked into these parameters, which can directly encode the shape itself, often using splines (Hoschek et al., 1993) or a “rig” to control a shape’s deformation, as with cage-based generalized barycentric coordinates (Joshi et al., 2007; Lipman et al., 2008), linear-blend skinning (Magnenat-Thalmann et al., 1989; Jacobson et al., 2011; Wang et al., 2015), lattice deformers (Sederberg and Parry, 1986; Coquillart, 1990), wire curves (Singh and Fiume, 1998), or learned skinning weights (Genova et al., 2020), to list a few.

Approaches of this nature, although popular in computer graphics, have a few disadvantages. Firstly, since the locality is baked into the parameterization, it cannot easily adapt based on changes in the deformation. Secondly, without an optimization step, even in cases where a capable elastic energy is within reach there is no way to incorporate it into the deformation.

Instead of providing localized deformation via pre-chosen parameters, it is also possible to define a localized deformation field, then apply it to a shape. These methods often follow a “sculpting” metaphor, and include simple move, scale, pinch, and twist edits as well as more sophisticated operations (Cani and Angelidis, 2006). Recently, De Goes and James (2017) introduced regularized Kelvinlets, which provides real-time localized volumetric control based on the regularized closed-form solutions of linear elasticity. These closed-form solutions were later extended to handle dynamic secondary motions (De Goes and James, 2018), sharp deformation (de Goes and James, 2019) and anisotropic elasticity (Chen and Desbrun, 2022).

These approaches allow for local deformation with real-time feedback. However, as they are designed for digital sculpting, these methods usually require the user to explicitly pick the falloff of the brushes. Furthermore, these methods are usually based on Euclidean distance, unaware of the shape’s geometry. In contrast, our method is shape-aware and enables automatic dynamic region of influence with interactive feedback.

The most natural formulation of optimization-based deformation editing is by solving globally for the entire shape’s deformation at once (Smith et al., 2019; Zhu et al., 2018; Shtengel et al., 2017). Nevertheless, there are methods attempting to enforce locality in the shape optimization process. Previous methods of this sort have often computed the ROI of a manipulation as a preprocessing step, then restricting the optimization to only move parts of the shape within this ROI. The ROI can be taken as an input (Alexa, 2006) or based on a small amount of user markup (Kho and Garland, 2005; Zimmermann et al., 2007; Luo et al., 2007). Other methods combine deformation energies with handle-based systems, including skeleton rigs (Jacobson et al., 2012; Hahn et al., 2012; Kavan and Sorkine, 2012) and cages (Ben-Chen et al., 2009).

Unfortunately, in many contexts, the ROI is hard or impossible to know in advance. This is particularly the case when constraints are involved, or where it is not known in advance if a deformation will be small (best fitting a small ROI) or large (best fitting a large ROI). In addition, the correct ROI may also depend on the elastic energy driving the deformation, thus difficult to account for when the ROI calculation is decoupled in a separate step.

Sparsity-inducing norms, such as the smooth $\ell_{0}$ norm, have been widely applied to many domains and problems including medical image reconstruction (Xiang et al., 2022), sparse component analysis (Mohimani et al., 2007) and UV mapping (Poranne et al., 2017). To allow an adaptive ROI while preserving the benefits of optimization-based deformation, a few works have adopted a sparsity-inducing norm, typically a $\|x\|_{1}$ or $\|x\|_{2}$ norm, in their energy, which is then minimized by Alternating Direction Method of Multipliers (ADMM) (Boyd et al., 2011; Peng et al., 2018; Zhang et al., 2019) or Augmented Lagrangian Method (ALM) (Bertsekas, 1996). We refer the readers to (Xu et al., 2015) for a survey on sparsity in geometry modelling and processing.

Several methods of this variety rely on sparsity-inducing norm formulated as a sum of $\|x\|_{2}$ norms, referred to as $\ell_{2,1}$ or $\ell_{1}/\ell_{2}$ norms, or a group lasso penalty. They have been applied in a preprocessing phase to compute sparse deformation modes for interactive local control (Neumann et al., 2013; Deng et al., 2013; Brandt and Hildebrandt, 2017). However, the deformation is limited by the linear deformation modes and thus struggles with large deformation.

Another class of methods adds a sparsity-induced regularization to an elastic energy optimization to achieve local deformation. Gao et al. (2012) applied different $\ell_{p}$ sparsity norms to the as-rigid-as-possible energy (Sorkine and Alexa, 2007) to create various deformation styles. Recently, Chen et al. (2017) used $\ell_{2,1}$ regularization on vertex positions to locally control the deformation. However, their direct use of the $\ell_{2,1}$ norm will create artifacts when the control point is not on the boundary of the shape (see Fig. 3(b) and Fig. 13(b)). Moreover, their method requires one ADMM solve in each global iteration, which renders the optimization less efficient and slow in runtime. Also, their framework is limited to 2D deformation with ARAP energy only, while our framework generalizes across dimensions and a variety of energy models.

Our algorithm, inspired by sparsity-seeking regularizers such as that used by (Chen et al., 2017; Fan and Li, 2001), addresses these shortcomings. In particular, we propose a simple and novel sparsity-inducing norm that eliminates artifacts arising from the $\ell_{2,1}$ norm, and our efficient optimization scheme leads to interactive performance.

We suggest a sparsity-inducing regularization term to produce natural local deformation. This regularizer is applied per-vertex to ${\mathbf{V}}_{i}-{\widetilde{\mathbf{V}}}_{i}$ to bias each vertex deformed position ${\mathbf{V}}_{i}$ to exactly match its initial rest position ${\widetilde{\mathbf{V}}}_{i}$ except in isolated regions of the shape. The most obvious choice for this regularization would be to enforce sparsity either with an $\ell_{1}$-norm, or with a group lasso / $\ell_{2,1}$ regularization defined as $\sum_{i}\|{\mathbf{V}}_{i}\|_{2}$ as in (Chen et al., 2017).

However, direct use of a $\ell_{2,1}$ regularization term leads to artifacts, due to the fact that the $\ell_{2,1}$-norm competes with the elastic energy by dragging all the vertices towards their original positions. This results in undesired distortion near the deformation handles (see Fig. 3(b) and Fig. 13(b)), making the deformed region look unnatural. Previous $\ell_{2,1}$-based methods (Chen et al., 2017) focus specifically on ARAP-like deformation, and attempt to alleviate this artifact by adding a Laplacian smoothness term and a weighting term based on biharmonic distance. Unfortunately, as seen in Fig. 3 at the ends of the octocat’s tentacles, artifacts can arise in regions quite close to the deformation handles, and there is not necessarily any setting of these parameters which alleviates these artifacts without oversmoothing the entire deformation.

Inspired by “folded concave” losses in statistical regression (Fan and Li, 2001; Zhang, 2010) and the use of the $\ell_{2,1}$ loss in deformation (Chen et al., 2017), we propose using a smoothly clipped group $\ell_{1}$-norm as our locality-inducing regularization. We call it a SC-L1 loss for “smoothly clamped $\ell_{1}$ loss” (see the inset).

We adopt a simple implementation for our SC-L1 loss:

where $s$ is the threshold distance beyond which the regularizer is disabled (this is equivalent to a group-variant of the MCP loss in (Zhang, 2010), but we use the term “SC-L1” to emphasize that the minimax concave property is not critical for localized deformation). This function is continuously differentiable and piecewise smooth, and admits a proximal shrinkage operator free of local minima. Near the origin the SC-L1 loss function acts like the group $\ell_{1}$-norm, which drives $\|{\mathbf{x}}\|_{\text{{SC-L1}}}$ towards $0$ in a sparse-deformation-seeking manner. When $\|{\mathbf{x}}\|_{2}\geq s$, the SC-L1 loss function value is a constant and has no penalty on $\|{\mathbf{x}}\|_{2}$. For a detailed comparison between our SC-L1 loss function and other alternatives, please see Sec.5 of the supplementary material.

We denote ${\mathbf{V}}$ as a $|{\mathbf{V}}|\times d$ matrix of vertex positions at the deformed state, and ${\widetilde{\mathbf{V}}}$ as a $|{\mathbf{V}}|\times d$ matrix containing rest state vertex positions.

The total energy for our local deformation is as follows:

The first term is an elasticity energy of choice, and can be selected independent of the locality regularization. The second term is the novel “SC-L1 loss” term on the vertex position changes, which measures the locality of the deformation. $a_{i}$ is the barycentric vertex area of the $i$-th vertex, which ensures the consistency of the result across different mesh resolutions for the same constant ${w}$. To enable more user control, position constraints and optional affine constraints can be added on selected vertices to achieve different deformation effects. $s$ denotes the indices of the vertices with the position constraint, and we call these vertices “handles”. ${\mathcal{S}}_{k}$ is the $k$-th set of vertex indices where an affine constraint is added. For simplicity, we omit the position constraints and affine constraints in the discussion below, as they can be easily intergrated to the system by removing the corresponding degrees of freedom and using Lagrange multiplier method (see Eq(1) in (Wang et al., 2015)).

Inspired by the local-global strategy in (Brown and Narain, 2021), our local deformation energy (Eq. 2) can be rewritten as:

where ${\mathbf{D}}_{j}$ is the selection matrix for edges of the $j$-th vertex or element. $\text{sym}({\mathbf{F}})$ denotes the symmetric factor ${\mathbf{S}}$ computed using the polar decomposition ${\mathbf{F}}={\mathbf{R}}{\mathbf{S}}$, where ${\mathbf{F}}$ is the deformation gradient. Thus ${\mathbf{X}}_{j}$ is the symmetric factor of deformation gradient of the $j$-th vertex or element. (Note that in general $\text{sym}({\mathbf{F}})\neq\frac{1}{2}({\mathbf{F}}+{\mathbf{F}}^{\top})$.) The goal of using $\text{sym}()$ here is to ensure the local coordinates ${\mathbf{X}}_{j}$ are invariant to rotations as well as translations. For details, please see (Brown and Narain, 2021).

We begin by considering how to minimize an as-rigid-as-possible (ARAP) energy (Sorkine and Alexa, 2007) when combined with a SC-L1 loss regularizer. With an ARAP elastic energy, the total energy (Eq. 3) for our local deformation is as follows:

where ${\mathbf{R}}_{i}$ is a $d\times d$ rotation matrix, $W_{i}$ is a $|{\mathcal{N}}(i)|\times|{\mathcal{N}}(i)|$ diagonal matrix of cotangent weights, $\widetilde{{\mathbf{D}}}_{i}$ and ${\mathbf{D}}_{i}$ are $3\times|{\mathcal{N}}(i)|$ matrices of ”spokes and rims” edge vectors of the $i$-th vertex at the rest and deformed states respectively. $\|{\mathbf{X}}\|_{{\mathbf{W}}_{i}}^{2}$ denotes $\operatorname{Tr}({\mathbf{X}}^{\top}{\mathbf{W}}_{i}{\mathbf{X}})$. Here we use ${\mathbf{R}}_{i}$ to denote ${\mathbf{X}}_{i}$, since we drive the deformation gradient towards a rotation matrix in ARAP energy.

Previous method (Chen et al., 2017) optimizes the $\ell_{2,1}$ version of Eq. 4 in a less efficient way. Their local step optimizes over per-vertex rotation ${\mathbf{R}}_{i}$ and their global step minimizes over vertex

positions ${\mathbf{V}}$ using a two-block ADMM scheme. This leads to an expensive optimization with a full ADMM optimization in each global step, making their method too slow for interactive usage. In contrast, applying our new three-block ADMM scheme to the local ARAP energy results in a much more efficient solver, which is one ADMM optimization itself (see the inset, where the blue regions denote an ADMM optimization). We further show the pseudocode of our three-block ADMM for local ARAP energy in Suppl. Alg.1.

More concretely, by setting ${\mathbf{Z}}_{i}={\mathbf{V}}_{i}-{\widetilde{\mathbf{V}}}_{i}$, we can further rewrite Eq. 4 as

The above minimization problem can be solved efficiently using the following ADMM update steps:

Here $\rho$ is a fixed penalty parameter. For a detailed derivation of the ADMM update, please see Sec. 2 of the supplementary material.

The various steps in this ADMM-based algorithm are computed as follows:

For updating ${\mathbf{R}}_{i}$, local step 1 (Eq. 6a) is an instance of the Orthogonal Procrustes problem, which can be solved in the same way as the rotation fitting step in (Sorkine and Alexa, 2007). The optimal ${\mathbf{R}}_{i}$ can be computed as ${\mathbf{R}}_{i}^{k+1}\leftarrow\mathcal{V}_{i}\mathcal{U}_{i}^{\top}$ from the singular value decomposition of ${\mathbf{M}}_{i}=\mathcal{U}_{i}\Sigma_{i}\mathcal{V}_{i}^{\top}$, where ${\mathbf{M}}_{i}={\mathbf{D}}_{i}\widetilde{{\mathbf{D}}}_{i}^{\top}$.

For updating ${\mathbf{Z}}_{i}$, following the derivation of the proximal operator of SC-L1 loss in Sec. 1 of the supplementary material, our local step 2 (Eq. 6b) is solved using a SC-L1 loss-specific shrinkage step:

To avoid local minima in the shrinkage step, this assumes $\rho$ is set to satisfy $\rho>\frac{\text{max}({w}a_{i})}{s}$ (see Sec. 1 of the supplementary material).

For updating ${\mathbf{V}}$, the global step (Eq. 6c) can be achieved by solving a linear system:

where the Laplacian ${\mathbf{L}}$ and ${\mathbf{B}}$ are defined in the same way as the global step (Eq. 9) in (Sorkine and Alexa, 2007). For fixed $\rho$ an efficient implementation is obtained by precomputing and storing the Cholesky factorization of ${\mathbf{L}}+\rho{\mathbf{I}}$.

Our local deformation scheme can be further extended to physics-based elasticity energies, e.g., Neo-Hookean energy. Using the Neo-Hookean energy as our elasticity energy and following the framework of (Brown and Narain, 2021), the optimization problem in Eq. 3 can be written as follows:

where $T$ denotes all the elements.

Similarly, by introducing ${\mathbf{Z}}_{i}={\mathbf{V}}_{i}-{\widetilde{\mathbf{V}}}_{i}$, we can minimize our local Neo-Hookean energy using ADMM. For a detailed derivation, please see Sec. 3 of the supplementary material.

The ADMM update (Alg. 1) for the above minimization problem is as follows:

Here $\rho$ and $\gamma$ are fixed penalty parameters.

The local step 2 (updating ${\mathbf{Z}}_{i}$) and the global step (updating ${\mathbf{V}}$) can be solved in the same way as the local ARAP energy (see Sec. 4.1).

For updating ${\mathbf{X}}_{i}$, local step 1 (Eq. 11a) can be solved by performing the energy minimization on the singular values of $\text{sym}({\mathbf{D}}_{j}{\mathbf{V}})+{\mathbf{W}}_{j}$. This is a proximal operator of $E_{\text{nh}}$ at the rotation-invariant $\text{sym}({\mathbf{D}}_{j}{\mathbf{V}})+{\mathbf{W}}_{j}$.

Let us denote the proximal operator of $E_{\text{nh}}$ and the singular value decomposition of $\text{sym}({\mathbf{D}}_{j}{\mathbf{V}})+{\mathbf{W}}_{j}$ as:

where $\gamma$ is the augmented Lagrangian parameter for ${\mathbf{X}}_{j}$.

As shown by (Brown and Narain, 2021), we can compute the optimal ${\mathbf{X}}_{j}$ as:

Specifically, one can compute the SVD of $\text{sym}({\mathbf{D}}_{j}{\mathbf{V}})+{\mathbf{W}}_{j}$ and perform the minimization of $\operatorname{prox}_{E_{\text{nh}}}$ only on its singular values, while keeping singular vectors unchanged. The above optimization of singular values $\Sigma_{j}^{k+1}$ can be performed using an L-BFGS solver.

Our algorithm can easily generalize across different dimensions and material models. Switching the material model only requires a change on the minimization problem in the local step 1 $\operatorname*{arg\,min}_{X}$, which can be optimized over the singular values of the symmetric factor ${\mathbf{X}}_{i}$ of the deformation gradient.