This paper introduces a novel geometric multigrid solver for unstructured curved surfaces. Multigrid methods are highly efficient iterative methods for solving systems of linear equations. Despite the success in solving problems defined on structured domains, generalizing multigrid to unstructured curved domains remains a challenging problem. The critical missing ingredient is a prolongation operator to transfer functions across different multigrid levels. We propose a novel method for computing the prolongation for triangulated surfaces based on intrinsic geometry, enabling an efficient geometric multigrid solver for curved surfaces. Our surface multigrid solver achieves better convergence than existing multigrid methods. Compared to direct solvers, our solver is orders of magnitude faster. We evaluate our method on many geometry processing applications and a wide variety of complex shapes with and without boundaries. By simply replacing the direct solver, we upgrade existing algorithms to interactive frame rates, and shift the computational bottleneck away from solving linear systems.
@article{Liu:2021:multigrid,
author = {Liu, Hsueh-Ti Derek and Zhang, Jiayi Eris and Ben-Chen, Mirela and Jacobson, Alec},
title = {Surface Multigrid via Intrinsic Prolongation},
journal = {ACM Trans. Graph.},
volume = {40},
number = {4},
year = {2021},
publisher = {ACM}
}
Our research is funded in part by New Frontiers of Research Fund (NFRFE–201), German-Israeli Foundation for Scientific Research and Development (I–1339–407.6/2016), European Research Council (714776 OPREP), NSERC Discovery (RGPIN2017–05235, RGPAS–2017–507938), Israel Science Foundation (504/16), the Ontario Early Research Award program, the Canada Research Chairs Program, the Fields Centre for Quantitative Analysis and Modelling and gifts by Adobe Systems, Autodesk and MESH Inc. We thank Uri Ascher, Tiantian Liu, and Irad Yavneh for sharing inspiring lessons on multigrid methods; Zhongshi Jiang for helps on experiements. We thank members of Dynamic Graphics Project at the University of Toronto; Michael Tao and Kazem Cheshmi for valuable discussions; Benjamin Chislett for proofreading; and John Hancock for the IT support. We thank all the artists for sharing a rich variety of 3D models.