贝塞尔曲线

为什么用参数曲线（17 章引言、17.1 节）

• 曲线曲面的好处：比三角形更紧凑、可伸缩（可细分成 2 个或 2000 个三角形，天然的 LOD）、更平滑，动画和碰撞检测可能更简单（只需动画少量控制点）。
• 例：相机要在 1 秒内从一点移到另一点，每帧 50 ms 时取 20 个位置，25 ms 时取 40 个，参数曲线都能给出。线性插值 $\mathbf{p}(t)=(1-t)\mathbf{p}_0+t\mathbf{p}_1$ 在多点之间会在接点处突然"抖动"，因此需要更平滑的曲线。朝向插值见 四元数。

de Casteljau 算法（17.1.1 节）

贝塞尔曲线由 de Casteljau 和 Bézier 为法国汽车工业各自独立发明，因 Bézier 先公开发表而得名。三个控制点 $\mathbf{a},\mathbf{b},\mathbf{c}$ 时，先在 $\mathbf{a}\mathbf{b}$、$\mathbf{b}\mathbf{c}$ 上按 $t$ 插值出 $\mathbf{d},\mathbf{e}$，再在 $\mathbf{d}\mathbf{e}$ 上插值： $\mathbf{p}(t) = (1-t)^2\mathbf{a} + 2(1-t)t\,\mathbf{b} + t^2\mathbf{c}$ 一般地，$n+1$ 个控制点给出 $n$ 次曲线，递推为 $\mathbf{p}_i^k(t) = (1-t)\,\mathbf{p}_i^{k-1}(t) + t\,\mathbf{p}_{i+1}^{k-1}(t),\quad k=1\dots n,\ i=0\dots n-k$ 曲线点为 $\mathbf{p}(t)=\mathbf{p}_0^n(t)$。

flowchart BT
  P0[p0] --> A1[p0^1]
  P1[p1] --> A1
  P1 --> B1[p1^1]
  P2[p2] --> B1
  A1 --> C[p0^2 = p t]
  B1 --> C

上图（自下而上读）是二次曲线的递推三角：每一层由下一层相邻两点按 $(1-t)$、$t$ 加权得到。

Bernstein 形式

$\mathbf{p}(t)=\sum_{i=0}^{n} B_i^n(t)\,\mathbf{p}_i,\qquad B_i^n(t)=\binom{n}{i}t^i(1-t)^{n-i}$

• 性质：$t\in[0,1]$ 时 $B_i^n(t)\in[0,1]$，且 $\sum_i B_i^n(t)=1$，所以曲线位于控制点的凸包内（便于求包围体）；插值两个端点；在 $t=0$ 处与 $\mathbf{p}_1-\mathbf{p}_0$ 相切，在 $t=1$ 处与 $\mathbf{p}_n-\mathbf{p}_{n-1}$ 相切；先变换控制点再求曲线点等价且更快。
• 三次曲线： $\mathbf{p}(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$ 矩阵形式 $\mathbf{p}(t)=\begin{pmatrix}1 & t & t^2 & t^3\end{pmatrix}\begin{pmatrix}1&0&0&0\\-3&3&0&0\\3&-6&3&0\\-1&3&-3&1\end{pmatrix}\begin{pmatrix}\mathbf{p}_0\\\mathbf{p}_1\\\mathbf{p}_2\\\mathbf{p}_3\end{pmatrix}$
• 导数仍是贝塞尔曲线，次数低一： $\frac{d}{dt}\mathbf{p}(t)=n\sum_{i=0}^{n-1}B_i^{n-1}(t)(\mathbf{p}_{i+1}-\mathbf{p}_i)$
• 缺点：除端点外不经过控制点；次数随控制点增加而升高，求值越来越贵。解决办法是分段低次曲线。

有理贝塞尔曲线

$\mathbf{p}(t)=\frac{\sum_{i=0}^n w_iB_i^n(t)\mathbf{p}_i}{\sum_{i=0}^n w_iB_i^n(t)}$ 权重 $w_i$ 是额外自由度。普通贝塞尔曲线无法精确表示圆，用三段有理贝塞尔曲线可以。

GPU 上的有界贝塞尔曲线 (Loop-Blinn)（17.1.2 节）

填充二次曲线与首尾连线之间的区域：渲染三角形 $\triangle\mathbf{p}_0\mathbf{p}_1\mathbf{p}_2$，顶点纹理坐标分别为 $(0,0)$、$(0.5,0)$、$(1,1)$，像素着色器计算 $f(u,v)=u^2-v$，$f<0$ 在内部，否则在外。透视投影下同样得到投影后的曲线。可用于渲染 TrueType 字体（字形由直线和二次贝塞尔曲线组成，"细分"为有界曲线三角形和普通三角形），Loop 与 Blinn 还给出有理二次、三次曲线和抗锯齿方法。详见 文本渲染。

分段曲线与连续性（17.1.3 节）

两段三次曲线 $\mathbf{q}_i$、$\mathbf{r}_i$ 以 $\mathbf{q}_3=\mathbf{r}_0$ 相接，到达时间 $t_0, t_1, t_2$。第二段的参数要重映射到 $[0,1]$： $t'=\frac{t-t_1}{t_2-t_1}$

• 切向相接：$(\mathbf{r}_1-\mathbf{r}_0)=c(\mathbf{q}_3-\mathbf{q}_2)$，$c>0$。
• 取 $c=\dfrac{t_2-t_1}{t_1-t_0}$ 得到 $C^1$；时间间隔相等时 $c=1$。若间隔不等仍用 $c=1$，形状相同但沿曲线的速度在接点突变。

$G^1$ 弱于 $C^1$。三次曲线是能表示 S 形（拐点）的最低次曲线，因此分段曲线常用三次。

PBRT 的视角：开花（Blossoming）（PBRT 4e B.2.8）

• 三次贝塞尔曲线的开花 (blossom) $p(u_0,u_1,u_2)$ 是对称、对每个参数仿射的三元函数，$p(u,u,u)$ 就是曲线在 $u$ 处的值；$p(0,0,0)$、$p(0,0,1)$、$p(0,1,1)$、$p(1,1,1)$ 是四个控制点。计算方式就是三层线性插值，每层用不同参数（de Casteljau 的推广），pbrt 用 BlossomCubicBezier() 实现。
• 用途：区间 $[u_a,u_b]$ 上子曲线的控制点就是 $p(u_a,u_a,u_a)$、$p(u_a,u_a,u_b)$、$p(u_a,u_b,u_b)$、$p(u_b,u_b,u_b)$（SubdivideCubicBezier() 中有的直接化为原控制点的简单组合，不必调用开花函数）；求值时最后被插值的两个点所连直线就是切线，因此可以同时得到导数。开花由 Ramshaw（1987）提出。
• 原书问题（参考文献）：参考文献中"Ramshaw, R. 1989. Blossoms are polar forms"的名字缩写应为 L.（Lyle Ramshaw，与同页 1987 条一致；见 CAGD 6(4):323–358）。