GCL学术成果：SIGGRAPH 2026-基于非线性多重网格（MG/Opt）的单射映射框架

近日，SIGGRAPH 2026 接收成果公布，来自中国科学技术大学数学科学学院GCL实验室的陈仁杰研究团队提出了一种基于非线性多重网格（MG/Opt）的优化框架，用于最小化 Total Lifted Content（TLC）能量，从而实现单射映射。

计算单纯形网格的局部单射嵌入是几何处理中参数化、变形与体映射等任务的基础问题。尽管已有工作提出了多种光滑能量（如Total Lifted Content（TLC）能量）以保证单射性，但这类非凸能量的高效优化仍然是核心瓶颈：一阶方法常陷入严重的“停滞”，二阶方法则受限于海森矩阵组装与大规模线性求解，难以扩展到高分辨率网格。

为突破这一局限，本文引入非线性多重网格（MG/Opt）框架，直接在多尺度网格上优化非凸能量，而非在每一层仅求解线性化系统。然而，将 MG/Opt 成功应用于单射映射计算并非平凡。单纯形非结构化网格缺乏规则网格的嵌套结构，要求层级算子在设计时严格保持几何与数学的一致性；多尺度更新必须始终构成对原始非线性能量的有效下降方向，否则可能破坏优化稳定性；而初始状态中密集存在的翻转单元，也会显著降低传统平滑算子的有效性。

为此，本文构建了一个面向单射映射的非线性多重网格框架，并以TLC能量为优化目标进行实例化。我们在多层级网格上引入梯度一致性修正项，确保各层校正量始终沿原能量的下降方向演化；构造了区分状态变量与能量梯度的延拓与限制算子，以适应非结构化分片线性网格的特性；同时采用基于 Hessian 矩阵对角近似的无矩阵光滑器，在不显式组装全 Hessian 的前提下大幅降低单步计算成本，并结合自适应参数退火策略，使多重网格能够从密集翻转中快速恢复。

实验结果表明，该 MG/Opt 框架在全部二维及绝大多数三维数据集上均达到100%的成功率，并在高分辨率网格上相比拟牛顿与投影牛顿求解器最高实现63倍加速。综上，本文将非线性多重网格系统地引入单射映射计算，在保留 TLC 能量理论保证的同时显著提升了求解效率与可扩展性，为大规模几何处理任务提供了一种高效、鲁棒的数值解决方案。

算法框架：基于Total Lifted Content (TLC)的单射映射 本文的目标是计算 d 维（d=2,3）单纯形网格M在目标边界B内的局部单射嵌入。核心难点在于：初始配置往往并非单射，需要在优化过程中逐步消除所有翻转单元，使每个三角形或四面体始终保持正向定向。

一种直观思路是直接最小化网格的总无符号面积（total unsigned area），但无符号面积在退化构型处是非光滑的，不利于梯度驱动的数值优化。为此，Du 等人提出的Total Lifted Content（TLC）能量引入一个固定的辅助单纯形t̃‌，通过“升维（lifting）”操作将原始构型映射到更高维空间，从而构造出全局C∞光滑的能量。单个单纯形t的 TLC 能量定义为：

其中和分别表示原单纯形与辅助单纯形的边向量矩阵，α>0控制提升强度。整个网格的总能量则为所有单元能量之和：

该形式在翻转或退化状态下依然良定，且在α足够小时，其全局最小值理论上保证为一个无翻转的单射嵌入。

TLC 能量因其全局光滑性和理论完备性，特别适合与多尺度优化方法结合使用：在整个构型空间中均可稳定地进行梯度计算与优化，而不会像传统势垒能量那样在翻转区域产生数值奇异，从而为后续非线性多重网格优化奠定了坚实基础。

非线性多重网格优化框架（MG/Opt）

TLC 能量在全构型空间内全局光滑且良定，非常适合采用多尺度优化加速。传统线性多重网格通过限制（restriction）与延拓（prolongation）算子在不同层级间传递残差与校正，在粗网格上高效消除低频误差，在细网格上通过局部平滑抑制高频误差，对椭圆问题通常可达到最优O(N)复杂度。然而，将其直接用于非线性几何优化时，若采用 Newton–Multigrid 策略，则需在每一层组装并求解形如Hx=-g的线性系统，导致最细层 Hessian 矩阵的存储与计算代价过高，抵消了多重网格的效率优势。

为此，本文采用MG/Opt 框架，由Nash提出，直接在嵌套的多层网格上优化非线性能量，而无需在最细层显式组装 Hessian。其核心是一个递归的V-cycle：在最细层进行预平滑以消除高频误差；将当前解限制到粗层 ；在粗层构造并优化修正后的能量泛函；再将粗层校正延拓回细层，并通过线搜索更新细层解。

梯度一致性与替代能量 MG/Opt 的关键创新在于通过线性修正项保证层级间的梯度一致性。在第l+1层，并不直接最小化原始 TLC 能量，而是最小化如下替代能量：

其中为粗层离散 TLC 能量，为修正向量，定义为:

该构造保证了起始点处粗层梯度与细层梯度的限制完全一致：

这一同步机制是算法稳定性的基石：任何在粗层获得的下降方向，延拓回细层后仍然是有效的下降方向。

无矩阵平滑与翻转恢复机制

在 MG/Opt 的多尺度框架下，平滑算子的效率直接决定整体计算性能。为避免全 Hessian 组装带来的高昂存储与计算代价，本文采用无矩阵 Jacobi 平滑器。在 V‑cycle 的每一层，仅计算 Hessian的对角项，并对其取绝对值，以保证非凸 TLC 能量下的数值稳定性与下降性。平滑更新方向由高效给出，其单步开销与一阶方法相当。

尽管 Jacobi 平滑能有效抑制大多数高频误差，但在复杂几何中仍可能出现局部翻转簇，即少量相邻单元持续保持翻转状态。为防止此类结构导致算法停滞，我们在全局平滑基础上引入针对性翻转恢复机制：

●每 100 次迭代检测一次翻转单元数量；

●若翻转单元少于 10 个，提取其3‑邻域网格，并在该局部子网格上执行 100 次投影牛顿（PN）迭代；

●若翻转单元超过 10 个，则进一步划分连通分量，对平均面积小于全局均值 1/20 的分量，构造7邻域，并在固定边界条件下施加局部Tutte重参数化。

该策略以极低的计算代价隔离并消除顽固翻转区域，有效避免了单尺度一阶方法常见的停滞问题，从而显著提高了整体收敛成功率与鲁棒性。

结果展示 为全面评估求解器在鲁棒性与可扩展性方面的表现，本文构建并采用了两类测试数据集：

标准基准数据集（[Du et al. 2020]采用的数据集）

该集合涵盖多种典型几何映射任务，用于验证算法在常规场景下的稳定性：

2D 玩具示例（Simple）：基础几何映射测试；字母轮廓嵌入（Letters）：将曲面映射至 “S‑G‑R‑A‑P‑H” 字母轮廓；无交叠映射（[Liu et al. 2018]数据集）：验证避免重叠与翻转的能力；3D 多立方体映射（PolyCube）：测试复杂体网格的单射嵌入；球面与自由曲面映射（Sphere、Surface）：评估曲面参数化质量；高扭曲增量变形（Armadillo、Cube、Rod）：检验在极端几何畸变下的稳定性。

压力测试数据集（本文新增）

为进一步探索求解器极限，本文设计了更具挑战性的测试集：

细分字母数据集（Letters_div）：对 Letters 进行高分辨率细分，用于评估算法在大规模网格上的可扩展性；非凸 2D 映射（Polygons）：将 Liu 等人数据集的边界映射至独立非凸多边形，测试非凸约束下的鲁棒性；柱状字母映射（Letters3d）：将立方体映射至柱状字母边界并进行剧烈变形，模拟复杂三维拓扑变化；VOLMAP 体积测试集：选自 [Cherchi et al. 2023]的网格案例。

测试结果如下：

论文发表

该工作已被计算机图形学顶级国际会议 SIGGRAPH 2026 接收。

论文原文

● 论文标题：Nonlinear Multigrid for Injective Embedding

● 作者：Yu Zhao, Renjie Chen

● 单位：中国科学技术大学