贝塞尔曲线学习笔记
前言
近段时间我在工作中实现了一个动画功能，其中涉及到动画元素要按一定的轨迹在屏幕上移动，运动轨迹的生成我使用了Path.cubicTo方法来实现的，这个方法其实是生成了一条有两个控制点的贝塞尔曲线。借此机会我再收集了一些资料，想系统地学习一下贝塞尔曲线相关的知识。
简介
贝塞尔曲线（Bézier curve）又被称为贝兹曲线或贝济埃曲线，是应用于二维图形应用程序的数学曲线，它的数学基础是伯恩斯坦多项式（Bernstein polynomial，since 1912），1959年法国数学家Paul de Casteljau提出了数值稳定的de Casteljau算法，开始贝塞尔曲线的图形化应用研究，而贝塞尔曲线的名称来源于一位就职于雷诺的法国工程师Pierre Bézier，他在1962年开始对贝塞尔曲线做了广泛的宣传，他使用这种只需要很少的控制点就能生成复杂平滑曲线的方法来进行汽车车体的工业设计。
贝塞尔曲线因为它控制简便却具有极强的描述能力，迅速在工业设计和计算机图形学等相关领域得到了广泛应用。比如在矢量绘图中，贝塞尔曲线用来给需要无限制地缩放的平滑曲线定模，许多绘图软件都提供了绘制贝塞尔曲线的功能。贝塞尔曲线还用于动画时间控制以实现美观逼真的缓动效果，还用于机器人转动手臂等方面的设计。
de Casteljau算法原理
在向量AB上选择一个点C，使得C分向量AB为u：1-u（即|AC|：|AB|=u）。给定点A、B的坐标以及u（u∈[0,1]）的值，点C的坐标则为C=A+(B-A)*u=（1-u）*A+u*B。
de Casteljau算法基本原理
贝塞尔曲线原理
利用de Casteljau算法可以计算贝塞尔曲线上的点C(u)，u∈[0,1]。因此，通过给定一组u的值，即可算出贝塞尔曲线上的坐标序列，从而绘制出贝塞尔曲线。
为了计算n阶贝塞尔曲线上的点C(u)，u∈[0,1]，首先将控制点连接形成一条折线00-01-02······0（n-1）-0n，利用de Casteljau算法，计算出折线中每条线段0j-0（j+1）上的一个点1j，使得点1j分该线段的比为u:1-u，然后在折线10-11-12-······-1（n-1）上递归调用该算法，以此类推。最终求得一个点n0，已证明点n0一定是曲线上的点。
de Casteljau算法的几何表达
上图中u=0.4，这从几何形状上形象地说明了de Casteljau算法的过程，可以将上述直观的几何描述表达为算术方法，如下图所示：
de Casteljau算法的算术表达图示
首先将所有的控制点排成一列，如上图最左列，每一对相邻的控制点之间画出两个箭头，分别指向右下方和右上方，在两个箭头交汇的位置记下一个新的点。比如控制点ij和i(j+1)生成新的控制点(i+1)j。指向右下方的箭头表示乘以(1-u)，指向右上方的箭头表示乘以u。
将上述过程表达为下面的算法：
Input:arrayP[0:n] ofn+1 points and real numberuin [0,1]
Output:point on curve,C(u)
Working:point arrayQ[0:n]
fori:= 0 to n do
Q[i] :=P[i]; // save input
fork:= 1 to n do
fori:= 0ton - kdo
Q[i] := (1 -u)Q[i] +uQ[i+ 1];
returnQ[0];
这个算法还可以被递归地表达，上述点列还有其他有趣的性质，详细描述请参考论文Finding a Point on a Bézier Curve: De Casteljau's Algorithm。
贝塞尔曲线展示
一阶贝塞尔曲线
一阶贝塞尔曲线动画，t∈[0,1]
给定点P0和P1，一阶贝塞尔曲线就是这两点间的一条直线段，对应公式：
一阶贝塞尔曲线的一般方程
二阶贝塞尔曲线
二阶贝塞尔曲线动画，t∈[0,1]
给定点P0、P1和P2，二阶贝塞尔曲线是由下述方程产生的轨迹
二阶贝塞尔曲线的直接方程
这个方程可以被描述为由两段独立的一阶贝塞尔曲线再按de Casteljau算法合成的，分别是由 P0 至 P1 的连续点 Q0描述一条线段，由 P1 至 P2 的连续点 Q1描述另一条线段，最后由 Q0 至 Q1 的连续点 B(t)描述了贝塞尔曲线。整理上述公式变成：
二阶贝塞尔曲线的一般方程
三阶贝塞尔曲线
三阶贝塞尔曲线动画，t∈[0,1]
二维平面或者更高维度的空间中的4个点P0、P1、P2和P3可以定义一条三阶的贝塞尔曲线，这条曲线从P0点开始向P1点方向运动，最后从来自P2点的方向运动到达P3点。一般点P1和P2不会在曲线上，它们用来控制曲线运动的方向；点P0与P1间的距离将会影响曲线在转向P2之前向P1点方向运动的远近和快慢。按照二阶贝塞尔曲线方程可以表达为一阶的形式，三阶贝塞尔曲线也可以由两个二阶贝塞尔曲线组合来线性地表达：
三阶贝塞尔曲线的线性表达式
将方程递归带入整理得到：
三阶贝塞尔曲线的一般方程
更一般地，n阶贝塞尔曲线的一般方程为：
n阶贝塞尔曲线的一般表达式
例如，n=5时，即5阶贝塞尔曲线的方程为：
5阶贝塞尔曲线的一般方程
贝塞尔曲线应用
Android SDK中提供的API
在android.graphics包中的Path类提供了几个可以绘制贝塞尔曲线的API，常用的就是lineTo、quadTo和cubicTo三个方法，分别可以绘制一、二、三阶的贝塞尔曲线，一阶没什么可说的，就是通常的画直线，传入的参数就是目标点坐标。下面分别是quadTo和cubicTo方法的接口说明：
Path类的quadTo方法说明
Path类的cubicTo方法说明
自定义贝塞尔工具
在实际项目中我自己写了一个贝塞尔估值器类，核心方法如下：
自定义贝塞尔估值器
后记
我第一次写这样长篇的技术博客，惭愧！！想以此加深自己的理解，也方便以后迅速查阅相关的资料。写博客真的是一个深入学习的好方法，让我不再流于解决问题的表面，通过查找资料可以透过直接的技术方案发现方案背后的逻辑和原理。理解了最本质的东西，其他的都是可以举一反三、触类旁通的方法变幻。加油，少年！~
Thanks To：
Finding a Point on a Bézier Curve: De Casteljau's Algorithm
