06｜几何（基本表示方法 & 曲线与曲面 & 网格处理）与阴影映射

课程主讲：闫令琪 (Lingqi Yan) | UCSB B站课程链接：https://www.bilibili.com/video/BV1X7411F744 本章对应课件：第 10 讲（Geometry 1: Introduction）、第 11 讲（Geometry 2: Curves and Surfaces）、第 12 讲（Geometry 3）

几何 (Geometry) 是图形学中极其重要且困难的一个主题。本文介绍几何的各种表示方法（隐式与显式）、曲线与曲面（贝塞尔曲线、B 样条、贝塞尔曲面）、网格处理（细分、简化、正规化）以及阴影映射 (Shadow Mapping) 技术。

1 几何表示方法

在图形学中，几何的表示方法可以分为两大类：隐式表示 (Implicit) 和 显式表示 (Explicit)。每种方法都有各自的优缺点，没有"最好"的表示方法，选择哪种取决于具体任务。

隐式几何 (Implicit)

隐式表示基于点的分类：点满足某种指定的关系（不会告诉你点的位置）。

例如，球面上所有点满足：

内外测试示例：对于球面 $f(x,y,z) = x^2 + y^2 + z^2 - 1$，判断点 $(3/4, 1/2, 1/4)$ 是否在内部：

结果为负，说明该点在球体内部。

显式几何 (Explicit)

显式表示中，所有点直接给出，或通过参数映射给出。

例如，一个环面的参数化表示：

隐式 vs 显式对比

“I hate meshes. I cannot believe how hard this is. Geometry is hard.” —— David Baraff (Pixar)

2 隐式几何的更多例子

在计算机图形学中，隐式几何有多种表示方法：

代数曲面 (Algebraic Surfaces)

表面由关于 $x, y, z$ 的多项式的零集定义。

局限：复杂的形状很难用单一的代数方程表示（如何绘制出现实场景中的奶牛，会很困难）。

构造实体几何 (Constructive Solid Geometry, CSG)

通过布尔运算（Boolean operations）组合简单的隐式几何体来构造复杂形状。

CSG 的布尔表达式可以用简单的函数运算表示：

• 并：$\min(f_A, f_B) = 0$
• 交：$\max(f_A, f_B) = 0$
• 差：$\max(f_A, -f_B) = 0$

CSG 广泛应用于 CAD 建模中，可以通过简单几何体的组合创建非常复杂的模型。

距离函数 (Distance Functions / SDF)

距离函数给出从任意位置到物体表面的最小距离（可以是带符号的距离，即 Signed Distance Function）。

核心思想：不用布尔运算直接组合表面，而是通过混合 (blending) 距离函数来逐渐融合表面。

距离函数的混合：任意两个距离函数 $d_1$、$d_2$ 可以通过线性插值来混合：

SDF 的优势：

• 可以实现平滑的几何体融合（如液滴合并效果）
• 适合光线追踪中的光线步进 (ray marching) 算法
• 整个场景可以由纯距离函数构成

水平集 (Level Sets)

水平集是距离函数的一种变体，将函数值存储在网格上（类似二维图像中的等高线）。

• 在网格的每个格点处存储函数值 $f(x, y, z)$
• 表面是 $f = 0$ 的等值面
• 通过插值可以得到光滑的表面

应用：医学成像（CT/MRI 数据的等值面提取）、物理模拟（如流体模拟中编码气-液界面距离）等。

分形 (Fractals)

分形几何具有自相似性 (self-similarity)：局部与整体在统计或精确意义上相似。

特点：

• 在所有尺度上都有细节
• 难以用传统方法描述
• 适用于描述自然现象：雪花、山脉、海岸线、树枝等

例子：Koch 雪花、Mandelbrot 集合、Sierpinski 三角形等。

问题：分形在放大后会出现无限细节，难以进行采样和渲染。

隐式表示的优缺点总结

3 显式几何的更多例子

显式几何在图形学中有多种表示方法：

点云 (Point Cloud)

最简单的表示方法：一个点列表 $(x, y, z)$。

点云常用于 3D 扫描、LiDAR 数据的原始表示。

多边形网格 (Polygon Mesh)

存储顶点和多边形（通常是三角形或四边形）。

Wavefront .obj 文件格式

.obj 是图形学研究中常用的文件格式，是一个文本文件，指定顶点、法线、纹理坐标及其连接关系。

# 顶点
v 1.000000 -1.000000 -1.000000
v 1.000000 -1.000000  1.000000
v -1.000000 -1.000000  1.000000
v -1.000000 -1.000000 -1.000000
...

# 纹理坐标
vt 0.748573 0.750412
...

# 法线
vn 0.000000 0.000000 -1.000000
...

# 面 (顶点索引/纹理坐标索引/法线索引)
f 5/1/1 1/2/1 4/3/1
f 5/1/1 4/3/1 8/4/1
...

关键格式：

• v x y z：顶点坐标
• vt u v：纹理坐标
• vn x y z：法线向量
• f v/vt/vn v/vt/vn v/vt/vn：面（每个顶点由 顶点索引/纹理坐标索引/法线索引 组成）

4 贝塞尔曲线 (Bezier Curves)

贝塞尔曲线是一种通过控制点定义的参数曲线，广泛应用于字体设计、路径动画、矢量图形等领域。

用切线定义三次贝塞尔曲线：给定控制点 $p_0, p_1, p_2, p_3$，起点切线 $t_0 = 3(p_1 - p_0)$，终点切线 $t_1 = 3(p_3 - p_2)$。

de Casteljau 算法

de Casteljau 算法通过递归线性插值来计算贝塞尔曲线上对应参数 $t$ 的点。

以二次贝塞尔曲线为例（3 个控制点 $b_0, b_1, b_2$）：

步骤 1：在 $b_0 b_1$ 上取 $t$ 比例处的点 $b_0^1$

步骤 2：在 $b_1 b_2$ 上取 $t$ 比例处的点 $b_1^1$

步骤 3：在 $b_0^1 b_1^1$ 上取 $t$ 比例处的点 $b_0^2$

步骤 4：对 $[0, 1]$ 中的每一个 $t$ 重复上述过程，即可得到整条曲线。

三次贝塞尔曲线（4 个控制点 $b_0, b_1, b_2, b_3$）：

同理进行递归线性插值：

最终 $b_0^3(t)$ 即为曲线上对应参数 $t$ 的点。

代数公式

de Casteljau 算法给出一个金字塔形的系数结构，每条向右的箭头乘以 $t$，向左的箭头乘以 $(1-t)$。

二次贝塞尔曲线的展开：

相当于 $x^2+2xy+y^2 = (x+y)^2$，以此类推三阶 $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$：二阶有三个点，三阶有四个点。

Bernstein 伯恩斯坦多项式与通式

$n$ 阶贝塞尔曲线的 Bernstein 形式：

其中 $B_j^n(t)$ 是 Bernstein 多项式（基函数）：

$\binom{n}{i}$ 为二次项系数，$\binom{n}{i} = \frac{n!}{i!(n-i)!}$，给每个控制点分配"公平的权重"。

三次贝塞尔曲线（$n = 3$）的展开：

三次贝塞尔基函数（Bernstein 多项式，$n=3$）：

Bernstein 系数构成帕斯卡三角（二项式展开系数）：

        1          (n=0)
      1   1        (n=1)
    1   2   1      (n=2)
  1   3   3   1    (n=3)  ← 三次贝塞尔
1   4   6   4   1  (n=4)

这些基函数满足：

• 非负性：$B_i^n(t) \geq 0$，对 $t \in [0, 1]$
• 归一性（和为1）：$\sum_{i=0}^{n} B_i^n(t) = 1$，对任意 $t$

贝塞尔曲线性质

凸包 (Convex Hull)：包含一组点的最小凸集。可以想象用一根橡皮筋围住所有点，橡皮筋收紧后的形状就是凸包。

分段贝塞尔曲线 (Piecewise Bezier Curves)

问题：高阶贝塞尔曲线（控制点多）非常难以控制，实际中很少使用。

解决方案：将多个低阶贝塞尔曲线链接在一起，最常用的是分段三次贝塞尔曲线。

分段三次贝塞尔曲线被广泛用于：字体设计、路径定义、Illustrator、Keynote 等（类似于里面的钢笔工具）。

分段贝塞尔曲线的连续性

设有两段贝塞尔曲线：

• $a: [k, k+1] \to \mathbb{R}^N$，控制点为 $a_0, a_1, \ldots, a_n$
• $b: [k+1, k+2] \to \mathbb{R}^N$，控制点为 $b_0, b_1, \ldots, b_n$

$C^1$ 连续的几何意义：连接点 $a_n(=b_0)$ 是前一段倒数第二个控制点 $a_{n-1}$ 和后一段第二个控制点 $b_1$ 的中点。

5 B样条 (B-splines)

样条 (Spline) 的定义：一条连续曲线，通过给定的点集，并具有特定数量的连续导数。简而言之，就是一条受控的曲线。

B样条 (B-splines) 全称为 Basis Splines（基样条）。

B样条 vs 贝塞尔曲线：

注意：本课程不深入讲解 B-splines 和 NURBS，也不涉及曲线的操作（如升降阶等）。更深入的内容可参考胡事民教授的课程：https://www.bilibili.com/video/av66548502

6 贝塞尔曲面 (Bezier Surfaces)

将贝塞尔曲线扩展到曲面。Ed Catmull 的 Gumbo 模型与 Utah Teapot 均为贝塞尔曲面的经典实例。

双三次贝塞尔曲面片 (Bicubic Bezier Surface Patch)

使用一个 $4 \times 4$ 的控制点数组来定义一个曲面片。

• 输入：$4 \times 4 = 16$ 个控制点
• 输出：由参数 $(u, v) \in [0,1]^2$ 定义的二维曲面

贝塞尔曲面的求值方法

采用可分离的 1D de Casteljau 算法：

目标：求对应参数 $(u, v)$ 的曲面位置。

步骤 1：在 $u$ 方向上，对 4 条贝塞尔曲线分别用 de Casteljau 算法求值，每条曲线在 $u$ 处得到一个点。这样得到 4 个"移动的"控制点。

步骤 2：用这 4 个控制点构成一条新的贝塞尔曲线，在 $v$ 方向上用 de Casteljau 算法求值。

最终得到的点即为曲面在 $(u, v)$ 处的位置：

7 曲面细分 (Mesh Subdivision)

网格细分是一种上采样 (upsampling) 操作：增加网格的分辨率，使表面更光滑。

Loop 细分

Loop 细分是三角形网格的常用细分方法。

核心思想：

1. 创建更多的三角形（顶点）
2. 调整顶点位置，让模型变得更加光滑

步骤 1：分裂三角形

将每个三角形分裂为 4 个小三角形（连接每条边的中点）。

步骤 2：更新顶点位置

新顶点和旧顶点使用不同的更新规则。

新顶点的更新（新顶点位于边上）：

其中 $A$、$B$ 是该边两端的旧顶点，$C$、$D$ 是与该边相邻的两个三角形的对面顶点。

旧顶点的更新（以度为 $n$ 的顶点为例）：

其中：

• $n$：顶点的度（相邻顶点数或顶点连接边的个数）
• $u$：权重，当 $n = 3$ 时 $u = 3/16$，当 $n > 3$ 时 $u = \frac{3}{8n}$

新顶点通过加权平均计算位置；旧顶点根据自己的位置和相邻老顶点的位置进行加权计算（自己的信息用多一些还是周围顶点的信息用多一些）进行更新；最终完成整个网格的细分。

Loop 细分效果：

Catmull-Clark 细分

Catmull-Clark 细分适用于一般网格（可以同时包含三角形和四边形）。

关键概念：

• 奇异点 (Extraordinary vertex)：度（顶点连接边的个数）不为 4 的顶点
• 三角形面的中心一定是一个度为 3 的奇异点

步骤 1：细分操作

对于每个面：

• 在每个面中添加一个面点 (Face point)：取面顶点的平均值
• 在每条边添加一个边点 (Edge point)：取边两端和相邻两个面点的平均值

步骤 2：连接

连接面点与边点，将每个面细分为 4 个四边形。

重要性质：

• 经过一次细分后，所有面都变成四边形
• 奇异点的数量在第一次细分后不再增加（每个非四边形面产生一个奇异点，之后所有面都是四边形）

一次细分思考题（课件示例网格）：一次细分后引入 2 个新奇异点（度 3 与度 5），非四边形面数量变为 0——所有非四边形面一次细分后都会消失。

Catmull-Clark 顶点更新规则（四边形网格）：

其中：

• $f_1, f_2, f_3, f_4$：相邻的面点
• $m_1, m_2, m_3, m_4$：相邻边的中点
• $p$：原顶点位置

收敛性：经过多次细分后，整体形状和折痕 (creases) 会趋于稳定。

Loop 细分 vs Catmull-Clark 细分

8 网格简化 (Mesh Simplification)

网格简化是一种下采样 (downsampling) 操作：在保持整体形状的前提下减少网格元素数量。

边坍缩 (Edge Collapse)

基本思想：通过坍缩边来简化网格——将一条边的两个顶点合并为一个顶点。

问题：坍缩边后，新顶点应该放在哪里？

• 简单方法：取两个顶点的平均值 → 效果不好
• 更好的方法：使用二次误差度量 (Quadric Error Metric) 选择最优位置

二次误差度量 (Quadric Error Metrics, QEM)

目标：量化简化引入的几何误差。

定义：新顶点应该最小化其到之前相关三角面所在平面的平方距离之和（L2 距离）。

具体计算：

• 对于每条待坍缩的边，计算其二次误差作为代价
• 简单做法：取边的中点，测量其二次误差
• 更好的做法：选择使二次误差最小化的点位置

距离近似：将到表面的距离近似为到包含三角形的平面距离之和。

简化算法流程

1. 对每条边，计算坍缩后的二次误差（作为该边的"代价"）
2. 选择代价最小（二次误差最小）的边进行坍缩
3. 坍缩后，更新受影响边的二次误差
4. 重复步骤 2-3，直到达到目标面数

这是一个贪心算法 (greedy algorithm)，每次选择当前最优的边进行坍缩，但效果非常好。

参考：Garland & Heckbert, 1997. “Surface Simplification Using Quadric Error Metrics”

使用优先队列 (Priority Queue)：

• 将所有边按二次误差排序
• 每次取出误差最小的边进行坍缩
• 坍缩后更新受影响边的误差值
• 重新排序

9 网格正规化 (Mesh Regularization)

网格正规化是一种保持三角形数量不变的操作：修改采样分布以提高网格质量。

目标：使三角形更接近正三角形，避免过细、过长的退化三角形。

方法：

• 调整顶点位置使三角形形状更均匀
• 不改变三角形的数量和连接关系
• 改善渲染质量和数值计算的稳定性

10 阴影映射 (Shadow Mapping)

阴影映射是光栅化中生成阴影的经典技术，是一种图像空间 (Image-space) 算法。

核心思想

关键观察：不在阴影中的点必须同时被光源和相机看到。

如果一个点：

• 被相机看到（在相机视图中可见）
• 但没有被光源看到（被光源视图中的其他物体遮挡）
• 那么该点在阴影中

两个 Pass 的详细流程

Pass 1：从光源渲染 (Render from Light)

1. 将相机放在光源位置
2. 渲染场景，只记录深度图 (Depth map)，不记录颜色
3. 这个深度图就是 Shadow Map——记录了从光源看，每个方向最近的物体距离

Pass 2A：从相机渲染 (Render from Eye)

1. 将相机放回原来的位置
2. 正常渲染场景（带深度），得到标准图像

Pass 2B：投影到光源并比较深度 (Project to Light)

1. 将相机视图中可见的每个点，重新投影回光源
2. 比较该点的深度与 Shadow Map 中对应位置的深度

可视化：光源视角的深度缓冲（Shadow Map），以及在着色点处比较 Dist(light, shading point) 与 shadow map 深度——绿色为深度近似相等（可见）的区域，非绿色即阴影所在。

阴影映射的伪代码

// Pass 1: 从光源渲染
RenderSceneFromLight():
    将相机移到光源位置
    渲染场景，只记录深度
    得到 shadow_map

// Pass 2: 从相机渲染
RenderSceneFromEye():
    将相机移到观察位置
    for each pixel (x, y):
        计算该像素对应的世界坐标点 P
        将 P 投影到光源的视图空间，得到深度 d_P
        查找 shadow_map 中对应位置的深度 d_shadow

        if d_P ≈ d_shadow:  // 深度匹配
            该点不在阴影中，正常着色
        else:  // d_P > d_shadow，被遮挡
            该点在阴影中，不着色（或降低亮度）

阴影映射的问题

硬阴影 vs 软阴影

阴影映射是经典的渲染技术，是早期动画电影（如《玩具总动员》）的基本阴影技术，也是几乎所有 3D 视频游戏中的标准阴影方案。

总结

本章涵盖了 GAMES101 几何部分的核心内容：

本文是 GAMES101 - 现代计算机图形学学习系列的第 6 篇笔记。