mirror of
https://github.com/Pomax/BezierInfo-2.git
synced 2025-09-03 05:12:43 +02:00
139 lines
7.9 KiB
Markdown
139 lines
7.9 KiB
Markdown
# 曲线的升次与降次
|
||
|
||
贝塞尔曲线有一个有意思的性质——*n*阶曲线总可通过给出*n+1*阶曲线对应的控制点而用高一阶的曲线精确表示。
|
||
|
||
如果有一条二次曲线，那么可以如下构造三次曲线精确重现原来的曲线：首先选择相同的起点和终点，然后两个控制点分别选为“1/3*起点+2/3*终点”和“2/3*起点+1/3*终点”。所得曲线与原来的相同，只不过表示为了三次曲线而不是二次曲线。
|
||
|
||
将*n*次曲线升为*n+1*次曲线的一般规则如下（注意起点和终点的权重与旧曲线的相同）：
|
||
|
||
\[
|
||
\textit{Bézier}(k,t) = \sum_{i=0}^{k}
|
||
\underbrace{\mathrm{C}_k^i}_{\textit{二项式系数项}}
|
||
\cdot\
|
||
\underbrace{(1-t)^{k-i} \cdot t^{i}}_{\textit{多项式项}}
|
||
\ \cdot \
|
||
\underbrace{\left ( \frac{(k-i) \cdot w_i + i \cdot w_{i-1}}{k} \right )}_{\textit{新权重}}
|
||
\textit{，其中}\ k=n+1 \textit{，} w_{-1}=0
|
||
\]
|
||
|
||
然而这一规则也直接意味着通常**无法**将*n*次曲线稳妥地降到*n-1*次，这是因为控制点无法被简洁地“拆开”。可以做些尝试，但所得曲线不会与原曲线重合，而且其实还可能看起来完全不同。
|
||
|
||
不过有一种好得出人意料的方法可以保证低次曲线看起来与原曲线“尽可能地接近”——用仅仅一次操作优化低次曲线与原曲线之间的“最小二乘法距离”（[Sirver's Castle](https://www.sirver.net/blog/2011/08/23/degree-reduction-of-bezier-curves/)中亦有解释），但是为了用上这种方法，需要先做些变形再转用线性代数。正如矩阵表示一章所言，有些东西用矩阵去做比用函数方便得多，而这就是一例。那么……开始吧！
|
||
|
||
先将标准的贝塞尔函数写得紧凑一些：
|
||
|
||
\[
|
||
\textit{Bézier}(n,t)
|
||
=
|
||
\sum_{i=0}^{n} w_i B^n_i(t)
|
||
\textit{，其中}\
|
||
B^n_i(t)
|
||
=
|
||
\mathrm{C}_n^i \cdot (1-t)^{n-i} \cdot t^{i}
|
||
\]
|
||
|
||
然后用一个朴素（其实极其有用）的变形技巧：既然`t`值总在0到1之间（含端点），且`1-t`加`t`恒等于1，那么任何数都可表示为`t`与`1-t`的和：
|
||
|
||
\[
|
||
x = 1 x = \left ( (1-t) + t \right ) x = (1-t) x + t x = x (1-t) + x t
|
||
\]
|
||
|
||
于是用这一看似平凡的性质可将贝塞尔函数拆分为`1-t`和`t`两部分之和：
|
||
|
||
\[
|
||
\begin{aligned}
|
||
\textit{Bézier}(n,t) &= (1-t) B(n,t) + t B(n,t) \\
|
||
&= \sum_{i=0}^{n} w_i (1 - t) B^n_i(t) + \sum_{i=0}^{n} w_i t B^n_i(t)
|
||
\end{aligned}
|
||
\]
|
||
|
||
目前一切顺利。现在为了理解为什么这么做，将`1-t`和`t`两部分具体写出并观察结果。首先是`1-t`：
|
||
|
||
\[
|
||
\begin{aligned}
|
||
(1 - t) B^n_i(t) &= (1-t) \frac{n!}{(n-i)!i!} (1-t)^{n-i} t^i \\
|
||
&= \frac{n+1-i}{n+1} \frac{(n+1)!}{(n+1-i)!i!} (1-t)^{n+1-i} t^i \\
|
||
&= \frac{k-i}{k} \frac{k!}{(k-i)!i!} (1-t)^{k-i} t^i\text{，其中}\ k = n + 1\\
|
||
&= \frac{k-i}{k} B^k_i(t)
|
||
\end{aligned}
|
||
\]
|
||
|
||
用这一看似朴素的技巧瞬间就将n次贝塞尔函数的一个部分用n+1次贝塞尔函数表示出来了，这非常像曲线升次！当然`t`的部分也要表示出来，但这不是问题：
|
||
|
||
\[
|
||
\begin{aligned}
|
||
t B^n_i(t) &= t \frac{n!}{(n-i)!i!} (1-t)^{n-i} t^i \\
|
||
&= \frac{i+1}{n+1} \frac{(n+1)!}{((n+1)-(i+1))!(i+1)!} (1-t)^{(n+1)-(i+1)} t^{i+1} \\
|
||
&= \frac{i+1}{k} \frac{k!}{(k-(i+1))!(i+1)!} (1-t)^{k-(i+1)} t^{i+1}\text{，其中}\ k = n + 1 \\
|
||
&= \frac{i+1}{k} B^k_{i+1}(t)
|
||
\end{aligned}
|
||
\]
|
||
|
||
将`n`次的表达式变为`n+1`次的之后再将其重新合并。虽然`n`次函数是从0到`n`求和，`n+1`次函数是从0到`n+1`求和，但补上“贡献为零”的项即可。下一章“导数”会论述为什么“没有对应的二项式系数的更高次项”和“低于零次的项”都“贡献为零”，因此需要什么形式的项就可以加上什么项。将这些项包含在和式中没有影响，而所得函数与低次曲线依然相等：
|
||
|
||
\[
|
||
\begin{aligned}
|
||
Bézier(n,t) &= \sum_{i=0}^{n+1} w_i (1 - t) B^n_i(t) + \sum_{i=0}^{n+1} w_i t B^n_i(t) \\
|
||
&= \sum_{i=0}^{n+1} w_i \frac{k-i}{k} B^k_i(t) + \sum_{i=0}^{n+1} w_i \frac{i+1}{k} B^k_{i+1}(t)\textit{，其中}\ k = n + 1 \\
|
||
&= \sum_{i=0}^{n+1} w_i \frac{k-i}{k} B^k_i(t) + \sum_{i=0}^{n+1} p_{i-1} \frac{i}{k} B^k_i(t) \\
|
||
&= \sum_{i=0}^{n+1} \left ( w_i \frac{k-i}{k} + p_{i-1} \frac{i}{k} \right ) B^k_i(t) \\
|
||
&= \sum_{i=0}^{n+1} \left ( w_i (1-s) + p_{i-1} s \right ) B^k_i(t)\textit{，其中}\ s = \frac{i}{k}
|
||
\end{aligned}
|
||
\]
|
||
|
||
接下来从变形转到线性代数（矩阵）——现在Bézier(n,t)和Bézier(n+1,t)之间的关系可用非常简单的矩阵乘法表示：
|
||
|
||
\[
|
||
M B_n = B_k
|
||
\]
|
||
|
||
其中矩阵**M**为`(n+1)×n`阶的矩阵，其形如：
|
||
|
||
\[
|
||
M =
|
||
\left [
|
||
\begin{matrix}
|
||
1 & 0 & . & . & . & . & . & . \\
|
||
\frac{1}{k} & \frac{k-1}{k} & 0 & . & . & . & 0 & . \\
|
||
0 & \frac{2}{k} & \frac{k-2}{k} & 0 & . & . & . & . \\
|
||
. & 0 & \frac{3}{k} & \frac{k-3}{k} & 0 & . & . & . \\
|
||
. & . & 0 & ... & ... & 0 & . & . \\
|
||
. & . & . & 0 & ... & ... & 0 & . \\
|
||
. & . & . & . & 0 & \frac{n-1}{k} & \frac{k-n+1}{k} & 0 \\
|
||
. & 0 & . & . & . & 0 & \frac{n}{k} & \frac{k-n}{k} \\
|
||
. & . & . & . & . & . & 0 & 1
|
||
\end{matrix}
|
||
\right ]
|
||
\]
|
||
|
||
这虽然看似庞杂，但真的只是几乎全为零的矩阵，而且对角线上为很简单的分数，其左侧为更简单的分数。这意味着将一列坐标乘以这一矩阵，再将所得变形之后的坐标代入高一次的函数即可得到与原曲线一模一样的曲线。
|
||
|
||
还不错！
|
||
|
||
同样有意思的一点是，在建立这一矩阵操作之后即可利用非常强大又极其简单的方法求出“最优拟合”倒转操作——即[法方程组](https://mathworld.wolfram.com/NormalEquation.html)，这种方法将一组数与另一组数的平方差之和最小化。具体而言，对于超定方程组**A x = b**，利用法方程组可以求出使方程两侧之差长度最小的`x`。既然现在面临的问题即为如此，那么：
|
||
|
||
\[
|
||
\begin{aligned}
|
||
M B_n &= B_k \\
|
||
(M^T M) B_n &= M^T B_k\\
|
||
(M^T M)^{-1} (M^T M) B_n &= (M^T M)^{-1} M^T B_k \\
|
||
I B_n &= (M^T M)^{-1} M^T B_k \\
|
||
B_n &= (M^T M)^{-1} M^T B_k
|
||
\end{aligned}
|
||
\]
|
||
|
||
其中的步骤为：
|
||
|
||
1. 既然有一个具有法方程组可以处理的形式的方程组，那么
|
||
2. 使用法方程组！
|
||
3. 然后因为左侧只需保留B<sub>n</sub>，所以在两侧左乘矩阵使左侧的很多东西化为“因数1”（在矩阵语言中即为[单位矩阵](https://en.wikipedia.org/wiki/Identity_matrix)）。
|
||
4. 具体而言，左乘左侧已有项的逆可以将这个庞大的矩阵约简为单位矩阵**I**。于是将这一大堆替换为**I**，然后
|
||
5. 因为矩阵与单位矩阵相乘不会发生变化（就像在四则运算中数与1相乘不会发生变化），所以略去单位矩阵。
|
||
|
||
此即用`n`次曲线逼近`n+1`次曲线的表达式。这虽然不是精确拟合，但却是非常好的近似。下图对一条（半）随机的曲线实现了这些升次和降次的规则，图上的控制点可以移动，点击按钮可以升高或降低曲线的次数。
|
||
|
||
<graphics-element title="可变次数贝塞尔曲线" src="./reorder.js">
|
||
<button class="raise">升次</button>
|
||
<button class="lower">降次</button>
|
||
</graphics-element>
|