网格处理与阴影图
网格模型是计算机图形学中最常用的三维表示方式。当我们在计算机中表示了一个三维网格（比如由大量三角形组成的兔子、茶壶）后，如何操控和优化它？这就涉及到本篇介绍的网格处理与阴影图技术。我们主要讨论以下三个主题：
- 网格细分（Mesh Subdivision） — 让粗糙模型变光滑
- 网格简化（Mesh Simplification） — 让精细模型变轻量
- 阴影图（Shadow Mapping） — 实时渲染中的阴影技术
网格细分
网格细分的核心任务是：引入更多的三角形，增加几何细节，并让模型表面变得更加平滑。
这不仅仅是把一个三角形劈成多个 — 最关键的是调整新旧顶点的位置，使模型表面趋向光滑。如果不调整位置，即使增加再多顶点，模型的棱角依旧不会改变。
下面介绍两种经典的细分方法：Loop 细分（Loop Subdivision） 和 Catmull-Clark 细分（Catmull-Clark Subdivision）。
Loop 细分
Loop 细分中的 “Loop” 不是”循环”的意思，而是其发明人 Charles Loop 的姓氏。
Loop 细分是专门针对三角形网格的细分算法。
Loop 细分的拓扑逻辑非常简单：将原网格中的每一个三角形，通过连接三条边的中点，一分为四。
拆分后，顶点被分成了两类：
- 新顶点（New Vertices）：边上的中点，由边分裂产生。
- 旧顶点（Old Vertices）：原有的顶点，位置需要根据邻居信息调整。
Loop 算法的核心就是分别用不同的加权平均公式来更新这两类顶点的位置，从而得到表面更加平滑的模型。
新顶点的更新
每一个新顶点都是由一条边分裂出来的。这条边在未分裂前，必然被两个三角形共享（边界边除外）。
如图所示，新顶点位于两个三角形的共享边
对于新顶点，更新公式为：
直观理解：新顶点的位置主要由所在边的两个端点决定（权重各
旧顶点的更新
对于旧顶点，我们认为它的新位置受自身坐标和其邻近顶点坐标的共同影响。假设它的度（Degree
/ Valence，即连接的边数）为
如图所示，旧顶点是多个三角形的共享顶点，它有
对于旧顶点，更新公式为：
其中，
- 当
时： - 当
时：
直观理解：旧顶点的新位置是自身位置与周围邻居平均位置的加权混合。邻居越多（
Catmull-Clark 细分
Loop 细分只能处理三角形网格。面对工业界更常见的四边形网格（Quad Mesh）或混合多边形网格，就需要 Catmull-Clark 细分。
Catmull-Clark 的核心目标是：把一个由任意多边形（三角形、四边形、五边形等混杂）组成的粗糙网格，全部转化为四边形网格，并让它更密、更光滑。
细分步骤
每一次 Catmull-Clark 细分，首先在原始网格上创建两类”新点”：
- 面点（Face Point）：取原网格每个面的几何中心（该面所有顶点的平均位置）。
- 边点（Edge Point）：取原网格每条边的中点。
之后对点进行连线，规则为：
- 把新创建的面点，和它周围所有相邻边的边点连接起来。
- 把原有的旧顶点，和与它相连的旧边的边点连接起来。
连线完成后，更新所有顶点的位置：
（1）新的面点
位置直接取该面所有原顶点的坐标平均值，保持不变。
（2）新的边点
一条边被两个面共享。新边点的位置等于该边两个端点与左右两个新面点的平均值：
其中
（3）旧的顶点
设该旧顶点
更新公式为：
核心结论
这里定义奇异点（Extraordinary Point / Singular
Point）为度数（连接边数）不等于
结论 1：非四边形面在 1 次细分后彻底消失。
对于每一个多边形面，从面点向每条边上的边点连线 — 显然，切分出来的新面全部是四边形。
结论 2：奇异点的数量在第 1 次细分后固定，之后不再增加。
- 对于面点：如果原多边形不是四边形，该面点的度数不等于
，成为奇异点。但根据结论 1，第 1 次细分后所有面都是四边形，此后新产生的面点度数恒为 ，不再是奇异点。 - 对于边点：边点必然向两侧面点连 2 条线、向两端顶点连 2
条线，因此所有新边点的度数恒为
，绝不可能是奇异点。
综合来看：经过第 1 次细分后，不会再有非四边形面，也就不会再产生新的奇异点。奇异点总数在第 1 次细分后固定下来。
网格简化
在三维场景中，如果所有物体（无论是远处的背景还是近处的特写）都使用最高精度的几何模型，显卡的计算资源很快就会被海量的三角形吞没。
为了解决这个问题，我们需要在保持模型原有外形特征（轮廓、视觉效果）的前提下，尽量减少三角形的数量。这就是网格简化（Mesh Simplification）。简化后的模型常用于构建 LOD（Level of Detail，细节层次）：离摄像机近时使用高精度模型，远时自动切换为低精度模型。
这里介绍一种经典的简化算法 — 基于 二次误差度量（Quadric Error Metrics, QEM） 的 边崩溃（Edge Collapse） 算法。
边崩溃
网格简化的基础操作有多种（如删除顶点、删除面等），但最可控、最常用的当属边崩溃：
选中网格上的一条边，将它的两个端点
和 合并成一个全新的顶点 。
拓扑变化：原本连接
由此，模型简化的核心问题变成两个：
- 位置问题：塌陷之后，新顶点
应该放在哪里，才能让模型变形最小？ - 顺序问题：整个模型有成千上万条边，应该先塌陷哪一条？
二次误差度量（QEM）
QEM 算法的核心思想是：用数学公式量化”如果塌陷这条边，会给模型带来多大的几何误差”。
QEM 将几何误差定义为：新顶点
数学上，每个三角面可以表示为一个平面方程
其中
整体流程（贪心算法 + 最小堆）
有了量化误差的方法，就可以对整个模型进行全局简化。这是一个典型的 贪心算法（Greedy Algorithm） 应用：
- 初始化：为网格中的每一条边，计算如果它被塌陷时能找到的”最佳新点位置
“以及对应的”最小误差值”。 - 构建优先队列：把所有边按照误差从小到大放入一个 最小堆（Min-Heap） 中。
- 循环塌陷（贪心核心）：
- 从堆顶取出当前误差最小的那条边。
- 执行边崩溃，将两个端点融合成计算好的新点
。 - 动态更新：这条边塌陷后，与它相邻的其他边的几何拓扑全部改变。需要重新计算这些邻近边的误差，并在最小堆中更新它们的位置。
- 结束条件：重复步骤 3，直到网格的三角形数量减少到预设的百分比（例如简化到只剩原模型的 20%）为止。
阴影图
前面介绍着色模型时我们提到，Blinn-Phong 等着色模型都是局部性的 — 只考虑着色点本身与光源的关系，并不会自动渲染出由其他物体遮挡产生的阴影。想要精确的阴影计算，可以使用光线追踪，但光追计算量大，更适合离线渲染。
这里介绍一种经典的实时阴影技术 — 阴影图（Shadow Mapping），它能在游戏等实时渲染场景中高效生成阴影。
Shadow Mapping 的核心思想非常直观：如果一个点在阴影里，说明它能被摄像机看到，但不能被光源看到。
两趟渲染流程（2-Pass）
Shadow Mapping 需要渲染场景两遍：
Pass 1：从光源视角渲染
把摄像机”移到”光源的位置，朝向场景：
- 在这个视角下正常进行光栅化，但不需要计算任何颜色。
- 我们只关心深度（Depth），把这个视角下渲染出来的深度缓冲（Depth Buffer）保存下来。这幅只记录了”距离光源最近的表面深度”的特殊纹理，就是阴影图（Shadow Map）。
Pass 2：从摄像机视角正常渲染
把摄像机放回真正的观察位置，正常渲染场景并输出到屏幕：
- 对于屏幕上的每个像素，通过光栅化找到它在三维空间中的真实点
。 - 计算点
距离摄像机的深度，进行常规的 Z-Buffer 测试，判断它是否该被绘制到屏幕上。 - 关键投影测试（Shading
阶段）：通过投影变换（坐标变换），计算出点
在光源视角下对应 Shadow Map 上的哪一个像素，同时算出点 距离光源的实际物理距离 。 - 读取 Shadow Map 中对应位置记录的最近深度
，进行比较：
- 如果
：说明从光源看过来，最先碰到的就是点 。点 在光照区，正常计算着色。
- 如果
：说明从光源看过来，在碰到点 之前已经碰到了更近的物体（该物体的距离是 ）。点 被遮挡，处于阴影区，只赋予环境光（Ambient）或直接涂黑。
是否使用阴影图的渲染效果对比如上。
补充说明
实际工程中，由于浮点精度的限制，
这次的插图来自画师 Aio
图片地址：https://www.pixiv.net/artworks/129636433