“Surface multigrid via intrinsic prolongation” by Liu, Zhang, Ben-Chen and Jacobson

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.

1. Mridul Aanjaneya, Chengguizi Han, Ryan Goldade, and Christopher Batty. 2019. An Efficient Geometric Multigrid Solver for Viscous Liquids. Proceedings of the ACM in Computer Graphics and Interactive Techniques (2019).Google ScholarDigital Library
2. Mark Adams and Jim Demmel. 1999. Parallel Multigrid Solver for 3D Unstructured Finite Element Problems. In Proceedings of the ACM/IEEE Conference on Supercomputing, SC 1999, November 13–19, 1999, Portland, Oregon, USA. ACM, 27.Google ScholarDigital Library
3. Burak Aksoylu, Andrei Khodakovsky, and Peter Schröder. 2005. Multilevel Solvers for Unstructured Surface Meshes. SIAM J. Sci. Comput. 26, 4 (2005), 1146–1165.Google ScholarDigital Library
4. Dmitry Anisimov, Chongyang Deng, and Kai Hormann. 2016. Subdividing barycentric coordinates. Computer Aided Geometric Design 43 (2016), 172–185.Google ScholarDigital Library
5. Omri Azencot, Orestis Vantzos, Max Wardetzky, Martin Rumpf, and Mirela Ben-Chen. 2015. Functional thin films on surfaces. In Proceedings of the 14th ACM SIGGRAPH / Eurographics Symposium on Computer Animation, SCA 2015, Los Angeles, CA, USA, August 7–9, 2015, Jernej Barbic and Zhigang Deng (Eds.). ACM, 137–146.Google ScholarDigital Library
6. Achi Brandt. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of computation 31, 138 (1977), 333–390.Google Scholar
7. Achi Brandt and Oren E Livne. 2011. Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics, Revised Edition. SIAM.Google Scholar
8. A Brandt, S McCoruick, and J Huge. 1985. Algebraic multigrid (amg) for sparse matrix equati0ns. Sparsity and its Applications 257 (1985).Google Scholar
9. Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. ACM Trans. Math. Softw. 35, 3, Article 22 (Oct. 2008), 14 pages. Google ScholarDigital Library
10. Kazem Cheshmi, Danny M. Kaufman, Shoaib Kamil, and Maryam Mehri Dehnavi. 2020. NASOQ: Numerically Accurate Sparsity-Oriented QP Solver. ACM Trans. Graph. 39, 4, Article 96 (July 2020), 17 pages. Google ScholarDigital Library
11. Ming Chuang, Linjie Luo, Benedict J. Brown, Szymon Rusinkiewicz, and Michael M. Kazhdan. 2009. Estimating the Laplace-Beltrami Operator by Restricting 3D Functions. Comput. Graph. Forum 28, 5 (2009), 1475–1484.Google ScholarCross Ref
12. Jonathan D. Cohen, Dinesh Manocha, and Marc Olano. 2003. Successive Mappings: An Approach to Polygonal Mesh Simplification with Guaranteed Error Bounds. Int. J. Comput. Geom. Appl. 13, 1 (2003), 61.Google ScholarCross Ref
13. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2017. The Heat Method for Distance Computation. Commun. ACM 60, 11 (Oct. 2017), 90–99. Google ScholarDigital Library
14. Fernando de Goes, Mathieu Desbrun, Mark Meyer, and Tony DeRose. 2016. Subdivision exterior calculus for geometry processing. ACM Trans. Graph. 35, 4 (2016), 133:1–133:11.Google ScholarDigital Library
15. Christian Dick, Joachim Georgii, and Rüdiger Westermann. 2011. A real-time multigrid finite hexahedra method for elasticity simulation using CUDA. Simul. Model. Pract. Theory 19, 2 (2011), 801–816.Google ScholarCross Ref
16. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: a practical gauss-seidel method for stable soft body dynamics. ACM Trans. Graph. 35, 6 (2016), 214:1–214:9.Google ScholarDigital Library
17. Ilja Friedel, Peter Schröder, and Andrei Khodakovsky. 2004. Variational normal meshes. ACM Trans. Graph. 23, 4 (2004), 1061–1073.Google ScholarDigital Library
18. Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1997, Los Angeles, CA, USA, August 3–8, 1997, G. Scott Owen, Turner Whitted, and Barbara Mones-Hattal (Eds.). ACM, 209–216.Google ScholarDigital Library
19. Francisco José Gaspar, Jose L. Gracia, and Francisco Javier Lisbona. 2009. Fourier Analysis for Multigrid Methods on Triangular Grids. SIAM J. Sci. Comput. 31, 3 (2009), 2081–2102.Google ScholarDigital Library
20. Joachim Georgii and Rüdiger Westermann. 2006. A multigrid framework for real-time simulation of deformable bodies. Comput. Graph. 30, 3 (2006), 408–415.Google ScholarDigital Library
21. Seth Green, George Turkiyyah, and Duane W. Storti. 2002. Subdivision-based multilevel methods for large scale engineering simulation of thin shells. In Seventh ACM Symposium on Solid Modeling and Applications, Max-Planck-Institut für Informatik, Saarbrücken, Germany, June 17–21, 2002, Hans-Peter Seidel, Vadim Shapiro, Kunwoo Lee, and Nick Patrikalakis (Eds.). ACM, 265–272.Google ScholarDigital Library
22. Igor Guskov, Andrei Khodakovsky, Peter Schröder, and Wim Sweldens. 2002. Hybrid meshes: multiresolution using regular and irregular refinement. In Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, Spain, June 5–7, 2002, Ferran Hurtado, Vera Sacristán, Chandrajit Bajaj, and Subhash Suri (Eds.). ACM, 264–272.Google ScholarDigital Library
23. Igor Guskov, Kiril Vidimce, Wim Sweldens, and Peter Schröder. 2000. Normal meshes. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2000, New Orleans, LA, USA, July 23–28, 2000, Judith R. Brown and Kurt Akeley (Eds.). ACM, 95–102.Google ScholarDigital Library
24. Tom Haber, Tom Mertens, Philippe Bekaert, and Frank Van Reeth. 2005. A computational approach to simulate subsurface light diffusion in arbitrarily shaped objects. In Proceedings of the Graphics Interface 2005 Conference, May 9–11, 2005, Victoria, British Columbia, Canada, Kori Inkpen and Michiel van de Panne (Eds.). Canadian Human-Computer Communications Society, 79–86.Google ScholarDigital Library
25. Wolfgang Hackbusch. 2013. Multi-grid methods and applications. Vol. 4. Springer Science & Business Media.Google Scholar
26. PW Hemker. 1990. On the order of prolongations and restrictions in multigrid procedures. J. Comput. Appl. Math. 32, 3 (1990), 423–429.Google ScholarDigital Library
27. Philipp Herholz and Marc Alexa. 2018. Factor Once: Reusing Cholesky Factorizations on Sub-Meshes. ACM Transaction on Graphics (Proc. of Siggraph Asia) 37, 6 (2018), 9. Google ScholarDigital Library
28. Philipp Herholz and Olga Sorkine-Hornung. 2020. Sparse cholesky updates for interactive mesh parameterization. ACM Trans. Graph. 39, 6 (2020), 202:1–202:14.Google ScholarDigital Library
29. Hugues Hoppe. 1996. Progressive Meshes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1996, New Orleans, LA, USA, August 4–9, 1996, John Fujii (Ed.). ACM, 99–108.Google Scholar
30. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast tetrahedral meshing in the wild. ACM Trans. Graph. 39, 4 (2020), 117.Google ScholarDigital Library
31. Alec Jacobson, Elif Tosun, Olga Sorkine, and Denis Zorin. 2010. Mixed Finite Elements for Variational Surface Modeling. Comput. Graph. Forum 29, 5 (2010), 1565–1574.Google ScholarCross Ref
32. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant field-aligned meshes. ACM Trans. Graph. 34, 6 (2015), 189:1–189:15.Google ScholarDigital Library
33. In-Yong Jeon, Kwang-Jin Choi, Tae-Yong Kim, Bong-Ouk Choi, and Hyeong-Seok Ko. 2013. Constrainable Multigrid for Cloth. Comput. Graph. Forum 32, 7 (2013), 31–39.Google ScholarCross Ref
34. Zhongshi Jiang, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2020. Bijective projection in a shell. ACM Trans. Graph. 39, 6 (2020), 247:1–247:18.Google ScholarDigital Library
35. Alexandr Katrutsa, Talgat Daulbaev, and Ivan V. Oseledets. 2020. Black-box learning of multigrid parameters. J. Comput. Appl. Math. 368 (2020).Google Scholar
36. Misha Kazhdan and Hugues Hoppe. 2019. An Adaptive Multi-Grid Solver for Applications in Computer Graphics. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 138–150.Google Scholar
37. Michael Kazhdan, Jake Solomon, and Mirela Ben-Chen. 2012. Can Mean-Curvature Flow be Modified to be Non-singular? Comput. Graph. Forum 31, 5 (2012), 1745–1754.Google ScholarDigital Library
38. Michael M. Kazhdan and Hugues Hoppe. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27, 3 (2008), 21.Google ScholarDigital Library
39. Andrei Khodakovsky, Nathan Litke, and Peter Schröder. 2003. Globally smooth parameterizations with low distortion. ACM Trans. Graph. 22, 3 (2003), 350–357.Google ScholarDigital Library
40. Leif Kobbelt, Swen Campagna, and Hans-Peter Seidel. 1998. A General Framework for Mesh Decimation. In Proceedings of the Graphics Interface 1998 Conference, June 18–20, 1998, Vancouver, BC, Canada, Wayne A. Davis, Kellogg S. Booth, and Alain Fournier (Eds.). Canadian Human-Computer Communications Society, 43–50.Google Scholar
41. Dilip Krishnan, Raanan Fattal, and Richard Szeliski. 2013. Efficient preconditioning of laplacian matrices for computer graphics. ACM Trans. Graph. 32, 4 (2013), 142:1–142:15.Google ScholarDigital Library
42. Dilip Krishnan and Richard Szeliski. 2011. Multigrid and multilevel preconditioners for computational photography. ACM Trans. Graph. 30, 6 (2011), 177.Google ScholarDigital Library
43. Junyu Lai, Yangang Chen, Yu Gu, Christopher Batty, and Justin W. L. Wan. 2020. Fast and Scalable Solvers for the Fluid Pressure Equations with Separating Solid Boundary Conditions. Comput. Graph. Forum 39, 2 (2020), 23–33. Google ScholarCross Ref
44. Aaron W. F. Lee, Wim Sweldens, Peter Schröder, Lawrence C. Cowsar, and David P. Dobkin. 1998. MAPS: Multiresolution Adaptive Parameterization of Surfaces. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1998, Orlando, FL, USA, July 19–24, 1998, Steve Cunningham, Walt Bransford, and Michael F. Cohen (Eds.). ACM, 95–104.Google Scholar
45. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérôme Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (2002), 362–371.Google ScholarDigital Library
46. Hsueh-Ti Derek Liu, Vladimir G. Kim, Siddhartha Chaudhuri, Noam Aigerman, and Alec Jacobson. 2020. Neural subdivision. ACM Trans. Graph. 39, 4 (2020), 124.Google Scholar
47. Hsueh-Ti Derek Liu and Alec Jacobson. 2019. Cubic Stylization. ACM Transactions on Graphics (2019).Google Scholar
48. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local/Global Approach to Mesh Parameterization. Comput. Graph. Forum 27, 5 (2008), 1495–1504.Google ScholarCross Ref
49. Songrun Liu, Zachary Ferguson, Alec Jacobson, and Yotam Gingold. 2017. Seamless: Seam erasure and seam-aware decoupling of shape from mesh resolution. ACM Transactions on Graphics (TOG) 36, 6, Article 216 (Nov. 2017), 15 pages. Google ScholarDigital Library
50. Josiah Manson and Scott Schaefer. 2011. Hierarchical Deformation of Locally Rigid Meshes. Comput. Graph. Forum 30, 8 (2011), 2387–2396. Google ScholarCross Ref
51. Aleka McAdams, Eftychios Sifakis, and Joseph Teran. 2010. A Parallel Multigrid Poisson Solver for Fluids Simulation on Large Grids. In Proceedings of the 2010 Eurographics/ACM SIGGRAPH Symposium on Computer Animation, SCA 2010, Madrid, Spain, 2010, Zoran Popovic and Miguel A. Otaduy (Eds.). Eurographics Association, 65–73.Google Scholar
52. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. 30, 4 (2011), 37.Google ScholarDigital Library
53. Xinlai Ni, Michael Garland, and John C. Hart. 2004. Fair morse functions for extracting the topological structure of a surface mesh. ACM Trans. Graph. 23, 3 (2004), 613–622.Google ScholarDigital Library
54. Seungwoo Oh, Jun-yong Noh, and KwangYun Wohn. 2008. A physically faithful multigrid method for fast cloth simulation. Comput. Animat. Virtual Worlds 19, 3–4 (2008), 479–492.Google ScholarCross Ref
55. L. N. Olson and J. B. Schroder. 2018. PyAMG: Algebraic Multigrid Solvers in Python v4.0. https://github.com/pyamg/pyamg Release 4.0.Google Scholar
56. Miguel A. Otaduy, Daniel Germann, Stephane Redon, and Markus H. Gross. 2007. Adaptive deformations with fast tight bounds. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA 2007, San Diego, California, USA, August 2–4, 2007, Michael Gleicher and Daniel Thalmann (Eds.). Eurographics Association, 181–190.Google Scholar
57. Nicolas Ray and Bruno Lévy. 2003. Hierarchical Least Squares Conformal Map. In 11th Pacific Conference on Computer Graphics and Applications, PG 2003, Canmore, Canada, October 8–10, 2003. IEEE Computer Society, 263–270.Google Scholar
58. John W Ruge and Klaus Stüben. 1987. Algebraic multigrid. In Multigrid methods. SIAM, 73–130.Google Scholar
59. Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested cages. ACM Trans. Graph. 34, 6 (2015), 170:1–170:14.Google ScholarDigital Library
60. Ryan Schmidt and Karan Singh. 2010. Meshmixer: An Interface for Rapid Mesh Composition. In ACM SIGGRAPH 2010 Talks (Los Angeles, California) (SIGGRAPH ’10). Association for Computing Machinery, New York, NY, USA, Article 6, 1 pages.Google ScholarDigital Library
61. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: a sparse paged grid structure applied to adaptive smoke simulation. ACM Trans. Graph. 33, 6 (2014), 205:1–205:12.Google ScholarDigital Library
62. Lin Shi, Yizhou Yu, Nathan Bell, and Wei-Wen Feng. 2006. A fast multigrid algorithm for mesh deformation. ACM Trans. Graph. 25, 3 (2006), 1108–1117.Google ScholarDigital Library
63. Xiaohan Shi, Hujun Bao, and Kun Zhou. 2009. Out-of-core multigrid solver for streaming meshes. ACM Trans. Graph. 28, 5 (2009), 173. Google ScholarDigital Library
64. Mélina Skouras, Bernhard Thomaszewski, Bernd Bickel, and Markus H. Gross. 2012. Computational Design of Rubber Balloons. Comput. Graph. Forum 31, 2 (2012), 835–844.Google ScholarDigital Library
65. Oded Stein, Alec Jacobson, Max Wardetzky, and Eitan Grinspun. 2020. A Smoothness Energy without Boundary Distortion for Curved Surfaces. ACM Trans. Graph. 39, 3 (2020), 18:1–18:17.Google ScholarDigital Library
66. Rasmus Tamstorf, Toby Jones, and Stephen F. McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph. 34, 6 (2015), 245:1–245:13.Google ScholarDigital Library
67. Philip Trettner and Leif Kobbelt. 2020. Fast and Robust QEF Minimization using Probabilistic Quadrics. Comput. Graph. Forum 39, 2 (2020), 325–334. Google ScholarCross Ref
68. Ulrich Trottenberg, Cornelius W Oosterlee, and Anton Schuller. 2000. Multigrid. Elsevier.Google Scholar
69. Petr Vanek, Jan Mandel, and Marian Brezina. 1996. Algebraic Multigrid by Smoothed Aggregation for Second and Fourth Order Elliptic Problems. Computing 56, 3 (1996), 179–196.Google ScholarCross Ref
70. Zhendong Wang, Longhua Wu, Marco Fratarcangeli, Min Tang, and Huamin Wang. 2018. Parallel Multigrid for Nonlinear Cloth Simulation. Comput. Graph. Forum 37, 7 (2018), 131–141.Google ScholarCross Ref
71. D. J. A. Welsh and M. B. Powell. 1967. An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10, 1 (1967), 85–86.Google ScholarCross Ref
72. Zangyueyang Xian, Xin Tong, and Tiantian Liu. 2019. A scalable galerkin multigrid method for real-time simulation of deformable objects. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–13.Google ScholarDigital Library
73. Hui Zhao, Na Lei, Xuan Li, Peng Zeng, Ke Xu, and Xianfeng Gu. 2017. Robust Edge-Preserved Surface Mesh Polycube Deformation. In 25th Pacific Conference on Computer Graphics and Applications, PG 2017 – Short Papers, Taipei, Taiwan, October 16–19, 2017, Jernej Barbic, Wen-Chieh Lin, and Olga Sorkine-Hornung (Eds.). Eurographics Association, 17–22.Google Scholar
74. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (2010), 16:1–16:18.Google ScholarDigital Library