We present the Accelerated Quadratic Proxy (AQP) - a simple first-order algorithm for the optimization of geometric energies defined over triangular and tetrahedral meshes.

The main stumbling block of current optimization techniques used to minimize geometric energies over meshes is slow convergence due to ill-conditioning of the energies at their minima. We observe that this ill-conditioning is in large part due to a Laplacian-like term existing in these energies. Consequently, we suggest to locally use a quadratic polynomial proxy, whose Hessian is taken to be the Laplacian, in order to achieve a preconditioning effect. This already improves stability and convergence, but more importantly allows incorporating acceleration in an almost universal way, that is independent of mesh size and of the specific energy considered.

Experiments with AQP show it is rather insensitive to mesh resolution and requires a nearly constant number of iterations to converge; this is in strong contrast to other popular optimization techniques used today such as Accelerated Gradient Descent and Quasi-Newton methods, e.g., L-BFGS. We have tested AQP for mesh deformation in 2D and 3D as well as for surface parameterization, and found it to provide a considerable speedup over common baseline techniques.

Just a teaser... download the paper if you want all the details.

Our goal

Minimize linearly constrained geometric energies taking the general form \[ \begin{align} \min_{\mathbf{x}} & \quad f(\mathbf{x}) \\ \mathrm{s.t.} & \quad A\mathbf{x}=b\\ \end{align} \]

The observation

Energies \(f\), defined over meshes in geometry processing, can often be decomposed \[ f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T H \mathbf{x} + g(\mathbf{x}) \] where \(H = L \otimes I_d\) is a Kroncker product composed of copies of the mesh Laplacian, \(L\), acting on each coordinate. We present such decompositions for the As-Rigid-As-Possible, Isometric Distortion and Conformal Distortion energies.

The Accelerated Quadratic Proxy Algorithm

Our algorithm has 3 simple steps

1. Acceleration: \[ \mathbf{y}_n = (1+\theta)\mathbf{x}_{n-1} - \theta\mathbf{x}_{n-2} \] 2. Quadratic Proxy Minimization: determines a search direction \(\mathbf{p}_n\) via the solution of the KKT system \[ \begin{bmatrix} H & A^T \\ A & 0 \\ \end{bmatrix} \begin{bmatrix} \mathbf{p}_n \\ \lambda \\ \end{bmatrix} = \begin{bmatrix} -\nabla f(\mathbf{y}_n) \\ 0 \\ \end{bmatrix} \] 3. Line search: \[ \mathbf{x}_n = \text{linesearch}_{0 < t \leq 1} f(\mathbf{y}_n + t\mathbf{p}_n) \]

Our choice \(H = L \otimes I_d\) has several consequences on the algorithm above:
- Efficiency - the left-hand side of the KKT above is fixed, and therefore can be prefactorized for an efficient solution.
- Preconditioning - this choice of \(H\) can be interpreted as using the Laplacian as a preconditioner for energies defined over meshes.
- Acceleration - this choice of \(H\) enables setting the acceleration parameter \(\theta\) in an almost universal way.

Find this interesting? we encourage you to read the paper for the full (and more accurate) details!

Experiments

A Matlab implementation of the paper can found on GitHub. A zip file of the latest version can be directly downloaded here.

The class `OptimSolverAcclQuadProx.m` implements the accelerated quadratic proxy optimization algorithm described in the paper for the minimization of geometric energies.

This package includes a few examples:

• example_deformation_2d_gecko_IsoDist.m demonstrates the minimization of the Isometric Distortion energy for shape deformation (Figure 1 in the paper).
• example_parameterization_cow_IsoDist.m demonstrates the minimization of the Isometric Distortion energy for parameterization (the cow of Figure 12 in the paper).
• example_deformation_2d_bar_ARAP.m and example_deformation_3d_boy_ARAP.m demonstrate the minimization of the As-Rigid-As-Possible energy for shape deformation (see video clips above).

Compatibility and dependencies: The code was tested with Matlab (2015a). The code depends on a few MEX functions. Windows (x64) binaries are included; they are compiled with Intel C++ Composer XE 2016 with Microsoft Visual Studio 2013; compilation requires Eigen; fast implementation of As-Rigid-As-Possible also relies on libigl. The source code is provided under the mex/ folder; run compileAllMex.m to compile all mex files (only tested under windows).

Disclaimer: The code is provided as-is for academic use only and without any guarantees. Please contact the authors to report any bugs.

@article{AQP:2016,
author = {Kovalsky, Shahar Z. and Galun, Meirav and Lipman, Yaron},
title = {Accelerated Quadratic Proxy for Geometric Optimization},
journal = {ACM Transactions on Graphics (proceedings of ACM SIGGRAPH)},
volume = {},
number = {},
year = {2016},
}