Abstract
Many computer graphics problems require computing geometric shapes subject to certain constraints. This often results in non-linear and non-convex optimization problems with globally coupled variables, which pose great challenge for interactive applications. Local-global solvers developed in recent years can quickly compute an approximate solution to such problems, making them an attractive choice for applications that prioritize efficiency over accuracy. However, these solvers suffer from lower convergence rate, and may take a long time to compute an accurate result. In this paper, we propose a simple and effective technique to accelerate the convergence of such solvers. By treating each local-global step as a fixed-point iteration, we apply Anderson acceleration, a well-established technique for fixed-point solvers, to speed up the convergence of a local-global solver. To address the stability issue of classical Anderson acceleration, we propose a simple strategy to guarantee the decrease of target energy and ensure its global convergence. In addition, we analyze the connection between Anderson acceleration and quasi-Newton methods, and show that the canonical choice of its mixing parameter is suitable for accelerating local-global solvers. Moreover, our technique is effective beyond classical local-global solvers, and can be applied to iterative methods with a common structure. We evaluate the performance of our technique on a variety of geometry optimization and physics simulation problems. Our approach significantly reduces the number of iterations required to compute an accurate result, with only a slight increase of computational cost per iteration. Its simplicity and effectiveness makes it a promising tool for accelerating existing algorithms as well as designing efficient new algorithms.
Introduction
Tasks such as mesh smoothing, architectural wireframe design, and cloth simulation are fundamental to computer graphics, typically formulated as non-linear optimization problems. "Local-global" solvers, including Shape-Up for geometry and Projective Dynamics for physics, have become industry standards due to their robustness, ease of parallelization, and ability to provide approximate solutions rapidly.
However, these first-order methods suffer from sublinear convergence. While they approach a solution quickly, they struggle to reach high precision, often requiring thousands of iterations to achieve exactness. This paper introduces a "wrapper" technique that treats these solvers as fixed-point iterations and applies Anderson Acceleration (AA) to dramatically improve their convergence rates.
Methodology
The core innovation lies in framing the two-step local-global process as a single fixed-point mapping: $Q_{k+1} = G(Q_k)$. By applying Anderson Acceleration, the solver utilizes information from the previous $m$ iterations (typically $m=5$) to find an optimal linear combination of states that minimizes the residual.
The "Safety Switch" for Global Convergence
A known issue with standard AA is potential instability, where the accelerated step might "jump" to a state with higher energy. To resolve this, the authors implement a simple energy check: if an accelerated step increases the target energy, the algorithm rejects it and reverts to a standard local-global step. This ensures a monotonic decrease in energy and guarantees global convergence.
Results and Evaluation
The method was evaluated across diverse scenarios, including geometry optimization (e.g., planar quadrilateral meshes), ARAP deformation, and physics simulations like cloth and elastic solids.
Key findings include:
- Significant Speedup: The accelerated solver often reaches high-accuracy thresholds ($10^{-10}$ relative energy error) 10x to 100x faster than unaccelerated versions.
- Minimal Overhead: The computational cost of the AA step—solving a small $5 \times 5$ linear system—is negligible compared to the primary mesh projections and linear solves.
- Robustness: The "safety switch" successfully maintains stability even when starting far from the solution or dealing with degenerate mesh elements.
Conclusion
By treating local-global solvers as fixed-point iterations, this research provides a simple, plug-and-play wrapper that significantly enhances the performance of standard graphics optimization tools. While future work may explore hard constraints and automated parameter tuning, the current approach offers a robust and efficient solution for high-accuracy geometry and physics simulation.
Summary updated