Games102
GAMES102:几何建模与处理(刘利刚)的笔记。
主题:如何表示形状,以及如何处理形状。
一、几何表示的三类
| 类型 | 形式 | 优点 | 缺点 |
|---|---|---|---|
| 离散 | 点云、网格 | 通用、易获取 | 无连续性信息 |
| 连续 | 参数曲线曲面 | 光滑、可精确求值 | 难表示复杂拓扑 |
| 混合 | 细分曲面、隐式 | 兼顾 | 复杂 |
核心矛盾:真实世界是连续的,计算机只能存离散的。如何在离散数据上恢复/保持连续性,是几何处理的主线。
二、参数曲线
多项式曲线的问题
用高阶多项式插值很多点 → Runge 现象(振荡)。
/\ /\
________________/ \____/ \______ ← 高次插值的振荡解法:分段低阶(样条),而不是单段高阶。
Bézier 曲线
性质:
- 端点插值:,
- 凸包性:曲线在控制点的凸包内
- 端点切线方向:
- 仿射不变,但非射影不变
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)优点:数值稳定,同时给出子曲线的控制点(用于细分)。
拼接连续性
| 等级 | 要求 | 视觉 |
|---|---|---|
| 位置连续 | 无断点 | |
| 一阶导连续 | 切线连续,无折角 | |
| 二阶导连续 | 曲率连续,无"光顺度"突变 | |
| 切线方向连续(大小可不同) | 视觉上光滑 |
vs: 只要求几何连续(方向), 要求参数连续(含速率)。视觉上 就够了,但 更严格。
B 样条(B-Spline)
动机:Bézier 的全局性——移动一个控制点整条曲线都变。
B 样条用**节点向量(knot vector)**实现局部支撑:
| 特性 | 值 |
|---|---|
| 局部性 | ✓(移动一个控制点只影响局部) |
| 连续性 | 自动( 是次数) |
| 端点插值 | ✗(除非用重节点) |
三次 B 样条是最常用的( 连续 + 局部性 + 计算简单)。
NURBS
非均匀有理 B 样条 = B 样条 + 权重:
有理的意义:能精确表示圆锥曲线(圆、椭圆),B 样条只能逼近。
工业标准:CAD/CAM(STEP、IGES 格式都基于 NURBS)。
三、参数曲面
张量积曲面
Bézier 曲面、B 样条曲面、NURBS 曲面都是这个形式——控制点变成控制网格。
问题:张量积要求四边形网格,且拓扑受限(柱面、球面要接缝)。
隐式曲面
| 优点 | 缺点 |
|---|---|
| 判断内外极快 | 采样表面难 |
| 布尔运算简单(/) | 难以精确建模 |
| 拓扑变化自动处理 | — |
| 表达能力强(分形) | — |
SDF(Signed Distance Field):
f(x) = 到表面的最短距离(内部为负)
|∇f| = 1 ← 关键性质用途:
- 光线步进(sphere tracing):每次可以安全前进
f(x)的距离 - 软阴影(见实时阴影)
- 碰撞检测
- 布尔运算(smooth min)
细分曲面(Subdivision)
从一个粗网格反复细分,极限是一个光滑曲面。
| 方案 | 适用网格 | 极限连续性 |
|---|---|---|
| Catmull-Clark | 四边形 | (除奇异点) |
| Loop | 三角形 | (除奇异点) |
| Doo-Sabin | 四边形 | |
| Butterfly | 三角形 |
Catmull-Clark 规则(四边形):
面点: 4 个顶点的平均
边点: (两端点 + 相邻两个面点) / 4
顶点: 按 valence 加权更新(保证收缩到光滑极限)**奇异点(valence ≠ 4)**处只有,是细分曲面的固有缺陷。
价值:电影/游戏建模的标准(Pixar 的 Geri's Game 开始)——艺术家操作简单拓扑,计算机生成光滑表面。
四、网格处理
曲率
主曲率:
| 量 | 定义 | 用途 |
|---|---|---|
| 高斯曲率 | 判断局部形状( 椭圆、 双曲、 抛物) | |
| 平均曲率 | 光顺、最小曲面 |
离散高斯曲率(角度亏损):
平面上角度和是,亏损量就是曲率。
网格光顺(Smoothing)
Laplacian 平滑:
问题:会收缩(shrinkage)。反复迭代网格越缩越小。
解法:
- Taubin λ|μ:一次正 λ + 一次负 μ,抵消低频收缩
- 隐式拉普拉斯:解,保持稳定
- cotangent Laplacian:用余切权重代替均匀权重,保持几何特征
余切权重(离散微分几何的关键):
其中 是边 对面的两个角。这个离散化收敛到连续 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)
问题:把三维网格映射到二维平面(以便贴图、纹理合成)。
必然有畸变(除非是可展曲面,如柱面)。度量畸变:
| 畸变类型 | 含义 |
|---|---|
| 共形(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)
每个顶点受若干骨骼影响,权重和为 1。
经典问题:
- 糖果纸效应(candy wrapper):扭转时体积塌陷
- 手风琴效应(elbow collapse):弯曲时关节处塌陷
原因:矩阵插值的平均值不是旋转矩阵(旋转的线性插值会缩短长度)。
改进:
- 双四元数蒙皮(Dual Quaternion Skinning):保持刚性,解决糖果纸效应
- DQS 的代价:可能膨胀(bulging)
自由形变(FFD)
把物体放进一个格子(lattice),变形格子 → 物体跟着变形。
ARAP 形变
尽可能刚体:把网格分成若干小片,每片允许旋转,但尽量保持形状。
迭代两步:
1. 固定位置,求每片的最优旋转(Procrustes / SVD)
2. 固定旋转,求最优位置(解线性系统)收敛快,效果好,是交互式形变的主流方法。
七、几何处理的核心思想
把几何问题转化为优化问题:
定义能量 E(网格) = 数据项 + 光滑项 + 约束项
求 argmin E| 任务 | 能量函数 |
|---|---|
| 光顺 | 拉普拉斯能量 |
| 参数化 | 畸变能量(共形/等距) |
| 形变 | 刚性能量(ARAP) |
| 重建 | 拟合误差 + 正则项 |
统一框架:
- 数据项:贴合输入/约束
- 光滑项/正则项:保证结果的良好性质(避免过拟合、保持光滑)
- 大部分能写成二次型 → 解稀疏线性系统(很快)
这也解释了为什么几何处理和数值线性代数关系密切——大规模稀疏求解器是关键工具。
常见坑
- Bézier 的全局性:控制点多时用 B 样条
- 细分曲面的奇异点:valence ≠ 4 处连续性下降,建模时要避免或特殊处理
- Laplacian 平滑会收缩:长迭代必须用 Taubin 或隐式方法
- 参数化的畸变不可避免:割缝位置的选择直接决定最终畸变大小
- LBS 的塌陷:关节处必须加辅助骨骼或用 DQS
- 隐式曲面难以精确建模:适合做"形状混合/布尔"而非"精确设计"
- UV 接缝:纹理接缝处的过滤要有 padding,否则有黑边
- 法线贴图与形变的冲突:形变后切线空间变了,法线要跟着变换(TBN 矩阵)