Catmull-Rom Spline
Catmull-Rom样条线是一种由四个控制点P0,P1,P2,P3定义的插值样条曲线(通过其控制点的曲线),曲线只绘制从P1到P2的部分。相比bezier曲线的优点是可以通过控制点,更加直观。
one segment of Catmull-Rom spline
如果我们想要绘制一条通过k个点的曲线,需要k+2个控制点,因为曲线绘制不会通过第一个和最后一个点,这两个额外的点可以自己任意选择,但它们会影响曲线形状。对于每一个在Pn到Pn+1点之间的曲线段,都由点Pn-1,Pn,Pn+1,Pn+2四个点计算得(1≤ n ≤k-1 )。当这些线段组合在一起时,就形成了一条连续的曲线,该曲线通过P1到Pk之间的所有点。
A smooth path
定义
假设 $P_i= \begin{bmatrix}x_i & y_i\end{bmatrix}^T$代表二维中的一个点,对于一段由 $P_0,P_1,P_2,P_3$和节点$t_0,t_1,t_2,t_3$定义的曲线段$C$,Catmull–Rom可以表示为:
\[q(t)=\frac {t_2-t}{t_2-t_1} B_1+\frac {t-t_1}{t_2-t_1} B_2\]其中
\[B_1=\frac {t_2-t}{t_2-t_0} A_1+\frac {t-t_0}{t_2-t_0} A_2\] \[B_2=\frac {t_3-t}{t_3-t_1} A_2+\frac {t-t_1}{t_3-t_1} A_3\] \[A_1=\frac {t_1-t}{t_1-t_0} p_0+\frac {t-t_0}{t_1-t_0} p_1\] \[A_2=\frac {t_2-t}{t_2-t_1} p_1+\frac {t-t_1}{t_2-t_1} p_2\] \[A_3=\frac {t_3-t}{t_3-t_2} p_2+\frac {t-t_2}{t_3-t_2} p_3\]其中
$t_i=t_{i-1}+\begin{Vmatrix}p_i-p_{i-1}\end{Vmatrix}^{\alpha}$ 以及 $t_0=0,i=1,2,3, and \ \alpha \in [0,1]$
解释
接下来解释这些定义以及公式的含义:
首先t代表去插值这条曲线的自变量,t0,t1,t2,t3分别为t位于p0,p1,p2,p3点时的数值。A1,A2,A3分别为点p0到p1,p1到p2,p2到p3的一维插值函数,即例如A1相当于lerp(p0,p1,(t-t0)/(t1-t0))。B1,B2为A1到A2,A2到A3的插值函数,例如B1相当于lerp(A1,A2,(t-t0)/(t2-t0)),最终曲线段C为B1到B2的插值结果,就是lerp(B1,B2,(t-t1)/(t2-t1)),即最后C会是三次曲线函数。
假设t1=1,t2=2,t3=3,下图中橙色虚线为A1,A2,A3,蓝色线为B1,绿色线为B2,黑色线为C。
$t_i=t_{i-1}+\begin{Vmatrix}p_i-p_{i-1}\end{Vmatrix}^{\alpha}$中 $\alpha$是控制样条线形状的参数,当 $\alpha=0$时t1=1,t2=2,t3=3,正如上图所示,此时得到的曲线是标准的uniform Catmull-Rom样条曲线,当$\alpha=1$,结果被称为chordal atmull-Rom spline,当$\alpha=0.5$,结果为centripetal Catmull–Rom spline。
下图是三种样条曲线节点参数的变化尺度,可以看到uniform是均匀变化的,每次加1。
下图是当 $\alpha$取0-1间不同值时样条线的变化。
可以看到当$\alpha$取0时曲线会产生自相交,而当$\alpha$取1时曲线会偏离直线路径较远,因此实际使用中常选用Centripetal cat-mull样条线。
这里提供了交互式示例演示了 Catmull-Rom 样条和这些参数。
计算应用
用上面的方程计算曲线可能相当不方便,通常情况下,使用预计算好的常数比较好,那么p1和p2之间的曲线段就可以用下面的方程表示,
\[p(t)=at^3+bt^2+ct+d,\]$t \in [0,1],p(0)=p_1,p(1)=p_2$.另一种定义方式$p(t)=q(t_1+t(t_2-t_1)).$
可得,
$p’(t)=3at^2+2bt+c=(t_2-t_1)q’(t_1+t(t_2-t_1)).$
现在我们有,
$p(0)=q(t_1)=p_1=d,$
$p(1)=q(t_2)=p_2=a+b+c+d,$
$p’(0)=(t_2-t_1)q’(t_1)=m_1=c,$
$p’(1)=(t_2-t_1)q’(t_2)=m_2=3a+2b+c,$
其中m1,m2代表p1,p2处的切线,通过以上四个公式求解a,b,c,d得,
$a=2p_1-2p_2+m_1+m_2,$
b=$-3p_1+3p_2-2m_1-m_2,$
$c=m_1,$
$d=p_1$
至此,我们只需要确定m1和m2,那就需要求q的导数,得到,
$q’(t_1)=\frac {p_1-p_0}{t_1-t_0}-\frac {p_2-p_0}{t_2-t_0}+\frac {p_2-p_1}{t_2-t_1},$
$q’(t_2)=\frac {p_2-p_1}{t_2-t_1}-\frac {p_3-p_1}{t_3-t_1}+\frac {p_3-p_2}{t_3-t_2},$
所以m1,m2为,
$m_1=(t_2-t_1)(\frac {p_1-p_0}{t_1-t_0}-\frac {p_2-p_0}{t_2-t_0}+\frac {p_2-p_1}{t_2-t_1})$
$m_2=(t_2-t_1)(\frac {p_2-p_1}{t_2-t_1}-\frac {p_3-p_1}{t_3-t_1}+\frac {p_3-p_2}{t_3-t_2})$
至此我们得到了三次曲线中的四个参数a,b,c,d,可以快速地插值曲线。
参考文章:
Smooth Paths Using Catmull-Rom Splines
Centripetal Catmull–Rom spline