计算机图形学中的曲线问题——贝塞尔曲线的绘制

贝塞尔曲线的绘制

由于 CSDN 的博客修改字数的限制，我们不得不将这一部分放到一个新的博客中。原文详见：

GGN_2015
计算机图形学中的曲线问题

贝塞尔曲线的几何作图法

在上面介绍儿时的回忆中，我们介绍了对于抛物线绘制的一种方法。如下图所示，我们要先选定三个控制点 $A,B,C$，连接 $AB$、$BC$。我们在 $AB$ 上取一点 $D$，在 $BC$ 上取一点 $E$ 使得：
$$\frac{AD}{AB}=\frac{BE}{BC}=t$$

其中 $t$ 是一个定义在 $[0,1]$ 区间上的数。之后我们再连接 $DE$ 并在 $DE$ 上取一点 $F$ 使得：
$$\frac{DF}{DE}=t$$

当 $t$ 在 $[0,1]$ 之间变化时，$F$ 点的轨迹就是一条抛物线（换言之，二次贝塞尔曲线）。当 $t$ 变化时，点 $F$ 的运动效果如下：

对于三次贝塞尔曲线我们也可以使用同样的方法进行绘制，只不过这次控制点的个数要增加到四个。先取四个控制点 $A,B,C,D$，分别连接 $AB$，$BC$，$CD$，使用同样的比例 $t$ 在这三个线段上各取一点，记为 $E,F,G$。连接 $EF$ 和 $FG$，再使用相同的比例 $t$ 在这两条线段上分别取一点，记为 $J,K$。最后，连接 $JK$，在线段 $JK$ 上按照比例 $t$ 取一点 $M$。在 $t$ 变化的过程中，$M$ 点的运动轨迹就是一条三次贝塞尔曲线。

相同的比例指：
$$\frac{AE}{AB}=\frac{BF}{BC}=\frac{CG}{CD}=\frac{EJ}{EF}=\frac{FK}{FG}=\frac{JM}{JK}=t$$

这个关系虽然看起来比较繁琐，但实际上并不复杂。可以看到在这个三次贝塞尔曲线的几何作图法表述中，点 $J$ 和点 $K$ 各自运动的轨迹就是一条二次的贝塞尔曲线，而点 $M$ 的运动轨迹是一条三次贝塞尔曲线，因此，我们可以说三次贝塞尔曲线是对两条二次贝塞尔曲线的“合并”。运动效果如下：

设 $J$ 点的运动方程为 $f_1(t),t\in [0,1]$，$K$ 点的运动方程为 $f_2(t),t\in [0,1]$，则 $M$ 点的运动方程为 $f_3(t)=(1-t)\cdot f_1(t)+t\cdot f_2(t)$ 。这种合并会使得曲线 $f_3$ 的前半段比较接近 $f_1$，后半段比较接近 $f_2$。下图中的绿线和蓝线分别是 $f_1$ 和 $f_2$，红线是 $f_3$。

为了表述方便，我们称：折线 $ABCD$ 是红色曲线 $f_3$ 的控制多边形。

贝塞尔曲线的分裂法绘制

根据文章正文中的介绍我们已经得知，如果 $ABCD$ 是曲线 $f_3$ 的控制多边形，那么有：
$$f_3(t)=(1-t{)}^3\cdot A+3(1-t{)}^{2}t\cdot B+3(1-t)t^2\cdot C+t^3\cdot D,t\in [0,1]$$

在 $t$ 变化的过程中，我们可以观察到，当 $t\to 0$ 时，$AEJM$ 四点几乎接近左半段曲线，当 $t\to 1$ 时，$MKGD$ 几乎接近右半段曲线，而这种性质中似乎暗含着一些不可告人的秘密。正如 $ABCD$ 是整段曲线 $f_3$ 的控制多边形，我们有理由猜测： $AEJM$ 是否是 $f_3$ 在 $M$ 左侧部分的曲线的控制多边形而 $MKGD$ 是 $f_3$ 在 $M$ 右侧部分的控制多边形呢？

假设当前 $t=\frac{1}{2}$，那么我们可以算出 $E,J,M$ 三点各自的坐标：
E = ( 1 − t ) ⋅ A + t ⋅ B = A + B 2 F = ( 1 − t ) ⋅ B + t ⋅ C = B + C 2 G = ( 1 − t ) ⋅ C + t ⋅ D = C + D 2 J = ( 1 − t ) ⋅ E + t ⋅ F = A + 2 B + C 4 K = ( 1 − t ) ⋅ F + t ⋅ G = B + 2 C + D 4 M = A + 3 B + 3 C + D 8

EFGJKM​=(1−t)⋅A+t⋅B=2A+B​=(1−t)⋅B+t⋅C=2B+C​=(1−t)⋅C+t⋅D=2C+D​=(1−t)⋅E+t⋅F=4A+2B+C​=(1−t)⋅F+t⋅G=4B+2C+D​=8A+3B+3C+D​​

我们定义 $AEJM$ 四个点确定的三次贝塞尔曲线为 $f(t)$，则有：
$$f(t)=(1-t{)}^3\cdot A+3(1-t{)}^{2}t\cdot E+3(1-t)t^2\cdot J+t^3\cdot M,t\in [0,1]$$

我们不妨把上式整理成只含有 $ABCD$ 四个点的形式：
f ( t ) = ( 1 − t ) 3 ⋅ A + 3 ( 1 − t ) 2 t ⋅ A + B 2 + 3 ( 1 − t ) t 2 ⋅ A + 2 B + C 4 + t 3 ⋅ A + 3 B + 3 C + D 8 , t ∈ [ 0 , 1 ] = ( A B C D ) × [ 1 1 2 1 4 1 8 0 1 2 2 4 3 8 0 0 1 4 3 8 0 0 0 1 8 ] × ( ( 1 − t ) 3 3 ( 1 − t ) 2 t 3 ( 1 − t ) t 2 t 3 ) , t ∈ [ 0 , 1 ]

f(t)​=(1−t)3⋅A+3(1−t)2t⋅2A+B​+3(1−t)t2⋅4A+2B+C​+t3⋅8A+3B+3C+D​,t∈[0,1]=(A​B​C​D​)×⎣⎢⎢⎡​1000​21​21​00​41​42​41​0​81​83​83​81​​⎦⎥⎥⎤​×⎝⎜⎜⎛​(1−t)33(1−t)2t3(1−t)t2t3​⎠⎟⎟⎞​,t∈[0,1]​

接下来这一步需要比较复杂的整理，具体的步骤我们就不做了，简单而言，我们要将上面的三个矩阵中的后两个乘起来：
f ( t ) = ( A B C D ) × ( ( 1 − t 2 ) 3 3 ( 1 − t 2 ) 2 t 2 3 ( 1 − t 2 ) ( t 2 ) 2 ( t 2 ) 3 ) = f 3 ( t 2 ) , t ∈ [ 0 , 1 ] f(t)=\left(

\right)\times \left(\right)=f_3(\frac t 2), t\in [0, 1] f(t)=(A​B​C​D​)×⎝⎜⎜⎛​(1−2t​)33(1−2t​)22t​3(1−2t​)(2t​)2(2t​)3​⎠⎟⎟⎞​=f3​(2t​),t∈[0,1]

这也就说明了，当 $t$ 从 $0$ 取到 $1$ 时，$f(t)$ 恰好取遍曲线 $f_3$ 的前一半。因此以 $AEJM$ 为控制多边形的贝塞尔曲线恰好为以 $ABCD$ 为控制多边形的贝塞尔曲线的前一半；同理，以 $MKGD$ 为控制多边形的贝塞尔曲线恰好为以 $ABCD$ 为控制多边形的贝塞尔曲线的后一半。

按照这一原理，我们可以设计一个递归算法来绘制一条贝塞尔曲线：当我们要绘制以 $ABCD$ 为控制多边形的贝塞尔曲线时，我们先要计算 $B$ 点和 $C$ 点到 $AD$ 的距离，如果 $B$ 点和 $C$ 点到 $AD$ 的距离都很近，换言之，$ABCD$ 近似共线，我们就不再递归直接将线段 $AD$ 视为对贝塞尔曲线的近似。如果 $B$ 或 $C$ 中有一者离线段 $AD$ 很远，将这个贝塞尔曲线按照上述方法分成 $AEJM$ 和 $MKGD$ 两部分，并分别递归地进行绘制。