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.
翻译:本文为未结构的曲线表面引入了新型的几何多格化求解器。 多元格化方法是解决线性方程式系统的高效迭代方法。 尽管在解决结构化域定义的问题方面取得了成功, 将多格化法推广到非结构化曲线域仍然是一个挑战性的问题。 关键缺失的成分是将功能转移到不同多格化级的延长操作器。 我们提出了一个基于内在几何方法计算三角形表面延长时间的新方法, 使曲线表层能够有一个高效的几何多格化求解器。 我们的表面多格化求解器比现有的多格化法更能融合。 与直接求解器相比, 我们的求解器速度更快。 我们评估了许多几何处理应用程序的方法, 以及有边界和无边界的多种复杂形状。 我们简单地替换直接求解器, 将现有的算法升级为互动框架率, 并将计算瓶颈从解决线性系统上移开。