3. 简化算法入门：顶点聚类法、边坍缩法、二次误差度量(QEM)原理

好，我们正式开始聊简化算法。说实话，刚入行那会儿，我觉得网格简化不就是“删点删面”嘛，有啥难的？结果第一次把角色模型简化到 60% 面数，手臂直接变成了一坨多边形……嗯，从那以后我老实了。

这一章，我会带你过三种最经典的简化思路。它们不是互相替代的关系，而是不同场景下的不同武器。你理解透了，后面做性能优化才能有的放矢。

3.1 顶点聚类法：简单粗暴，但有用

顶点聚类法，说白了就是“把靠得近的点合并成一个”。

它的流程很直观：

1. 把模型包围盒划分成均匀的网格（3D 格子）
2. 每个格子内的所有顶点，合并成一个代表顶点
3. 重新连接三角形，删除退化的面

你想想看，这方法的好处是什么？快。真的快。我曾在一次地形 LOD 生成中用过它，百万级顶点，几毫秒就出结果。但代价也很明显——细节丢失不可控。

维度	说明
算法复杂度	O(n)，n 为顶点数
内存占用	低，只需维护网格哈希表
简化质量	一般，容易丢失棱边和尖锐特征
适用场景	预处理、粗简化、对质量要求不高的 LOD

3.2 边坍缩法：更聪明，但更慢

边坍缩法，是目前工业界最主流的简化思路。它的核心动作很简单：选一条边，把两个顶点合并成一个，删掉退化的三角形。

但关键问题是——先坍缩哪条边？

这就引出了“代价函数”的概念。每次坍缩前，我们计算每条边的“坍缩代价”，优先坍缩代价最小的边。代价怎么算？早期做法是用边长、邻接三角形面积变化等启发式指标。

我记得第一次实现边坍缩时，我用了最简单的边长作为代价。结果模型简化到一半，出现了大量狭长三角形，渲染时闪烁得厉害。后来我才意识到：边长短不代表坍缩后影响小。

3.3 二次误差度量(QEM)：黄金标准

QEM 是边坍缩法的“灵魂升级”。它由 Garland 和 Heckbert 在 1997 年提出，至今仍是大多数游戏引擎和 DCC 工具的默认简化算法。

QEM 的核心思想是：坍缩一个顶点后，新顶点到原始邻接平面的距离平方和最小。

具体来说：

• 每个顶点维护一个 4×4 的二次误差矩阵 Q
• 坍缩边 (v1, v2) 时，新顶点 v' 的误差为 v'^T * (Q1 + Q2) * v'
• 我们找一个 v' 使得这个误差最小

你可能会问：为什么要用矩阵？直接算距离不行吗？

嗯，这里有个巧妙之处。QEM 把“点到平面的距离平方”编码成了矩阵形式，这样在坍缩时只需要做矩阵加法，然后解一个 3×3 的线性方程组。效率极高。

下面是一个简化的 QEM 实现骨架：

// 每个顶点维护一个 4x4 矩阵
struct VertexQEM {
    float Q[4][4];  // 二次误差矩阵
    Vec3 position;
};

// 计算坍缩代价
float CollapseCost(Edge e) {
    // 合并两个顶点的 Q 矩阵
    float Q_new[4][4];
    MatrixAdd(Q_new, v1.Q, v2.Q);
    
    // 求解最优顶点位置
    Vec3 best_pos = SolveOptimalPosition(Q_new);
    
    // 计算误差
    return EvaluateQuadric(Q_new, best_pos);
}

3.4 三种算法对比

算法	速度	质量	内存	实现难度	典型应用
顶点聚类法	极快	一般	低	低	预处理、粗简化
边坍缩法（基础）	中等	较好	中	中	中等精度 LOD
QEM 边坍缩	较慢	优秀	高	高	高质量 LOD、游戏资产

3.5 知识结构图

下面这张图帮你理清三种算法的关系和适用场景：

3.6 实际项目中的选择建议

说了这么多理论，到底怎么选？我根据多年经验给你一个实用指南：

• 如果你在做编辑器工具：用 QEM，质量第一，速度可以接受
• 如果你在做运行时 LOD：用顶点聚类法做快速降级，或者用预计算的 QEM 结果
• 如果你在做移动端：优先用顶点聚类法，内存和计算都受限
• 如果你在做科学计算可视化：QEM 是唯一选择，特征保留要求高