第5章：Mesh处理与优化

在实际应用中，原始的3D mesh往往不能直接满足需求：扫描数据包含噪声、CAD模型过于精细、重建网格存在拓扑缺陷。本章将系统介绍mesh处理与优化的核心算法，包括简化、细分、平滑、修复和重网格化技术。这些技术是3D内容创作管线中的关键环节，直接影响渲染性能、存储效率和视觉质量。

学习目标：

• 掌握基于QEM的网格简化算法及其数学原理
• 理解Loop和Catmull-Clark细分的差异与适用场景
• 熟练运用Laplacian平滑和双边滤波进行去噪
• 学会诊断和修复常见的网格缺陷
• 掌握重网格化技术，生成高质量的三角形网格
• 理解特征保持和各向异性处理的高级技术

5.1 基于QEM的网格简化

网格简化是减少多边形数量同时保持视觉质量的关键技术。Quadric Error Metrics (QEM)算法通过最小化几何误差实现高质量简化。

5.1.1 二次误差度量

QEM的核心思想是用二次形式表示顶点到相关平面集合的距离平方和。对于顶点$v = [x, y, z, 1]^T$，其误差定义为：

$$E(v) = v^T Q v$$ 其中$Q$是4×4对称矩阵，称为二次误差矩阵。对于平面$\pi: n^T p + d = 0$（$n$为单位法向量），其贡献的误差矩阵为： $$Q_\pi = \begin{bmatrix} n_x^2 & n_x n_y & n_x n_z & n_x d \\ n_x n_y & n_y^2 & n_y n_z & n_y d \\ n_x n_z & n_y n_z & n_z^2 & n_z d \\ n_x d & n_y d & n_z d & d^2 \end{bmatrix}$$ 顶点的总误差矩阵是所有相邻面片贡献的和： $$Q = \sum_{\pi \in \text{planes}(v)} Q_\pi$$

5.1.2 边收缩操作

简化通过迭代执行边收缩操作实现。对于边$(v_1, v_2)$，收缩后生成新顶点$\bar{v}$，其误差矩阵为： $$Q_{\bar{v}} = Q_{v_1} + Q_{v_2}$$ 最优收缩位置通过最小化误差得到： $$\bar{v} = \arg\min_v (v^T Q_{\bar{v}} v)$$ 当$Q$的左上3×3子矩阵可逆时，最优解为： $$\bar{v} = -Q^{-1}_{3×3} \cdot q_{4}$$ 其中$q_4$是$Q$的第四列前三个元素。

5.1.3 算法流程

1. 初始化：计算所有顶点的误差矩阵
2. 对每条边：
   - 计算收缩代价（最优位置的误差）
   - 插入优先队列（最小堆）
3. 迭代简化：
   - 取出代价最小的边
   - 执行边收缩
   - 更新相邻边的收缩代价
4. 直到达到目标面片数

5.1.4 边界和特征保持

对于mesh边界和尖锐特征，需要特殊处理：

• 边界约束：边界边只能沿边界收缩
• 特征检测：二面角大于阈值的边标记为特征
• 权重调整：增加特征边的收缩代价

ASCII图示例：

收缩前:          收缩后:
    v1              
   /|\             /\
  / | \           /  \
 /  |  \    =>   /    \
/___|___\       /______\
v3  v2  v4      v3  v̄  v4

5.2 Loop与Catmull-Clark细分

细分曲面通过递归细化网格来生成平滑曲面，是建模和动画中的重要技术。Loop细分适用于三角形网格，Catmull-Clark适用于四边形网格。

5.2.1 Loop细分算法

Loop细分是针对三角形网格的细分方案，每次细分将一个三角形分成四个：

新顶点计算：

1. 边点（Edge vertices）：对于边$(v_1, v_2)$，相邻两个三角形的对角顶点为$v_3, v_4$： $$v_{edge} = \frac{3}{8}(v_1 + v_2) + \frac{1}{8}(v_3 + v_4)$$

2. 旧顶点更新（Vertex vertices）：对于度为$n$的内部顶点$v$，邻接顶点为$v_i$： $$v_{new} = (1 - n\beta)v + \beta\sum_{i=1}^{n}v_i$$ 其中$\beta = \frac{1}{n}(\frac{5}{8} - (\frac{3}{8} + \frac{1}{4}\cos\frac{2\pi}{n})^2)$

Warren建议的简化版本：$\beta = \frac{3}{16}$（$n=3$）或$\beta = \frac{3}{8n}$（$n>3$）

拓扑细分规则：

原始三角形:        细分后:
    v1                v1
    /\               /\
   /  \             /e3\
  /    \      =>   /----\
 /      \         /\    /\
/________\       /__\/__\
v2      v3      v2 e1 e2 v3

5.2.2 Catmull-Clark细分

Catmull-Clark细分是最通用的细分方案，可处理任意多边形网格：

新顶点计算：

1. 面点（Face vertices）：多边形中心 $$F = \frac{1}{n}\sum_{i=1}^{n}v_i$$

2. 边点（Edge vertices）： $$E = \frac{1}{4}(v_1 + v_2 + F_1 + F_2)$$ 其中$v_1, v_2$是边的端点，$F_1, F_2$是相邻面的面点

3. 顶点更新： $$V_{new} = \frac{F + 2R + (n-3)V}{n}$$ 其中$F$是相邻面点均值，$R$是相邻边中点均值，$n$是顶点度

5.2.3 细分矩阵与极限曲面

细分可表示为矩阵运算： $$P^{k+1} = S \cdot P^k$$ 其中$S$是细分矩阵。极限曲面的性质由$S$的特征值决定：

• 最大特征值$\lambda_0 = 1$（仿射不变性）
• 次大特征值$\lambda_1 = \lambda_2$（正则性）
• $\lambda_1 > \lambda_3$（曲率有界）

5.2.4 自适应细分

均匀细分会产生大量多边形，自适应细分根据曲率动态调整：

判断准则:
if (曲率 > 阈值 || 视角依赖误差 > 阈值) {
    细分此区域
} else {
    保持当前分辨率
}

T-junction处理是自适应细分的关键挑战。

5.3 Laplacian平滑与双边滤波

网格去噪是处理扫描数据的必要步骤。Laplacian平滑和双边滤波是两种经典方法，前者简单高效，后者能保持特征。

5.3.1 离散Laplace算子

对于网格顶点$v_i$，离散Laplace算子定义为： $$\Delta v_i = \frac{1}{|N_i|}\sum_{j \in N_i}(v_j - v_i)$$ 其中$N_i$是$v_i$的一环邻域。加权版本使用cotangent权重： $$\Delta v_i = \frac{1}{2A_i}\sum_{j \in N_i}(\cot\alpha_{ij} + \cot\beta_{ij})(v_j - v_i)$$ $\alpha_{ij}$和$\beta_{ij}$是边$(v_i, v_j)$对应的两个对角。

5.3.2 显式Laplacian平滑

最简单的平滑方法是迭代更新顶点位置： $$v_i^{(k+1)} = v_i^{(k)} + \lambda\Delta v_i^{(k)}$$ 其中$\lambda \in (0,1)$是平滑因子。此方法等价于求解热扩散方程： $$\frac{\partial v}{\partial t} = \Delta v$$ 收敛性分析：

• 稳定条件：$\lambda < \frac{2}{\lambda_{max}}$（$\lambda_{max}$是Laplace矩阵最大特征值）
• 收缩问题：长时间迭代导致体积收缩

5.3.3 隐式Laplacian平滑

隐式方法通过求解线性系统避免稳定性限制： $$(I - \lambda\Delta t L)V^{(k+1)} = V^{(k)}$$ 其中$L$是Laplace矩阵，$\Delta t$是时间步长。

优点：

• 无条件稳定
• 大时间步长
• 更好的低频滤波

5.3.4 双边滤波

双边滤波同时考虑空间距离和法向差异，保持尖锐特征： $$v_i^{new} = v_i + \frac{\sum_{j \in N_i} w_s(|p_j - p_i|)w_n(|n_j \cdot n_i|)(c_j - p_i)\cdot n_i}{\sum_{j \in N_i} w_s(|p_j - p_i|)w_n(|n_j \cdot n_i|)} \cdot n_i$$ 其中：

• $w_s$：空间权重函数（高斯核）
• $w_n$：法向权重函数
• $c_j$：邻域顶点$v_j$在$v_i$法向的投影

典型权重函数： $$w_s(d) = \exp(-d^2/2\sigma_s^2)$$ $$w_n(x) = \exp(-(1-x)^2/2\sigma_n^2)$$

5.3.5 各向异性扩散

根据局部几何自适应调整平滑强度： $$\frac{\partial v}{\partial t} = \nabla \cdot (g(|\nabla v|)\nabla v)$$ 其中$g$是边缘停止函数： $$g(x) = \frac{1}{1 + (x/K)^2}$$ ASCII示意图：

噪声网格:        Laplacian平滑:      双边滤波:
  /\  /\          ___                 /\
 /  \/  \   =>   /   \      或      /  \
/        \      /     \            /    \
（失去特征）     （平滑）          （保持特征）

5.4 网格修复：孔洞填充与自相交处理

实际扫描和重建的网格常包含各种缺陷：孔洞、自相交、非流形边、退化三角形等。这些缺陷严重影响后续处理和应用：渲染产生artifacts、物理模拟不稳定、3D打印失败。本节介绍系统的诊断和修复技术，从理论算法到工程实践。

5.4.1 网格缺陷诊断

常见缺陷类型：

1. 孔洞：边界环未闭合的区域
2. 自相交：面片相互穿透
3. 非流形：边连接超过2个面，或顶点邻域不同胚于圆盘
4. 退化元素：零面积三角形、重复顶点
5. 法向不一致：相邻面片法向相反

检测算法：

边界检测: 度为1的半边
非流形边: 连接>2个面的边
自相交: AABB树加速的面片相交测试
退化检测: 面积 < ε 或 边长 < ε

5.4.2 孔洞填充算法

基于最小面积的填充：

对于边界环$B = \{v_1, v_2, ..., v_n\}$，寻找三角剖分使总面积最小：

动态规划解法： $$A(i,j) = \min_{i<k<j}\{A(i,k) + A(k,j) + Area(v_i, v_k, v_j)\}$$ 时间复杂度：$O(n^3)$

基于AFT的填充（Advancing Front Triangulation）：

1. 初始化前沿为边界环
2. 选择最短边$(v_i, v_{i+1})$
3. 寻找最优第三点$v_k$： - 最小化二面角 - 避免自相交
4. 更新前沿，重复直到闭合

体积扩散法：

将孔洞区域视为薄膜，求解最小曲面问题： $$\min \int\int_S |\nabla u|^2 dS$$ 边界条件：$u|_{\partial S} = u_{boundary}$

5.4.3 自相交检测与修复

空间划分加速：

使用AABB树或八叉树加速相交检测：

构建AABB树(mesh)
for each 面片对(f1, f2):
    if AABB(f1) ∩ AABB(f2) ≠ ∅:
        精确相交测试(f1, f2)

修复策略：

1. 局部重网格化：删除相交区域，重新三角化
2. 布尔运算：计算自并集$M' = M \cup M$
3. 隐式表面重建：转换为SDF，重新提取等值面

5.4.4 非流形结构处理

顶点分裂： 对于非流形顶点，根据连通分量分裂：

检测顶点v的面片连通分量
for each 分量C:
    创建新顶点v'
    将C中的面片连接到v'

边分裂： 非流形边连接多个面片扇，需要分离：

    f1
    /\
   /  \
e1 ---- e2  <- 非流形边
   \  /
    \/
    f2

5.4.5 网格定向

确保所有面片法向一致：

传播算法：

1. 选择种子面片，确定朝向
2. BFS遍历相邻面片
3. 检查共享边的顶点顺序：
   if 顺序相反: 保持朝向
   else: 翻转面片

4. 对每个连通分量重复

全局优化： 最小化法向不一致的边数： $$\min \sum_{(i,j) \in E} (1 - o_i \cdot o_j)$$ 其中$o_i \in \{-1, 1\}$表示面片朝向。

这是一个NP难问题，但可用图割算法近似求解。对于大规模网格，启发式传播算法通常足够有效。

5.5 重新网格化（Remeshing）

重新网格化是改善网格质量的综合技术，目标是生成具有良好几何和拓扑性质的新网格：均匀采样、规则连接度、等边三角形。这对数值模拟、参数化和压缩至关重要。

5.5.1 网格质量度量

评估三角形质量的常用指标：

形状质量：

• 长宽比（Aspect Ratio）：$AR = \frac{l_{max}}{2r_{in}}$，其中$l_{max}$是最长边，$r_{in}$是内切圆半径
• 等边性（Equilateral Measure）：$Q = \frac{4\sqrt{3}A}{p^2}$，其中$A$是面积，$p$是周长
• 最小角：$\theta_{min} = \min(\theta_1, \theta_2, \theta_3)$，理想值60°

尺寸场适应性： 给定尺寸场$h(x)$，边$e_{ij}$的相对长度： $$l_{rel} = \frac{|v_i - v_j|}{\frac{h(v_i) + h(v_j)}{2}}$$ 理想范围：$l_{rel} \in [0.7, 1.4]$

度规适应性： 对于各向异性度规$M(x)$（3×3正定矩阵），边长度： $$l_M = \sqrt{(v_j - v_i)^T M(\frac{v_i + v_j}{2})(v_j - v_i)}$$

5.5.2 增量重网格化

通过局部操作迭代改善网格质量：

基本操作集：

1. 边分裂（Split）：长边一分为二
2. 边收缩（Collapse）：短边收缩为点
3. 边翻转（Flip）：改变边连接关系
4. 顶点平滑（Smooth）：优化顶点位置

算法框架：

for iteration = 1 to max_iter:
    // 1. 分裂长边
    for each edge e with length > 4/3 * target_length:
        split(e)

    // 2. 收缩短边
    for each edge e with length < 4/5 * target_length:
        if collapse_preserves_topology(e):
            collapse(e)

    // 3. 翻转改善质量
    for each edge e:
        if flip_improves_quality(e):
            flip(e)

    // 4. 切向平滑
    for each vertex v:
        smooth_tangential(v)

切向平滑： 保持顶点在原始曲面上，只在切平面内移动： $$v_{new} = v + P_T(v_{smooth} - v)$$ 其中$P_T$是切平面投影算子：$P_T = I - nn^T$

5.5.3 CVT基重网格化

Centroidal Voronoi Tessellation (CVT)生成高质量的均匀网格：

Lloyd算法：

1. 初始化$n$个种子点$\{s_i\}$
2. 迭代： - 计算Voronoi图$\{V_i\}$ - 移动种子到质心：$s_i = \frac{\int_{V_i} x \rho(x)dx}{\int_{V_i} \rho(x)dx}$
3. 提取Delaunay三角化

受限于曲面的CVT： 种子点和Voronoi图都限制在曲面$S$上：

• 使用测地距离计算Voronoi区域
• 质心投影回曲面

能量优化视角： CVT最小化量化误差： $$E = \sum_{i=1}^{n} \int_{V_i} \rho(x)|x - s_i|^2 dx$$ 这等价于k-means聚类的连续版本。

5.5.4 各向异性重网格化

根据曲率自适应调整网格密度和方向：

曲率驱动的度规场： 基于主曲率$\kappa_1, \kappa_2$构造度规： $$M = R \begin{bmatrix} h_1^{-2} & 0 & 0 \\ 0 & h_2^{-2} & 0 \\ 0 & 0 & 0 \end{bmatrix} R^T$$ 其中$R$是主方向构成的旋转矩阵，$h_i = \min(\epsilon/|\kappa_i|, h_{max})$

各向异性CVT： 使用Riemannian度规定义的距离： $$d_M(x,y) = \inf_{\gamma} \int_0^1 \sqrt{\dot{\gamma}^T M(\gamma(t)) \dot{\gamma}} dt$$ 其中$\gamma$是连接$x,y$的路径。

5.5.5 特征对齐重网格化

保持和对齐几何特征：

特征检测：

• 二面角阈值：$\theta > 30°$的边标记为特征
• 曲率极值：主曲率的局部极大值
• 用户标注：交互式特征线绘制

约束Delaunay三角化： 确保特征线成为网格边：

1. 在特征线上采样点
2. 执行约束Delaunay三角化（CDT）
3. 优化非特征顶点位置

四边形主导重网格化： 沿主曲率方向生成四边形：

主方向场 -> 参数化 -> 规则采样 -> 四边形提取

ASCII示意图：

原始网格:        均匀重网格:      各向异性:
  /\  /\          △△△△           ——△——
 /  \/  \   =>   △△△△      或    |△|△|
/___/\___\       △△△△           ——△——
（不规则）       （均匀）        （沿特征）

5.6 高级话题

5.6.1 特征保持简化

在简化过程中精确保持几何特征和拓扑特征：

二次误差扩展：

• 法向约束：惩罚法向变化 $$Q_{normal} = w_n \sum_{f \in F} (n_f^T v)^2$$

• 颜色/纹理保持：将属性编码入误差度量 $$v_{extended} = [x, y, z, r, g, b, u, v, 1]^T$$ 特征敏感的边收缩：

• 检测特征边（高曲率、边界、材质边界）

• 限制收缩：特征边只能沿特征收缩
• 拓扑约束：防止改变亏格或连通分量数

外观驱动简化： 基于屏幕空间误差而非几何误差： $$E_{screen} = \sum_{pixels} |I_{original} - I_{simplified}|^2$$ 使用可微渲染计算梯度，优化简化结果。

5.6.2 流驱动的处理

使用几何流演化网格：

平均曲率流（Mean Curvature Flow）： $$\frac{\partial x}{\partial t} = -H \cdot n$$ 其中$H$是平均曲率，$n$是法向。离散化： $$x^{t+1} = x^t - \Delta t \cdot L(x^t)$$ Willmore流： 最小化弯曲能量$E = \int H^2 dA$： $$\frac{\partial x}{\partial t} = -\Delta_S H - 2H(H^2 - K)$$ 其中$K$是Gauss曲率，$\Delta_S$是曲面Laplacian。

应用：

• 去噪：短时间MCF去除高频噪声
• fairing：Willmore流生成美观曲面
• 形状插值：两个形状间的测地线

5.6.3 神经网格处理

深度学习在网格处理中的应用：

学习型简化：

• 训练网络预测边收缩顺序
• 端到端优化感知质量
• 自适应于特定领域（人脸、CAD等）

神经网格去噪：

• PointNet++提取局部特征
• 预测顶点位移场
• 保持细节的同时去除噪声

学习型重网格化：

• 预测最优采样位置
• 学习局部参数化
• 生成领域特定的网格模式

本章小结

本章系统介绍了mesh处理与优化的核心技术：

关键算法：

1. QEM简化：$E(v) = v^T Q v$，通过二次误差度量实现高质量简化
2. 细分曲面：Loop（三角形）和Catmull-Clark（四边形）生成光滑曲面
3. Laplacian平滑：$\Delta v_i = \frac{1}{|N_i|}\sum_{j \in N_i}(v_j - v_i)$，去除高频噪声
4. 双边滤波：同时考虑空间和法向相似性，保持特征
5. 重网格化：通过局部操作或全局优化改善网格质量

核心概念：

• 误差度量与优化
• 多分辨率表示
• 特征检测与保持
• 拓扑修复
• 质量评估指标

实践要点：

• 简化需要平衡视觉质量和多边形数量
• 细分产生大量多边形，考虑自适应策略
• 平滑操作可能改变体积和特征
• 修复算法需要鲁棒处理各种缺陷
• 重网格化改善数值性质但可能丢失细节

练习题

基础题

习题5.1：QEM矩阵计算 给定三角形顶点$v_1 = (0,0,0)$，$v_2 = (1,0,0)$，$v_3 = (0,1,0)$，计算顶点$v_1$的二次误差矩阵$Q$。

习题5.2：Loop细分权重 对于度为6的内部顶点，计算Loop细分的$\beta$值。使用Warren的简化公式和原始公式分别计算。

习题5.3：Laplacian平滑稳定性 给定网格的Laplace矩阵最大特征值$\lambda_{max} = 4$，显式平滑的最大稳定步长是多少？

习题5.4：三角形质量度量 计算等边三角形、直角等腰三角形、退化三角形（三点共线）的等边性度量$Q = \frac{4\sqrt{3}A}{p^2}$。

挑战题

习题5.5：自适应QEM简化 设计一个改进的QEM算法，根据视点自适应调整简化程度。屏幕空间投影面积大的区域保留更多细节。

习题5.6：拓扑保持的网格简化 证明边收缩操作可能改变网格的拓扑（如亏格），并设计检测算法防止此类改变。

习题5.7：最优传输重网格化 使用最优传输理论设计重网格化算法，最小化Wasserstein距离。

习题5.8：深度学习网格去噪 设计一个基于图神经网络的mesh去噪架构，输入噪声顶点位置，输出去噪位置。

常见陷阱与错误（Gotchas）

数值稳定性问题

1. QEM矩阵奇异 - 问题：平面共线时矩阵不可逆 - 解决：添加正则化项$Q' = Q + \epsilon I$

2. 浮点精度丢失 - 问题：大模型坐标值范围大 - 解决：中心化坐标，使用相对误差

3. Laplacian平滑发散 - 问题：步长过大导致振荡 - 解决：自适应步长或隐式方法

拓扑破坏

1. 自相交生成 - 问题：aggressive简化产生折叠 - 解决：相交检测，限制收缩

2. 非流形产生 - 问题：边收缩创建非流形结构 - 解决：检查link condition

3. 孔洞误填充 - 问题：错误识别边界 - 解决：用户确认，保守策略

特征丢失

1. 过度平滑 - 问题：迭代次数过多 - 解决：自适应迭代，特征检测

2. 尖锐边模糊 - 问题：uniform权重 - 解决：特征敏感权重

3. 纹理坐标破坏 - 问题：几何操作未更新UV - 解决：同步更新所有属性

性能问题

1. 优先队列失效 - 问题：局部更新导致堆破坏 - 解决：懒惰删除，版本标记

2. 内存爆炸 - 问题：细分产生海量多边形 - 解决：自适应细分，流式处理

3. 邻域查询缓慢 - 问题：朴素遍历 - 解决：半边结构，空间索引

最佳实践检查清单

算法选择

• [ ] 根据输入质量选择合适算法（扫描数据vs CAD模型）
• [ ] 考虑下游应用需求（渲染vs模拟vs打印）
• [ ] 评估时间/质量权衡
• [ ] 测试边界情况和退化输入

参数调优

• [ ] 简化率与视觉质量平衡
• [ ] 平滑迭代次数与特征保持
• [ ] 阈值设置（特征角度、最小边长）
• [ ] 权重因子（几何vs属性）

质量保证

• [ ] 验证拓扑不变性（Euler数、亏格）
• [ ] 检查法向一致性
• [ ] 确保水密性（闭合、无自相交）
• [ ] 监控数值稳定性指标

性能优化

• [ ] 使用合适的数据结构（半边、四叉树）
• [ ] 实现增量更新而非全局重算
• [ ] 并行化独立操作
• [ ] 内存池避免频繁分配

鲁棒性保证

• [ ] 处理退化情况（零面积、重复顶点）
• [ ] 边界条件正确处理
• [ ] 数值精度考虑（缩放不变性）
• [ ] 用户可控（参数暴露、交互确认）

验证测试

• [ ] 标准模型测试（Stanford Bunny、Dragon）
• [ ] 极端输入（高亏格、大规模）
• [ ] 与ground truth比较（Hausdorff距离）
• [ ] 跨平台一致性