Mar 21, 2014 programming generative art

三次样条曲线

阅读 Cocos2d-x 源码的时候，有几个有趣的关于路径运动的 Test Case 之前一直没有时间去研究：ActionCardinalSpline 和 ActionCatmullRom。由于对 Bezier 比较熟悉，所以 ActionBezier 就略过了。于是特地看了一下前两个陌生的名字。

之前在博客里记录过几个曲线，一个是贝塞尔曲线，一个是Chaikin曲线以及利萨茹曲线。它们各有特点：

贝塞尔曲线通过两个端点和多个控制点来构造。插值容易，但端点处的斜率不容易控制，控制点牵一发而动全身。
Chaikin曲线通过直线边来构造。用迭代法构造，几乎不可能用于插值。
利萨茹曲线以不同相位和振幅的正弦函数来构造。位置由参数可直接获得，可以用来做一些特效。想不到其它功能了。

在游戏中，我们常常给定一些坐标点，让角色逐一通过。角色在运动的时候，沿着这些点平滑地移动。所以我们需要有一些方法能求出通过给点坐标集合的曲线。

为了弄明白 Cocos2d-x 提供的那两个曲线，我特地查找了一些资料，以下是一些笔记。

¶多项式曲线

一个常量，可由一个点唯一确定
一条直线，可由两个点唯一确定
一条抛物线，可由三个点唯一确定
一条三次曲线，可由四个点唯一确定，并且它拥有一个拐点。

三次曲线是多项式曲线中拥有拐点的最高项次数最小的曲线。拐点使它拥有非常有意义的作用，可以用它将多个点平滑地连接起来。

一条三次曲线，需要由四个系数的多项式来描述：

$$ a + bx + cx^2 + dx^3 = y $$

由已知的四个点，可以构造四个方程，解这四个方程即可求出四个系数。可由矩阵的逆运算得到：

$$ Ma = y \Rightarrow a = M^{-1}y $$

矩阵运算使得用计算机求解非常容易。

¶分段曲线

复杂的曲线，可以由多个三次曲线连续起来成形。（得益于拐点）。于是我们可以将曲线以每两点进行分段，分别求出两点间的三次曲线。

为了使这些三次曲线平滑地相连，我们约束连接点处必须是连续的，并且一次导数和二次导数都是连续的。于是通过两个点和两个约束，我们就有了四个方程，可解出该多项式的四个系数，同时保证它与相邻的三次曲线是连续的。（由于起始端点和结束端点没有导数，所以我们需要人工指定两个斜率）

将多段曲线同时置入一个矩阵，即可一次性求出全部系数。

¶曲线参数化

上面的方法得到的都是基于x轴的曲线，这并不好用。我们希望每段曲线都通过参数t描述：

$$ f_i(t_i) = a_i + b_i t_i + c_i t_i^2 + d_i t_i^3 (0 \leqslant t \leqslant 1) $$

详细的推导过程可见文末参考资料。

¶平面曲线

将参数化后的曲线分别应用的两个坐标轴上，我们可以在2维平面上构造任意曲线！使其头尾相连，可形成环。

¶插值曲线

虽然多项式曲线已经这么牛逼，但是它使用一个矩阵来计算整个曲线，所以当用户调整其中的一个点的时候，会影响整个曲线的形状。这对造形来说是一个灾难，我们希望能够局部修改曲线。

¶Hemiter 曲线

为了实现这个需求，我们可以将多项式的两个约束改为用户指定每个分段两个端点的斜率，这样就可以将单点变化的影响缩小到局部了。多项式曲线变成了 Hemiter 曲线。

¶Catmul-Rom 曲线

Hemiter 曲线要求用户提供每个点的斜率，并不是那么方便。 Catmul-Rom 提供了一种自动设置斜率的方法：每个点的斜率由前后两个点决定。

$$ t_i = \frac{1}{2} (p_{i+1}-p_{i-1}) \ t_{i+1} = \frac{1}{2} (p_{i+2}-p_i) $$

¶Cardinal 曲线

Cardinal 曲线为 Catmul-Rom 的斜率生成提供了一个可选参数t。当t=0时，Cardinal 曲线即为 Catmul-Rom 曲线。当 t>0 时，得到绷紧后的 Catmul-Rom 曲线。反之 t<0 时，得到松跨后的 Catmul-Rom 曲线。

$$ t_i = \frac{1}{2} (1-t)(p_{i+1}-p_{i-1}) \ t_{i+1} = \frac{1}{2} (1-t)(p_{i+2}-p_i) $$

¶参考资料

Spline Curves: http://www.ae.metu.edu.tr/~ae464/splines.pdf