第6章：几何表示

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

6.1 基本几何表示方法

6.1.1 隐式表示与显式表示

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

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

优点：

• 易于判断点的内外关系：$f(\mathbf{x}) < 0$ 表示内部，$f(\mathbf{x}) > 0$ 表示外部
• 便于进行布尔运算（并、交、差）
• 自然支持实体建模
• 光线求交简化为求解方程 $f(\mathbf{o} + t\mathbf{d}) = 0$
• 易于实现形变和扰动
• 无需存储连接信息，内存占用可预测
• 支持无限精度的表面细节

缺点：

• 难以参数化采样
• 不易控制局部形状
• 需要特殊技术（如Marching Cubes）进行可视化
• 难以获得表面的参数化坐标
• 纹理映射需要额外计算
• 直接编辑困难

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

优点：

• 易于采样和遍历
• 便于纹理映射
• 直观的形状控制
• 天然提供UV坐标
• 适合GPU硬件加速
• 支持分层细节（LOD）
• 艺术家友好的编辑工具

缺点：

• 难以判断点的内外关系
• 拓扑变化处理复杂
• 自相交检测困难
• 难以表示体积信息
• 需要额外的数据结构维护连接关系
• 采样密度影响表示精度

数学转换关系：

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

• 等值面提取：Marching Cubes、Dual Contouring
• 光线投射：沿视线方向求解 $f(\mathbf{r}(t)) = 0$
• 粒子采样：在表面上分布粒子并松弛

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

• 距离场计算：计算到最近表面点的距离
• 体素化：在规则网格上采样内外信息
• 径向基函数插值：$f(\mathbf{x}) = \sum_i w_i \phi(|\mathbf{x} - \mathbf{c}_i|)$

混合表示的应用场景：

• 建模阶段：使用显式表示便于艺术家控制
• 物理仿真：隐式表示便于碰撞检测
• 渲染阶段：转换为三角网格利用GPU
• 机器学习：神经隐式表示（如NeRF、DeepSDF）结合两者优势
• 医学成像：体数据的隐式表示，表面提取用于可视化
• CAD/CAM：精确的隐式表示，网格化用于加工

表示选择的决策因素：

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$$ 其中：

• $a = \mathbf{d}^T\mathbf{Q}\mathbf{d}$
• $b = 2(\mathbf{d}^T\mathbf{Q}\mathbf{o} + \mathbf{b}^T\mathbf{d})$
• $c = \mathbf{o}^T\mathbf{Q}\mathbf{o} + 2\mathbf{b}^T\mathbf{o} + c$

交点数量分析：

• $a = 0$：光线平行于二次曲面的渐近方向
• $\Delta = b^2 - 4ac < 0$：无交点
• $\Delta = 0$：相切（一个交点）
• $\Delta > 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$：

• 并集（Union）：$A \cup B: \min(f_A(\mathbf{x}), f_B(\mathbf{x})) \leq 0$
• 交集（Intersection）：$A \cap B: \max(f_A(\mathbf{x}), f_B(\mathbf{x})) \leq 0$
• 差集（Difference）：$A - B: \max(f_A(\mathbf{x}), -f_B(\mathbf{x})) \leq 0$
• 对称差（Symmetric Difference）：$(A - B) \cup (B - A)$

R-函数理论：

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

• R-并集：$f_{A \cup B} = f_A + f_B + \sqrt{f_A^2 + f_B^2}$
• R-交集：$f_{A \cap B} = f_A + f_B - \sqrt{f_A^2 + f_B^2}$

这些函数保证了 $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的变换操作：

7. 刚体变换： - 平移：$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}))$

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

9. 对称操作： - 镜像：$f_{\text{mirror}}(\mathbf{x}) = f(|x|, y, z)$ - 重复：$f_{\text{repeat}}(\mathbf{x}) = f(\text{mod}(\mathbf{x}, \mathbf{p}) - \mathbf{p}/2)$

10. 扭曲变换： - 弯曲：应用非线性空间变换 - 扭转：$\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 点云与体素表示

点云表示：

• 无连接信息的3D点集合 ${\mathbf{p}_i}_{i=1}^N$
• 常用于3D扫描和激光雷达数据
• 每个点可附加属性：法向量、颜色、置信度等
• 表面重建方法：泊松重建、移动最小二乘（MLS）、Ball Pivoting

点云处理技术：

• 降采样：体素网格滤波、随机采样、FPS（最远点采样）
• 法向量估计：PCA分析局部邻域、一致性传播
• 特征提取：FPFH、3D-SIFT、ISS关键点
• 配准：ICP（迭代最近点）、RANSAC、特征匹配

移动最小二乘（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)$

体素表示：

• 3D网格中的占用信息
• 规则网格：简单但内存密集
• 层次结构：八叉树（Octree）表示
• 稀疏体素八叉树（SVO）用于大规模场景
• 适合体积渲染和物理仿真

八叉树结构：

• 递归空间划分：每个节点有8个子节点
• 自适应分辨率：细节区域深度更大
• 高效的空间查询：$O(\log N)$
• 支持out-of-core处理

体素化算法：

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

混合表示：

• 点云 + 局部曲面：Surfels（surface elements）
• 体素 + SDF：TSDF（Truncated SDF）用于3D重建
• 八叉树 + 点云：用于大规模场景的LOD系统

现代应用：

• SLAM系统：实时3D地图构建
• 自动驾驶：LiDAR点云处理
• 医学成像：体素数据可视化
• 深度学习：PointNet、VoxelNet等架构

6.1.6 网格表示

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

基本元素：

• 顶点（Vertices）：位置坐标，可附加法向量、UV坐标、颜色等
• 边（Edges）：连接两个顶点
• 面（Faces）：由边围成的多边形，通常是三角形或四边形
• 半边（Half-edges）：有向边，便于遍历

网格数据结构：

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（三角网格）

网格质量度量：

• 三角形质量：长宽比、最小角度
• 顶点分布：均匀性、各向同性
• 边长变化：梯度限制
• 二面角：避免过于尖锐的折叠

常见网格操作：

• 边翻转（Edge Flip）：改变对角线
• 边收缩（Edge Collapse）：合并顶点
• 边分裂（Edge Split）：添加顶点
• 面分裂（Face Split）：细分三角形

网格的紧凑表示：

• 索引网格：顶点数组 + 面索引数组
• 三角形条带（Triangle Strips）：共享边的三角形序列
• 三角形扇（Triangle Fans）：共享顶点的三角形序列
• 压缩格式：量化坐标、预测编码

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标架：

• 切向量：$\mathbf{T} = \frac{\mathbf{c}'}{|\mathbf{c}'|}$
• 法向量：$\mathbf{N} = \frac{\mathbf{T}'}{|\mathbf{T}'|}$
• 副法向量：$\mathbf{B} = \mathbf{T} \times \mathbf{N}$

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基函数。

性质：

• 端点插值：$\mathbf{B}(0) = \mathbf{P}_0$，$\mathbf{B}(1) = \mathbf{P}_n$
• 凸包性质：曲线完全位于控制点的凸包内
• 仿射不变性
• 变差减少性质

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$

性质：

• 局部支撑：$N_{i,p}(t) = 0$ 当 $t \notin [t_i, t_{i+p+1})$
• $C^{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$$ 其中：

• $E = \mathbf{S}_u \cdot \mathbf{S}_u$
• $F = \mathbf{S}_u \cdot \mathbf{S}_v$
• $G = \mathbf{S}_v \cdot \mathbf{S}_v$

法向量： $$\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$$ 其中：

• $L = \mathbf{S}_{uu} \cdot \mathbf{n}$
• $M = \mathbf{S}_{uv} \cdot \mathbf{n}$
• $N = \mathbf{S}_{vv} \cdot \mathbf{n}$

主曲率：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细分（三角网格）：

• 新顶点位置（边中点）： $$\mathbf{v}_{\text{new}} = \frac{3}{8}(\mathbf{v}_1 + \mathbf{v}_2) + \frac{1}{8}(\mathbf{v}_3 + \mathbf{v}_4)$$

• 旧顶点更新： $$\mathbf{v}_{\text{updated}} = (1 - n\beta)\mathbf{v}_{\text{old}} + \beta\sum_{i=1}^n \mathbf{v}_i$$ 其中 $\beta = \frac{1}{n}(\frac{5}{8} - (\frac{3}{8} + \frac{1}{4}\cos\frac{2\pi}{n})^2)$

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$$ 权重选择：

• 均匀权重：$w_{ij} = 1$
• 余切权重：$w_{ij} = \cot\alpha_{ij} + \cot\beta_{ij}$
• 平均值坐标：考虑角度和距离

保角参数化（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）问题：

• 恒定偏移：$\text{bias} = \epsilon$
• 斜率偏移：$\text{bias} = \epsilon \cdot \tan(\theta)$
• 法线偏移：沿法线方向偏移采样点

6.3.6 级联阴影图（CSM）

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

分割策略：

• 均匀分割：$z_i = z_{near} + i \cdot \frac{z_{far} - z_{near}}{N}$
• 对数分割：$z_i = z_{near} \cdot (z_{far}/z_{near})^{i/N}$
• 实用分割：两者的混合

层级选择：

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：

• 每顶点存储遮蔽值
• 使用光线投射计算
• 考虑法线加权：$AO = \frac{1}{\pi}\int_{\Omega} V(\omega) \cdot (\mathbf{n} \cdot \omega)^+ d\omega$

本章小结

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

基本几何表示：

• 隐式表示：$f(\mathbf{x}) = 0$，便于内外判断和布尔运算
• 显式表示：参数化形式，便于采样和纹理映射
• 符号距离场（SDF）：特殊的隐式表示，梯度为单位向量
• CSG：通过布尔运算构建复杂几何

曲线与曲面理论：

• 贝塞尔曲线：$\mathbf{B}(t) = \sum_{i=0}^n B_i^n(t) \mathbf{P}_i$
• B样条：局部控制，$C^{p-1}$ 连续性
• NURBS：有理形式，精确表示二次曲线
• 微分几何：第一/第二基本形式，高斯曲率 $K$，平均曲率 $H$
• 细分曲面：Loop（三角网格）、Catmull-Clark（四边形网格）

网格处理与阴影技术：

• 网格简化：QEM边收缩算法
• 网格参数化：调和映射、LSCM
• 阴影图：深度比较 + 偏移处理
• 级联阴影图：多分辨率解决透视走样
• 软阴影：PCF、PCSS、VSM
• 环境光遮蔽：SSAO、预计算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$。

练习 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$ 到贝塞尔曲线公式。

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

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

练习 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$。

挑战题

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

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

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

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

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

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

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

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

常见陷阱与错误

1. 符号距离场的梯度假设 - 错误：认为SDF的梯度处处为1 - 正确：在中轴（medial axis）上梯度不连续

2. 贝塞尔曲线的参数化 - 错误：假设参数 $t$ 对应弧长 - 正确：贝塞尔曲线通常不是弧长参数化的

3. 网格简化的拓扑保持 - 错误：边收缩可能改变拓扑（创建非流形结构） - 正确：需要检查收缩操作的有效性

4. 阴影图的深度精度 - 错误：忽略深度缓冲的有限精度 - 正确：使用适当的偏移和高精度深度格式

5. 细分曲面的边界处理 - 错误：对边界顶点使用内部规则 - 正确：边界需要特殊的细分规则

6. NURBS权重的影响 - 错误：认为权重只是简单的缩放 - 正确：权重影响曲线的参数化速度

7. CSG运算的数值稳定性 - 错误：直接使用 min/max 进行布尔运算 - 正确：在边界附近需要特殊处理

8. 环境光遮蔽的法线偏移 - 错误：不考虑自遮挡问题 - 正确：沿法线偏移采样起点

最佳实践检查清单

几何表示选择

• [ ] 根据应用需求选择合适的表示（隐式/显式）
• [ ] 考虑内存占用和查询效率的平衡
• [ ] 评估修改操作的频率和复杂度
• [ ] 确保表示支持所需的查询操作

曲线曲面设计

• [ ] 选择适当的连续性要求（$C^0$/$C^1$/$C^2$）
• [ ] 验证控制点数量与曲线复杂度的匹配
• [ ] 检查参数域的有效范围
• [ ] 考虑数值精度和稳定性

网格处理

• [ ] 保持网格的流形性质
• [ ] 验证欧拉特征数的一致性
• [ ] 使用半边结构进行拓扑操作
• [ ] 实现鲁棒的相交测试

阴影实现

• [ ] 选择合适的阴影图分辨率
• [ ] 正确设置深度偏移参数
• [ ] 实现阴影图的过滤（PCF等）
• [ ] 考虑级联阴影图的必要性

性能优化

• [ ] 使用空间数据结构加速查询
• [ ] 实现细节层次（LOD）系统
• [ ] 利用GPU并行计算
• [ ] 缓存重复计算的结果

数值稳定性

• [ ] 避免除零和接近奇异的情况
• [ ] 使用稳定的算法（如QR分解代替法线方程）
• [ ] 选择合适的浮点精度
• [ ] 实现容错机制