网格简化

三种简化（16.5 节）

Luebke 把简化分为：

• 静态：渲染前生成若干离散 LOD 模型，运行时选择（第 19.9 节）；也可为细分曲面提供粗网格。
• 动态：提供连续的 LOD 谱，即连续细节层次 (CLOD)。
• 视角相关：模型内部细节随位置变化，典型是地形：近处精细、远处粗糙。

边折叠（16.5.1 节）

把一条边的两个顶点移到一起。对实体模型，一次边折叠去掉 2 个三角形、3 条边、1 个顶点（由 $f-e+v=2$ 推出封闭网格约有 $2v$ 个面、$3v$ 条边），3000 个三角形的封闭模型折叠 1500 次即为零面。

• 可逆：按顺序记录折叠，从简化模型可重建原模型，适合网络上压缩传输并渐进显示，因此称为视角无关的渐进网格 (VIPM)。
• 放置策略：

• 局部性：代价只依赖少数局部变量（边长、边附近面法线），每次折叠只影响少数邻居（如 3000 个候选只需重算约 10 个），因此用堆或优先队列维护代价表。
• 无论代价多低都必须禁止的折叠：会导致边交叉的折叠，可通过检查邻接三角形法线是否翻转来发现。

flowchart TD
  A["计算所有候选边折叠的代价"] --> B["放入优先队列"]
  B --> C["取代价最小者执行折叠"]
  C --> D{"邻接三角形法线翻转?"}
  D -- "是" --> E["放弃该折叠"]
  D -- "否" --> F["记录折叠, 重算受影响的少数候选"]
  E --> B
  F --> B

上图是基于代价的边折叠主循环；记录下的折叠序列就是渐进网格。

二次误差度量 (QEM)

共享顶点的每个三角形都有平面方程，把顶点移到新位置 $\mathbf{v}$ 的代价是到这些平面距离的平方和： $c(\mathbf{v}) = \sum_{i=1}^{m} (\mathbf{n}_i\cdot\mathbf{v} + d_i)^2$ $\mathbf{n}_i$ 为第 $i$ 个平面法线，$d_i$ 为其到原点的偏移。例：边长 2 的立方体在某条边上多了一个点 $e$，$e\to c$（折到角点）代价 0，因为 $e$ 不离开它所在的平面；$c\to e$ 代价 1，因为 $c$ 偏离右侧面的平方距离为 1，所以选 $e\to c$。

• 扩展：鱼鳍、涡轮叶片这类尖锐边上点的基本代价很低（代价与移除特征的体积变化有关，而非视觉重要性）；可加一个包含该边、法线为两侧法线平均的额外平面来保留锐边；或按三角形面积变化加权。
• 应保护的特征：折痕边与边界边、材质变化处、纹理贴图边缘、逐顶点颜色变化处。
• 地形简化中 Garland 与 Heckbert 早期发现 Hausdorff 距离（简化网格顶点到原网格的最远距离）效果最好。

常见问题

• 纹理扭曲：边折叠会使纹理映射变形；镜像模型中线处纹理坐标相同却属于不同区域。Caillaud 等的算法能处理纹理接缝。
• 速度：用户创作内容（CAD）需即时生成 LOD。可用 GPU 简化，或用顶点聚类：用三维体素网格覆盖模型，每个格子内的顶点移到该格"最佳"位置，两个以上顶点落在一起的三角形退化消失。稳健、不需要连接信息、可把多个网格合在一起，但基本版质量很少能比得上完整 QEM；Willmott 团队在《Spore》的用户生成内容中把它做得稳健高效。
• 烘焙法线贴图：把纽扣、褶皱等小特征转成法线贴图是与简化相关的思路，常见于把高模烘焙成带纹理的低模。
• 跳变 (popping)：LOD 瞬间替换可见；已知高低模顶点对应关系，可用 geomorph 平滑过渡（第 19.9.1 节）。
• VIPM 可让同一模型不同 LOD 的副本共享一个顶点缓冲，但基本方案每个副本需要单独索引缓冲；折叠顺序决定三角形顺序，顶点缓存一致性差（Forsyth 讨论了改进方法）。
• 对称性与关键特征：自动简化会破坏对称（10 面圆柱减一面后不对称，不如让 faceter 重新生成 9 面），会把眼睛、嘴这些最重要的部位当作无关紧要抹平；优秀美术手工做的低模往往更好。重拓扑 (retopology) 通过加边让特征在建模、平滑或简化时保持分离。