贝塞尔曲线和曲面

1. 指数基多项式

虽然，多项式(polynomials)在数学形式上也很简单而且易于理解，并且能够被计算机方便的进行数值运算。但是有一些特殊的曲线或者曲面不能写成多项式的形式。常用的多项式表示方法有指数基(power basis)和贝塞尔(Bézier)两种方法，虽然它们在数学本质上是等价的，但在实际应用中，贝塞尔曲线是一种更好用的形式。

一条 $n$阶的指数基曲线可以写成如下的形式：

$$ \boldsymbol{C}(u) = \begin{bmatrix} x(u) \\ y(u) \\ z(u) \end{bmatrix} = \Sigma_{i = 0}^n \boldsymbol{a}_i u^i, (0 ≤ u ≤ 1) $$

其中，$a_i = \begin{bmatrix} x_i & y_i & z_i \end{bmatrix}$:

$$ \begin{array}{rcl} x(u) & = & \Sigma_{i = 0}^n x_i u^i \\ y(u) & = & \Sigma_{i = 0}^n y_i u^i \\ z(u) & = & \Sigma_{i = 0}^n z_i u^i \end{array} $$

写成矩阵的形式有:

$$ \boldsymbol{C}(u) = \begin{bmatrix} x(u) \\ y(u) \\ z(u) \end{bmatrix} = \begin{bmatrix} a_0 & a_1 & \cdots & a_n \end{bmatrix} \begin{bmatrix} 1 \\ u \\ \vdots \\ u^n \end{bmatrix} = \begin{bmatrix} a_i \end{bmatrix}^T \begin{bmatrix} u^i \end{bmatrix} $$

指数基曲线有如下的一些缺点:

不适用于交互式的形状编辑。尤其是，设计者通常希望能够表述曲线两端的约束条件，但指数基曲线只能描述起始点的约束。
处理指数基曲线的算法通常都是代数形式的，很少有几何意义。
在数值计算上不稳定，容易因为舍入误差而发散。

2. Bézier 贝塞尔曲线

一条 $n$阶的贝塞尔曲线被定义为:

$$ \boldsymbol{C}(u) = \Sigma_{i = 0}^n B_{i,n}(u) \boldsymbol{P}_i, (0 ≤ u ≤ 1) $$

其中，$\left\{ B_{i,n}(u) \right\}$是经典的$n$阶 Bernstein 多项式：

$$ \boldsymbol{B}_{i,n}(u) = \frac{n!}{i!(n-i)!} u^i(1-u)^{n-i} $$

该形式的几何系数$\left\{ \boldsymbol{P}_i \right\}$，被称为控制点(control points)。

贝塞尔曲线在旋转、平移和缩放的变换下具有不变性。

贝塞尔曲线的导数可以写成如下的形式:

$$ \begin{array}{rcl} \boldsymbol{C}'(u) & = & \frac{d\left(\Sigma_{i=0}^n \boldsymbol{B}_{i,n}(u) \boldsymbol{P}_i \right)}{du} = \Sigma_{i = 0}^n \boldsymbol{B}_{i,n}'(u) \boldsymbol{P}_i \\ & = & \Sigma_{i = 0}^n\left(\boldsymbol{B}_{i-1,n-1}(u) - \boldsymbol{B}_{i, n-1}(u) \right) \boldsymbol{P}_i \\ & = & n \Sigma_{i = 0}^{n - 1} \left\{\boldsymbol{B}_{i, n-1}(u)\left(\boldsymbol{P}_{i+1} - \boldsymbol{P}_i\right) \right\} \end{array} $$

上式意味着，$n$阶的贝塞尔曲线是一个$n-1$阶的贝塞尔曲线。贝塞尔曲线还有如下的性质:

$$ \begin{array}{rcl} \boldsymbol{C}_n(\boldsymbol{P}_0, \cdots, \boldsymbol{P}_n) = (1-u)\boldsymbol{C}_{n-1}(\boldsymbol{P}_0, \cdots, \boldsymbol{P}_{n-1}) + u \boldsymbol{C}_{n-1}(\boldsymbol{P}_1, \cdots, \boldsymbol{P}_n) \end{array} $$

给定 $u = u_0$，$n+1$个控制点$\boldsymbol{P}_0, \cdots, \boldsymbol{P}_n$，那么 n 阶的贝塞尔曲线可以写成:

$$ \begin{align}\label{deCasteljau_bezier} \boldsymbol{C}(u_0) & = \boldsymbol{P}_{n,0}(u_0) \\ \boldsymbol{P}_{k,i}(u_0) & = (1 - u_0) \boldsymbol{P}_{k-1, i}(u_0) + u_0 \boldsymbol{P}_{k-1, i+1} & for \begin{cases} k = 1, \cdots, n \\ i = 0, \cdots, n - k \end{cases} \end{align} $$

上述特性可以写成如右图所示的一个三角形的表格，该算法称为deCasteljau Algorithm。

3. 有理贝塞尔曲线

上述的指数基多项式和贝塞尔都是多项式的表示方法。虽然多项式的表示方法有很多优点，但有很多重要的曲线和曲面不能够精确地得到描述。实际上，所有的圆锥曲线(conic curves)，包括圆，都可以用rational functions来表示，也就是两个多项式的比值，即：

$$ x(u) = \frac{X(u)}{W(u)}, y(u) = \frac{Y(u)}{W(u)} $$

我们定义 $n$阶的有理贝塞尔曲线(rational Bézier):

$$\begin{equation}\label{rational_bezier_1} \boldsymbol{C}(u) = \frac{\Sigma_{i=0}^n \boldsymbol{B}_{i,n}(u)w_i \boldsymbol{P}_i}{\Sigma_{i=0}^n \boldsymbol{B}_{i,n}(u) w_i } , (0 ≤ u ≤ 1) \end{equation} $$

其中，$\boldsymbol{P}_i = (x_i, y_i, z_i)$，$\boldsymbol{B}_{i,n}(u)$仍为$n$阶的 Bernstein 多项式。$w_i$是一个标量，称为权重。在没有特别说明的情况下，我们认为$w_i > 0$。这样可以保证对于所有的$u \in [0, 1]$都有分母$W(u) = \Sigma_{i=0}^n \boldsymbol{B}_{i,n}(u) w_i > 0$。

式$\ref{rational_bezier_1}$还可以写成:

$$\begin{align}\label{rational_bezier_2} \boldsymbol{C}(u) & = \Sigma_{i=0}^n \boldsymbol{R}_{i,n}(u) \boldsymbol{P}_i, (0 ≤ u ≤ 1) \\ \boldsymbol{R}_{i,n}(u) & = \frac{\boldsymbol{B}_{i,n}(u)w_i}{\Sigma_{i=0}^n \boldsymbol{B}_{i,n}(u) w_i } \end{align} $$

$R_{i,n}(u)$被称为有理基函数(rational basis function)，有如下的性质:

非负(nonnegativity): 对于所有的 $i, n$ 和 $0 ≤ u ≤ 1$, 都有$R_{i,n}(u) ≥ 0$
和为一: $\Sigma_{i = 0}^n R_{i,n}(u) = 1$
$R_{0,n}(0) = R_{n,n}(1) = 1$
在闭区间$[0,1]$中，$R_{i,n}(u)$只有一个极值。
如果所有的权重$w_i = 1$，则有$R_{i,n}(u) = B_{i,n}(u)$，即贝塞尔曲线是有理贝塞尔曲线的一个特例。

式$\ref{rational_bezier_1}, \ref{rational_bezier_2}$还可以写成齐次坐标的形式，给定控制点集$\left\{\boldsymbol{P}_i\right\}$和权重$\left\{w_i\right\}$，可以构建加权的控制点 $\boldsymbol{P}_i^w = (w_i x_i, w_i y_i, w_i z_i, w_i)$，于是有被称为非有理贝塞尔曲线(nonrational Bézier)的形式:

$$ \begin{equation}\label{nonrational_bezier} \boldsymbol{C}^w(u) = \Sigma_{i = 0}^n \boldsymbol{B}_{i,n}(u) \boldsymbol{P}_i^w \end{equation}$$ 给定$u = u_0$还可以应用 deCasteljau 算法计算$\boldsymbol{C}^w(u)$: $$ \begin{align}\label{deCasteljau_nonrational_bezier} \boldsymbol{C}^w(u_0) & = \boldsymbol{P}_{n,0}^w(u_0) \\ \boldsymbol{P}_{k,i}^w(u_0) & = (1 - u_0) \boldsymbol{P}_{k-1, i}^w(u_0) + u_0 \boldsymbol{P}_{k-1, i+1}^w & for \begin{cases} k = 1, \cdots, n \\ i = 0, \cdots, n - k \end{cases} \end{align} $$

4. 曲面

曲线$\boldsymbol{C}(u)$是单变量$u$的参数方程，把直线段映射到3维的欧氏空间中。曲面则是双变量$u,v$的参数方程，将$uv$平面中一个区域$\mathcal{R}$映射到三维的欧氏空间中。具有形式:

$$ \boldsymbol{S}(u,v) = \left(x(u,v), y(u,v), z(u,v)\right), (u,v) \in \mathcal{R} $$

有很多种表达曲面的方式，张量积tensor product是其中一种广泛使用的方式。它使用基函数和几何系数来描述曲面。几何系数在两个方向上分布，形成一个$n \times m$的网格。因此，张量积曲面具有如下的形式:

$$ \boldsymbol{S}(u,v) = \left(x(u,v), y(u,v), z(u,v)\right) = \Sigma_{i=0}^n \Sigma_{j=0}^m f_i(u) g_j(v) \boldsymbol{b}_{i,j} $$ $$ \boldsymbol{b}_{i,j} = (x_{i,j}, y_{i,j}, z_{i,j}) $$ $$ 0 ≤ u, v ≤ 1 $$

我们也可以写成矩阵的形式:

$$ \boldsymbol{S}(u,v) = \begin{bmatrix} f_i(u) \end{bmatrix}^T \begin{bmatrix} \boldsymbol{b}_{i,j} \end{bmatrix} \begin{bmatrix} g_i(v) \end{bmatrix} $$

其中，$\begin{bmatrix} f_i(u) \end{bmatrix}^T$是一个$1 \times (n+1)$的行向量，$\begin{bmatrix} g_i(v) \end{bmatrix}$是一个$(m+1) \times 1$的列向量。 $\begin{bmatrix} \boldsymbol{b}_{i,j} \end{bmatrix}$则是一个$(n+1) \times (m+1)$的矩阵。如果，我们固定变量$u = u_0$或者$v = v_0$，就可以得到一条在曲面$\boldsymbol{S}(u,v)$上的一条曲线$\boldsymbol{C}_{u_0}(v)$或$\boldsymbol{C}_{v_0}(u)$，称之为等参数曲线(isocurves, isoparametric curves)，$\boldsymbol{C}_{u_0}(v)$为v curve，$\boldsymbol{C}_{v_0}(u)$为u curve。特别的，有$\boldsymbol{C}_{u_0}(v_0) = \boldsymbol{C}_{v_0}(u_0)$。

非有理贝塞尔曲面，有控制点网格和双变量 Bernstein 多项式张量积构成：

$$ \begin{align} \boldsymbol{S}(u,v) & = \Sigma_{i=0}^n \Sigma_{j=0}^m \boldsymbol{B}_{i,n}(u) \boldsymbol{B}_{j,m}(v) \boldsymbol{P}_{i,j} & 0 ≤ u, v ≤ 1 \end{align} $$

由于等参数线是曲面上的曲线，所以对于给定的$u_0, v_0$我们可以分别在两个参数上应用 deCasteljau 算法计算出 $\boldsymbol{S}(u_0, v_0)$。需要计算$\frac{n(n+1)(m+1)}{2} + \frac{m(m+1)}{2}$次线性插值。