Catmull Rom curve

Catmull Rom curve 是一種曲線生成的方式，可以讓路線圓滑的同時使路線經過所有控制點。

Try it out: https://acezxn.github.io/Pathtracker-online/#/path-follow-simulator

黑點和灰點為控制點，路線從第二個控制點開始，在倒數第二個控制點結束

先看四個點

以四個點生成路徑的方式為

$$x_{new}(t)=\frac{1}{2}((-t^3+ 2t^2 - t)x_1+ (3t^3 - 5t^2 + 2)x_2+ (-3t^3 + 4t^2 + t)x_3+ (t^3 - t^2)x_4)$$

$$y_{new}(t)=\frac{1}{2}((-t^3+ 2t^2 - t)y_1+ (3t^3 - 5t^2 + 2)y_2+ (-3t^3 + 4t^2 + t)y_3+ (t^3 - t^2)y_4)$$

t 為路線的進度。0 代表在一開始，1 代表在路線的結尾

合併多個控制點

我們可以把整條路線分為小線段。設 t 的最大值為控制點的數量 - 3，可以得到線段的數量。當 t 在 0 到 1 之間時，設 $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$為路線一開始的四個控制點，進行計算。當 t 在 1 到 2 之間時，設 $(x_1, y_1)$為上一步的 $(x_2, y_2)$； 設 $(x_2, y_2)$為上一步的 $(x_3, y_3)$； 設 $(x_3, y_3)$為上一步的 $(x_4, y_4)$； 設 $(x_4, y_4)$為下一個控制點，進行計算，以此類推。

Desmos

更多資訊

https://www.cs.cmu.edu/~fp/courses/graphics/asst5/catmullRom.pdf https://www.youtube.com/watch?v=9_aJGUTePYo