A Fast Geometric Multigrid Method for Curved Surfaces

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

13 Downloads (Pure)


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. Code is available at https://graphics.tudelft.nl/gravo_mg.
Original languageEnglish
Title of host publicationSIGGRAPH '23: ACM SIGGRAPH 2023 Conference Proceedings
EditorsStephen N. Spencer
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Number of pages11
ISBN (Electronic)9798400701597
ISBN (Print)979-8-4007-0159-7
Publication statusPublished - 2023
SIGGRAPH '23: Special Interest Group on Computer Graphics and Interactive Techniques Conference
- Los Angeles, United States
Duration: 6 Aug 202310 Aug 2023

Publication series

NameProceedings - SIGGRAPH 2023 Conference Papers


Country/TerritoryUnited States
CityLos Angeles


  • geometry processing
  • multigrid methods
  • Poisson problems
  • geometric multigrid
  • Laplace matrix

Cite this