计算机图形学 15：怎样减少面数又控制形变
一个 64 面的封闭模型，能否只保留 8 面？删除任意三角形会留下孔洞；直接合并最近的两个顶点，也可能改变连接或翻转表面。减少面数需要同时回答三个问题：合并哪条边、把合并点放在哪里、怎样判断结果还能使用。
本篇复用第 12 篇的网格和半边结构，实现受约束的边折叠。排序代价采用二次误差度量（QEM），验收另算真实三角形距离与固定视角轮廓。三项数值回答不同的问题，不能用一个低代价数值替代全部检查。
折叠一条边会删除什么
对内部边 (a,b)，把两个端点合并到新位置 x。包含整条边的两个三角形因顶点重合而删除；其余引用 b 的三角形改为引用 a，再从顶点数组删掉 b 并修正编号。
合法的闭合三角网格边折叠通常使 V 减 1、E 减 3、F 减 2，因此欧拉示性数 V−E+F 不变。但数量相符不能保证操作合法：两个原本不同的面可能变成相同索引集合，顶点一环也可能不再是单一扇区。
一个反例是四面体。折叠任一边会删除它相邻的两个面，余下两个面却落到同一组三个顶点上。若只检查“公共邻点有两个”，这个反例会通过；完整的邻接条件还涉及边等单纯形，不能缩成邻点数量比较。
collapse_closed_edge 先检查公共邻点与两个对顶点一致，再重建 Mesh。构造器继续拒绝重复面、错误绕序和非单扇区连接，因此四面体折叠实际报出 repeated vertex or face。这里没有把前一个快速检查冒充完整拓扑证明。
当前简化器只接受闭合、有一致绕序的三角网格，候选仅为已有边。开放边界、任意非邻接点对聚合不在实现范围内。这是本篇明确的输入约束，也不同于原论文允许的更宽泛聚合方案。
从到平面的距离得到一个矩阵
一个三角面所在平面写成 ax+by+cz+d=0，令法线 (a,b,c) 的长度为 1。点 v=(x,y,z,1) 到这个无限平面的有符号距离，就是 pᵀv，其中 p=(a,b,c,d)。平方距离为：
单位法线不可省略。把同一个平面方程整体乘 10，平面位置没有改变，未经归一化的平方值却会放大 100 倍。plane_quadric 同时除法线和偏移 d，不只修改前三项。
对一个顶点，把原始邻接面的 Kₚ 相加得到 Q。若折叠 a、b，新顶点保存 Qₐ+Qᵦ。这些矩阵沿折叠过程累计，保留被删除原始面的约束；不能每次只根据当前粗网格重算，否则优化目标也随删除而丢失。
共享面可能同时出现在两端的矩阵里，相加时会重复计数。这是当前加和规则的一部分，不是面集合去重。本实验每个初始面使用相同权重，没有引入面积权重、颜色或纹理坐标误差。
QEM 衡量的是到一组无限平面的平方距离之和。一个点即使离有限三角形很远，只要仍在其所在平面内，贡献就是零。因此它适合提供局部排序信号，却不是最终模型到原表面的最大距离保证。
合并点为什么不总在边中间
把 Q 分块，前三维为 A，最后一列前三项为 b，右下角为 c。代价可写成：
若 A 可逆，驻点满足 Ax=−b。由于 Q 来自平方项之和，精确算术下这是凸二次目标。实现通过带行选主元的消元求解，主元不超过初始 A 最大绝对元素的 10⁻¹² 倍时视为病态或奇异，不计算一个极大的不稳定坐标。
可手算的检查使用三个平面 x=1、y=2、z=3。最小点应是 (1,2,3)，代价为 0；移到 (2,2,3)，只有第一个平面的距离平方为 1。程序分别核对位置与代价，避免只让求解器和同一段公式互相印证。
若约束只有 z=0，A 只有一个有效方向：任何 (x,y,0) 都是零代价点，唯一解不存在。实验用法线 (0,0,2) 输入该平面，检查归一化后 (100,−200,0) 的代价为 0，(0,0,2) 的代价为 4，求解器报告无唯一候选。
每条边总会比较端点 a、端点 b 和中点；若消元成功，再加入解析候选。奇异时只在三个有限候选中选择，不实现原论文的线段约束最小化步骤。这种回退容易验证，但可能错过比三个点更好的位置。
所有边按选定位置的代价稳定排序，依次尝试折叠。某条边的选定位置不合法时，当前实现跳到下一条边，没有继续尝试同一条边的次优位置。因此“本轮没有可执行候选”只说明当前策略停下，不证明所有合法位置都不存在。
低代价仍可能翻面
对于保留下来的每个受影响三角形，比较新旧未归一化法线的点积。如果点积不大于 0，就拒绝操作。这同时拒绝退化为零面积的面，以及法线偏转达到或超过 90 度的情况。
这是保守的局部几何限制，不是全局无自交检测。远处两块不相邻表面仍可能相交；本篇没有三角形对的全局碰撞检查，所以不能把验收结果用于承诺任意输入都不自交。
四类拒绝实验分别检查具体报错：四面体折叠导致重复面、开放单三角形不符合输入约束、非边点对不能折叠、把实际边的合并点移到 (−100,−100,−100) 导致翻面或退化。只检查“抛过异常”不足以确认命中了预期路径。
候选操作先生成新位置和新面数组，只有通过 Mesh 构造才替换当前网格。失败候选不会留下部分更新的连接。Q 矩阵也在候选网格通过后才合并和删除。
本实现每轮重新枚举、排序全部边，每次候选通过完整网格重建检查。它服务于 64 面的有界实验；大网格需要局部更新和优先队列，但这些优化不能省略拓扑与几何过滤。
固定输入逐级减少面数
输入由第 14 篇四面体执行两轮 Loop 细分得到，再把坐标分别乘以 (3,2,2)，形成 34 顶点、64 面的非球形模型。参考表面从此固定，不在各级重新生成或拟合。
简化连续执行到 32、16、8 面。图中四块依次为原始、32 面、16 面、8 面；每块 256×256。相机位置 (3,2,4)，看向原点，正交半高 1.3，近远平面 1 和 10。照明方向与第 14 篇一致，采用面法线和累计线性颜色输出。
32 面仍保留多数外形，但面片变大；16 面和 8 面的顶端、底边及右侧变化明显。每级没有自动缩放到相同包围盒，图像差异来自实际几何与法线变化。
为了独立于 QEM 检查表面，程序对每个源三角形取 15 个重心格点：i、j 为非负整数且 i+j≤4，权重为 (i/4,j/4,(4−i−j)/4)。每个点到目标网格所有三角形求最小欧氏距离。
点到三角形的计算先投影到平面。垂足在三角形内部就取垂直距离；在外部则取三条线段的最近距离。独立检查在单位直角三角形上使用面内垂足、边最近点、顶点最近点，平方距离分别为 4、1/2、2。
采样同时执行原始→简化与简化→原始，两方向的平方和合并后除以总样本数再开根，得到下表 RMS。最大值同样取两个方向中的较大者。
| 面数 | 顶点数 | 双向样本数 | 合并 RMS | 采样最大距离 | 轮廓异或像素 |
|---|---|---|---|---|---|
| 64 | 34 | 960 / 960 | 0 | 0 | 0 |
| 32 | 18 | 960 / 480 | 0.03727974 | 0.08276171 | 965 |
| 16 | 10 | 960 / 240 | 0.08535108 | 0.18498062 | 2664 |
| 8 | 6 | 960 / 120 | 0.13591576 | 0.23980686 | 5206 |
距离使用模型坐标单位，没有除以包围盒尺度。重复的共享边、顶点样本保留，各面贡献相同数量的样本，因此这不是面积均匀积分；两方向样本数不同，也不是两方向 RMS 的简单平均。
有限格点可能漏掉误差峰值，表中“采样最大距离”不是连续表面的 Hausdorff 距离上界。增加采样密度可以改善观测，但仍需区分近似测量与经过证明的误差界。
轮廓为什么还要单独测量
几何距离不直接等于当前相机下的可见差异。程序以黑色背景区分覆盖掩码，统计原始与简化覆盖的异或像素，并输出对照图：灰色为两者共有，红色为只在原始轮廓内，蓝色为只在简化轮廓内。
四级并集像素数分别为 16285、16483、16711、16482。异或除以并集，可得到当前离散视角的相对轮廓差异；不要除以不同级别各自的覆盖面积后混称同一指标。
图像底部出现连续红带，说明简化模型失去部分原始覆盖；顶端或侧面的蓝色表示新增覆盖。红蓝同时存在，不能简单概括为“整个模型缩小”。该指标还依赖视角、分辨率和光栅覆盖规则，没有测试其他相机时不能外推到所有方向。
8 面输出之后，程序继续运行到策略不能折叠为止。最终停在 4 面，共成功折叠 30 次；最后四面体的 6 个候选全部被拒绝。四个展示级别之前没有发生候选拒绝，这个事实只属于当前输入，不代表过滤没有用途。
复跑与练习
1 | |
核心实现为 quadric.hpp，独立距离测量在 mesh_distance.hpp，共享展示在 mesh_view.hpp。实际 PPM 为 simplify-levels.ppm 和 simplify-silhouette.ppm；PNG 由它们转换。完整精度记录位于 writing-plans/computer-graphics/evidence/15-cpu.txt。实验完全确定，无随机种子、性能测量或 GPU 验证宣称。
练习一：只用平面 z=0 的 Q，点 (10,10,0) 代价是多少？它到顶点 (0,0,0)、(1,0,0)、(0,1,0) 组成的三角形是否也为零距离？
答案：QEM 代价为零。最近三角形点为 (1/2,1/2,0)，距离为 9.5√2。无限平面不限制沿平面的移动，这正是需要独立几何距离验收的原因。
练习二：一个合法闭合网格从 64 面降到 32 面，每次折叠删两个面，需要几次折叠？原始 34 顶点会剩多少？若程序输出 17 顶点，应该先检查什么？
答案：需要 16 次，剩 18 顶点。17 顶点说明计数或删除路径不符合当前一边折叠约定，应核查是否多删顶点、删除了额外面或混用了其他聚合操作；不能仅凭图像相似接受。
练习三：某一次折叠的 QEM 代价小于另一次，能否推出它在任意相机下轮廓差异也更小？
答案：不能。QEM 没有相机和像素分辨率，轮廓差异受投影与遮挡影响。需要固定相机单独比较；涉及多个观察方向时，还需明确方向集合和聚合规则。
系列导航与资料
前篇：14：粗网格怎样变成曲面。系列入口。后篇：16：多个模型怎样组成场景。
Garland、Heckbert：Surface Simplification Using Quadric Error Metrics，实际核对 §3.2、§4–6 的点对收缩、矩阵累加、位置选择及几何质量检查。当前实现限制为闭合边折叠，奇异回退和约束均已在正文标明。CGAL 6.2.1 Surface Mesh Simplification User Manual，核对 Garland-Heckbert 策略与 link condition 说明，作为拓扑和代价分离的资料；实验没有调用 CGAL。资料于 2026-09-20 实际读取。
