CAGD 学习笔记 | 极形式

极形式是计算机图形学中用于处理样条曲线和曲面的数学工具, 它是一种将多项式表示为多重仿射函数的方法，它具有对称性和多重仿射性的性质.

例如对于多项式 $P(t)=a t^3+b t^2+c t+d$, 我们可以将它改写为 $P(t)=a \cdot t \cdot t \cdot t+b \cdot t \cdot t+c \cdot t+d$, 则这一多项式的极形式就是

$$ P(t) = a \cdot t_1 t_2 t_3 + b (t_1 t_2 + t_2 t_3 + t_3 t_1) / 3 + c (t_1 + t_2 + t_3) / 3 + d $$

如下图是一段 3 阶 Bézier 曲线, 其中的点就是 Bézier 曲线的控制点和 de Casteljau 算法的中间点, 这些点恰好可以用极形式进行表示. 在后文中将介绍极形式的具体定义, 以及为什么可以用极形式表示这些点.

定义

仿射组合

在介绍极形式的定义之前, 我们需要先介绍仿射组合的概念.

$n$ 个 $\mathbb{R}^d$ 中点的仿射组合 (Affine Combination) 指的是

$$ P_\alpha=\sum_{i=1}^n \alpha_i p_i \text { with } \sum_{i=1}^n \alpha_i=1 $$

某一函数 $f = f(x_1, \dots, x_m)$ 对于它的参数 $x_i$ 是仿射的指的是

$$ f\left(x_1, \ldots, \sum_{i=1}^n \alpha_i x_i^{(k)}, \ldots, x_m\right) =\sum_{i=1}^n \alpha_i f\left(x_1, \ldots, x_i^{(k)}, \ldots, x_m\right) \text { for } \sum_{i=1}^n \alpha_i=1 $$

两个点和三个点的仿射组合如下图所示.

注意到, 仿射组合与凸组合 (Convex Combination) 的区别只是, 凸组合的每一个系数都是非负的. 事实上, 凸组合就是一种特殊的仿射组合, 也可以将仿射组合理解为凸组合的一种推广, 两个点的所有凸组合是它们相连得到的线段, 所有仿射组合是它所确定的直线, 三个点的所有凸组合是它们构成的三角形的闭包, 仿射组合是它所确定的平面.

直觉地来看, de Casteljau 算法就是不断计算凸组合的过程, 从这一点出发我们可以注意到 Bézier 曲线与极形式之间的紧密联系.

极形式的定义

对于一个 $n$ 阶的多项式 $F: \mathbb{R} \rightarrow \mathbb{R}$, 若 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是满足以下条件的函数:

• Diagonality: $f(t, t, \ldots, t)=F(t)$,
• Symmetry: $f\left(t_1, t_2, \ldots, t_n\right)=f\left(t_{\pi(1)}, t_{\pi(2)}, \ldots t_{\pi(n)}\right)$, 其中 $\pi$ 是 $(1,\dots,n)$ 的任意一个置换,
• Multi-affine: $f$ 对它的每一个参数都是仿射的 (或者说是线性的),

则称 $f$ 是 $F$ 的多重仿射极形式 (Multi-affine Polar Form) 或开花 (Blossom).

可以通过单项式的极形式得到任意一个多项式的极形式:

• 0 阶: $1 \rightarrow 1$
• 1 阶: $1 \rightarrow 1, \ t \rightarrow t$
• 2 阶: $1 \rightarrow 1, \ t \rightarrow \frac{t_1+t_2}{2}, \ t^2 \rightarrow t_1 t_2$
• 3 阶: $1 \rightarrow 1, \ t \rightarrow \frac{t_1+t_2+t_3}{3}, \ t^2 \rightarrow \frac{t_1 t_2+t_2 t_3+t_1 t_3}{3}, \ t^3 \rightarrow t_1 t_2 t_3$
• n 阶: $t^k \rightarrow \binom{n}{k}^{-1} \sum_{S \subset \{1,...,n\} \atop |S| = k} \prod_{i \in S} t_i$

$$ F(t) = \sum_{k=0}^{n} c_k t^k \rightarrow f(t_1,\dots,t_n) = \sum_{k=0}^{n} \binom{n}{k}^{-1} \sum_{S \subset \{1,\dots,n\} \atop |S| = k} \prod_{i \in S} t_i $$

不难验证, 每个单项式对应的极形式是唯一的, 进而多项式与极形式是一一对应的.

注 多项式与极形式是一一对应的, 指的是对于一个 $n$ 阶的多项式 $F$, 存在唯一的多重仿射函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是它的极形式. 但是我们可以在形式上假定一个 $n$ 阶的多项式是 $n+1$ 阶的 (只不过它的 $n+1$ 次项的系数为 0), 并得到一个有 $n+1$ 个参数的极形式, 这不与多项式与极形式是一一对应的相矛盾. 事实上, 这就是极形式的升阶, 在后文中将介绍它的应用.

极形式, Bézier 曲线和 de Casteljau 算法

上文中已经给出过结论, 一条定义在 $[0,1]$ 上的 Bézier 曲线 $F(t)$ 的控制点和 de Casteljau 算法的中间点都可以用 $f(0,\dots,0,1,\dots,1,t,\dots,t)$ 来表示, 接下来我们将证明这一结论.

我们知道 Bézier 曲线的显示表达式为

$$ F(t) = \sum_{k=0}^n B_k^n(t)p_k $$

设它的极形式为 $f(t_1, \dots,t_n)$, 只需验证 $f(\overbrace{0,\dots,0}^{\text{重复}n-k\text{次}}, \overbrace{1,\dots,1}^{\text{重复}k\text{次}}) = p_k$.

由归纳法

$$ \begin{aligned} F(t) & = f(t, \dots, t) \\ & = (1-t) f(t, \dots, t, 0) + t f(t, \dots, t, 1) \\ & = (1-t)^2 f(t, \dots, t, 0, 0) + 2t(1-t) f(t, \dots, t, 0, 1) + t^2 f(t, \dots, t, 1, 1) \\ & = B^2_0(t) f(t, \dots, t, 0, 0) + B^2_1(t) f(t, \dots, t, 0, 1) + B^2_2(t) f(t, \dots, t, 1, 1) \\ & = \cdots \\ & = \sum_{k=0}^n B^n_k(t) f(\overbrace{0,\dots,0}^{\text{重复}n-k\text{次}}, \overbrace{1,\dots,1}^{\text{重复}k\text{次}}) \end{aligned} $$

又因为 Bernstein 基函数是 $n$ 阶多项式空间的基, 知 $f(\overbrace{0,\dots,0}^{\text{重复}n-k\text{次}}, \overbrace{1,\dots,1}^{\text{重复}k\text{次}}) = p_k$.

注 事实上, 可以在这一证明中, 将区间 $[0,1]$ 替换为任意区间 $[r,s]$, 并得到这一条 Bézier 曲线在 $[r,s]$ 上的控制点. 这一结论还可以用于 Bézier 曲线的细分.

注2 从这里的推导可以联想到, 在 B 样条的结点向量中适当地重复结点, 可以得到 Bernstein 基函数.

升阶

给定极形式 $f(t_1, \dots, t_n)$, 可以用下式对其进行升阶

$$ f^{(+1)}(t_1, \dots, t_{n+1}) = \frac{1}{n+1} \sum_{k=0}^n f(t_1,\dots,t_{k-1},t_{k+1},\dots{t_{n+1}}) $$

注 事实上, 我们可以直接把 $F(t)$ 当作高阶多项式来写出它的极形式, 进而实现 Bezier 曲线的升阶这样的操作.

导数

我们可以将极形式的定义域从点集扩展到点和向量的集合. 称 $t$ 为点, 而 $\hat{v}$ 为向量, 向量是两个点之间的差: $\hat{v} = p - q$. 递归地定义极形式

$$ f(t_1, \dots, t_{n-k}, \hat{v}_1, \hat{v}_2, \dots, \hat{v}_k) = f(t_1, \dots, t_{n-k}, p_1, \hat{v}_2, \dots, \hat{v}_k) - f(t_1, \dots, t_{n-k}, q_1, \hat{v}_2, \dots, \hat{v}_k) $$

显然, 对 $p_i$ 和 $q_i$ 作一个平移, 所得到的 $f(t_1, \dots, t_{n-k}, \hat{v}_1, \dots, \hat{v}_k)$ 的值不会改变, 因此这一定义是合理的.

利用向量域上的极形式, 我们可以给出 $F$ 的导数

$$ \frac{\mathrm{d}^r}{\mathrm{d}t^r} F(t) = \frac{n!}{(n-r)!} f(\underbrace{t,\dots,t}_{\text{重复}n-r\text{次}}, \underbrace{\hat{1},\dots,\hat{1}}_{\text{重复}r\text{次}}) $$

这一结论的证明可以归约为单项式的一阶导数的情况, 而这是容易证明的.

基的变换

假设有一条多项式曲线 $F(t) = \sum_{k=0}^n c_k t^k$, 则可以通过改写为极形式, 得到它作为区间 $[a, b]$ 上的 Bézier 曲线的控制点:

$$ p_k = f(\underbrace{a,\dots,a}_{\text{重复}n-k\text{次}}, \underbrace{b,\dots,b}_{\text{重复}k\text{次}}) $$

极形式, B 样条和 de Boor 算法

在上文中, 我们已经实现了将 de Casteljau 算法改写为极形式的语言, 那么对于与它非常相像的 de Boor 算法, 是否也可以做类似的操作? 答案是可以, 但只能做到形式上类似.

以下的讨论将沿用上一篇笔记中推导 de Boor 算法所采用的记号.

首先, 假设 $t \in [t_{l}, t_{l+1})$, 则有

$$ \begin{aligned} p(t) & = p_l^{(d)}(t) \\ & = (1 - \alpha_l^{(d-1)} (t)) p_{l-1}^{(d-1)} (t) + \alpha_l^{(d-1)}(t) p_{l}^{(d-1)}(t) \\ & = \frac{t_{l+1}-t}{t_{l+1}-t_l} p_{l-1}^{(d-1)} + \frac{t-t_l}{t_{l+1}-t_l} p_{l}^{(d-1)}(t) \end{aligned} $$

与 de Casteljau 算法类似地, 可以将上式改写为

$$ f(\overbrace{t,\dots,t}^{\text{重复}d\text{次}}) = \frac{t_{l+1}-t}{t_{l+1}-t_l} f(t,\dots,t,t_l) + \frac{t-t_l}{t_{l+1}-t_l} f(t,\dots,t,t_{l+1}) $$

递推可知, 影响 $f(t)$ 的 de Boor 点为 $\{f(t_{l-d+1},\dots,t_l), f(t_{l-d+2},\dots,t_{l+1}), \dots, f(t_{l},\dots,t_{l+d-1})\}$.

下图中给出了更为直观的递推过程, $t \in [t_3,t_4)$, $d = 3$.

通过这种方式, 我们就可以用极形式的语言来简单地表述 de Boor 算法, 下图是用这一方法绘制 B 样条曲线的例子.

值得注意的是, 因为 B 样条是分段的多项式, 所以极形式当然也是分段的, 并且很难找出它的显式表达式 (就像很难找出 B 样条曲线的的显式表达式一样). 但笔者认为这或许是没有必要的, 我们暂时只认为极形式在这里只担任表述 de Boor 算法的角色即可.