16 Polygonal Techniques

多边形技术 (Polygonal Techniques)

引言：处理不完美的模型数据

在理想世界中，我们用于渲染的模型数据是完美无缺的。但在现实中，从各种建模软件或扫描设备中获得的数据往往充满了各种问题。本章的核心就是探讨如何处理这些“不完美”的多边形数据，使其不仅能被正确渲染，还能渲染得更高效。

• 核心观点: 原始的3D模型数据很少能直接用于高效渲染，必须经过一系列处理和优化。这是一个在视觉质量、渲染效率和内存占用之间进行权衡的过程。

• 关键流程术语:

  • 曲面细分 (Tessellation): 将复杂的表面或多边形拆分成更简单的、适合硬件处理的图元（通常是三角形）。
  • 整合 (Consolidation): 将零散的多边形组织成一个连贯的网格结构，并计算出用于着色的新数据（如顶点法线）。
  • 优化 (Optimization): 重新组织网格数据，使其更适合GPU的缓存机制，从而加快渲染速度。
  • 简化 (Simplification): 移除模型中不重要的细节（即删除三角形），以在不严重影响视觉效果的前提下提升性能。
  • 压缩 (Compression): 采用各种技术减少描述网格所需的数据量，以节省内存和带宽。

---

16.1 三维数据的来源 (Sources of 3D Data)

了解模型的来源至关重要，因为不同的来源会引入不同类型的问题。

• 核心观点: 模型数据并非凭空而来，其创建方式和原始用途决定了它是否适合实时渲染。通常，为其他目的（如工程分析、3D打印）创建的数据需要大量后处理才能用于游戏引擎。

• 主要数据来源及特点:

  • 建模软件:
    • 基于实体的 (Solid-based): 常见于CAD领域（如SolidWorks）。内部用数学方式精确描述物体，通过一个叫做 Faceter 的工具将其转换为可视化的三角形网格。关键： 调整Faceter的精度是降低模型复杂度的第一步。
    • 基于表面的 (Surface-based): 常见于数字内容创作领域（如Blender, Maya）。艺术家直接操作顶点、边和面。内部可能使用样条曲线或细分表面 (Subdivision Surface)，最终也需要细分成三角形来渲染。
  • 扫描与重建:
    • 摄影测量 (Photogrammetry): 通过多张照片重建3D模型。
    • 3D扫描仪: 直接采集真实世界物体的表面点，形成点云 (Point Cloud)。这类数据通常非常密集且包含噪声，是简化 (Simplification) 技术的主要应用对象。
  • 程序化生成 (Procedural Modeling): 用算法代码生成模型，灵活性高。
  • 等值面提取 (Isosurfacing): 从体积数据（如CT、MRI扫描）中提取出表面。例如，使用移动立方体 (Marching Cubes) 算法生成网格。

---

16.2 曲面细分和三角形划分 (Tessellation and Triangulation)

这是处理多边形数据的第一步：确保所有图元都是GPU最喜欢的格式——三角形。

• 核心观点: 三角形划分 (Triangulation) 是将任意多边形分解为三角形集合的过程，这是现代图形硬件渲染的基础。选择不同的划分方式会影响最终的渲染质量和效率。

• 关键术语与技术:

  • 曲面细分 (Tessellation): 更广义的概念，指将表面分割成多边形集合。
  • 凸分割 (Convex Partitioning): 将一个凹多边形分解成若干个凸多边形。
  • Delaunay 三角形划分: 一种特殊的划分方式，旨在最大化三角形的最小内角，避免产生过于狭长的**“ Sliver Triangles ”**。这种细长的三角形不仅光栅化效率低，还容易在插值计算时产生瑕疵。

• 处理非平面多边形:

  • 问题: 建模软件可能产生顶点不共面的多边形，在某些视角下会变成 “沙漏”或“领结”形状 (Hourglass/Bowtie Quads)，导致渲染错误。
  • 解决方案:
    1. 将多边形的顶点投影到一个近似平面上。
    2. 这个平面的法线可以通过 Newell公式 计算得出，该公式通过计算多边形在三个坐标平面（xy, yz, xz）上的投影面积来稳健地获得平均法线。

• 核心算法：耳切法 (Ear Clipping)

  • 概念: “耳朵”是指由多边形的三个连续顶点 $(v_i,v_{i+1},v_{i+2})$ 构成的三角形，且其对角线 $(v_i,v_{i+2})$ 完全位于多边形内部。
  • 流程: 迭代地寻找并“切掉”多边形上的“耳朵”，直到整个多边形被完全分解为三角形。
  • 复杂度: 是一种相对直观且稳健的算法，时间复杂度为 $O(n^2)$。虽然存在更快的算法（如$O(n\log n)$甚至$O(n)$），但耳切法在实践中已足够常用。

• 处理带孔洞的多边形:

  • 问题: 多边形可能包含一个或多个“洞”，即由多个轮廓线（contours）定义。
  • 解决方案: 通过添加 桥接边 (Bridge Edges) 将内部的洞与外部轮廓连接起来，从而将其转换为一个单一的、复杂的轮廓线，然后再进行三角形划分。

• 一个巧妙的GPU技巧:

  • 可以使用模板缓冲区 (Stencil Buffer) 来快速渲染任意复杂（甚至自相交）的多边形，而无需在CPU端进行复杂的三角化计算。
  • 原理: 利用模板缓冲区的奇偶规则。将复杂多边形作为一个三角扇（Triangle Fan）渲染两次。第一次渲染时，被三角形覆盖奇数次的像素区域会被标记；第二次渲染时，只绘制被标记的区域。这对于动态生成的、临时的复杂区域高亮显示等场景非常有用。

16.2.1 着色问题 (Shading Issues)

即使是简单的四边形，如何将其划分为两个三角形也会影响最终的视觉效果。

• 核心观点: 对四边形对角线的选择，会直接影响顶点属性（如颜色、纹理坐标）的插值方式，从而产生不同的视觉结果。

• 选择对角线的启发式规则:

  1. 最短对角线: 在没有其他信息时，优先选择长度较短的那条对角线，这通常能产生形状更优的三角形。
  2. 最小化属性差异: 如果顶点带有颜色或其它属性，应选择连接后 属性差异最小 的那条对角线，以减少插值带来的突变和色带。

• 纹理扭曲 (Texture Warping)

  • 问题: 当将一个矩形纹理贴到一个非平面的、扭曲的四边形上时，无论选择哪条对角线，纹理都会出现不自然的扭曲。
  • 根本原因: 三角形只能进行仿射变换 (Affine Transformation)，而无法表达透视变换 (Perspective Transformation)。纹理在一个三角形内部的插值是线性的，无法模拟出在扭曲四边形上应有的透视缩短效果。
  • 解决方案:
    • 对表面进行更密集的细分，用更多的小三角形去逼近正确的扭曲效果。
    • 使用投影纹理 (Projective Texturing)，在像素着色器中进行正确的透视校正计算。
    • 在顶点数据中增加额外信息，实现双线性映射 (Bilinear Mapping)。

16.2.2 边界开裂和T顶点 (Cracking and T-Vertices)

这是在拼接独立的网格片时非常常见的几何瑕疵。

• 核心观点: 当相邻的多边形或曲面片没有严格共享边界上的顶点时，就会在接缝处产生可见的裂缝或着色错误。

• 关键术语与问题:

  • 边界开裂 (Edge Cracking):
    • 场景: 两个独立的曲面（如NURBS曲面）被分别细分成三角形网格。如果它们各自的细分算法没有精确匹配边界上的点，就会在接缝处产生微小的缝隙。
    • 解决方案: 边缘缝合 (Edge Stitching)，即强制让共享边界的两个曲面片生成完全一致的顶点。
  • T顶点 (T-Vertices):
    • 定义: 一个顶点 B 位于边 AC 上，但顶点 B 属于一个多边形，而 A 和 C 属于另一个相邻的多边形。从形状上看，这形成了一个 "T" 字路口。
    • 导致的问题:
      1. 物理裂缝: 由于浮点数精度问题，B 点的位置可能与 AC 边不能完美重合，导致像素级的缝隙。
      2. 着色不连续: 即使位置完全重合，由于 B 点的法线、颜色等属性没有被 AC 所在的三角形用于插值计算，会导致光照在接缝处出现明显的明暗变化。
    • 解决方案:
      • 简单修复: 将T顶点 B 添加到边 AC 所在的三角形中，将其一分为二。
      • 更优修复: 重新进行局部三角化 (Re-triangulation)，调整周围的拓扑结构，消除T顶点，并避免产生细长的三角形。

16.3 整合 (Consolidation)

在模型数据经过初步的三角形划分后，我们得到了一堆多边形。但它们可能还是零散、无序、缺少关键渲染信息的。“整合”这一步就是为了解决这些问题，将“原始素材”加工成一个结构良好、信息完备、可以被高效渲染的网格 (Mesh)。

• 核心观点: 整合是将一堆无序的多边形（“多边形汤”）转变为一个结构化、有向且带有平滑法线的连贯网格的过程。这是数据准备流程中至关重要的一环，直接影响渲染效率和视觉质量。

16.3.1 合并：从“多边形汤”到索引网格

• 问题: 原始数据常常是 “多边形汤” (Polygon Soup) 的形式，即一个长长的、由独立多边形组成的列表。每个三角形都存着它自己的三个顶点，即使这些顶点在空间中是同一个点。这种方式极度浪费内存，并且渲染效率极低（因为GPU无法利用顶点缓存）。

• 核心任务: 合并 (Merging) 重复的顶点，建立一个索引网格 (Indexed Mesh)。

• 关键术语:

  • 顶点列表/缓冲区 (Vertex Buffer): 一个数组，存储模型中所有 独一无二 的顶点。每个顶点包含位置、法线、UV坐标等信息。
  • 索引列表/缓冲区 (Index Buffer): 一个整数数组，其中的每三个整数定义一个三角形，整数的值对应顶点缓冲区中的索引。
  • 焊接 (Welding): 一个更宽泛的合并概念，指将位置 非常接近但不完全相同 的顶点也合并为一个。这对于修复从不同来源拼接模型时产生的微小缝隙非常重要。

• 实现方法:

  1. 使用哈希表 (Hash Table):
  2. 遍历“多边形汤”中的每一个顶点。
  3. 以顶点的位置坐标作为键（Key），在哈希表中查找。
  4. 如果未找到: 说明这是一个新顶点。将其添加到最终的顶点列表中，获得一个新的索引，然后将（位置坐标 → 新索引）这个键值对存入哈希表。
  5. 如果找到了: 说明该顶点已经存在。直接从哈希表中获取其已有的索引。
  6. 将获得的索引（无论是新的还是旧的）存入索引列表。
  7. 处理完所有顶点后，我们就得到了一个紧凑的顶点缓冲区和一个高效的索引缓冲区。

16.3.2 定向：统一朝向

• 问题: 一个模型上的多边形法线可能朝向各不相同，有些朝外，有些朝内。这会导致背面剔除 (Back-face Culling) 错误，光照计算也会出现严重问题。

• 核心任务: 定向 (Orientation)，即确保一个连续表面上的所有多边形都朝向同一个方向（通常是“外面”）。

• 关键术语:

  • 缠绕方向 (Winding Direction): 定义多边形正面的顶点顺序。通常使用逆时针 (Counter-Clockwise, CCW) 顺序为正面。
  • 右手定则 (Right-hand Rule): 用右手手指顺着顶点缠绕方向弯曲，大拇指的指向就是该多边形的法线方向。
  • 邻接图 (Adjacency Graph): 描述多边形之间通过共享边相互连接关系的数据结构。
  • 半边 (Half-Edge): 一种常用于表示邻接关系的数据结构，每条共享边被看作两个方向相反的“半边”，各自属于一个多边形。

• 定向算法流程:

  1. 建立邻接关系: 遍历所有多边形，找出哪些多边形共享了哪些边，构建邻接图。使用哈希表或排序可以高效地找到共享边。
  2. 区域传播 (Flood Fill):
     • 从任意一个多边形 S 开始，将其作为“正确”朝向的基准。
     • 遍历 S 的每一个邻居 B。
     • 检查它们共享边 $(v_x,v_y)$ 的遍历方向。如果 S 和 B 在遍历各自顶点时，都是从 $v_x$ 到 $v_y$（方向相同），说明它们的朝向是 相反 的。
     • 要使朝向一致，必须翻转 B 的顶点顺序（例如，将其从 $v_x,v_y,v_z,...$ 变为 $...,v_z,v_y,v_x$）。
     • 将 B 标记为已处理，并递归地对 B 的所有未处理邻居执行此过程，直到整个连通块的朝向都统一。
  3. 判断内外: 上一步保证了局部朝向的一致性，但整个连通块可能统一朝向了模型“内部”。
     • 解决方法: 计算该连通块的 带符号体积 (Signed Volume)。如果体积为负，说明整个模型朝向是反的，需要将 所有 多边形的顶点顺序翻转过来。

16.3.3 实体性 (Solidity)

• 核心观点: 一个“实体”或 “水密” (Watertight) 的网格，是指它完全封闭了一个空间，没有任何“洞”或边界。

• 判断标准: 一个最简单且常用的测试是：检查网格中的每一条边是否都恰好被两个多边形共享。

  • 被一个多边形共享的边是边界边 (Boundary Edge)。
  • 被三个或更多多边形共享的边是非流形边 (Non-manifold Edge)，这在几何上是不“干净”的。

• 重要性: 确认模型是实体对于背面剔除、阴影体积 (Shadow Volumes) 算法和3D打印等应用至关重要。

16.3.4 法线平滑与折痕边缘：创造曲面感

• 问题: 如果直接使用每个三角形的面法线来做光照，模型会呈现出明显的棱角，看起来像一堆面片。为了模拟光滑的曲面，我们需要计算逐顶点法线 (Per-vertex Normals)。

• 核心任务: 在需要平滑的地方计算共享的顶点法线，同时保留模型应有的尖锐折痕边缘 (Crease Edges)。

• 定义折痕的方法:

  • 平滑组 (Smoothing Groups): 由美术师在建模软件中手动指定。属于同一个平滑组的多边形，它们共享的顶点法线才会被平均，从而显得平滑。不同组之间的边界则保持锐利。
  • 折痕角度 (Crease Angle): 一种自动化的方法。计算相邻两个多边形法线之间的二面角 (Dihedral Angle)。如果该角度大于设定的阈值（例如30°），则它们之间的边被视为折痕。

• 更优的顶点法线计算方法:

  • 简单平均法的缺陷: 直接对共享顶点的所有面法线求平均。这种方法的问题在于，如果一个面被细分成更多三角形，那么它在平均计算中的权重就会不合理地增大，导致最终的顶点法线偏移。
  • 角度加权法 (Angle Weighting): 一种更稳健的方法。在计算平均法线时，每个面法线的贡献度由它在该顶点处所形成的夹角大小来加权。这样，无论一个多边形被如何三角化，最终得到的顶点法线都是一致的。（这是业界推荐的做法）

• 针对高度场的快速近似法线:

  • 对于规则网格的高度场，可以用一个非常高效的公式来近似计算顶点 p 处的法线 n（未归一化）： $\mathbf{n}=(p_x^{x+1}-p_x^{x-1},p_y^{y+1}-p_y^{y-1},2)$
  • 其中 $p_z^{x+1}$ 和 $p_z^{x-1}$ 是x轴上相邻点的高度值，$p_z^{y+1}$ 和 $p_z^{y-1}$ 是y轴上相邻点的高度值。这个公式本质上是用中心差分来求高度变化的梯度。

---

这部分内容是实时渲染中的一个核心优化主题：如何高效地组织和提交三角形数据给GPU。理解这些数据结构和其背后的硬件原理，对于编写高性能的渲染代码至关重要。

---

16.4 三角形扇、三角形带与三角形网格

引言：顶点复用的重要性

• 核心观点: 向GPU提交几何体时，最暴力的方法是独立的三角形列表 (Triangle List)，即每个三角形都发送3个独立的顶点。但模型中绝大多数顶点都被多个三角形共享。通过复用顶点数据，我们可以极大地减少需要处理的顶点数量，从而显著降低顶点着色器 (Vertex Shader) 的负载和内存带宽，这是提升渲染性能的关键一步。

16.4.1 三角形扇 (Triangle Fan)

• 核心概念: 一系列三角形共享一个公共的中心顶点。
• 工作方式:
  1. 第一个三角形由 v0, v1, v2 构成，其中 v0 是中心顶点。
  2. 第二个三角形复用 v0 和上一个顶点 v2，只需再提供一个新顶点 v3，构成 v0, v2, v3。
  3. 第三个三角形复用 v0 和 v3，再提供 v4，构成 v0, v3, v4，以此类推。
• 效率分析:
  • 渲染 m 个三角形，需要发送 m+2 个顶点（3个用于启动，之后每个新三角形只需1个）。
  • 平均每三角形顶点数 $v_a$: $v_a=\frac{3+(m-1)}{m}=1+\frac{2}{m}$
  • 随着扇区增大 ($m\to \infty$)，$v_a$ 趋近于 1。
• 适用场景: 非常适合表示凸多边形，只需将任意一个顶点作为中心点即可。在现代图形API中依然被支持，但对于复杂网格已不常用。

16.4.2 三角形带 (Triangle Strip)

• 核心概念: 一条连续的三角形链，其中每个新三角形都与前一个三角形共享一条边（即两个顶点）。
• 工作方式:
  1. 第一个三角形由 v0, v1, v2 构成。
  2. 第二个三角形复用 v1 和 v2，只需再提供一个新顶点 v3，构成 v1, v2, v3。
  3. 第三个三角形复用 v2 和 v3，再提供 v4，构成 v2, v3, v4，以此类推。
  4. 注意: 为了维持统一的缠绕方向（例如，所有三角形都是逆时针），硬件会自动“翻转”奇数位置三角形的顶点顺序（如将 v1, v2, v3 解释为 v1, v3, v2）。
• 效率分析:
  • 与三角形扇完全相同，渲染 m 个三角形也需要 m+2 个顶点。
  • 平均每三角形顶点数 $v_a$ 同样趋近于 1。
• 历史与现状: 曾经是提升性能的“黄金标准”，有大量研究致力于将任意网格分解为最优的三角形带。但如今，其优势已被更灵活、更高效的索引三角形网格所超越。

16.4.3 三角形网格 (Triangle Mesh) 与顶点缓存

• 核心概念: 这是现代GPU渲染复杂模型的标准方式。它使用一个独立的索引列表 (Index Buffer) 来引用顶点列表 (Vertex Buffer) 中的顶点，从而实现任意、灵活的顶点共享。

• 理论效率:

  • 对于一个封闭的、没有洞的（genus=0）大型三角网格，欧拉-庞加莱公式可以推导出一个重要结论：

    三角形数量 (f) ≈ 2 × 顶点数量 (v)

  • 这意味着，理论上每个三角形平均只对应 0.5 个顶点（$v/f\approx 0.5$）。这是比三角形带/扇的极限 1.0 更高的顶点复用率。

• 关键硬件：变换后顶点缓存 (Post-Transform Vertex Cache)

  • 工作原理: GPU内部有一个小型的FIFO或LRU缓存（通常能存16-32个顶点）。当一个顶点被顶点着色器处理后，其结果会被存入这个缓存。
  • 命中 (Hit): 如果索引缓冲区接下来的一个索引指向的顶点已经存在于缓存中，GPU会直接复用缓存里的结果，跳过 对该顶点的再次处理（变换、光照等）。
  • 未命中 (Miss): 如果顶点不在缓存中，GPU则必须完整地运行顶点着色器，并将新结果存入缓存（可能会踢出一个旧的顶点）。
  • 核心目标: 优化三角形的提交顺序，以最大化顶点缓存的命中率。

• 衡量指标：ACMR (Average Cache Miss Ratio)

  • 定义: 平均每个三角形引发了多少次顶点缓存未命中。即 “平均每个三角形实际处理了多少个顶点”。
  • 范围: 最好是 0.5 (大型闭合网格的理论最优值)，最差是 3.0 (完全没有复用)。
  • 意义: ACMR是衡量网格渲染顺序优劣的黄金标准。

16.4.4 缓存无关的网格布局：优化渲染顺序

• 问题: 不同的GPU拥有不同大小和策略的顶点缓存。为一个GPU优化出的最佳三角形顺序，在另一个GPU上可能表现不佳。

• 核心任务: 对索引缓冲区中的三角形顺序进行离线预处理，使其在任何大小的顶点缓存上都能获得良好的性能。

• 关键术语:

  • 缓存无关算法 (Cache-Oblivious Algorithm): 生成一种“通用”的渲染顺序，不依赖于特定的缓存大小。
  • 代表算法: Forsyth算法 和 Tipsify算法 是业界著名且高效的实现。

• 算法思想 (简述):

  1. 采用贪心策略，为待处理的顶点和三角形打分。
  2. 优先处理那些能连接到“最近”被处理过的顶点的三角形（倾向于绘制局部连贯的面片）。
  3. 算法会试图完成一小块区域再移动到下一块，其访问模式类似于希尔伯特曲线 (Hilbert curve)，具有良好的空间局部性。

• 实践建议: 将三角形顺序优化整合到你的资产处理管线中。这是一个低成本、高回报的自动化优化步骤，能显著提升顶点阶段的性能。

16.4.5 顶点与索引缓冲区：API实践

这部分讲述了在DirectX或OpenGL中如何具体实现上述概念。

• 关键对象:

  • 顶点缓冲区 (Vertex Buffer / VBO): 一块连续的GPU内存，用于存储所有唯一的顶点数据。
  • 索引缓冲区 (Index Buffer / IBO): 一块连续的GPU内存，用于存储定义三角形拓扑的顶点索引。

• 顶点数据布局:

  • 交错式 (Interleaved): 单个顶点的所有属性（位置、法线、UV等）都连续存放。这是GPU缓存最友好的方式。 [P0, N0, UV0, P1, N1, UV1, ...]
  • 非交错式/多流 (Multiple Streams): 每种属性存放在各自独立的缓冲区中。 [P0, P1, ...]，[N0, N1, ...]，[UV0, UV1, ...] 优点: 便于CPU端使用SIMD指令处理；当只需更新某一个属性时（如蒙皮动画只更新位置和法线），效率更高。

• 从模型文件到GPU缓冲区:

  • 挑战: 像 .obj 这样的模型文件格式，可能为位置、法线、UV提供各自独立的索引，以求文件尺寸最小。
  • 转换: GPU只支持单一索引。因此，必须将这种格式“展开”或“扁平化”。如果一个空间位置的顶点因为有不同的法线或UV而需要被当成不同的顶点处理（例如立方体的角），那么在最终的顶点缓冲区中，它就必须被复制成多个独立的顶点记录。
  • 优化: 将这种展开过程自动化，并确保生成的顶点/索引缓冲区是经过缓存优化排序的。

• 另一个缓存：变换前顶点缓存 (Pre-Transform Vertex Cache)

  • GPU在将顶点送入顶点着色器前，也有一个缓存。为了优化这个缓存，顶点缓冲区中顶点的物理顺序，最好能大致匹配它们在索引缓冲区中首次被访问的顺序。上述的网格优化算法通常也会处理这个问题。

16.5 网格简化 (Mesh Simplification)

核心目标与分类

• 核心观点: 网格简化是在尽可能保持模型原有外观的前提下，减少其多边形（三角形）数量的过程。其根本目的是降低渲染负载，让应用能够在不同性能的硬件上流畅运行，或者为远处的物体使用更低成本的模型。

• 关键术语:

  • 静态简化 (Static Simplification): 在游戏运行前，离线为同一个模型创建多个不同精度的版本，这些版本被称为 LOD (Level of Detail)。引擎在运行时根据物体距离等因素，选择其中一个LOD进行渲染。
  • 动态简化 (Dynamic Simplification): 在运行时动态地、连续地改变模型的面数，实现平滑的细节层次过渡，也称为 CLOD (Continuous Level of Detail)。
  • 视图相关简化 (View-Dependent Simplification): 同一个模型在视野内的各个部分具有不同的细节层次。最典型的应用是地形渲染，近处的地形网格密集，远处的网格稀疏。

动态简化的核心：边坍缩 (Edge Collapse)

• 核心概念: 边坍缩是实现动态简化的基本操作。它将一条边的两个顶点 u 和 v 合并为一个新顶点，这个操作会同时移除这条边以及共享这条边的两个三角形。
• 关键术语:
  • 渐进式网格 (Progressive Meshing): 边坍缩操作是可逆的（逆操作称为“顶点分裂”）。通过记录一系列的边坍缩操作，我们就可以从一个高精度模型平滑过渡到任意低精度的版本，反之亦然。这种技术对于网络传输模型非常有用（先传一个粗糙的基础网格，再逐步应用顶点分裂来增加细节）。
  • 放置策略 (Placement Strategy): 合并后的新顶点放在哪里？
    • 子集放置 (Subset Placement): 新顶点直接放在 u 或 v 的原始位置上。实现简单，但质量可能不高。
    • 最优放置 (Optimal Placement): 计算出一个全新的位置来最小化引入的视觉误差。这种策略能产生质量更高的简化网格。

关键问题：选择哪条边坍缩？—— 代价函数

• 核心观点: 简化算法的“灵魂”在于其代价函数 (Cost Function) 或 误差度量 (Error Metric)。算法每一次都会选择当前所有可坍缩的边中，代价“最低”的那条边进行坍缩，即选择对模型外观破坏最小的操作。

• 二次误差度量 (Quadric Error Metric, QEM):

  • 这是由Garland和Heckbert提出的一个非常经典且高效的代价函数。
  • 原理: 对每个顶点，计算一个“误差二次型”，它表示该顶点到其周围所有关联三角面片平面的距离平方和。一条边坍缩的代价，就是其合并后的新顶点所对应的误差值。
  • 公式: 新顶点 v 的代价 $c(v)$ 是： $c(\mathbf{v})={\sum }_{i=1}^m{\left({\mathbf{n}}_i\cdot \mathbf{v}+d_i\right)}^2$ 其中，$n_i$ 和 $d_i$ 定义了第 $i$ 个关联平面的方程 $n\cdot x+d=0$。算法会求解一个能使 $c(v)$ 最小化的新顶点位置 v。
  • 优点: QEM在速度和质量之间取得了很好的平衡，并且可以被扩展以保留模型的边界、材质接缝和尖锐折痕等重要特征。

简化的挑战与局限性

• 拓扑翻转: 错误的边坍缩可能导致网格自身发生交叉或翻转，必须在算法中进行检测和避免。
• 纹理扭曲: 这是最严重的问题之一。简化会改变网格的拓扑结构，导致UV坐标被拉伸和扭曲，使得纹理看起来“游移”或模糊。处理好纹理接缝是高级简化算法的重点。
• 对称性与重要特征: 自动化算法通常无法理解模型的美学特征，比如保持对称性，或者保留人脸的眼睛、嘴巴等关键区域。高质量的低多边形模型，往往还需要美术师进行重拓扑 (Retopology) 手动优化。

快速简化方法：顶点聚类 (Vertex Clustering)

• 概念: 一种更简单、更快速、更鲁棒的简化方法。
• 流程: 用一个三维网格（体素）覆盖整个模型，所有落入同一个网格单元内的顶点被强制合并成一个代表点。如果一个三角形的两个或三个顶点被合并，它就会退化（变成一条线或一个点），从而被移除。
• 优缺点: 质量通常不如QEM，但胜在速度快且极其稳健，甚至可以处理非流形的“脏”数据。非常适合用于处理用户生成内容（UGC）的场景。

---

16.6 压缩与精度 (Compression and Precision)

核心目标：减少每个顶点的数据量

• 核心观点: 压缩的目标不是减少三角形数量，而是减少描述每个顶点和索引所需占用的比特数。更小的数据量意味着更低的内存占用、更少的带宽消耗和更好的GPU缓存利用率。

• 关键技术:

  • 索引压缩: 最简单的压缩。如果模型的顶点数少于65536，就使用16位的 unsigned short 作为索引，而不是32位的 unsigned int，索引缓冲区大小直接减半。
  • 量化 (Quantization): 将高精度的浮点数映射到低精度的整数或半浮点数。
    • 颜色: float (32位) → unsigned byte (8位)。
    • 纹理坐标 (UV): 通常在 [0, 1] 范围内，可以用 unsigned short (16位) 或 half (16位浮点数) 精确表示。
    • 任意数据 (标量量化): 对于任意范围 [min, max] 的浮点数据，可以将其线性映射到 [0, 2^N-1] 的整数范围。在Shader中通过 value = stored_int * scale + offset 的方式解压，其中 scale 和 offset 作为常量传入。
    • 位置: 可以用 half 浮点数，或对整个模型应用一个变换矩阵（存储为常量），将顶点位置量化到 [-1, 1] 范围后用带符号短整型 signed short (16位) 存储。
  • 法线压缩: 法线是单位向量，所有法线都分布在一个单位球面上。可以利用这个几何特性进行高效压缩。例如，通过八象限/球面投影等方法，将一个三维向量用两个数值（如两个 byte 或 short）来表示。
  • 切线空间压缩: 法线、切线、副切线构成的TBN矩阵是正交的。我们只需存储法线和切线，然后在Shader中通过叉乘 bitangent = cross(normal, tangent) 实时计算出副切线。通常还需要1个比特位来存储手性（方向）。

“大世界”坐标系下的精度问题

• 问题: 在巨大的游戏世界（如开放世界或太空游戏）中，当物体距离世界原点 (0,0,0) 非常遥远时，标准的32位浮点数会丧失精度。因为浮点数的大部分比特位被用来表示整数部分（巨大的坐标值），导致小数部分的精度严重不足。
• 现象:
  • 顶点抖动 (Jittering): 物体在静止时也会轻微晃动。
  • 动画撕裂: 蒙皮动画的顶点会“游离”。
  • 阴影闪烁: 阴影边缘会随着摄像机的微小移动而跳变。
• 解决方案:
  • 相机相对渲染 (Camera-Relative Rendering): 在CPU端使用64位双精度浮点数计算出相机与物体之间的相对偏移，然后将这个高精度的相对偏移和相机矩阵传递给GPU。在Shader中，所有顶点变换都基于这个相对位置进行，从而避免了大坐标值带来的精度损失。
  • 世界分割 (World Partitioning): 将大世界切分成块（Chunks），当玩家进入一个新区域时，将世界原点动态地移动到该区域的中心。

总结：顶点数据压缩方法一览

这张表总结了常见的顶点属性及其压缩策略（参考原文图16.23）：

属性	常见格式	压缩后格式	备注
位置	float3 (12字节)	half3 (6字节) 或 short3 + scale/offset	关键的性能/质量权衡点
法线	float3 (12字节)	byte4 (4字节, e.g., 10_10_10_2 格式) 或 short2	使用球面坐标或投影等技术
纹理坐标	float2 (8字节)	half2 (4字节) 或 ushort2_norm	_norm 表示自动归一化到 [0,1]
颜色	float4 (16字节)	ubyte4_norm (4字节)	RGBA8格式，足够多数场景使用
切线空间	float3+float3 (24字节)	quat (e.g., 10_10_10_2 4字节)	用四元数编码整个TBN矩阵

---