在实际应用中，原始的3D mesh往往不能直接满足需求：扫描数据包含噪声、CAD模型过于精细、重建网格存在拓扑缺陷。本章将系统介绍mesh处理与优化的核心算法，包括简化、细分、平滑、修复和重网格化技术。这些技术是3D内容创作管线中的关键环节，直接影响渲染性能、存储效率和视觉质量。
学习目标：
网格简化是减少多边形数量同时保持视觉质量的关键技术。Quadric Error Metrics (QEM)算法通过最小化几何误差实现高质量简化。
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\)
简化通过迭代执行边收缩操作实现。对于边$(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$的第四列前三个元素。
1. 初始化：计算所有顶点的误差矩阵
2. 对每条边：
- 计算收缩代价（最优位置的误差）
- 插入优先队列（最小堆）
3. 迭代简化：
- 取出代价最小的边
- 执行边收缩
- 更新相邻边的收缩代价
4. 直到达到目标面片数
对于mesh边界和尖锐特征，需要特殊处理：
ASCII图示例：
收缩前: 收缩后:
v1
/|\ /\
/ | \ / \
/ | \ => / \
/___|___\ /______\
v3 v2 v4 v3 v̄ v4
细分曲面通过递归细化网格来生成平滑曲面，是建模和动画中的重要技术。Loop细分适用于三角形网格，Catmull-Clark适用于四边形网格。
Loop细分是针对三角形网格的细分方案，每次细分将一个三角形分成四个：
新顶点计算：
边点（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)\)
旧顶点更新（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
Catmull-Clark细分是最通用的细分方案，可处理任意多边形网格：
新顶点计算：
面点（Face vertices）：多边形中心 \(F = \frac{1}{n}\sum_{i=1}^{n}v_i\)
边点（Edge vertices）： \(E = \frac{1}{4}(v_1 + v_2 + F_1 + F_2)\) 其中$v_1, v_2$是边的端点，$F_1, F_2$是相邻面的面点
顶点更新： \(V_{new} = \frac{F + 2R + (n-3)V}{n}\) 其中$F$是相邻面点均值，$R$是相邻边中点均值，$n$是顶点度
细分可表示为矩阵运算： \(P^{k+1} = S \cdot P^k\)
其中$S$是细分矩阵。极限曲面的性质由$S$的特征值决定：
均匀细分会产生大量多边形，自适应细分根据曲率动态调整：
判断准则:
if (曲率 > 阈值 || 视角依赖误差 > 阈值) {
细分此区域
} else {
保持当前分辨率
}
T-junction处理是自适应细分的关键挑战。
网格去噪是处理扫描数据的必要步骤。Laplacian平滑和双边滤波是两种经典方法，前者简单高效，后者能保持特征。
对于网格顶点$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)$对应的两个对角。
最简单的平滑方法是迭代更新顶点位置：
\[v_i^{(k+1)} = v_i^{(k)} + \lambda\Delta v_i^{(k)}\]其中$\lambda \in (0,1)$是平滑因子。此方法等价于求解热扩散方程：
\[\frac{\partial v}{\partial t} = \Delta v\]收敛性分析：
隐式方法通过求解线性系统避免稳定性限制：
\[(I - \lambda\Delta t L)V^{(k+1)} = V^{(k)}\]其中$L$是Laplace矩阵，$\Delta t$是时间步长。
优点：
双边滤波同时考虑空间距离和法向差异，保持尖锐特征：
\[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(d) = \exp(-d^2/2\sigma_s^2)\) \(w_n(x) = \exp(-(1-x)^2/2\sigma_n^2)\)
根据局部几何自适应调整平滑强度：
\[\frac{\partial v}{\partial t} = \nabla \cdot (g(|\nabla v|)\nabla v)\]其中$g$是边缘停止函数： \(g(x) = \frac{1}{1 + (x/K)^2}\)
ASCII示意图：
噪声网格: Laplacian平滑: 双边滤波:
/\ /\ ___ /\
/ \/ \ => / \ 或 / \
/ \ / \ / \
（失去特征） （平滑） （保持特征）
实际扫描和重建的网格常包含各种缺陷：孔洞、自相交、非流形边、退化三角形等。这些缺陷严重影响后续处理和应用：渲染产生artifacts、物理模拟不稳定、3D打印失败。本节介绍系统的诊断和修复技术，从理论算法到工程实践。
常见缺陷类型：
检测算法：
边界检测: 度为1的半边
非流形边: 连接>2个面的边
自相交: AABB树加速的面片相交测试
退化检测: 面积 < ε 或 边长 < ε
基于最小面积的填充：
对于边界环$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）：
体积扩散法：
将孔洞区域视为薄膜，求解最小曲面问题： \(\min \int\int_S |\nabla u|^2 dS\)
| 边界条件：$u | {\partial S} = u{boundary}$ |
空间划分加速：
使用AABB树或八叉树加速相交检测：
构建AABB树(mesh)
for each 面片对(f1, f2):
if AABB(f1) ∩ AABB(f2) ≠ ∅:
精确相交测试(f1, f2)
修复策略：
顶点分裂： 对于非流形顶点，根据连通分量分裂：
检测顶点v的面片连通分量
for each 分量C:
创建新顶点v'
将C中的面片连接到v'
边分裂： 非流形边连接多个面片扇，需要分离：
f1
/\
/ \
e1 ---- e2 <- 非流形边
\ /
\/
f2
确保所有面片法向一致：
传播算法：
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难问题，但可用图割算法近似求解。对于大规模网格，启发式传播算法通常足够有效。
重新网格化是改善网格质量的综合技术，目标是生成具有良好几何和拓扑性质的新网格：均匀采样、规则连接度、等边三角形。这对数值模拟、参数化和压缩至关重要。
评估三角形质量的常用指标：
形状质量：
尺寸场适应性： 给定尺寸场$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)}\)
通过局部操作迭代改善网格质量：
基本操作集：
算法框架：
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$
Centroidal Voronoi Tessellation (CVT)生成高质量的均匀网格：
Lloyd算法：
受限于曲面的CVT： 种子点和Voronoi图都限制在曲面$S$上：
能量优化视角： CVT最小化量化误差： \(E = \sum_{i=1}^{n} \int_{V_i} \rho(x)\|x - s_i\|^2 dx\)
这等价于k-means聚类的连续版本。
根据曲率自适应调整网格密度和方向：
曲率驱动的度规场： 基于主曲率$\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$的路径。
保持和对齐几何特征：
特征检测：
约束Delaunay三角化： 确保特征线成为网格边：
四边形主导重网格化： 沿主曲率方向生成四边形：
主方向场 -> 参数化 -> 规则采样 -> 四边形提取
ASCII示意图：
原始网格: 均匀重网格: 各向异性:
/\ /\ △△△△ ——△——
/ \/ \ => △△△△ 或 |△|△|
/___/\___\ △△△△ ——△——
（不规则） （均匀） （沿特征）
在简化过程中精确保持几何特征和拓扑特征：
二次误差扩展：
法向约束：惩罚法向变化 \(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\)
使用可微渲染计算梯度，优化简化结果。
使用几何流演化网格：
平均曲率流（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。
应用：
深度学习在网格处理中的应用：
学习型简化：
神经网格去噪：
学习型重网格化：
本章系统介绍了mesh处理与优化的核心技术：
关键算法：
| Laplacian平滑：$\Delta v_i = \frac{1}{ | N_i | }\sum_{j \in N_i}(v_j - v_i)$，去除高频噪声 |
核心概念：
实践要点：
习题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去噪架构，输入噪声顶点位置，输出去噪位置。