Games102

GAMES102:几何建模与处理(刘利刚)的笔记。

主题:如何表示形状,以及如何处理形状。

一、几何表示的三类

类型形式优点缺点
离散点云、网格通用、易获取无连续性信息
连续参数曲线曲面光滑、可精确求值难表示复杂拓扑
混合细分曲面、隐式兼顾复杂

核心矛盾:真实世界是连续的,计算机只能存离散的。如何在离散数据上恢复/保持连续性,是几何处理的主线。

二、参数曲线

多项式曲线的问题

用高阶多项式插值很多点 → Runge 现象(振荡)。

                 /\      /\
________________/  \____/  \______     ← 高次插值的振荡

解法:分段低阶(样条),而不是单段高阶。

Bézier 曲线

B(t)=∑i=0nBin(t) Pi,Bin(t)=(ni)ti(1−t)n−iB(t) = \sum_{i=0}^{n} B_i^n(t)\, P_i, \quad B_i^n(t) = \binom{n}{i} t^i (1-t)^{n-i}

性质:

  • 端点插值:B(0)=P0B(0) = P_0,B(1)=PnB(1) = P_n
  • 凸包性:曲线在控制点的凸包内
  • 端点切线方向:B′(0)=n(P1−P0)B'(0) = n(P_1 - P_0)
  • 仿射不变,但非射影不变

de Casteljau 算法(求值):递归线性插值。

n=3, t:
层0: P0    P1    P2    P3
层1:   Q0    Q1    Q2         Qi = lerp(Pi, Pi+1, t)
层2:     R0    R1
层3:       S0                 ← 就是 B(t)

优点:数值稳定,同时给出子曲线的控制点(用于细分)。

拼接连续性

等级要求视觉
C0C^0位置连续无断点
C1C^1一阶导连续切线连续,无折角
C2C^2二阶导连续曲率连续,无"光顺度"突变
G1G^1切线方向连续(大小可不同)视觉上光滑

CkC^k vsGkG^k:GG 只要求几何连续(方向),CC 要求参数连续(含速率)。视觉上G1G^1 就够了,但C1C^1 更严格。

B 样条(B-Spline)

动机:Bézier 的全局性——移动一个控制点整条曲线都变。

B 样条用**节点向量(knot vector)**实现局部支撑:

Bik(t) 只在 [ti,ti+k+1) 上非零B_i^k(t) \text{ 只在 } [t_i, t_{i+k+1}) \text{ 上非零}

特性值
局部性✓(移动一个控制点只影响局部)
连续性自动Ck−1C^{k-1}(kk 是次数)
端点插值✗(除非用重节点)

三次 B 样条是最常用的(C2C^2 连续 + 局部性 + 计算简单)。

NURBS

非均匀有理 B 样条 = B 样条 + 权重:

C(t)=∑wiPiNik(t)∑wiNik(t)C(t) = \frac{\sum w_i P_i N_i^k(t)}{\sum w_i N_i^k(t)}

有理的意义:能精确表示圆锥曲线(圆、椭圆),B 样条只能逼近。

工业标准:CAD/CAM(STEP、IGES 格式都基于 NURBS)。

三、参数曲面

张量积曲面

S(u,v)=∑i∑jPijNi(u)Nj(v)S(u,v) = \sum_i \sum_j P_{ij} N_i(u) N_j(v)

Bézier 曲面、B 样条曲面、NURBS 曲面都是这个形式——控制点变成控制网格。

问题:张量积要求四边形网格,且拓扑受限(柱面、球面要接缝)。

隐式曲面

f(x,y,z)=0f(x,y,z) = 0

优点缺点
判断内外极快采样表面难
布尔运算简单(min⁡\min/max⁡\max)难以精确建模
拓扑变化自动处理—
表达能力强(分形)—

SDF(Signed Distance Field):

f(x) = 到表面的最短距离(内部为负)
|∇f| = 1                          ← 关键性质

用途:

  • 光线步进(sphere tracing):每次可以安全前进 f(x) 的距离
  • 软阴影(见实时阴影)
  • 碰撞检测
  • 布尔运算(smooth min)

细分曲面(Subdivision)

从一个粗网格反复细分,极限是一个光滑曲面。

方案适用网格极限连续性
Catmull-Clark四边形C2C^2(除奇异点)
Loop三角形C2C^2(除奇异点)
Doo-Sabin四边形C1C^1
Butterfly三角形C1C^1

Catmull-Clark 规则(四边形):

面点: 4 个顶点的平均
边点: (两端点 + 相邻两个面点) / 4
顶点: 按 valence 加权更新(保证收缩到光滑极限)

**奇异点(valence ≠ 4)**处只有C1C^1,是细分曲面的固有缺陷。

价值:电影/游戏建模的标准(Pixar 的 Geri's Game 开始)——艺术家操作简单拓扑,计算机生成光滑表面。

四、网格处理

曲率

主曲率k1,k2k_1, k_2:

量定义用途
高斯曲率KKk1k2k_1 k_2判断局部形状(>0>0 椭圆、<0<0 双曲、=0=0 抛物)
平均曲率HH(k1+k2)/2(k_1 + k_2)/2光顺、最小曲面

离散高斯曲率(角度亏损):

K(v)=2π−∑θiAK(v) = \frac{2\pi - \sum \theta_i}{A}

平面上角度和是2π2\pi,亏损量就是曲率。

网格光顺(Smoothing)

Laplacian 平滑:

vi←vi+λ⋅L(vi),L(vi)=1∣Ni∣∑j∈Ni(vj−vi)\mathbf{v}_i \leftarrow \mathbf{v}_i + \lambda \cdot L(\mathbf{v}_i), \quad L(\mathbf{v}_i) = \frac{1}{|\mathcal{N}_i|}\sum_{j \in \mathcal{N}_i} (\mathbf{v}_j - \mathbf{v}_i)

问题:会收缩(shrinkage)。反复迭代网格越缩越小。

解法:

  • Taubin λ|μ:一次正 λ + 一次负 μ,抵消低频收缩
  • 隐式拉普拉斯:解(I−λL)v′=v(I - \lambda L) \mathbf{v}' = \mathbf{v},保持稳定
  • cotangent Laplacian:用余切权重代替均匀权重,保持几何特征

余切权重(离散微分几何的关键):

L(vi)=12Ai∑j(cot⁡αij+cot⁡βij)(vj−vi)L(v_i) = \frac{1}{2A_i} \sum_{j} (\cot\alpha_{ij} + \cot\beta_{ij})(\mathbf{v}_j - \mathbf{v}_i)

其中α,β\alpha, \beta 是边(i,j)(i,j) 对面的两个角。这个离散化收敛到连续 Laplace-Beltrami 算子。

网格简化

边坍缩(Edge Collapse)+ 二次误差度量(Quadric Error Metrics, QEM):

每条边有一个坍缩代价
用优先队列,每次坍缩代价最小的边
代价 = 新顶点到"原来所有相关平面"的距离平方和

每个平面: ax + by + cz + d = 0
二次误差: E(v) = v^T Q v,Q 是 4×4 矩阵(可加,便于合并)

QEM 的优势:误差矩阵可以相加(坍缩后新顶点的误差 = 两个旧顶点的误差矩阵之和),所以能高效增量计算。

这是 Garland & Heckbert 1997 的经典算法,至今仍是主流。

网格重划分(Remeshing)

目标:把不规则网格变成均匀、各向同性的。

1. 按目标边长,太长的边分裂
2. 太短的边坍缩
3. 调整顶点位置(切向松弛,让 valence 趋向 6)
4. 迭代

各向同性三角形网格:理想情况每个顶点 valence = 6,三角形接近等边。

五、参数化(Parameterization)

问题:把三维网格映射到二维平面(以便贴图、纹理合成)。

f:M⊂R3→Ω⊂R2f: \mathcal{M} \subset \mathbb{R}^3 \to \Omega \subset \mathbb{R}^2

必然有畸变(除非是可展曲面,如柱面)。度量畸变:

畸变类型含义
共形(Conformal)保持角度,允许面积畸变
等距(Isometric)保持面积,允许角度畸变
等积(Authalic)保持面积
低畸变两者都尽量小

经典方法:

  • Tutte 嵌入:把边界固定到凸多边形,内部顶点是邻居的重心 → 保证无翻转,但畸变大
  • LSCM(Least Squares Conformal Maps):最小化共形能量
  • ABF(Angle Based Flattening):在角度空间优化
  • ARAP(As Rigid As Possible):尽可能刚体,畸变极小,但要迭代

割缝(Seams):复杂拓扑(如球面)必须切开才能展平。接缝处会有纹理不连续——这是 UV 展开的核心难点。

六、形变(Deformation)

线性蒙皮(Linear Blend Skinning, LBS)

v′=∑iwi(v)⋅Mi⋅v\mathbf{v}' = \sum_i w_i(\mathbf{v}) \cdot \mathbf{M}_i \cdot \mathbf{v}

每个顶点受若干骨骼影响,权重和为 1。

经典问题:

  • 糖果纸效应(candy wrapper):扭转时体积塌陷
  • 手风琴效应(elbow collapse):弯曲时关节处塌陷

原因:矩阵插值的平均值不是旋转矩阵(旋转的线性插值会缩短长度)。

改进:

  • 双四元数蒙皮(Dual Quaternion Skinning):保持刚性,解决糖果纸效应
  • DQS 的代价:可能膨胀(bulging)

自由形变(FFD)

把物体放进一个格子(lattice),变形格子 → 物体跟着变形。

f(x,y,z)=∑i,j,kBi(u)Bj(v)Bk(w)Pijkf(x,y,z) = \sum_{i,j,k} B_i(u) B_j(v) B_k(w) P_{ijk}

ARAP 形变

尽可能刚体:把网格分成若干小片,每片允许旋转,但尽量保持形状。

迭代两步:
  1. 固定位置,求每片的最优旋转(Procrustes / SVD)
  2. 固定旋转,求最优位置(解线性系统)

收敛快,效果好,是交互式形变的主流方法。

七、几何处理的核心思想

把几何问题转化为优化问题:

定义能量 E(网格) = 数据项 + 光滑项 + 约束项
求 argmin E
任务能量函数
光顺拉普拉斯能量
参数化畸变能量(共形/等距)
形变刚性能量(ARAP)
重建拟合误差 + 正则项

统一框架:

  • 数据项:贴合输入/约束
  • 光滑项/正则项:保证结果的良好性质(避免过拟合、保持光滑)
  • 大部分能写成二次型 → 解稀疏线性系统(很快)

这也解释了为什么几何处理和数值线性代数关系密切——大规模稀疏求解器是关键工具。

常见坑

  • Bézier 的全局性:控制点多时用 B 样条
  • 细分曲面的奇异点:valence ≠ 4 处连续性下降,建模时要避免或特殊处理
  • Laplacian 平滑会收缩:长迭代必须用 Taubin 或隐式方法
  • 参数化的畸变不可避免:割缝位置的选择直接决定最终畸变大小
  • LBS 的塌陷:关节处必须加辅助骨骼或用 DQS
  • 隐式曲面难以精确建模:适合做"形状混合/布尔"而非"精确设计"
  • UV 接缝:纹理接缝处的过滤要有 padding,否则有黑边
  • 法线贴图与形变的冲突:形变后切线空间变了,法线要跟着变换(TBN 矩阵)