SIGGRAPH 2023

A Fast Geometric Multigrid Method for Curved Surfaces

Ruben Wiersma¹, Ahmad Nasikun^{1, 2} (equal contribution); Elmar Eisemann¹; and Klaus Hildebrandt¹
¹Delft University of Technology, ²Universitas Gadjah Mada

Code Paper PDF Supplement PDF Presentation Cite

Abstract

We introduce a geometric multigrid method for solving linear systems arising from variational problems on surfaces in geometry processing, Gravo MG. Our scheme uses point clouds as a reduced representation of the levels of the multigrid hierarchy to achieve a fast hierarchy construction and to extend the applicability of the method from triangle meshes to other surface representations like point clouds, nonmanifold meshes, and polygonal meshes. To build the prolongation operators, we associate each point of the hierarchy to a triangle constructed from points in the next coarser level. We obtain well-shaped candidate triangles by computing graph Voronoi diagrams centered around the coarse points and determining neighboring Voronoi cells. Our selection of triangles ensures that the connections of each point to points at adjacent coarser and finer levels are balanced in the tangential directions. As a result, we obtain sparse prolongation matrices with three entries per row and fast convergence of the solver.

Full presentation

Fast Forward

Learn more

Find out more about Gravo MG in our paper, or come see our (virtual) presentation at SIGGRAPH 2023.

Code Paper PDF Supplement PDF Presentation Cite

Contact

r.t.wiersma [at] tudelft.nl, k.a.hildebrandt [at] tudelft.nl

Computer Graphics and Visualization group TU Delft

Cite

@Article{WiersmaNasikun2023GravoMG,
  author    = {Ruben Wiersma, Ahmad Nasikun, Elmar Eisemann, Klaus Hildebrandt},
  journal   = {SIGGRAPH 2023},
  title     = {A Fast Geometric Multigrid Method for Curved Surfaces},
  year      = {2023},
  month     = jul,
  number    = {4},
  volume    = {41},
  doi       = {10.1145/3588432.3591502},
  publisher = {ACM}
}