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

  • ©Hsueh-Ti Derek Liu, Jiayi Eris Zhang, Mirela (Miri) Ben-Chen, and Alec Jacobson




    Surface multigrid via intrinsic prolongation



    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

ACM Digital Library Publication: