计算机图形学-07：曲面与网格

曲线用途

曲线可描述字体轮廓、相机路径、角色运动和工业造型。与逐像素图像相比，参数曲线在任意缩放级别都能重新采样；与折线相比，它用较少控制点表达平滑形状。实际系统通常使用多段低阶曲线，而不是一条难以控制的高阶多项式。

把曲线绘制到屏幕时，参数步长不能脱离像素尺度固定不变。若步长过大，曲线会表现为稀疏点列或明显折线；若步长远小于当前像素覆盖范围，大量样本会重复落在同一个像素内，只增加重复工作，还可能在简单点绘制实现中形成过粗或发糊的线。常用做法是估计投影后的弧长和曲率，自适应细分到相邻样本间距接近像素尺度，并根据曲线在像素中的 coverage 计算抗锯齿权重，而不是把一次命中当成完整像素覆盖。

贝塞尔曲线

贝塞尔曲线 Bézier Curve 由一组控制点定义。三次曲线使用 $\mathbf p_0,\mathbf p_1,\mathbf p_2,\mathbf p_3$ 四点，曲线经过首尾两个控制点；中间控制点通常不在曲线上，它们通过端点切线和整体凸包控制弯曲趋势。

移动一个控制点会影响整段曲线，这种全局控制适合短小曲线段。字体轮廓和动画路径通常把多段低阶 Bézier 拼接起来，使编辑影响限制在局部。

几何求值

de Casteljau 算法 只使用线性插值。令第 0 层控制点为 $\mathbf p_i^0=\mathbf p_i$，递推

$$\mathbf p_i^r(t) = (1-t)\mathbf p_i^{r-1}(t) +t\mathbf p_{i+1}^{r-1}(t).$$

每一层都对相邻点执行

$$\operatorname{lerp}(\mathbf a,\mathbf b,t) =(1-t)\mathbf a+t\mathbf b,$$

直到第 $n$ 层只剩一个点，$\mathbf p_0^n(t)$ 就是参数 $t\in[0,1]$ 处的曲线值。

以二次曲线为例：

$$\mathbf p_0^1 =(1-t)\mathbf p_0+t\mathbf p_1, \qquad \mathbf p_1^1 =(1-t)\mathbf p_1+t\mathbf p_2,$$

$$\begin{aligned} \mathbf p_0^2 &=(1-t)\mathbf p_0^1+t\mathbf p_1^1\\ &=(1-t)^2\mathbf p_0 +2t(1-t)\mathbf p_1 +t^2\mathbf p_2. \end{aligned}$$

系数 $1,2,1$ 来自两层线性插值的展开。更高阶曲线重复同一过程，二项式系数由此自然出现。

该算法数值稳定、几何意义清楚，还能在任意 $t$ 处把一条曲线精确分成两段。递归三角形左边界上的点成为前半段控制点，右边界上的点成为后半段控制点。

Bézier 的代数公式来自重复线性插值；Bernstein 基函数并非额外假设。

代数形式

$n$ 阶递推完全展开后，可写成 Bernstein 基函数 的加权和：

$$\mathbf b(t)=\sum_{i=0}^{n}B_i^n(t)\mathbf p_i, \qquad B_i^n(t)=\binom ni t^i(1-t)^{n-i}.$$

三次形式为

$$\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\in[0,1]$ 上，每个 $B_i^n(t)\ge0$，并且由二项式定理

$$\sum_{i=0}^{n}B_i^n(t) = \sum_{i=0}^{n} \binom ni t^i(1-t)^{n-i} = [t+(1-t)]^n =1.$$

因此曲线点始终是控制点的凸组合，必定位于控制点凸包内。

对三次形式求导并整理：

$$\begin{aligned} \mathbf b'(t) ={}& 3(1-t)^2(\mathbf p_1-\mathbf p_0)\\ &+6t(1-t)(\mathbf p_2-\mathbf p_1)\\ &+3t^2(\mathbf p_3-\mathbf p_2). \end{aligned}$$

代入端点：

$$\mathbf b'(0) = 3(\mathbf p_1-\mathbf p_0), \qquad \mathbf b'(1) = 3(\mathbf p_3-\mathbf p_2).$$

曲线经过 $\mathbf p_0,\mathbf p_3$，端点切线分别沿第一、最后一条控制边，这些性质都由代数式直接推出。

Bézier 曲线还具有仿射不变性。对仿射变换 $A\mathbf x+\mathbf t$，

$$\sum_iB_i^n(t)(A\mathbf p_i+\mathbf t) = A\sum_iB_i^n(t)\mathbf p_i +\mathbf t\sum_iB_i^n(t) = A\mathbf b(t)+\mathbf t.$$

因此先变换控制点再求曲线，等价于先求曲线再做仿射变换。

分段连续

设两段三次 Bézier 的控制点分别为 $A_0,\ldots,A_3$ 与 $B_0,\ldots,B_3$，局部参数都取 $[0,1]$。位置连续 $C^0$ 要求

$$A_3=B_0.$$

参数连续 $C^1$ 还要求连接处一阶导数相同。由端点导数公式，

$$3(A_3-A_2) = 3(B_1-B_0),$$

所以

$$A_3-A_2 = B_1-B_0.$$

连接点两侧的控制边方向和长度都要匹配。若两段对应的物理持续时间分别为 $\Delta t_A,\Delta t_B$，物理速度连续应改为

$$\frac{A_3-A_2}{\Delta t_A} = \frac{B_1-B_0}{\Delta t_B}.$$

若只要求几何切线方向一致，允许两段参数速度不同，则

$$A_3-A_2 = \lambda(B_1-B_0), \qquad \lambda>0,$$

这称为几何连续 $G^1$。动画路径还可能要求二阶导数连续 $C^2$，因为加速度突变会表现为明显顿挫。

B-Spline 用局部基函数限制单个控制点的影响范围，NURBS 再引入节点间隔与有理权重，可以精确表示圆锥曲线。本课程只说明它们与 Bézier 的关系，不展开完整求值算法。

贝塞尔曲面

双三次 Bézier 曲面 Bicubic Bézier Surface 使用 $4\times4$ 个控制点，参数 $(u,v)\in[0,1]^2$。先固定 $v$ 方向的第 $j$ 行，沿 $u$ 求一条三次曲线：

$$\mathbf q_j(u) = \sum_{i=0}^{3} B_i^3(u)\mathbf p_{ij}.$$

四行分别求值后得到 $\mathbf q_0,\ldots,\mathbf q_3$，再沿 $v$ 对它们求一次三次 Bézier：

$$\mathbf S(u,v) = \sum_{j=0}^{3} B_j^3(v)\mathbf q_j(u).$$

代入第一式便得到张量积形式

$$\mathbf S(u,v)= \sum_{i=0}^{3}\sum_{j=0}^{3} B_i^3(u)B_j^3(v)\mathbf p_{ij}.$$

这解释了二维曲面为何可以分离成两轮一维 de Casteljau，而不需要新的求值算法。偏导数 $\mathbf S_u,\mathbf S_v$ 给出两条切线，法线与 $\mathbf S_u\times\mathbf S_v$ 同向。

多个曲面片拼接时也要约束边界控制点和偏导数，才能获得位置或切线连续。曲面片适合规则造型，复杂拓扑通常仍需要网格组织。

网格操作

网格处理有三类基本目标：

• 细分：增加三角形或多边形数量，得到更平滑的表面。
• 简化：减少元素数量，同时控制形状误差。
• 规则化：元素数量大致不变，改善三角形大小、角度和分布。

这些操作改变的是离散采样。好的算法既要更新顶点位置，也要正确处理连接关系、边界和尖锐特征。

Loop 细分

Loop Subdivision 面向三角网格。先在每条边上插入新顶点，把一个三角形拆成四个；再分别更新新旧顶点位置。

内部边 $AB$ 两侧三角形的另外两个顶点为 $C,D$ 时，新边点为

$$\mathbf v_{\mathrm{new}} = \frac38(A+B) +\frac18(C+D).$$

两个端点各占 $3/8$，两侧顶点各占 $1/8$，权重和为 1，因此该更新对平移和其他仿射变换保持一致。

旧顶点 $\mathbf v$ 的度数为 $n$、邻点为 $\mathbf v_i$ 时，

$$\mathbf v' = (1-n\beta)\mathbf v +\beta\sum_{i=1}^{n}\mathbf v_i,$$

常用权重为

$$\beta= \begin{cases} \frac{3}{16},&n=3,\\ \frac{3}{8n},&n>3. \end{cases}$$

规则内部顶点通常有 $n=6$，此时旧顶点保留 $5/8$，六个邻点各占 $1/16$。反复应用后，高频位置变化被邻域平均，离散三角网格趋向光滑极限曲面。

边界要使用专门规则。边界新点通常取两个端点中点，边界旧点可更新为

$$\mathbf v' = \frac34\mathbf v +\frac18 (\mathbf v_{\mathrm{prev}} +\mathbf v_{\mathrm{next}}).$$

这样边界沿一维三次样条平滑，而不会错误使用缺失的另一侧三角形。

Catmull-Clark

Catmull–Clark Subdivision 可处理一般多边形网格，并在一次细分后把所有面变成四边形。

含 $m$ 个顶点的面生成面点

$$\mathbf F = \frac1m \sum_{j=1}^{m}\mathbf v_j.$$

内部边端点为 $\mathbf v_1,\mathbf v_2$，两侧面点为 $\mathbf F_1,\mathbf F_2$，边点为

$$\mathbf E = \frac{ \mathbf v_1+\mathbf v_2 +\mathbf F_1+\mathbf F_2 }{4}.$$

对度数为 $n$ 的旧顶点 $\mathbf P$，令 $\bar{\mathbf F}$ 为相邻面点平均，$\bar{\mathbf R}$ 为相邻边中点平均，则

$$\mathbf P' = \frac{ \bar{\mathbf F} +2\bar{\mathbf R} +(n-3)\mathbf P }{n}.$$

这三类点重新连接后，每个旧面顶点对应一个新四边形。规则四边形区域的极限曲面等价于双三次 B-spline；度数不为 4 的旧顶点称为 奇异顶点 Extraordinary Vertex，特殊行为只局限在其邻域。

边界和 折痕 Crease 需要额外规则，否则邻域平均会逐步抹圆所有棱角。细分算法同时包含拓扑细分与位置滤波，只增加三角形而不更新位置，不能得到同样的平滑极限。

网格简化

边折叠 Edge Collapse 把一条边的两个端点合并为一个点，同时删除退化面。关键问题是选择哪条边，以及新点放在哪里。Quadric Error Metrics 用点到相关平面的距离平方和衡量形状误差。

把平面写成

$$\boldsymbol\pi =(a,b,c,d)^T, \qquad a^2+b^2+c^2=1.$$

候选点的齐次坐标为 $\bar{\mathbf v}=(x,y,z,1)^T$。法线经过归一化后，点到平面的有符号距离就是 $\boldsymbol\pi^T\bar{\mathbf v}$，距离平方为

$$(\boldsymbol\pi^T\bar{\mathbf v})^2 = \bar{\mathbf v}^T (\boldsymbol\pi\boldsymbol\pi^T) \bar{\mathbf v}.$$

对顶点邻接的所有平面求和：

$$Q = \sum_k \boldsymbol\pi_k\boldsymbol\pi_k^T.$$

候选点偏离这些原始平面的总误差为

$$E(\bar{\mathbf v}) = \bar{\mathbf v}^TQ\bar{\mathbf v}.$$

折叠端点 $\mathbf v_1,\mathbf v_2$ 时，新顶点继承

$$Q_{\mathrm{new}}=Q_1+Q_2,$$

所以历史误差能够在连续折叠中累积。

还需求出让当前边代价最小的新位置。把 $Q$ 分块：

$$Q= \begin{pmatrix} A&\mathbf b\\ \mathbf b^T&c \end{pmatrix}, \qquad \bar{\mathbf v} = \begin{pmatrix} \mathbf x\\1 \end{pmatrix}.$$

代入得到

$$E(\mathbf x) = \mathbf x^TA\mathbf x +2\mathbf b^T\mathbf x +c.$$

令梯度为零：

$$\nabla E = 2A\mathbf x+2\mathbf b =0,$$

若 $A$ 可逆，最优点为

$$\mathbf x^* = -A^{-1}\mathbf b.$$

若 $A$ 奇异，常在两个端点、中点和伪逆解中选择误差最小者。每条边以最小 $E$ 作为优先级，算法反复折叠当前代价最低的合法边，并更新邻域候选。

QEM 同时回答“先折叠哪条边”和“新顶点放在哪里”；只计算平面误差而不解最小点，简化质量会明显下降。

QEM 是高效贪心策略，能生成多层次细节模型，但二次距离并不自动保证拓扑正确。实际实现仍需拒绝导致翻面、非流形连接或重要边界丢失的折叠。

阴影贴图

阴影贴图 Shadow Mapping 把“光源能否看到该点”转化为一次深度比较：

1. 从光源视角渲染场景，只保存最近深度，得到 shadow map。
2. 从相机视角正常渲染，把每个可见点乘以光源的 MVP 矩阵，变换回光源裁剪空间。
3. 查询同一光源像素记录的深度。若当前点更远，说明光线先遇到遮挡物，该点处于阴影中。

设光源裁剪坐标为 $(x_c,y_c,z_c,w_c)$。先做透视除法，再把 NDC 的 $x,y$ 从 $[-1,1]$ 映射到纹理坐标：

$$(u,v) = \left( \frac12\frac{x_c}{w_c}+\frac12, \frac12\frac{y_c}{w_c}+\frac12 \right).$$

若继续沿用第三篇的 NDC 约定，先计算

$$d_{\mathrm{light}} = \frac{1-z_c/w_c}{2},$$

使近处为 0、远处为 1，再与纹理中保存的最近深度 $d_{\mathrm{map}}$ 比较：

$$d_{\mathrm{light}} > d_{\mathrm{map}}+\varepsilon$$

表示点被遮挡。偏移 $\varepsilon$ 用来容忍浮点量化和两次光栅化产生的深度差。

浮点误差和有限分辨率会导致自阴影痤疮、悬浮边界与锯齿。深度 bias 或法线偏移可以减少自遮挡，却可能造成 Peter Panning。提高分辨率、按视锥分块或使用过滤能改善质量。单张点光源 shadow map 主要产生硬阴影；面积光源的软阴影需要多次采样或专门近似。

光源投影后的 $(u,v)$ 超出 $[0,1]^2$ 时，应根据光源投影的边界策略使用 clamp 或 border value；使用 repeat 会把阴影图另一侧的深度错误拼接到当前区域，造成边缘漏光或假阴影。PCF Percentage-Closer Filtering 在查询点周围取多个 texel，分别比较可见性，再对 0/1 结果求平均；它过滤的是比较结果，而非直接模糊深度：

$$V_{\mathrm{PCF}}(u,v) = \frac1M\sum_{j=1}^{M} \mathbf 1\left[ d_{\mathrm{recv}}(u,v) \le d_{\mathrm{map}}(u_j,v_j)+\varepsilon \right].$$

$d_{\mathrm{recv}}(u,v)$ 是当前接收点的固定光源空间深度，只有查询的 shadow-map texel $(u_j,v_j)$ 随核偏移。采样数量和分布决定阶梯噪声与边缘稳定性，shadow map 的深度精度和 bias 又会影响每个比较结果。PCF 只是邻域可见性的平均，得到的是软化的阴影边缘，并不等价于真实面积光源对遮挡区域的积分；要模拟真实软阴影，还需对光源表面或可见性函数进行适当采样。