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

点云

显式几何最直接的形式，是把表面采样成一组空间点。点云 Point Cloud 可以写成

$$\{\mathbf p_i\},\qquad \mathbf p_i=(x_i,y_i,z_i).$$

点还可以附带法线、颜色和激光反射强度。激光雷达扫描和多视角重建通常直接产生点云，因为测量设备首先得到的是离散样本，而不是已经连接好的表面。

点云的优点是数据结构简单，不需要预先决定拓扑，孔洞、分支和断裂都可以自然出现。缺点也来自同一件事：点没有面积，没有边和面，稀疏区域会出现空洞，近距离放大时容易看穿模型。渲染时常把点扩展成面向视点的圆盘或小球，但点的足迹小于一个像素时仍可能漏掉。点云通常需要通过曲面重建转成网格，才能方便地进行平滑着色、纹理展开和薄壳物理模拟。

左下先用离散点表示形体，后两幅显示形成连续表面后的外形；右侧雕像包含大量扫描样本。点说明表面经过哪些位置，点之间怎样连接仍需要重建或其他覆盖规则，稀疏处尤其容易留下空洞。

点云还可能带有激光反射强度，但它受到入射角、距离和材质反射率共同影响，不能直接当成漫反射颜色。泊松曲面重建等方法会从带法线的点云拟合一个表示内外的隐式场，再抽取等值面得到流形网格，这也是点云与隐式表示之间的直接联系。

多边形网格

多边形网格 Polygon Mesh 由顶点、边和面组成。工业和实时渲染中最常见的是三角形网格，因为三个点一定共面，光栅化、属性插值和光线求交都可以围绕平面三角形建立。四边形和更高边数的面在进入大多数图形管线前通常会先三角化。

网格不仅记录顶点坐标，还记录连接关系。共享顶点和边可以避免重复存储，并为细分、简化、法线计算和物理模拟提供邻域信息。三角形划分并不唯一：曲率平缓处可以使用较规则的三角形，连接处和尖锐结构附近通常需要更密的面。过于细长或面积接近零的三角形会使重心坐标、法线和纹理插值变得不稳定。

左侧曲面看起来连续，右侧线框显出它由顶点和三角面连接而成。同一顶点参与多个面，连接关系决定邻域、法线估计和网格操作，只保存坐标无法恢复这些面。

顶点-索引列表适合提交给 GPU，却不适合频繁的拓扑查询。细分需要找到边的对面，光顺需要遍历顶点的一环邻域，简化需要判断边是否可以折叠。半边数据结构 Half-Edge 把一条无向边拆成方向相反的两条半边，每个半边通常保存：

• twin：指向同一条边的反向半边；
• next：指向当前面内的下一条半边；
• vertex：指向半边的起点；
• face：指向半边所属的面。

从一条半边反复走 next 可以遍历一个面的边界；在 twin 与 next 之间交替行走可以访问顶点的一环邻域。单次指针跳转是 $O(1)$，完整遍历仍与邻域大小成正比。边界半边需要空指针或虚拟半边；三个以上面共享一条边时，普通半边结构无法直接表达非流形连接。

OBJ格式

Wavefront OBJ 是常用的 ASCII 几何交换格式。文件按行存储顶点、法线、纹理坐标和面连接：

v  x y z
vt u v
vn x y z
f  v1/vt1/vn1 v2/vt2/vn2 v3/vt3/vn3

OBJ 的索引从1开始，面引用允许四种形式：v、v/vt、v//vn 和 v/vt/vn。位置、UV 和法线拥有独立的索引系统，但 GPU 的顶点缓冲通常要求一个索引同时指向一组对齐属性。因此加载器遇到同一位置配不同 UV 或不同法线时，必须拆成多个渲染顶点；也可以对 $(v,vt,vn)$ 组合做哈希去重。

OBJ 可以写四边形或任意多边形，而现代 GPU 管线通常要求先三角化。建模软件导出的文件还可能包含重复行，行数不等于逻辑上不同的顶点数。一个立方体只有8个几何角点，但硬边法线、纹理接缝和面拆分会使最终渲染顶点数增加。

Bézier曲线

曲线用于字体轮廓、相机路径、动画轨迹和工业外形。TrueType 字形常用二次 B 样条，PostScript 与 CFF 轮廓常用三次 Bézier；这些格式都用少量控制数据描述可缩放的边界。若直接保存密集离散点，分辨率在导出时就固定，放大后只能看到折线；若保存控制点和求值规则，就可以在任意参数处重新计算。Bézier 曲线采用一组控制点定义参数曲线。

给定 $n+1$ 个控制点 $\mathbf p_0,\dots,\mathbf p_n$，可定义一条 $n$ 次 Bézier 曲线。三次曲线有四个控制点 $\mathbf p_0,\mathbf p_1,\mathbf p_2,\mathbf p_3$：曲线严格经过 $\mathbf p_0$ 和 $\mathbf p_3$，中间两个点通常不在曲线上，但决定端点附近的切向方向并影响整段形状。两个控制点时，曲线退化为一条线段。

参数 $t\in[0,1]$ 控制沿曲线的位置。它不是物理时间，也不保证等弧长运动；相同的 $\Delta t$ 可能对应不同的空间距离。若用于动画匀速运动，需要先建立弧长与参数的对应表，再用弧长反查参数。

直接要求曲线穿过一批插值点需要随点数增加而求解更高阶方程，改动一个点还会牵动整条曲线。Bézier 的控制点通常只牵引曲线而不必位于曲线上，改变控制点不需要重新解插值方程；代价是单段高阶曲线仍具有全局影响，所以工程上多用分段低阶曲线。高阶多项式插值可能出现中段振荡，不能把“经过所有数据点”和“易编辑的控制曲线”混为同一目标。

de Casteljau求值

给定 $t$，求曲线上的一个点，比一次生成整条曲线更基本。de Casteljau 算法只使用线性插值：对每一对相邻控制点按同一个比例 $t$ 插值，得到下一层点；重复这个过程，直到只剩一个点。

递推式为

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

约定第0层为原始控制点，即 $\mathbf p_i^{(0)}=\mathbf p_i$。每轮点数减少一个，$n+1$ 个控制点总共需要 $n(n+1)/2$ 次线性插值；三次情形是 $3+2+1=6$ 次。由于每一步都是系数非负且和为1的凸组合，递推过程不会离开控制点凸包，也避免了直接展开高次多项式时的严重相消。

对三次曲线，点集规模依次为 $4\to3\to2\to1$：

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

最后的 $\mathbf p_0^{(3)}$ 就是曲线上参数 $t$ 处的点。三次求值需要 $3+2+1=6$ 次线性插值，一般 $n+1$ 个控制点需要 $n(n+1)/2$ 次。每个中间点都是相邻点的凸组合，因此递推过程不会离开控制点的凸包，也比直接展开高次多项式更稳定。

de Casteljau 的中间点还有一个重要用途：在参数 $t$ 处把一条 Bézier 曲线拆成两段。金字塔左侧边界点构成左子曲线的控制多边形，右侧边界点构成右子曲线的控制多边形。绘制时可以递归细分，在平坦区域用少量线段近似，在弯曲区域继续细分。

这使得自适应绘制不必预先固定同一个参数步长：若控制多边形与弦线之间的几何误差仍大，就在该段继续细分；平坦段可以提前停止。参数均匀采样还不等于屏幕上匀速，动画若要求匀速仍需使用弧长表重新参数化。过密采样只会重复覆盖相同像素，抗锯齿需要单独估计像素覆盖率，不能把重复样本直接累加成更亮的颜色。

图中紫色折线先在相邻控制点之间取同一比例，绿色折线再对紫色点插值，最后的蓝色点就是曲线上当前参数的位置。改变 $t$ 时，三层点一起移动，只有最后一点是曲线点，中间点只是本次求值的辅助量。

显示曲线时不能无条件使用固定参数步长。若相邻控制多边形距离较大或屏幕曲率较高，应继续细分；若一段已经足够接近直线，则可以停止。过密采样只会重复写入相同像素，抗锯齿仍需单独处理。

求一个参数位置的点，不必先生成整条曲线。下面每层都读取前一层，避免原地覆盖后误用新数据：

DeCasteljau(controlPoints, t):
    points = controlPoints 的副本
    当 points 的数量大于 1：
        next = 空数组
        对每对相邻点 points[i]、points[i + 1]：
            next 加入 (1 - t) * points[i] + t * points[i + 1]
        points = next
    返回 points[0]

Bernstein代数

逐层展开 de Casteljau 递推，可以得到 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.$$

Bernstein 基函数在 $t\in[0,1]$ 内满足两条性质：

$$B_i^n(t)\ge0, \qquad \sum_{i=0}^{n}B_i^n(t)=1.$$

第二个等式就是二项式定理：

$$\sum_{i=0}^{n}B_i^n(t)=\bigl(t+(1-t)\bigr)^n=1.$$

例如二次和三次基函数的组合数分别给出 $1,2,1$ 与 $1,3,3,1$。组合数满足 $\binom ni=\binom n{n-i}$，所以把控制点顺序整体反转只会让同一条几何曲线沿相反方向遍历。

所以曲线上的每一点都是控制点的凸组合，整条曲线严格位于控制点凸包内。所有控制点共线时，凸包退化为一条线，曲线也只能落在这条线上。凸包可以作为几何碰撞的粗筛选：若两组控制点的凸包不相交，曲线不可能相交。

仿射不变性也来自权重与控制点位置的线性关系：先对控制点做平移、旋转、缩放或错切，再求曲线，与先求曲线再逐点做同一仿射变换相同。透视投影含有除以深度的非线性，不能把投影后的控制点直接当成新控制点重建原投影曲线。

曲线性质

端点由代数式直接得到：

$$\mathbf b(0)=\mathbf p_0,\qquad \mathbf b(1)=\mathbf p_n.$$

三次曲线的一阶导数为

$$\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),$$

因此

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

一般 $n$ 次曲线的端点导数为

$$\mathbf b'(0)=n(\mathbf p_1-\mathbf p_0), \qquad \mathbf b'(1)=n(\mathbf p_n-\mathbf p_{n-1}).$$

三次导数本身还是一条二次 Bézier 曲线，其三个控制点是 $3(\mathbf p_1-\mathbf p_0)$、$3(\mathbf p_2-\mathbf p_1)$ 与 $3(\mathbf p_3-\mathbf p_2)$。若相邻控制点重合，端点导数可能为零，不能直接用零向量判定切线方向；控制边长度还决定参数在端点附近的速度。

仿射变换可以直接作用于控制点：先变换控制点再求 Bézier 曲线，与先求曲线再逐点变换相同。透视投影含有除以深度的非线性步骤，不满足这个性质；先投影控制点再重建曲线，通常不等于把原曲线逐点投影。

首尾控制边给出端点的切向。公式中的系数 3 表示三次曲线参数导数与控制边向量的比例，改变控制边长度也会改变端点参数速度；图上箭头不必按真实速度尺度绘制。

分段曲线

控制点增多会让单条高阶曲线难以编辑。移动一个控制点可能改变整条曲线，中间形状也不直观。更实用的做法是把长曲线拆成多段低阶曲线。最常见的是分段三次 Bézier，每一段使用四个控制点，中间控制点像控制杆一样局部牵引曲线。

相邻两段的端点位置相同，只能保证位置连续；要让切向方向接上，还要约束连接点两侧的控制边；要让速度也连续，还要约束两侧控制边长度。局部曲线编辑因此需要在相邻段之间维护这些条件。

连续性

设前一段控制点为 $A_0,A_1,A_2,A_3$，后一段为 $B_0,B_1,B_2,B_3$。

$C^0$ 连续只要求位置连续：

$$A_3=B_0.$$

两段可以在连接处形成尖角，不能据此推出切线或曲率连续。

$G^1$ 连续要求连接处切线方向共线同向，但允许速度大小不同：

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

$C^1$ 连续要求一阶导数向量也相同。在两段使用相同参数尺度时，条件为

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

如果两段物理时间不同，应该比较按时间归一化后的速度。$C^2$ 连续要求二阶导数相同，曲率变化不突然；相机路径和加工路径通常比静态轮廓更关心这一条件。

这里的 $C^1$ 等式默认两段使用相同的局部参数尺度。若前后两段实际时长为 $\Delta t_A$ 与 $\Delta t_B$，物理速度连续应比较

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

因此“方向连续”与“速度连续”是两件事：$G^1$ 允许通过连接点时改变速度，$C^1$ 还要求参数速度匹配；$C^2$ 的说法也必须建立在统一的时间或参数尺度上。

图中绿色和橙色两段曲线在红圈标出的公共端点相接，底部参数轴也把两段放在相邻区间 $[k,k+1]$ 与 $[k+1,k+2]$。这张 $C^0$ 图只表达端点位置相同，并不额外保证切线或曲率连续；$G^1$ 和 $C^1$ 需要分别加入后文的控制边方向与长度条件。

样条曲线

早期制图使用弹性木条，通过少数固定点控制一条自然弯曲的曲线，这就是 spline 一词的直观来源。B 样条 B-spline 用局部支撑的基函数把控制影响限制在有限参数区间内：移动一个控制点，只改变局部曲线。

B 样条使用节点向量划分参数区间，重复节点可以降低该处连续性、制造尖角或让曲线靠近某个控制点。NURBS 在多项式基函数上加入有理权重和非均匀节点向量，能够精确表示圆、椭圆等圆锥曲线，因此是 CAD 建模中的常用表示。

“样条”一词来自用压铁固定的弹性木条：木条在固定点之间自然弯曲。现代 B 样条把这种局部影响写成分段多项式基函数，每个基函数只在有限节点区间上非零；节点向量决定参数分段和端点行为，重复节点会减少拼接处的连续阶数。

用节点基函数 $N_{i,d}(u)$ 表示，次数为 $d$ 的 B 样条曲线可写成

$$\mathbf C(u)=\sum_i N_{i,d}(u)\mathbf P_i.$$

NURBS 再引入控制点权重 $w_i$：

$$\mathbf C(u)= \frac{\sum_i N_{i,d}(u)w_i\mathbf P_i} {\sum_i N_{i,d}(u)w_i}.$$

在简单节点处，$d$ 次 B 样条通常具有 $C^{d-1}$ 连续；节点重复会降低连续阶数。有理形式中的除法使圆、椭圆等圆锥曲线能够被精确表示，也使它比普通多项式 Bézier 更适合保持投影下的圆锥形状。

分段 Bézier 也具有局部性，但需要手工维护各段端点和切线；B 样条用一套控制网和节点统一处理局部编辑。曲线细分、拼接和降阶逼近等操作都可以从 Bernstein 形式和 de Casteljau 中间点推导出来。

Bézier曲面

曲线只有一个参数。沿第二个参数方向再应用一次相同的基函数，就得到 Bézier 曲面。双三次 Bézier 曲面由 $4\times4=16$ 个控制点 $\mathbf p_{ij}$ 定义，参数为 $(u,v)\in[0,1]^2$。

先固定 $v$，对每一行控制点沿 $u$ 做三次 Bézier 求值，得到四个临时点

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

再把四个 $\mathbf q_j(u)$ 当作另一条 Bézier 曲线的控制点，沿 $v$ 求值：

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

两个方向的求值顺序可以交换。曲面只严格经过四个角点，内部控制点通过牵引改变形状。由于两个方向的基函数都非负且和为1，曲面也位于16个控制点的凸包内。

两条参数方向的偏导给出切向量，法线为

$$\mathbf n=\frac{\mathbf S_u\times\mathbf S_v} {\lVert\mathbf S_u\times\mathbf S_v\rVert}.$$

边界上的曲面点只由控制网边界控制点决定。两张曲面片要位置连续，公共边界的控制点必须重合；要让切平面连续，两侧靠近边界的控制点还要共线并满足相应比例。参数化退化时叉积可能为零，法线需要用极限或另一块参数片处理。

图中的黑色控制网位于蓝紫色曲面上方，网线沿两个参数方向排列；曲面只在四个角点处经过控制网，内部控制点通过张量积权重共同把曲面拉成拱形。固定一个参数时得到一条三次 Bézier 边界或截面曲线，沿另一个参数移动这条曲线就扫出曲面。茶壶等经典曲面模型正是由多片这样的参数曲面按公共边界拼接而成。

网格操作

曲面片适合描述少量光滑形状，复杂物体通常交给多边形网格。网格处理的三个核心操作是：

• 细分 Subdivision：增加面数并调整顶点，使网格趋于光滑，也为位移贴图提供足够的几何采样；
• 简化 Simplification：减少面数并尽量保持轮廓，用于移动设备和远距离 LOD；
• 规则化 Regularization：在面数大致不变的情况下改善三角形形状，减少过长、过尖和近退化三角形。

规则化不能只追求接近正三角形。耳朵、尾巴等薄结构如果只优化三角形质量，可能被错误地抹掉；几何质量指标必须和形状误差、轮廓误差一起使用。

图中模型从30000、3000、300到30个三角形逐级减少；缩小到实际屏幕尺寸时，较粗层级可能已经足够。简化的目标不是让每个局部都完全相同，而是在当前投影尺度下保留轮廓和重要结构。

Loop细分

Loop subdivision 专门处理三角形网格。一次迭代分两步：先在每条边插入新顶点，把每个三角形拆成四个；再按照权重分别更新新顶点和旧顶点。Loop 是算法提出者的姓氏，不是“循环细分”。

第一步只改变拓扑和采样密度，第二步才移动顶点并让网格趋向光滑极限。新点与旧点都应从同一轮开始前的网格计算，最后统一写回；边算边覆盖会让结果依赖遍历顺序。

对于内部边 $AB$，设其两侧三角形的对向顶点为 $C,D$，新边点为

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

它仍是四个邻域点的凸组合。只做拓扑拆分不会改变原有形状，只有第二步移动顶点才会使表面向光滑极限收敛。

Loop顶点更新

设旧顶点度数为 $n$，一环邻域顶点为 $\mathbf v_1,\dots,\mathbf v_n$。旧顶点更新为

$$\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$ 时，$\beta=1/16$，旧点权重为 $5/8$，六个邻居各占 $1/16$。新点和旧点必须都从迭代开始时的旧网格计算，最后统一写回；边算边覆盖会让结果依赖遍历顺序。

对 $n>3$ 的内部顶点，邻居总权重恒为 $n\beta=3/8$，自身保留 $5/8$；$n=3$ 使用单独的 $3/16$，以抑制三角网格中尖锐构型。规则内部区域的 Loop 极限通常具有 $C^2$ 连续性，奇异度数附近的连续性较低，不能把规则结论无条件推广到边界和异常顶点。

开流形边界没有第二个对向三角形，需单独处理。边界新点直接取中点

$$\mathbf v_{new}=\frac12(A+B),$$

边界旧点可用

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

Catmull–Clark细分

Loop 只适用于三角网格。Catmull–Clark subdivision 可以处理任意多边形，第一次细分后所有面都会变成四边形。非四边形面的面点会成为度数不为4的 extraordinary vertex；第一次细分产生这些奇异点后，后续规则迭代不再增加新的非四边形面。

每次迭代生成三类点。对 $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}.$$

面点连接边点，边点连接更新后的旧顶点，形成新四边形。规则四边形区域会趋于光滑曲面，非四边形面产生的奇异点是局部连续性较低的位置；锐边若需要保留，必须使用 crease 等特殊规则，而不能直接平均掉。

在规则区域，Catmull–Clark 细分与均匀双三次 B 样条加细相联系，极限曲面通常达到 $C^2$ 连续；奇异点附近一般只能保证较低阶的连续性。四边形面本身也不保证形状规则，度数异常的位置仍需单独检查。

上排以三角形网格执行 Loop，下排执行 Catmull–Clark；每次向右迭代都增加面数并重新放置顶点。面片内部逐渐光滑，图中的黑色锐边却被保留下来，因为这些边使用了 crease 特殊规则。细分能否保留尖角取决于更新规则，单纯增加面数不会自动保留它们。

橙色三角标记非四边形面，紫点标记连接度不为 4 的奇异顶点。沿旧顶点、边点和面点连接，可把原多边形拆成四边形；非四边形面的面点会成为新的奇异位置。

二次误差简化

细分增加面数，简化则反向减少面数。直接删除三角形会留下空洞，常见做法是把一条边的两个端点合并成一个新顶点，这叫边坍缩 Edge Collapse。

边坍缩后的新位置不一定取端点中点：在鼓起区域，中点可能压低轮廓，在细长结构上也可能造成收缩。二次误差测度 Quadric Error Metrics, QEM 把候选点到邻域平面的距离平方和作为目标，用同一误差度量选择边和新顶点位置。先把相关三角形所在平面写为

$$\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}$，平方距离为

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

记 $K_p=\boldsymbol\pi\boldsymbol\pi^T$，把候选顶点关联的所有平面矩阵相加：

$$Q=\sum_kK_{p_k}.$$

新顶点的误差为

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

将 $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.$$

令梯度为零：

$$2A\mathbf x+2\mathbf b=0, \qquad \mathbf x^*=-A^{-1}\mathbf b.$$

最小值为

$$E(\mathbf x^*)=c-\mathbf b^TA^{-1}\mathbf b.$$

若 $A$ 奇异，可在边端点和中点中选择误差最小者，或使用伪逆/正则化。每次坍缩后，新顶点的误差矩阵为两端矩阵之和；与受影响边相连的代价需要重新计算。优先队列可以反复取出当前误差最小的合法边，但这是贪心策略，不保证全局最优，还应检查翻面、边界和流形约束。

实现中可以采用惰性删除：被折叠的旧边留在堆中，弹出时检查端点是否仍存在、是否仍构成合法边。每次局部更新只影响邻域边，常见实现的总体开销约为 $O(n\log n)$，但具体复杂度取决于拓扑更新和堆实现。

边坍缩通过误差优先队列反复选择局部候选，并在操作后更新受影响邻域：

为每个顶点构造误差矩阵 Q
为每条边求候选位置、QEM 代价和合法性
把候选边加入最小优先队列
当面数仍高于目标且队列非空：
    弹出代价最小的边
    若边已失效、代价过期或坍缩会破坏约束：
        丢弃或重新计算候选
        继续
    将两端合并到候选位置，合并 Q
    更新连接关系及邻域边的候选代价

LOD与几何渐变

同一模型在近处和远处不需要相同面数。骷髅模型从30000个三角形简化到3000、300乃至30个时，远处缩小到很少像素后，细节差异会显著降低。简化可以同时降低顶点变换、光栅化和着色成本，尤其适合移动设备。

不同网格层级不能像 Mipmap 那样天然地做三线性插值。直接切换会出现跳变，因此可以在一段距离内对对应顶点位置做渐变，这种过渡叫 geomorph。实际切换阈值应与屏幕投影大小相关，而不能只按世界空间距离固定决定。

阴影问题

局部着色只使用着色点自身的法线、材质、光源方向和视线方向。若另一个物体挡住了着色点到光源的连线，着色点实际上收不到这部分光；这就是阴影。光栅化按图元逐个处理屏幕像素，本身没有直接回答“从光源看这个点是否可见”的机制。

阴影贴图

Shadow Mapping 把可见性问题转成一张光源视角的深度图。它需要两遍渲染：

1. 把相机放到光源位置，渲染场景但只保存每个光源视角像素的最近深度，形成 shadow map；
2. 从真实相机渲染可见表面，把每个表面点用光源的矩阵重新投影到 shadow map，比较它的光源深度与纹理中记录的最近深度。

方向光通常用正交投影覆盖场景；点光源需要覆盖周围方向，实际可使用多张深度图或深度立方体贴图。无论采用哪种形式，第二遍都必须使用与第一遍一致的光源投影和深度映射。

若两者一致，光源能看到这个点；若当前点更远，说明有其他物体挡在中间。判定应使用同一套投影和深度归一化，不能把世界空间距离直接与投影深度比较。

图中光源视角深度图记录了每个方向上最先看到的表面；相机看见的表面重新投影到这张图后，绿色区域的实际深度与记录深度一致，非绿色区域未通过相同深度的比较，理论上对应遮挡，也可能包含采样或精度导致的自遮挡误判。

实现中常写成

$$d_{light}>d_{map}(u,v)+\varepsilon \quad\Longrightarrow\quad \text{被遮挡}.$$

由于 shadow map 的一个纹素覆盖连续表面，而它只记录一个最近深度，受光面也可能被误判为遮挡，出现条纹或斑点，这叫 Shadow Acne。给深度比较加一个小偏置可以缓解，但偏置过大又会使阴影与物体分离，产生 Peter Panning。表面越接近与光线平行，纹素内深度跨度越大，所需偏置通常越大。

分辨率不足时，一个 shadow-map 纹素覆盖多个屏幕像素，阴影边缘会出现台阶；分辨率与相机画面不匹配时，运动还会引起闪烁。提高分辨率能减少误差，但会增加显存和渲染成本。Shadow Mapping 是图像空间近似，不能从根本上消除这些离散化误差。

相机可见但落在光源投影范围外的片元没有对应的深度记录，实际实现必须定义视锥外的边界行为；若把越界纹理坐标错误地 repeat，深度会从另一侧绕回并产生假阴影。级联阴影可以把相机视锥按距离分段，近处使用更密的光源深度图，仍然是分辨率预算与投影覆盖范围之间的折中。

硬阴影与软阴影

点光源在任意位置只有“看得见”或“看不见”两种状态，因此产生硬阴影。面积光源由许多发光点组成，同一着色点可能看见光源的一部分，形成连续的可见性变化。完全看不到光源的区域叫本影 Umbra，只能看到一部分光源的区域叫半影 Penumbra。

半影通常在遮挡物与接收面接触处较窄，距离接触处越远越宽。PCF 可以在 shadow map 邻域采样多个深度并先比较再平均，得到近似软边缘；它过滤的是0/1可见性，而不是直接把深度图模糊。真实软阴影应在面积光源上采样多个点并分别测试可见性，PCF 只是成本更低的图像空间近似。

左侧两幅同一几何的阴影边界分别较锐利和较柔和；右侧太阳—月球—地球示意区分了完全被遮挡的本影和部分被遮挡的半影。面积光源上的不同点具有不同可见性，部分可见的位置形成过渡。

若采样窗口内有 $M$ 个 shadow-map 样本，PCF 可写成

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

先比较再平均得到的是可见性比例；直接模糊深度图没有明确的几何含义，比较后仍然只会得到二值结果。