Conference

A Fast Geometric Multigrid Method for Curved Surfaces

Ruben Wiersma, Ahmad Nasikun, Elmar Eisemann, Klaus Hildebrandt

Delft University of Technology

SIGGRAPH 2023Geometry & ModelingGeometry ProcessingMultigrid MethodLaplace OperatorPoint CloudPoisson Problem
PaperProject

一句话总结

提出 Gravo MG（graph Voronoi multigrid），一种基于点云表示的几何多重网格方法：用图 Voronoi 图快速构建多层级层次结构，求解速度媲美当前最优的内蕴多重网格，而层次构建时间快一个数量级以上，并且能同时支持三角网格、点云、非流形网格与多边形网格。

研究背景

  • 领域现状：几何处理里大量问题（数据平滑、Poisson 问题、几何流、物理仿真）最终都归结为在曲面上求解稀疏线性系统。几何多重网格（GMG）通过在多层网格上做迭代求解，往往比稀疏直接求解器更高效。
  • 核心痛点：曲面上的 GMG 主要有两条路线，各有短板。一是先做网格粗化再在层级间建立映射（代表作是 Liu 等人的内蕴多重网格），延拓算子好、收敛快，但层次构建代价高昂；二是直接对输入网格的边图做粗化（Shi 等人），构建快但收敛慢。此外这些方法大多只适用于流形三角网格。
  • 本文 idea：把两条路线的优点合起来。用点云与邻居图表示各层级以获得快速构建，同时借助几何操作在延拓算子构建时生成局部三角形以保证快速收敛。核心构想是”在从曲面采样的点上模拟内蕴 Delaunay 三角化”，并把这一想法迁移到点云设定下。

方法

整体框架：多重网格求解沿用标准的 V-cycle（前松弛 → 递归到粗层做修正 → 后松弛，松弛用 Gauss–Seidel），本文的贡献集中在如何逐层构建层次结构与延拓矩阵。每一层从细层的图 \(\{V_l, E_l\}\) 出发，经过采样、图 Voronoi 邻居图、三角形延拓三步，产出粗层的图 \(\{V_{l+1}, E_{l+1}\}\) 和延拓矩阵 \(P_l\)，重复直到最粗层。

flowchart LR
  A["网格 / 点云 + 邻居图"] --> B["均匀子采样得到粗层节点"]
  B --> C["图 Voronoi 图 (多源 Dijkstra)"]
  C --> D["Voronoi 邻接构候选三角形"]
  D --> E["细点投影取重心坐标 -> 延拓矩阵 P_l"]
  E --> F["下一层"]

关键设计：

  1. 快速均匀采样。希望每层点数按固定比例递减且空间分布均匀。作者用一种基于最大独立集的贪心扫描：遍历所有点，遇到可用点就加入采样集并把其测地半径 \(r\) 内的点标记为不可用。半径由保留比例 \(\phi\) 和平均边长 \(\hat{e}\) 决定，\(r = \phi^{-\frac{1}{3}}\hat{e}\)。实验取 \(\phi = 1/8\)、粗化到 1000 点停止，并把邻近点搜索限制在 2-ring 上，在构建速度和采样质量间取得平衡。相比 Shi 等人必须是最大 \(\delta\)-独立集超集的约束，这种采样能以更高衰减率减少层数。

  2. 图 Voronoi 邻居图。把粗层点 \(V_{l+1}\) 作为种子，在细层图上用多源 Dijkstra 计算图 Voronoi 图：每个细点归属于图距离最近的种子。若两个种子的 Voronoi 单元之间存在连接边，就在粗层加一条边。这样得到的邻居关系直接作为下一层的边集 \(E_{l+1}\)。

  3. 三角形延拓。借助 Voronoi 图与 Delaunay 三角化的对偶性，从粗层边构造所有三元组候选三角形。对每个细点 \(p\)，在其最近粗点所属的三角形中找最近的三角形，用投影点的重心坐标作为延拓权重填入 \(P_l\)。这样得到的延拓矩阵每行最多三个非零项，非常稀疏，因而层间映射与限制矩阵 \(P_l^\top A P_l\) 都很快。权重在切向方向上分布均衡是快速收敛的关键。

  4. 退化处理与稀疏优化。当邻域内点近似共线或细点落在三角形外（约 0.25% 的情形）时，退回到取最近三点用反距离权重。此外，把采样点先移到其 Voronoi 单元的均值位置再做投影，可减少延拓矩阵中的单元素行，略微改善求解时间。

实验结果

主实验是在 40+ 个大规模模型（流形网格、非流形网格、点云）上求解 Poisson 问题（\(\eta = 10^{-6}\)，容差 \(10^{-4}\)），对比层次构建时间（Hier）、迭代次数（#It）与求解时间（Solve）。下表摘取若干代表模型，凸显核心结论：本方法层次构建远快于 Liu 等人、求解时间与之相当，且明显快于 Shi 等人。

模型 (#顶点) 本文 Hier / Solve Liu 2021 Hier / Solve Shi 2006 Hier / Solve
Bimba (502k) 0.43 / 0.65 15.58 / 0.74 0.24 / 4.16
Nefertiti (1m) 0.89 / 0.94 34.22 / 1.18 0.56 / 11.69
XYZ Dragon (3.6m) 3.24 / 5.32 121.97 / 5.32 1.57 / 28.95

平均而言，本文的层次构建比 Liu 等人快约 36 倍，仅比 Shi 等人慢约 1.8 倍；求解时间上 Liu 等人平均多花约 3%（Poisson）、Shi 等人多花约 274%（Poisson）。对所有超过 100k 顶点的网格，本方法在 Poisson 问题上都快于 Liu 等人。相比高度优化并行的 Pardiso 直接求解器，单次求解 Poisson 有 92% 的模型更快。此外在数据平滑、共形流、气球充气仿真三个应用中，由于系统矩阵随参数或时间步变化、直接求解器需反复重新分解，本方法的多次求解优势更明显。

亮点与局限

  • 亮点：
    • 用点云 + 图 Voronoi 表示层级，构建极快，同时靠”模拟 Delaunay 三角化 + 重心坐标”保住了快速收敛，兼得两条路线的长处。
    • 延拓矩阵每行至多三项，稀疏高效；限制矩阵是延拓的转置，保证粗层修正的对称性。
    • 通用性强：不依赖流形性质，天然适用于点云、非流形网格、多边形网格，配合鲁棒 Laplacian 即可求解。
  • 局限：
    • 多重网格在较高残差处停止，精度不及直接求解器，需要高精度解的场景仍应选直接法。
    • 图 Voronoi 生成的三角形不保证是 Delaunay，也不保证构成流形，缺乏理论上的三角化质量保证。
    • 当前实现单线程未并行；作者也指出退化情形（近共线）需专门兜底处理。

延伸思考

  • 论文提出的”从图 Voronoi 图快速得到高质量三角形与均匀采样”这一副产品本身颇有价值，可能推动点云处理中快速三角化/重采样的独立应用。
  • 作者展望把该求解器作为 GMRES / CG 等 Krylov 方法的预条件子来进一步加速，以及并行化层次构建与求解，这两条都是把方法推向实用规模的自然方向。
  • 相比 AMG 用系统矩阵建层次（矩阵一变就要重建），本方法只在域变化时才重建层次，因此特别适合”域固定、反复改变系统矩阵”的交互式几何处理与仿真迭代场景。