Versatile Geometry Optimization with Hard Constraints

Abstract

Constrained numerical optimization is ubiquitous in geometry processing and simulation. For example, it can be used to minimize distortion between shape mappings or finding equilibrium in a dynamical system. Many important real-world problems are nonlinear and require sophisticated methods to optimize. However, there are several challenges associated with common applications. Models used for natural materials and distortion metrics are prone to numerical instabilities. Large domains give rise to computationally expensive operations, such as repeated factorizations of linear systems. For volumetric meshes, generating a feasible starting point of the optimization can be non-trivial. Constraints that model global behavior such as avoiding interpenetration are difficult to resolve robustly and efficiently. For an accurate representation, hard constraints are necessary to enforce certain behavior during the optimization. These difficulties have been the focus of geometry optimization literature for many years. Proximal methods provide a robust and scalable approach to nonlinear optimization, in which constraints and energies are represented as proximal operators. The alternating direction method of multipliers (ADMM) has especially grown in popularity for computer graphics applications. This work shows how ADMM can be modified to resolve many of the challenges associated with geometry optimization. We introduce a novel algorithm that applies ADMM to the robust simulation of hyperelastic deformation and mesh parameterization. However, ADMM alone does not produce a feasible solution since its reliance on proximal operations means it may never fully satisfy constraints. Toward addressing this limitation we provide formulations for resolving hard, nonlinear inequality constraints while making use of efficient precomputation. The effectiveness of these methods are demonstrated with several complex examples, including implicit time integration with collision resolution, volumetric shape mapping, and globally injective mesh deformation.