贝塞尔曲线的绘制

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

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

贝塞尔曲线的几何作图法

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

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

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

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

相同的比例指：
AEAB=BFBC=CGCD=EJEF=FKFG=JMJK=t\frac{AE}{AB}=\frac{BF}{BC}=\frac{CG}{CD}=\frac{EJ}{EF}=\frac{FK}{FG}=\frac{JM}{JK}=t ABAE​=BCBF​=CDCG​=EFEJ​=FGFK​=JKJM​=t

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

设 JJJ 点的运动方程为 f1(t),t∈[0,1]f_1(t), t\in[0, 1]f1​(t),t∈[0,1]，KKK 点的运动方程为 f2(t),t∈[0,1]f_2(t), t\in[0, 1]f2​(t),t∈[0,1]，则 MMM 点的运动方程为 f3(t)=(1−t)⋅f1(t)+t⋅f2(t)f_3(t)=(1-t)\cdot f_1(t)+t\cdot f_2(t)f3​(t)=(1−t)⋅f1​(t)+t⋅f2​(t) 。这种合并会使得曲线 f3f_3f3​ 的前半段比较接近 f1f_1f1​，后半段比较接近 f2f_2f2​。下图中的绿线和蓝线分别是 f1f_1f1​ 和 f2f_2f2​，红线是 f3f_3f3​。

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

贝塞尔曲线的分裂法绘制

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

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

假设当前 t=12t=\frac 1 2t=21​，那么我们可以算出 E,J,ME, J, ME,J,M 三点各自的坐标：
E=(1−t)⋅A+t⋅B=A+B2F=(1−t)⋅B+t⋅C=B+C2G=(1−t)⋅C+t⋅D=C+D2J=(1−t)⋅E+t⋅F=A+2B+C4K=(1−t)⋅F+t⋅G=B+2C+D4M=A+3B+3C+D8\begin{aligned} E&=(1-t)\cdot A+t\cdot B=\frac{A+B}{2}\\ F&=(1-t)\cdot B+t\cdot C=\frac{B+C}{2}\\ G&=(1-t)\cdot C+t\cdot D=\frac{C+D}{2}\\ J&=(1-t)\cdot E+t\cdot F=\frac{A+2B+C}{4}\\ K&=(1-t)\cdot F+t\cdot G=\frac{B+2C+D}{4}\\ M&=\frac{A+3B+3C+D}{8} \end{aligned} 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​​

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

我们不妨把上式整理成只含有 ABCDABCDABCD 四个点的形式：
f(t)=(1−t)3⋅A+3(1−t)2t⋅A+B2+3(1−t)t2⋅A+2B+C4+t3⋅A+3B+3C+D8,t∈[0,1]=(ABCD)×[1121418012243800143800018]×((1−t)33(1−t)2t3(1−t)t2t3),t∈[0,1]\begin{aligned} f(t)&=(1-t)^3\cdot A+3(1-t)^2t\cdot \frac{A+B}{2}+3(1-t)t^2\cdot \frac{A+2B+C}{4}+t^3 \cdot \frac{A+3B+3C+D}{8}, t\in[0, 1]\\ &=\left(\begin{matrix}A&B&C&D \end{matrix}\right)\times\left[\begin{matrix}1&\frac 1 2 & \frac 1 4 & \frac 1 8\\ 0&\frac 1 2&\frac 2 4& \frac 3 8\\ 0&0&\frac 1 4 & \frac 3 8\\ 0&0&0&\frac 1 8 \end{matrix}\right]\times\left(\begin{matrix}(1-t)^3\\3(1-t)^2t\\3(1-t)t^2\\t^3\end{matrix}\right),t\in[0, 1] \end{aligned} 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)=(ABCD)×((1−t2)33(1−t2)2t23(1−t2)(t2)2(t2)3)=f3(t2),t∈[0,1]f(t)=\left(\begin{matrix}A&B&C&D \end{matrix}\right)\times \left(\begin{matrix}(1-\frac t 2)^3\\3(1-\frac t 2)^2 \frac t 2\\3(1- \frac t 2)\left(\frac t 2\right)^2\\(\frac t 2)^3\end{matrix}\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]

这也就说明了，当 ttt 从 000 取到 111 时，f(t)f(t)f(t) 恰好取遍曲线 f3f_3f3​ 的前一半。因此以 AEJMAEJMAEJM 为控制多边形的贝塞尔曲线恰好为以 ABCDABCDABCD 为控制多边形的贝塞尔曲线的前一半；同理，以 MKGDMKGDMKGD 为控制多边形的贝塞尔曲线恰好为以 ABCDABCDABCD 为控制多边形的贝塞尔曲线的后一半。

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