new_games_101

第6章：几何表示

本章深入探讨计算机图形学中几何对象的各种表示方法。我们将从基本的几何表示开始，逐步深入到参数化曲线曲面理论，最后讨论现代图形学中的网格处理技术和阴影图算法。对于AI科学家而言，理解这些几何表示不仅有助于3D视觉任务，还能为神经隐式表示（Neural Implicit Representations）等前沿技术打下坚实基础。

6.1 基本几何表示方法

6.1.1 隐式表示与显式表示

几何对象的数学表示主要分为两大类：

隐式表示（Implicit Representation）：通过方程 $f(\mathbf{x}) = 0$ 定义几何对象，其中 $\mathbf{x} \in \mathbb{R}^n$。

优点：

缺点：

显式表示（Explicit Representation）：直接给出几何对象上点的坐标，如参数化表示 $\mathbf{x} = \mathbf{g}(u, v)$。

优点：

缺点：

数学转换关系：

从隐式到显式的转换通常涉及：

从显式到隐式的转换方法：

混合表示的应用场景：

表示选择的决策因素：

  1. 查询类型：点测试频繁→隐式；遍历频繁→显式
  2. 修改需求：拓扑变化→隐式；局部编辑→显式
  3. 精度要求：解析表示→隐式；固定精度→显式
  4. 硬件限制：GPU友好→显式；CPU计算→隐式皆可
  5. 数据来源：扫描数据→显式；数学定义→隐式

6.1.2 代数表面

代数表面是由多项式方程定义的隐式表面。对于度数为 $d$ 的代数表面：

\[f(\mathbf{x}) = \sum_{i+j+k \leq d} a_{ijk} x^i y^j z^k = 0\]

代数表面的系数数量为 $\binom{d+3}{3}$，因此二次曲面有10个系数，三次曲面有20个系数。

二次曲面（Quadrics） 是最常用的代数表面（$d=2$）：

\[\mathbf{x}^T \mathbf{Q} \mathbf{x} + 2\mathbf{b}^T \mathbf{x} + c = 0\]

其中 $\mathbf{Q}$ 是 $3 \times 3$ 对称矩阵，可以写成展开形式： \(Q_{11}x^2 + Q_{22}y^2 + Q_{33}z^2 + 2Q_{12}xy + 2Q_{13}xz + 2Q_{23}yz + 2b_1x + 2b_2y + 2b_3z + c = 0\)

二次曲面的分类：

通过特征值分解 $\mathbf{Q} = \mathbf{V}\mathbf{\Lambda}\mathbf{V}^T$，根据特征值 $\lambda_1, \lambda_2, \lambda_3$ 的符号可以分类：

  1. 椭球体：三个正特征值 $(+,+,+)$
    • 标准形式：$\frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1$
    • 有界、凸、封闭曲面
  2. 单叶双曲面：两正一负 $(+,+,-)$
    • 标准形式：$\frac{x^2}{a^2} + \frac{y^2}{b^2} - \frac{z^2}{c^2} = 1$
    • 无界、鞍形曲面
  3. 双叶双曲面：一正两负 $(+,-,-)$
    • 标准形式：$\frac{x^2}{a^2} - \frac{y^2}{b^2} - \frac{z^2}{c^2} = 1$
    • 两个分离的无界部分
  4. 椭圆抛物面：两个非零特征值 $(+,+,0)$
    • 标准形式：$z = \frac{x^2}{a^2} + \frac{y^2}{b^2}$
    • 开放的碗状曲面
  5. 双曲抛物面：两个相反符号的非零特征值 $(+,-,0)$
    • 标准形式：$z = \frac{x^2}{a^2} - \frac{y^2}{b^2}$
    • 马鞍形曲面
  6. 圆柱面：一个零特征值 $(+,+,0)$，$\mathbf{b}$ 在零空间内
    • 标准形式：$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$
  7. 圆锥面：一个零特征值 $(+,+,0)$，顶点在原点
    • 标准形式：$\frac{x^2}{a^2} + \frac{y^2}{b^2} - z^2 = 0$
  8. 退化情况：
    • 平面对：两个零特征值
    • 直线：秩为1
    • 点：秩为0（仅当 $c > 0$）

标准形式转换：

  1. 找到二次型的中心（如果存在）：$\mathbf{x}_0 = -\mathbf{Q}^{-1}\mathbf{b}$
  2. 平移：$\mathbf{x}’ = \mathbf{x} - \mathbf{x}_0$
  3. 旋转：$\mathbf{y} = \mathbf{V}^T\mathbf{x}’$
  4. 得到标准形式：$\sum_{i=1}^3 \lambda_i y_i^2 + d = 0$

其中 $d = c - \mathbf{b}^T\mathbf{Q}^{-1}\mathbf{b}$（对于非退化情况）

光线-二次曲面求交：

将光线 $\mathbf{r}(t) = \mathbf{o} + t\mathbf{d}$ 代入二次曲面方程： \(at^2 + bt + c = 0\)

其中：

交点数量分析：

法向量计算：在交点 $\mathbf{p}$ 处，法向量为： \(\mathbf{n} = \nabla f(\mathbf{p}) = 2\mathbf{Q}\mathbf{p} + 2\mathbf{b}\)

高次代数表面：

  1. 三次曲面（$d=3$）：
    • 最多27条直线（Cayley-Salmon定理）
    • 包含Clebsch对角三次曲面、Fermat三次曲面
    • 可表示部分torus形状
  2. 四次曲面（$d=4$）：
    • Torus（环面）：$(x^2 + y^2 + z^2 + R^2 - r^2)^2 - 4R^2(x^2 + y^2) = 0$
    • Kummer曲面：具有16个奇点的特殊四次曲面
    • Steiner的Roman曲面：$x^2y^2 + y^2z^2 + z^2x^2 = r^2xyz$
  3. 特殊代数曲面：
    • Cayley曲面：三次确定性曲面，有4个锥形奇点
    • Enneper曲面：八次极小曲面
    • Boy曲面：实投影平面的浸入

代数几何中的重要定理：

  1. Bézout定理：
    • 平面情况：度数为 $m$ 和 $n$ 的代数曲线最多有 $mn$ 个交点（计重数）
    • 空间推广：代数簇的交集维数和度数关系
  2. Harnack定理：
    • 度数为 $d$ 的非奇异实代数曲线的连通分支数最多为 $\frac{(d-1)(d-2)}{2} + 1$
    • 对于曲面：限制了实部分的拓扑复杂度
  3. 代数曲面的拓扑不变量：
    • 欧拉特征数：$\chi = 2 - 2g + s$（$g$ 是亏格，$s$ 是奇点数）
    • Hodge数：描述曲面的复杂几何结构

计算技巧与优化：

  1. 隐式化：从参数表示转换为隐式表示
    • 使用结式（resultant）消去参数
    • Gröbner基方法
  2. 多项式求值优化：
    • Horner法则：减少乘法次数
    • 利用对称性减少计算
  3. 数值稳定性：
    • 条件数分析：病态二次型的处理
    • 使用齐次坐标避免无穷远点问题

6.1.3 构造实体几何（CSG）

CSG通过布尔运算组合简单几何体构建复杂形状。这是CAD系统中的核心技术，特别适合工程设计和精确建模。

基本布尔运算：

对于两个隐式表示的对象 $A: f_A(\mathbf{x}) \leq 0$ 和 $B: f_B(\mathbf{x}) \leq 0$：

R-函数理论：

Rvachev函数提供了保持可微性的布尔运算：

这些函数保证了 $C^1$ 连续性，梯度为： \(\nabla f_{A \cup B} = \nabla f_A \left(1 + \frac{f_A}{\sqrt{f_A^2 + f_B^2}}\right) + \nabla f_B \left(1 + \frac{f_B}{\sqrt{f_A^2 + f_B^2}}\right)\)

平滑布尔运算：

为避免尖锐边缘并改善数值性质，可使用各种平滑函数：

  1. 指数平滑（LogSumExp）： \(\text{smin}(a, b, k) = -\frac{1}{k}\log(e^{-ka} + e^{-kb})\)
    • 当 $k \to \infty$ 时趋向于标准 $\min$
    • 保持 $C^\infty$ 连续性
  2. 多项式平滑： \(\text{smin}(a, b, k) = \frac{a + b - \sqrt{(a-b)^2 + k^2}}{2}\)
    • 计算效率高
    • 过渡区域宽度为 $O(k)$
  3. 幂平滑： \(\text{smin}(a, b, k) = (a^{-k} + b^{-k})^{-1/k}\)
    • 要求 $a, b > 0$
    • 适合正定距离场
  4. 三次平滑： 在过渡区域 $|a - b| < k$ 内使用Hermite插值： \(h(t) = 3t^2 - 2t^3, \quad t = \frac{a - b + k}{2k}\)

CSG树结构：

CSGNode = Leaf(Primitive, Transform)
        | Internal(Operation, CSGNode, CSGNode)
        | Transform(Matrix, CSGNode)

树的属性：

CSG树的优化：

  1. 空间包围盒剪枝：
    • 并集：$\text{BBox}(A \cup B) = \text{BBox}(A) \cup \text{BBox}(B)$
    • 交集：$\text{BBox}(A \cap B) = \text{BBox}(A) \cap \text{BBox}(B)$
  2. 树平衡：
    • 使用启发式方法重组树以最小化深度
    • 相似大小的对象优先组合
  3. 公共子表达式消除：
    • 识别重复的子树
    • 使用DAG（有向无环图）代替树

光线追踪CSG：

经典的区间分类算法：

  1. 交点计算：
    • 对每个叶节点计算光线交点 ${t_i^{\text{in}}, t_i^{\text{out}}}$
    • 考虑数值容差处理相切情况
  2. 区间合并： 
    Union: 合并重叠区间
Intersection: 取区间交集
Difference: 从第一个区间中减去第二个
  3. 法向量计算：
    • 叶节点：直接计算几何体法向
    • 并集：选择较小 SDF 值的法向
    • 交集：选择较大 SDF 值的法向
    • 差集：可能需要翻转法向

改进的算法：

  1. Goldfeather算法：
    • 使用深度缓冲和模板缓冲
    • 适合GPU实现
  2. SCS（Sequenced Convex Subtraction）：
    • 将CSG转换为凸集的差集序列
    • 减少渲染遍数

CSG到边界表示的转换：

  1. 边界求值算法：
    • 计算所有基本体的交线
    • 根据布尔运算选择保留的边界片段
    • 拼接成完整的边界表示
  2. Marching Cubes扩展：
    • 在体素网格上评估CSG函数
    • 使用双线性插值提高精度

CSG的数学性质：

  1. 正则化布尔运算： \(A \cup^* B = \text{closure}(\text{interior}(A \cup B))\)
    • 消除悬挂边和孤立点
    • 保证结果是有效的实体
  2. CSG的完备性：
    • 任何正则集可以表示为有限个半空间的正则布尔组合
    • 实践中受基本体集合的限制

应用领域：

  1. CAD/CAM：
    • 机械零件设计
    • 建筑建模
    • 3D打印路径规划
  2. 游戏引擎：
    • 破坏系统（实时布尔运算）
    • 程序化内容生成
  3. 科学可视化：
    • 分子建模（范德华表面）
    • 地质建模（地层结构）

性能优化技巧：

  1. 空间哈希：加速邻近查询
  2. 层次化采样：自适应细化
  3. GPU并行化：利用片元着色器
  4. 增量更新：局部重计算

CSG的优缺点：

优点：

缺点：

6.1.4 符号距离场（SDF）

SDF是一种特殊的隐式表示，其中 $f(\mathbf{x})$ 表示点 $\mathbf{x}$ 到表面的有符号距离：

\[f(\mathbf{x}) = \text{sign}(\mathbf{x}) \cdot \min_{\mathbf{y} \in \partial S} \|\mathbf{x} - \mathbf{y}\|\]

其中符号函数定义为： \(\text{sign}(\mathbf{x}) = \begin{cases} -1 & \text{如果 } \mathbf{x} \text{ 在物体内部} \\ 0 & \text{如果 } \mathbf{x} \text{ 在表面上} \\ +1 & \text{如果 } \mathbf{x} \text{ 在物体外部} \end{cases}\)

SDF的数学性质：

  1. 梯度性质：
    • $|\nabla f| = 1$ 几乎处处成立（除了中轴上）
    • 法向量：$\mathbf{n} = \nabla f$
    • 梯度指向远离表面的方向

  2. 最近点映射： \(\mathbf{p}_{\text{closest}}(\mathbf{x}) = \mathbf{x} - f(\mathbf{x})\nabla f(\mathbf{x})\) 这个映射在中轴（medial axis）上不连续

  3. 曲率与Hessian的关系： 在表面上，主曲率 $\kappa_1, \kappa_2$ 是Hessian矩阵 $\mathbf{H}_f$ 的特征值

  4. 水平集性质：
    • 表面：${\mathbf{x} : f(\mathbf{x}) = 0}$
    • 偏移表面：${\mathbf{x} : f(\mathbf{x}) = d}$

Eikonal方程：

SDF满足偏微分方程： \(\|\nabla f\| = 1\)

这是一个Hamilton-Jacobi方程，可通过以下方法求解：

  1. 快速行进法（FMM）：
    • 基于Dijkstra算法的思想
    • 时间复杂度：$O(N \log N)$
    • 单向传播，适合单源问题
  2. 快速扫描法（FSM）：
    • 使用Gauss-Seidel迭代
    • 多次扫描直到收敛
    • 简单实现，易于并行化
  3. 并行算法：
    • GPU上的并行扫描
    • 分块并行FMM

基本几何体的解析SDF：

  1. 球体（半径$r$，中心$\mathbf{c}$）： \(f(\mathbf{x}) = \|\mathbf{x} - \mathbf{c}\| - r\)

  2. 立方体（半边长$\mathbf{b}$）： \(f(\mathbf{x}) = \|\max(\mathbf{0}, |\mathbf{x}| - \mathbf{b})\|_\infty + \min(\max(|x|-b_x, |y|-b_y, |z|-b_z), 0)\)

  3. 圆环体（大半径$R$，小半径$r$）： \(f(\mathbf{x}) = \sqrt{(R - \sqrt{x^2 + y^2})^2 + z^2} - r\)

  4. 圆柱体（半径$r$，高度$h$）： \(f(\mathbf{x}) = \max(\sqrt{x^2 + y^2} - r, |z| - h/2)\)

  5. 圆锥（底半径$r$，高度$h$）： \(f(\mathbf{x}) = \max(\sqrt{x^2 + y^2} - r(1 - z/h), z)\)

  6. 八面体（半径$r$）： \(f(\mathbf{x}) = (|x| + |y| + |z| - r) / \sqrt{3}\)

SDF的变换操作：

  1. 刚体变换：
    • 平移：$f_T(\mathbf{x}) = f(\mathbf{x} - \mathbf{t})$
    • 旋转：$f_R(\mathbf{x}) = f(\mathbf{R}^{-1}\mathbf{x})$
    • 组合：$f_{TR}(\mathbf{x}) = f(\mathbf{R}^{-1}(\mathbf{x} - \mathbf{t}))$

  2. 非均匀缩放（破坏距离场性质）： \(f_S(\mathbf{x}) \approx \min(s_x, s_y, s_z) \cdot f(\mathbf{x}/\mathbf{s})\)

  3. 对称操作：
    • 镜像：$f_{\text{mirror}}(\mathbf{x}) = f( x , y, z)$
    • 重复：$f_{\text{repeat}}(\mathbf{x}) = f(\text{mod}(\mathbf{x}, \mathbf{p}) - \mathbf{p}/2)$
  4. 扭曲变换：
    • 弯曲：应用非线性空间变换
    • 扭转：$\mathbf{x}’ = (x\cos(\theta z) - y\sin(\theta z), x\sin(\theta z) + y\cos(\theta z), z)$

SDF的组合运算：

  1. 标准布尔运算（破坏距离场性质）：
    • 并集：$f_{A \cup B} = \min(f_A, f_B)$
    • 交集：$f_{A \cap B} = \max(f_A, f_B)$
    • 差集：$f_{A - B} = \max(f_A, -f_B)$
  2. 改进的运算（部分保持距离场性质）：
    • Quilez的平滑最小： \(\text{smin}(a, b, k) = \min(a, b) - h(k)\) 其中 $h(k) = k^2 / 4$ 当 $|a - b| < k$
  3. 精确距离场运算：
    • 需要考虑中轴变化
    • 计算复杂度高
    • 通常使用近似方法

光线行进（Ray Marching）算法：

float rayMarch(vec3 ro, vec3 rd, float tMin, float tMax) {
    float t = tMin;
    for (int i = 0; i < MAX_STEPS; i++) {
        vec3 p = ro + t * rd;
        float d = SDF(p);
        
        if (d < EPSILON) return t;  // 命中
        if (t > tMax) break;        // 超出范围
        
        t += d * STEP_SCALE;        // 保守步进
    }
    return -1.0;  // 未命中
}

优化技术：

  1. 自适应步长：
    • 近表面时减小步长
    • 使用梯度信息调整
  2. 空间划分：
    • 包围盒层次结构
    • 八叉树加速
  3. 屏幕空间优化：
    • 时间相干性利用
    • 分层光线行进

SDF的高级应用：

  1. 实时渲染：
    • 体积渲染效果
    • 软阴影和环境光遮蔽
    • 次表面散射近似
  2. 物理仿真：
    • 碰撞检测：$d = \text{SDF}(\mathbf{p})$
    • 接触力计算：$\mathbf{f} = -k \cdot d \cdot \nabla\text{SDF}$
    • 流体边界条件
  3. 形状分析：
    • 中轴提取
    • 形状描述子
    • 对称性检测
  4. 机器学习应用：
    • DeepSDF：神经网络隐式表示
    • Neural Implicit Surfaces：连续形状表示
    • Occupancy Networks：占用概率场
  5. 形状操作：
    • 形态学操作（腐蚀、膨胀）
    • 形状插值：$f_t = (1-t)f_0 + tf_1$
    • 形状优化

数值方法与实现：

  1. 离散化存储：
    • 规则网格：简单但内存密集
    • 自适应网格：八叉树、KD树
    • 稀疏表示：仅存储窄带
  2. 插值方法：
    • 三线性插值：$C^0$ 连续
    • 三次插值：$C^1$ 连续
    • WENO方案：高阶精度
  3. 梯度计算：
    • 有限差分：$(f(x+h) - f(x-h))/(2h)$
    • 解析梯度：对于已知函数
    • 自动微分：对于复杂组合

常见问题与解决方案：

  1. C¹不连续性：
    • 在布尔运算边界
    • 使用平滑运算缓解
  2. 数值误差累积：
    • 多次变换后的误差
    • 定期重新初始化
  3. 中轴奇异性：
    • 梯度不存在
    • 使用正则化方法

6.1.5 点云与体素表示

点云表示：

点云处理技术：

移动最小二乘（MLS）表面： 对于查询点 $\mathbf{x}$，拟合局部参考平面： \(\min_{\mathbf{n}, d} \sum_{i} w_i(\mathbf{x})[\mathbf{n} \cdot \mathbf{p}_i - d]^2\) 其中权重函数 $w_i(\mathbf{x}) = \exp(-|\mathbf{x} - \mathbf{p}_i|^2/h^2)$

体素表示：

八叉树结构：

体素化算法：

  1. 保守光栅化：确保不丢失薄结构
  2. 深度剥离：处理非流形和自相交
  3. GPU并行化：使用原子操作
  4. 层次生成：自底向上构建八叉树

混合表示：

现代应用：

6.1.6 网格表示

多边形网格（主要是三角网格）是实时图形学的主流表示：

基本元素：

网格数据结构：

  1. 面表（Face List）：
    • 简单但冗余：每个面存储顶点索引列表
    • 适合静态网格和GPU渲染
    • 邻接查询效率低
  2. 边表（Edge List）：
    • 显式存储边信息
    • 支持非流形结构
    • 需要额外索引维护拓扑
  3. 半边数据结构（Half-Edge）： 
    struct HalfEdge {
 Vertex* vertex;      // 指向的顶点
 HalfEdge* twin;      // 对偶半边
 HalfEdge* next;      // 下一条半边
 Face* face;          // 所属面片
};
    • 高效的局部遍历
    • 只支持流形网格
    • 常用于网格编辑操作
  4. 翼边结构（Winged-Edge）：
    • 每条边存储四个相邻元素
    • 对称性好但访问复杂

欧拉公式：对于连通的多面体网格： \(V - E + F = 2(1 - g)\) 其中 $V$ 是顶点数，$E$ 是边数，$F$ 是面数，$g$ 是亏格（genus）。

网格的性质：

网格质量度量：

常见网格操作：

网格的紧凑表示：

6.2 曲线与曲面

6.2.1 参数曲线基础

参数曲线 $\mathbf{c}(t): [a, b] \rightarrow \mathbb{R}^3$ 的基本微分几何：

切向量：$\mathbf{t}(t) = \frac{d\mathbf{c}}{dt}$

弧长参数化：$s(t) = \int_a^t |\mathbf{c}’(\tau)| d\tau$

曲率：$\kappa = \frac{|\mathbf{t}’ \times \mathbf{t}|}{|\mathbf{t}|^3}$

Frenet-Serret标架：

Frenet-Serret公式： \(\begin{pmatrix} \mathbf{T}' \\ \mathbf{N}' \\ \mathbf{B}' \end{pmatrix} = \begin{pmatrix} 0 & \kappa & 0 \\ -\kappa & 0 & \tau \\ 0 & -\tau & 0 \end{pmatrix} \begin{pmatrix} \mathbf{T} \\ \mathbf{N} \\ \mathbf{B} \end{pmatrix}\)

6.2.2 贝塞尔曲线

$n$ 次贝塞尔曲线由 $n+1$ 个控制点 ${\mathbf{P}i}{i=0}^n$ 定义：

\[\mathbf{B}(t) = \sum_{i=0}^n B_i^n(t) \mathbf{P}_i\]

其中 $B_i^n(t) = \binom{n}{i}t^i(1-t)^{n-i}$ 是Bernstein基函数。

性质：

de Casteljau算法：递归计算 $\mathbf{B}(t)$： \(\mathbf{P}_i^{(k)}(t) = (1-t)\mathbf{P}_i^{(k-1)} + t\mathbf{P}_{i+1}^{(k-1)}\)

导数： \(\mathbf{B}'(t) = n\sum_{i=0}^{n-1} B_i^{n-1}(t)(\mathbf{P}_{i+1} - \mathbf{P}_i)\)

6.2.3 B样条曲线

B样条通过局部基函数实现局部控制：

\[\mathbf{C}(t) = \sum_{i=0}^{n} N_{i,p}(t) \mathbf{P}_i\]

其中 $N_{i,p}(t)$ 是 $p$ 次B样条基函数，由Cox-de Boor递归定义：

\[N_{i,0}(t) = \begin{cases} 1 & t_i \leq t < t_{i+1} \\ 0 & \text{否则} \end{cases}\] \[N_{i,p}(t) = \frac{t - t_i}{t_{i+p} - t_i}N_{i,p-1}(t) + \frac{t_{i+p+1} - t}{t_{i+p+1} - t_{i+1}}N_{i+1,p-1}(t)\]

节点向量：${t_0, t_1, …, t_{m}}$，其中 $m = n + p + 1$

性质：

6.2.4 NURBS（非均匀有理B样条）

NURBS通过引入权重和有理形式扩展B样条：

\[\mathbf{C}(t) = \frac{\sum_{i=0}^{n} w_i N_{i,p}(t) \mathbf{P}_i}{\sum_{i=0}^{n} w_i N_{i,p}(t)}\]

优势：

6.2.5 参数曲面

双参数曲面 $\mathbf{S}(u,v): D \subset \mathbb{R}^2 \rightarrow \mathbb{R}^3$

第一基本形式：度量曲面上的距离 \(I = E du^2 + 2F du dv + G dv^2\) 其中：

法向量： \(\mathbf{n} = \frac{\mathbf{S}_u \times \mathbf{S}_v}{|\mathbf{S}_u \times \mathbf{S}_v|}\)

第二基本形式：描述曲面的弯曲 \(II = L du^2 + 2M du dv + N dv^2\) 其中：

主曲率：Weingarten矩阵的特征值 \(\mathbf{W} = \begin{pmatrix} L & M \\ M & N \end{pmatrix} \begin{pmatrix} E & F \\ F & G \end{pmatrix}^{-1}\)

高斯曲率：$K = \kappa_1 \kappa_2 = \frac{LN - M^2}{EG - F^2}$

平均曲率：$H = \frac{\kappa_1 + \kappa_2}{2} = \frac{EN - 2FM + GL}{2(EG - F^2)}$

6.2.6 细分曲面

细分方案通过递归细化网格生成光滑曲面。

Loop细分（三角网格）：

Catmull-Clark细分（四边形网格）：

极限曲面在正则顶点处为 $C^2$ 连续，在非正则顶点处为 $C^1$ 连续。

6.3 网格处理与阴影图

6.3.1 网格简化

网格简化旨在减少多边形数量同时保持视觉质量。

边收缩（Edge Collapse）： 将边 $(v_i, v_j)$ 收缩到新顶点 $\bar{v}$。使用二次误差度量（QEM）：

每个顶点关联误差二次型： \(Q_v = \sum_{p \in \text{planes}(v)} K_p\)

其中 $K_p = \mathbf{n}_p\mathbf{n}_p^T$ 对于平面 $\mathbf{n}_p^T\mathbf{x} + d = 0$。

边收缩代价： \(\text{cost}(v_i, v_j) = \min_{\bar{v}} \bar{v}^T(Q_i + Q_j)\bar{v}\)

最优位置通过求解线性系统获得： \(\bar{v} = -(Q_i + Q_j)^{-1}\mathbf{b}\)

顶点聚类： 将空间划分为网格，每个单元内的顶点合并为一个代表顶点。

6.3.2 网格参数化

将3D曲面映射到2D参数域 $\phi: M \rightarrow \mathbb{R}^2$。

调和映射（Harmonic Mapping）： 最小化Dirichlet能量： \(E_D = \frac{1}{2}\int_M |\nabla \phi|^2 dA\)

离散化后得到线性系统： \(\sum_{j \in N(i)} w_{ij}(u_j - u_i) = 0\)

权重选择：

保角参数化（Conformal Parameterization）： 最小化角度畸变，使用复数表示和Cauchy-Riemann方程。

LSCM（最小二乘保角映射）： \(\min_{\phi} \sum_{T} A_T ||\nabla \phi - R_{90°}\nabla \phi||^2\)

6.3.3 网格平滑

拉普拉斯平滑： \(\mathbf{v}_i^{new} = \mathbf{v}_i + \lambda \mathbf{L}(\mathbf{v}_i)\)

其中离散拉普拉斯算子： \(\mathbf{L}(\mathbf{v}_i) = \frac{1}{|N(i)|}\sum_{j \in N(i)} (\mathbf{v}_j - \mathbf{v}_i)\)

双边滤波扩展： \(\mathbf{v}_i^{new} = \mathbf{v}_i + \lambda \sum_{j \in N(i)} w_s(\||\mathbf{v}_j - \mathbf{v}_i||) w_n(\mathbf{n}_i \cdot \mathbf{n}_j) (\mathbf{v}_j - \mathbf{v}_i)\)

6.3.4 网格修复

孔洞填充：

  1. 检测边界环
  2. 三角化边界多边形（最小角度、最小面积）
  3. 细分和平滑新增三角形

自相交检测与修复：

6.3.5 阴影图（Shadow Mapping）

阴影图是实时渲染中生成阴影的标准技术。

基本算法：

  1. 从光源视角渲染场景，存储深度
  2. 从相机视角渲染，测试每个片元是否在阴影中

深度比较： 对于世界空间点 $\mathbf{p}$：

  1. 变换到光源空间：$\mathbf{p}{light} = \mathbf{M}{light}\mathbf{p}$
  2. 采样阴影图：$z_{stored} = \text{ShadowMap}(p_{light}.xy)$
  3. 比较深度：$\text{inShadow} = (p_{light}.z > z_{stored} + \text{bias})$

深度偏移（Bias）问题：

6.3.6 级联阴影图（CSM）

将视锥体分割为多个子区域，每个使用独立的阴影图。

分割策略：

层级选择：

float depth = length(viewPos);
int cascade = 0;
for (int i = 0; i < NUM_CASCADES - 1; i++) {
    if (depth > cascadeSplits[i]) cascade = i + 1;
}

6.3.7 软阴影技术

PCF（Percentage Closer Filtering）： \(\text{shadow} = \frac{1}{N}\sum_{i=1}^N \text{ShadowTest}(\mathbf{p} + \delta_i)\)

PCSS（Percentage Closer Soft Shadows）：

  1. 阻挡物搜索：估计平均阻挡物深度
  2. 半影估计：$w_{penumbra} = (d_{receiver} - d_{blocker}) \cdot w_{light} / d_{blocker}$
  3. PCF过滤：使用估计的半影大小

方差阴影图（VSM）： 存储深度和深度平方，使用Chebyshev不等式估计阴影概率： \(P(z \geq t) \leq \frac{\sigma^2}{\sigma^2 + (t - \mu)^2}\)

6.3.8 光线追踪阴影

硬阴影： 发射阴影光线从着色点到光源： \(\text{visible} = \begin{cases} 1 & \text{无遮挡} \\ 0 & \text{有遮挡} \end{cases}\)

软阴影： 对面光源采样多条光线： \(L = \frac{1}{N}\sum_{i=1}^N V(\mathbf{p}, \mathbf{x}_i) \cdot L_e(\mathbf{x}_i) \cdot G(\mathbf{p}, \mathbf{x}_i)\)

其中 $V$ 是可见性函数，$G$ 是几何项。

6.3.9 环境光遮蔽（AO）

屏幕空间环境光遮蔽（SSAO）： \(AO(\mathbf{p}) = \frac{1}{N}\sum_{i=1}^N \text{visibility}(\mathbf{p}, \mathbf{p} + \mathbf{s}_i)\)

采样点在半球内随机分布，使用深度缓冲判断遮挡。

预计算AO：

本章小结

本章系统介绍了计算机图形学中的几何表示方法：

基本几何表示：

曲线与曲面理论：

网格处理与阴影技术：

练习题

基础题

练习 6.1：给定一个椭球的隐式方程 $\frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1$，推导其在点 $(x_0, y_0, z_0)$ 处的法向量。

提示：法向量是梯度方向 $\nabla f$。

答案 对隐式函数 $f(x,y,z) = \frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} - 1$ 求梯度： $$\nabla f = \left(\frac{2x}{a^2}, \frac{2y}{b^2}, \frac{2z}{c^2}\right)$$ 在点 $(x_0, y_0, z_0)$ 处的单位法向量： $$\mathbf{n} = \frac{1}{\sqrt{\frac{4x_0^2}{a^4} + \frac{4y_0^2}{b^4} + \frac{4z_0^2}{c^4}}} \left(\frac{2x_0}{a^2}, \frac{2y_0}{b^2}, \frac{2z_0}{c^2}\right)$$

练习 6.2：证明三次贝塞尔曲线的中点 $\mathbf{B}(0.5)$ 可以表示为： \(\mathbf{B}(0.5) = \frac{1}{8}(\mathbf{P}_0 + 3\mathbf{P}_1 + 3\mathbf{P}_2 + \mathbf{P}_3)\)

提示：代入 $t = 0.5$ 到贝塞尔曲线公式。

答案 三次贝塞尔曲线： $$\mathbf{B}(t) = (1-t)^3\mathbf{P}_0 + 3t(1-t)^2\mathbf{P}_1 + 3t^2(1-t)\mathbf{P}_2 + t^3\mathbf{P}_3$$ 代入 $t = 0.5$： - $(1-0.5)^3 = 0.125 = \frac{1}{8}$ - $3 \cdot 0.5 \cdot (0.5)^2 = 3 \cdot 0.5 \cdot 0.25 = 0.375 = \frac{3}{8}$ - $3 \cdot (0.5)^2 \cdot 0.5 = 3 \cdot 0.25 \cdot 0.5 = 0.375 = \frac{3}{8}$ - $(0.5)^3 = 0.125 = \frac{1}{8}$ 因此： $$\mathbf{B}(0.5) = \frac{1}{8}\mathbf{P}_0 + \frac{3}{8}\mathbf{P}_1 + \frac{3}{8}\mathbf{P}_2 + \frac{1}{8}\mathbf{P}_3 = \frac{1}{8}(\mathbf{P}_0 + 3\mathbf{P}_1 + 3\mathbf{P}_2 + \mathbf{P}_3)$$

练习 6.3：对于一个三角形网格，已知顶点数 $V = 100$，面数 $F = 196$，使用欧拉公式计算边数 $E$。假设网格是单连通的（genus = 0）。

提示：欧拉公式 $V - E + F = 2(1 - g)$。

答案 对于单连通网格（$g = 0$）： $$V - E + F = 2(1 - 0) = 2$$ 代入已知值： $$100 - E + 196 = 2$$ $$296 - E = 2$$ $$E = 294$$ 验证：对于三角网格，每个面有3条边，每条边被2个面共享，所以 $E = \frac{3F}{2} = \frac{3 \times 196}{2} = 294$ ✓

练习 6.4：给定参数曲面 $\mathbf{S}(u,v) = (u\cos v, u\sin v, u^2)$，计算在点 $(u,v) = (1, 0)$ 处的法向量。

提示：计算 $\mathbf{S}_u \times \mathbf{S}_v$。

答案 首先计算偏导数： $$\mathbf{S}_u = (\cos v, \sin v, 2u)$$ $$\mathbf{S}_v = (-u\sin v, u\cos v, 0)$$ 在 $(u,v) = (1,0)$ 处： $$\mathbf{S}_u(1,0) = (1, 0, 2)$$ $$\mathbf{S}_v(1,0) = (0, 1, 0)$$ 叉积： $$\mathbf{n} = \mathbf{S}_u \times \mathbf{S}_v = \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ 1 & 0 & 2 \\ 0 & 1 & 0 \end{vmatrix} = (-2, 0, 1)$$ 单位法向量： $$\hat{\mathbf{n}} = \frac{(-2, 0, 1)}{\sqrt{4 + 0 + 1}} = \frac{1}{\sqrt{5}}(-2, 0, 1)$$

挑战题

练习 6.5：证明对于符号距离场（SDF），如果 $f$ 是到曲面 $S$ 的符号距离函数，则 $|\nabla f| = 1$ 几乎处处成立。

提示：考虑最近点投影和距离函数的定义。

答案 设 $\mathbf{x}$ 是空间中一点，$\mathbf{p}$ 是 $\mathbf{x}$ 在曲面 $S$ 上的最近点。 定义：$f(\mathbf{x}) = \text{sign}(\mathbf{x}) \cdot \|\mathbf{x} - \mathbf{p}\|$ 对于曲面外的点（$f > 0$），沿任意方向 $\mathbf{v}$ 的方向导数： $$\frac{\partial f}{\partial \mathbf{v}} = \lim_{h \to 0} \frac{f(\mathbf{x} + h\mathbf{v}) - f(\mathbf{x})}{h}$$ 由于 $\mathbf{p}$ 是最近点，当 $h$ 足够小时，$\mathbf{x} + h\mathbf{v}$ 的最近点仍是 $\mathbf{p}$（除非 $\mathbf{x}$ 在中轴上）。 因此： $$f(\mathbf{x} + h\mathbf{v}) \approx \|\mathbf{x} + h\mathbf{v} - \mathbf{p}\|$$ 使用泰勒展开： $$\|\mathbf{x} + h\mathbf{v} - \mathbf{p}\| = \|\mathbf{x} - \mathbf{p}\| + h\frac{(\mathbf{x} - \mathbf{p}) \cdot \mathbf{v}}{\|\mathbf{x} - \mathbf{p}\|} + O(h^2)$$ 所以： $$\frac{\partial f}{\partial \mathbf{v}} = \frac{(\mathbf{x} - \mathbf{p}) \cdot \mathbf{v}}{\|\mathbf{x} - \mathbf{p}\|}$$ 梯度为： $$\nabla f = \frac{\mathbf{x} - \mathbf{p}}{\|\mathbf{x} - \mathbf{p}\|}$$ 因此 $\|\nabla f\| = 1$。 注意：在中轴（medial axis）上，最近点不唯一，梯度不存在。

练习 6.6：推导Loop细分中 $\beta$ 值的选择，使得细分曲面在正则顶点处达到 $C^2$ 连续性。

提示：分析细分矩阵的特征值。

答案 对于价数为 $n$ 的顶点，Loop细分的更新规则： $$\mathbf{v}_{\text{new}} = (1 - n\beta)\mathbf{v}_{\text{old}} + \beta\sum_{i=1}^n \mathbf{v}_i$$ 细分矩阵 $\mathbf{S}$ 的特征值决定了曲面的连续性。 对于 $C^2$ 连续性，需要： 1. 最大特征值 $\lambda_0 = 1$（保持仿射不变性） 2. 次大特征值 $\lambda_1 = \lambda_2 < 1$（收敛性） 3. $\lambda_1/\lambda_0 > \lambda_3/\lambda_1$（$C^2$ 条件） 通过傅里叶分析，特征值为： $$\lambda_k = \frac{1}{8}(5 - 3\cos\frac{2\pi k}{n}) + \beta(1 - \cos\frac{2\pi k}{n})$$ 要使 $\lambda_1 = \lambda_2$，需要旋转对称性。 最优的 $\beta$ 值（Warren's choice）： $$\beta = \frac{1}{n}\left(\frac{5}{8} - \left(\frac{3}{8} + \frac{1}{4}\cos\frac{2\pi}{n}\right)^2\right)$$ 这保证了： - $n = 3$：$\beta = 3/16$ - $n = 6$：$\beta = 1/16$（正则顶点） - 大 $n$：$\beta \approx 3/(8n)$

练习 6.7：设计一个算法，将任意多边形网格转换为符号距离场表示。讨论算法的时间复杂度和精度权衡。

提示：考虑快速行进法（FMM）或快速扫描法。

答案 **算法设计**： 1. **初始化**： - 在规则网格上采样 - 标记网格点的内外关系（射线法） - 计算到最近三角形的距离 2. **精确距离计算**（边界附近）： - 对每个网格点，找最近的三角形 - 计算点到三角形的距离（考虑顶点、边、面） - 使用空间划分加速（KD-tree或BVH） 3. **快速行进法**（远离边界）： - 从已知距离的点开始传播 - 求解Eikonal方程：$\|\nabla f\| = 1$ - 使用堆维护波前 4. **符号确定**： - 奇偶规则或缠绕数 - 法向量一致性检查 **时间复杂度**： - 初始化：$O(N \log M)$，$N$ 是网格点数，$M$ 是三角形数 - FMM传播：$O(N \log N)$ - 总体：$O(N \log N + N \log M)$ **精度权衡**： - 网格分辨率 vs. 内存消耗 - 窄带宽度 vs. 计算时间 - 插值阶数 vs. 平滑度 **优化策略**： - 自适应网格细化 - GPU并行化（特别适合快速扫描法） - 层次化表示（稀疏体素八叉树）

练习 6.8：分析PCSS（Percentage Closer Soft Shadows）算法中，光源大小、遮挡物距离和接收器距离如何影响半影大小。推导半影估计公式。

提示：使用相似三角形原理。

答案 **几何分析**： 设置： - 光源宽度：$w_{light}$ - 遮挡物到光源距离：$d_{blocker}$ - 接收器到光源距离：$d_{receiver}$ - 遮挡物到接收器距离：$d_{receiver} - d_{blocker}$ **半影大小推导**： 使用相似三角形： $$\frac{w_{penumbra}}{d_{receiver} - d_{blocker}} = \frac{w_{light}}{d_{blocker}}$$ 解得： $$w_{penumbra} = \frac{(d_{receiver} - d_{blocker}) \cdot w_{light}}{d_{blocker}}$$ **影响因素分析**： 1. **光源大小** $w_{light}$： - 线性关系：光源越大，半影越宽 - 点光源（$w_{light} \to 0$）：硬阴影 2. **遮挡物距离** $d_{blocker}$： - 反比关系：遮挡物越近光源，半影越大 - 极限情况：$d_{blocker} \to 0$，$w_{penumbra} \to \infty$ 3. **接收器距离** $d_{receiver}$： - 正相关：接收器越远，半影越大 - 相对距离 $(d_{receiver} - d_{blocker})$ 是关键 **PCSS算法步骤**： 1. **搜索遮挡物**： ```glsl float searchRadius = lightSize * (receiverDepth - nearPlane) / receiverDepth; float avgBlockerDepth = findAverageBlockerDepth(shadowCoord, searchRadius); ``` 2. **估计半影**： ```glsl float penumbraWidth = (receiverDepth - avgBlockerDepth) * lightSize / avgBlockerDepth; ``` 3. **PCF过滤**： ```glsl float shadow = PCF(shadowCoord, penumbraWidth); ``` **误差来源**： - 单一平均遮挡物深度的近似 - 离散采样导致的噪声 - 透视投影的非线性

常见陷阱与错误

  1. 符号距离场的梯度假设
    • 错误：认为SDF的梯度处处为1
    • 正确：在中轴（medial axis）上梯度不连续
  2. 贝塞尔曲线的参数化
    • 错误：假设参数 $t$ 对应弧长
    • 正确：贝塞尔曲线通常不是弧长参数化的
  3. 网格简化的拓扑保持
    • 错误：边收缩可能改变拓扑（创建非流形结构）
    • 正确：需要检查收缩操作的有效性
  4. 阴影图的深度精度
    • 错误：忽略深度缓冲的有限精度
    • 正确：使用适当的偏移和高精度深度格式
  5. 细分曲面的边界处理
    • 错误：对边界顶点使用内部规则
    • 正确：边界需要特殊的细分规则
  6. NURBS权重的影响
    • 错误：认为权重只是简单的缩放
    • 正确：权重影响曲线的参数化速度
  7. CSG运算的数值稳定性
    • 错误：直接使用 min/max 进行布尔运算
    • 正确：在边界附近需要特殊处理
  8. 环境光遮蔽的法线偏移
    • 错误：不考虑自遮挡问题
    • 正确：沿法线偏移采样起点

最佳实践检查清单

几何表示选择

曲线曲面设计

网格处理

阴影实现

性能优化

数值稳定性