Blended Cured Quasi-Newton for Distortion Optimization

Yufeng Zhu ^1,2 Robert Bridson^2,3 Danny M. Kaufman¹

¹Adobe Research ²University of British Columbia ³Autodesk

Abstract

Optimizing distortion energies over a mesh, in two or three dimensions, is a common and critical problem in physical simulation and geometry processing. We present three new improvements to the state of the art: a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms and so enables rapid progress; an energy proxy model that adaptively blends the Sobolev (inverse-Laplacian-processed) gradient and L-BFGS descent to gain the advantages of both, while avoiding L-BFGS's current limitations in distortion optimization tasks; and a characteristic gradient norm providing a robust and largely mesh- and energy-independent convergence criterion that avoids wrongful termination when algorithms temporarily slow their progress. Together these improvements form the basis for Blended Cured Quasi-Newton (BCQN), a new distortion optimization algorithm. Over a wide range of problems over all scales we show that BCQN is generally the fastest and most robust method available, making some previously intractable problems practical while offering up to an order of magnitude improvement in others.

Files

Paper:: [PDF]
Video:: [MP4] [YouTube]
Supplemental material:: [PDF]

Code

GitHub: [link]

BibTeX

@article{bcqn18,
    author = "Yufeng Zhu and Robert Bridson and Danny M. Kaufman",
    title = "Blended Cured Quasi-Newton for Distortion Optimization",
    journal = {ACM Trans. on Graphics (SIGGRAPH 2018)},
    year = 2018
}

Funding

This work was supported in part by the NSERC of Canada.