跳转到内容
Jason's Study

QEM — 给三角网格『瘦身』时算每一刀的代价

是什么

QEM（Quadric Error Metrics，二次误差度量）是一套把高精度三角网格简化成低精度版本的算法，同时尽量不让模型看起来变形。日常类比：像把一张高分辨率照片压缩成缩略图——你想去掉很多像素，但希望剪影还认得出。

输入是一个 100 万面的精细模型，输出可能是 1 万面的粗糙版本。中间每一步只做一件事：挑两个顶点，把它们合并成一个。一次合并通常能减少两个三角面（被合并的顶点共享的边和它的两个邻接面消失）。难点是：挑哪两个？合并到哪个位置？挑错了，模型会丢失重要轮廓；位置算错，原本平的地方会鼓起来。

QEM 给每个顶点配一本『债务账本』（一个 4x4 矩阵 Q），里面记着『如果把我挪走，会偏离原表面多少』。合并的代价就是两本账本相加后的最小值。代价最低的对优先合并。整个算法朴素得近乎理所当然，但在它出现之前，主流方法不是太慢就是太糙。

为什么重要

不理解 QEM，下面这些事都没法解释：

  • 为什么 Unity / Unreal 的 LOD（细节层级）系统能自动从一个高模生成 5 档低模
  • 为什么 Blender 的 Decimate 修改器拖一下滑条就能精确控制保留多少面
  • 为什么 MeshLab、CAD 后处理、3D 扫描清理这条工业链 30 年没换底层算法
  • 为什么 1997 年 SIGGRAPH 的一篇 8 页论文成了图形学引用上万次的『地基论文』
  • 为什么 GPU 上跑 100 万面只要几毫秒、但储存、传输、加载都要简化版

它在『简化质量 vs 速度』这条曲线上找到了一个工业界最舒服的甜点：质量比 vertex clustering 高一个量级，速度比 progressive meshes 快一个量级，实现复杂度比两者都低。

核心要点

QEM 把『一次简化』拆成 三件事：

  1. 给每个顶点算账本（Q 矩阵）：顶点 v 周围有几个三角面，每个面所在平面有方程 ax+by+cz+d=0（其中 a^2+b^2+c^2=1，单位法向量）。把 v 离这些平面的『距离平方』全加起来——单个平面贡献是 (p^T v)^2 = v^T (pp^T) v——把所有 pp^T 加起来就得到顶点的 Q。Q 是 4x4 对称矩阵，正好是顶点的账本。

  2. 算合并代价 + 最优新位置：要把顶点 v1、v2 合并成 v*。新顶点的账本是 Q1+Q2（账本相加是线性的，这是 QEM 最巧的地方）。最优 v* 通过解一个 3x3 线性方程得到——对 v^T Q v 求导置零，让代价 v*^T (Q1+Q2) v* 最小。如果 3x3 矩阵奇异（共面退化情形），fallback 到 v1、v2 中点或线段上最优点。

  3. 优先队列驱动：把所有候选对（每条边，再加上距离小于阈值 t 的非邻接顶点对）按代价丢进堆里。每次取代价最小的合并、更新邻居的 Q、重新入堆。停在你想要的面数。

整个算法 O(n log n)，n 是合并次数。每次合并实际更新很少邻居，所以工程上跑得比理论复杂度更接近线性。

实践案例

案例 1：从 100 万面到 1 万面

斯坦福兔子（Stanford Bunny，图形学界『Hello World』模型）原始 69k 面。用 QSlim（Garland 自己写的 QEM 实现）跑一次：

输入: bunny.ply (69,451 faces)
QSlim -t 1000 bunny.ply bunny_lod.ply
输出: bunny_lod.ply (1,000 faces)
耗时: < 1 秒

虽然面数掉了 70 倍，但兔子耳朵、眼睛轮廓还在——因为耳朵尖那种『高曲率』区域，每个顶点的 Q 都很大（挪一点点距离债就飙升），算法自然不敢动那里。平坦的肚皮反而被狠合并。这是 QEM 的另一个隐藏优点：自适应保真——曲率高的地方密、曲率低的地方疏，不需要人工标注。

案例 2：非邻接顶点合并修复破洞

纯边折叠（edge collapse）算法只能合并『有边相连』的顶点。如果模型有破洞或两块脱开的碎片，永远连不上。

QEM 允许『距离 < t 的任意顶点对』合并，所以一只手两个独立扫描的手指可以被自动『缝』在一起。这是 QEM 跟同期算法最大的差异。在 3D 扫描场景尤其重要——激光扫描经常因遮挡产生大量小破洞，没有这个能力就要靠人工补洞。

案例 3：游戏引擎里的隐形使用

原模型 (50k tri) → QEM → LOD0 (50k) / LOD1 (15k) / LOD2 (5k) / LOD3 (1k)
                                ↑ 远处自动切到低模

玩家走远了，引擎切到 LOD3，GPU 少干 50 倍活，看着一样。这套流水线 1998 年起就是 QEM 推动的。

案例 4：直观理解 Q 为什么是 4x4

平面方程 ax+by+cz+d=0 写成向量形式 p=[a,b,c,d]^T，把齐次坐标 v=[x,y,z,1]^T 代入：p^T v 就是『带符号距离』。距离平方就是 (p^T v)^2 = v^T (p p^T) v。

p p^T 是 4x4 矩阵。一个顶点周围 6 个三角面，就把 6 个 4x4 矩阵相加，结果还是 4x4。这就是为什么矩阵尺寸是 4 不是 3——为了用齐次坐标把常数项 d 装进矩阵。

合并两个顶点时，新顶点对所有原始平面的『总债务』就是 v^T (Q1+Q2) v。这个二次型对 v 求导置零：

2 (Q1+Q2) v* = 0

但 v 的最后一维必须是 1（齐次坐标约束），所以实际只解前 3 行的 3x3 子矩阵方程。一行代码搞定。

踩过的坑

  1. 可能产生翻转三角形：合并两个顶点后，原本朝外的三角形可能突然朝内（normal flip）。原始论文不检测，导致渲染时出现黑斑（背面剔除把翻转面变成洞）。工业实现都加了一道『法线检查』兜底——若新位置造成相邻面法线方向翻转，就否决这次合并、从堆里删掉。

  2. 不保 manifold：边界、孔洞会越简化越大；非流形（一条边被 3 个面共用）的退化情形 Q 矩阵奇异，需要 fallback 到端点或中点。后续 Garland 1999 给边界加了一道额外的『虚拟平面约束』，强行把边界顶点钉住，缓解了这个问题。

  3. 属性丢失：原始 1997 算法只管几何位置，颜色、UV 贴图、法线全不参与代价计算。1998 年作者写了续作，把状态向量从 4 维（x,y,z,1）扩成 4+k 维处理颜色、纹理坐标，Q 也从 4x4 变成 (4+k)x(4+k)。工业实现基本都用 1998 版，但一开始读论文别从 1998 起——先理解 1997 的几何核心，再看 1998 怎么把属性『塞』进同一个数学框架。

  4. t 太大会乱缝：非邻接合并阈值 t 设得过宽，会把不该接的两块（比如人物的左右眼球）粘在一起。默认值要根据模型尺度调，工业实现常给一个『相对尺度』参数（如对角线长的 1%），而不是绝对距离。

  5. 顶点权重未考虑面积：原版 Q 直接累加 pp^T，不乘三角面面积。结果是大面积平面和小面积平面权重一样，在网格疏密不均的模型上有偏差。后续工作普遍乘上面积权重。

适用 vs 不适用场景

适用：

  • 游戏 / 实时渲染的 LOD 自动生成
  • 3D 扫描数据后处理（清理破洞、降采样）
  • CAD 模型给 Web 预览生成轻量版本
  • 任何『要快、要够好、不要求极致质量』的简化任务
  • 配合属性扩展后用于贴图模型简化

不适用：

  • 极致质量要求 → 用 Hoppe 1996 Progressive Meshes（每步全局优化，慢但精）
  • 极致速度要求 → 用 Rossignac 1993 Vertex Clustering（按 3D 网格粗暴合并，快但糙）
  • 拓扑必须严格保持流形 → QEM 不保证，需要约束变体（如 Garland 1999 boundary-preserving）
  • 含动画骨骼绑定的模型 → QEM 不知道骨骼权重，简化后蒙皮会崩
  • 点云原始数据 → QEM 需要拓扑（三角面），点云要先三角化或用专门的点云简化算法

历史小故事（可跳过）

  • 1993 年：Jarek Rossignac 发表 Vertex Clustering，10 倍快于后续算法，但质量差到不能直接用——把空间切成立方体格子，一个格子里的所有顶点合并成一个。简单粗暴。
  • 1996 年：Hugues Hoppe 发表 Progressive Meshes，建立『连续 LOD』概念，但每步要全局优化、迭代式贪心搜索，慢得没法实时跑。
  • 1997 年：CMU 博士生 Michael Garland 在导师 Paul Heckbert 指导下，找到了『二次型』这个数学技巧——把所有距离平方求和压成一张 4x4 矩阵，让合并代价的计算近乎免费。论文 8 页，附带开源工具 QSlim。当年 SIGGRAPH 现场惊艳。
  • 1998 年：续作把颜色、纹理纳入度量，从此工业实现的『QEM』默认指 1998 版。
  • 1999 年：Garland 博士论文进一步把约束（边界、特征线、对称面）形式化进 Q 矩阵框架，让 QEM 能定向保护重要区域。

之后 25 年，Blender Decimate、MeshLab Quadric Edge Collapse、Unity LOD Generator、Unreal Simplygon——全是 QEM 的工业改装版。直到 Nanite（Unreal 2021）出现，连续 LOD 才有了新一代继任者，但 Nanite 的 cluster 内部简化仍用 QEM 的变体。

学到什么

  1. 二次型是几何度量的神器：『到一堆平面的距离平方和』天然写成 v^T Q v，矩阵相加 = 度量合并，这个性质让算法既快又简洁。背后是线性代数最朴素的工具被用在最对的地方。
  2. 优先队列 + 局部更新 是『大规模迭代式简化』的标配模式——每次只动最便宜的那一刀，全局缓慢改善。这个模式在编译优化、社区检测、聚类合并里都见得到。
  3. 允许非邻接合并 是 QEM 跟纯边折叠的关键差异，多了拓扑修复能力，代价是要给 t 调参。算法设计中『多一个旋钮换一类能力』是常见取舍。
  4. 甜点工程学：在『质量 vs 速度』曲线上找一个工业最舒服的点，比追极致更重要。一个 8 页论文统治 25 年，靠的不是数学最优，是『恰好够用且实现简单』。

延伸阅读

关联

  • taubin-1995-mesh-smoothing —— 同样是网格处理，平滑是『动顶点不变面数』，QEM 是『砍面数不动太狠』；两者经常先后使用（先平滑去噪声、再 QEM 简化）
  • ssa —— 程序优化里的『静态单赋值』也是优先队列驱动的局部变换，思想相通
  • kildall-dataflow —— 数据流分析也是『局部更新 + 收敛』模式，QEM 是几何版本
  • 3d-gaussian-splatting —— 现代 3D 表示，跟传统三角网格是两条路；但 Gaussian 也面临『密度太高要简化』的同类问题，思路可借鉴
  • immix-mark-region —— 同样是『局部贪心 + 全局收益』思路：垃圾回收选哪些块清扫，跟 QEM 选哪对顶点合并，决策结构相似

一句话总结

把『顶点离表面有多远』压缩成一张 4x4 矩阵，让网格简化的代价计算近乎免费——一篇 8 页论文统治图形学工业 25 年的秘密。

反向链接