最详细的Catmull-Rom Spline 推导与应用

附赠最强自动驾驶学习资料：直达链接

前言

我们往Spline 的方向深入，探究 Catmull-Rom 的曲线，想必研究的越深入，来到这里的人也越少。实际上，作为一个使用引擎的编程者，并不需要推导的那么深入，引擎自然有现成的实现。不过，既然已经钻研到了这里，“予之力尚足以入，火尚足以明也”如果不在此研究明白，恐怕以后也很难有机会再回到这里来研究更多吧。

当然，我们到了这里，会发现，这部分的中文的教材充斥着抽象的概念，晦涩难懂；这部分的博客往往伴有“无脑转译”和“不求甚解” 的存在。甚至能在一些他人的博文中发现隐蔽的错误，会困扰你对这部分知识的理解，这也是我本人亲自踩过的坑。所以，如果有能力，应阅读更多第一手的英文资料。

在参照各个讲义和教程（见最后的附录）后，我小心翼翼的推导每一个公式的每一个的步骤，只望能给每个认真想要知道原理与过程的人一个更能接近全面的答复。

加V好友：AutoDriverZone，获取史上最强的自动驾驶学习资料

1、Catmull-Rom Spline 简介

2、公式推导

这是个一般公式，我们是从二维中推导出来的，我们也可以运用在三维或者更高维度中，只要带入高维的坐标点即可。

3、理解 Spline

感性上，如何去理解它呢？我们一路是从最简单的贝塞尔曲线开始的，从最简单的插值开始，找到两个点的线上的任意一点，是这两个点进行线性插值来得到的，找到一个二阶贝塞尔曲线，曲线是这三个点的两条线的插值点连线线性插值出来…直到现在在叙述的 Catmull-Rom Spline，其实我们也可以将其理解为某种非线性的插值。

如图所示，这四个函数就代表了四个点在 0-1之间的插值比例，或者我们可以理解为，这是一个三次式插值，我们通过在 0⩽t⩽1 之前带入各个点的 x值，然后通过这四个三次项的式子来整理成一个关于 t 的三次多项式，这就是我们要求的Spline了。

它和Bézie曲线的关系呢？Catmull-Rom曲线和Bézier曲线之间的主要区别在于“点的含义”：三次Bézier曲线由一个起点、一个暗示起点切线的控制点、一个隐含终点切线的控制点将和一个终点定义，再加上一个特征矩阵，我们可以将该矩阵乘以该点向量来获得曲线坐标。

4、带有向心化参数的Catmull-Rom Spline（进阶）

以上，我们是基于一般情况来选择的控制点，并没有特别规定控制点的距离。Catmull-Rom曲线的行为在很大程度上取决于控制点的选择。但以上的计算与推论是一般性的结论，并没有涉及到控制点的选择，因为它可能在某些控制点离得比较近的情况下，产生尖端或者交点，这些都是我们想要绘制平滑曲线的时候不想要的内容：

图片来源：8. [On the Parameterization of Catmull-Rom Curves](http://www.cemyuksel.com/research/catmullrom_param/catmullrom.pdf )——论文：Cem Yuksel、Scott Schaefer、John Keyser

因此，我们还需要额外的关注控制点的距离来控制这个曲线的走势。在参考文章[8] 中，阐述了从均匀参数化到弦参数化的规律，并表明具有向心参数化的曲线包含该族中其他曲线所不具备的特性——即，它不会产生尖端和交点的现象。

图片来源：8. [On the Parameterization of Catmull-Rom Curves](http://www.cemyuksel.com/research/catmullrom_param/catmullrom.pdf )——论文：Cem Yuksel、Scott Schaefer、John Keyser

（示例头发网格，分别为单个发束和最终发束生成的控制多边形。头发曲线是使用带有向心参数化的Catmull-Rom曲线生成的。）

5、参数化的 Catmull-Rom Spline 的定义

如下图，我们可以看到，大致的，参数化后，这几个控制点的关系：

文献[10]除了从代数的角度，也从控制多边形的角度论证了向心化参数的 Catmull-Rom 曲线是一个不会相交的曲线。

5、参数化的 Catmull-Rom Spline 的实践

好了，我的朋友们，既然都看到这里了，何不尝试自己动手写一写呢？你已经知晓以上的原理和公式，请用代码写出能够返回一条 Catmull-Rom 曲线的函数吧~~

不开玩笑的讲，这个曲线的应用实际上很广泛，不单单是我们的二维画图。包括3D的轨道、IK Rigid、多边形算法、地图绘制、后处理…等等中都有所应用。

其实，写程序只是这里最简单的事情，稍微难一些的，还是数学分析中的内容。

① 基础款

（截图来自：[(转)插值技术之Catmull-Rom Spline Interpolating](https://www.cnblogs.com/bluebean/articles/12082693.html)）

（但正如没有引入向心参数化的那种情况一样，这对控制点的选择是任意的，可能会有尖角和交叉的情况。）

③ 进阶款

进阶的，参考文章15. [Smooth Paths Using Catmull-Rom Splines](https://qroph.github.io/2018/07/30/smooth-paths-using-catmull-rom-splines.html) ——Mika’s Coding Bits 中，使用了数学分析的方式，对金字塔算法的插值方法求导表示，式子实在太长，本人已无力推导出相同的结果。我们尝试直接采用它的结论，在 UE 中进行代码尝试：

void UTestBlueprintFunctionLibrary::DrawCatmullRom3(UPARAM(ref)FPaintContext& Context, const TArray<FVector2D> ControlPoints, float alpha, float tension, TArray<FVector2D>& OutPoints)
{
	TArray<FVector2D> outputpoints;
	for (float t = 0.f; t <= 1.f; t += 0.05) {
		float t0 = 0.0f;
		float t1 = t0 + FMath::Pow(FVector2D::DistSquared(ControlPoints[0], ControlPoints[1]), alpha * .5f);
		float t2 = t1 + FMath::Pow(FVector2D::DistSquared(ControlPoints[1], ControlPoints[2]), alpha * .5f);
		float t3 = t2 + FMath::Pow(FVector2D::DistSquared(ControlPoints[2], ControlPoints[3]), alpha * .5f);

		FVector2D m1 = (1.0f - tension) * (t2 - t1) *
			((ControlPoints[1] - ControlPoints[0]) / (t1 - t0) - (ControlPoints[2] - ControlPoints[0]) / (t2 - t0) + (ControlPoints[2] - ControlPoints[1]) / (t2 - t1));
		FVector2D m2 = (1.0f - tension) * (t2 - t1) *
			((ControlPoints[2] - ControlPoints[1]) / (t2 - t1) - (ControlPoints[3] - ControlPoints[1]) / (t3 - t1) + (ControlPoints[3] - ControlPoints[2]) / (t3 - t2));

		FVector2D param1 = 2.f * (ControlPoints[1] - ControlPoints[2]) + m1 + m2;
		FVector2D param2 = -3.f * (ControlPoints[1] - ControlPoints[2]) - m1 - m1 - m2;
		FVector2D param3 = m1;
		FVector2D param4 = ControlPoints[1];
		FVector2D C = param1 * t * t * t + param2 * t * t + param3 * t + param4;
		outputpoints.Add(C);
	}
	UWidgetBlueprintLibrary::DrawLines(Context, outputpoints, FLinearColor::White, true, 1.f);
}

参考文章：

[计算机表示物体形状的基本方法、贝塞尔曲线、B样条曲线、NURBS 曲线、Catmull-Rom 样条曲线](zhiwei：计算机表示物体形状的基本方法、贝塞尔曲线、B样条曲线、NURBS 曲线、Catmull-Rom 样条曲线)——知乎：zhiwei
[初识贝塞尔曲线](https://blog.csdn.net/keneyr/article/details/88427842)——CSDN：keneyr
[简单粗暴：B-样条曲线入门](我好饱啊：简单粗暴：B-样条曲线入门)——知乎：我好饱啊
[中国大学MOOC](https://www.bilibili.com/video/BV1Dt411f7Qj?p=1&vd_source=8c5d108bfddb65af9ec4c44bd9cfc29f)——B站：——中国农业大学赵明老师
https://observablehq.com/@herbps10/b-splines ——WhyObservale：Herb Susmann（注意，它这里使用的 k 值是我们这里的k-1）
https://web.cse.ohio-state.edu/~dey.8/course/784/note5.pdf ——讲义：The Ohio State University. Department of Science and engineering. Course 784.note 5
https://web.cse.ohio-state.edu/~dey.8/course/784/note6.pdf ——讲义：The Ohio State University. Department of Science and engineering. Course 784.note 6
[On the Parameterization of Catmull-Rom Curves](http://www.cemyuksel.com/research/catmullrom_param/catmullrom.pdf )——论文：Cem Yuksel、Scott Schaefer、John Keyser
https://www.cs.cmu.edu/~fp/courses/graphics/asst5/catmullRom.pdf ——课程作业附录
Parameterization of Catmull-Rom Curves - Cem Yuksel ——论文：Cem Yuksel、Scott Schaefer、John Keyser
https://www.youtube.com/watch?v=9_aJGUTePYo ——Youtube： javidx9
https://pomax.github.io/bezierinfo/ ——《贝塞尔曲线入门》
Catmull-Rom Spline With Bezier (4 points) ——网站：Desmos
https://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline ——WIki：Centripetal Catmull–Rom spline
[Smooth Paths Using Catmull-Rom Splines](https://qroph.github.io/2018/07/30/smooth-paths-using-catmull-rom-splines.html) ——Mika’s Coding Bits
[11 10 CatmullRomCurve](https://www.youtube.com/watch?v=XBLtqGiT0p0) ——Youtube：

附赠最强自动驾驶学习资料：直达链接

标签：Rom,曲线,控制点,https,Catmull,Spline
From： https://blog.csdn.net/liuphahaha/article/details/136888157

最详细的Catmull-Rom Spline 推导与应用