Curve Interpolation I

Curve Interpolation 將會用一個曲線函數連接節點，使得路徑變得平滑。 這個章節會介紹幾種曲線函數，例如 Explicit、Implicit 和 Parametric，並針對 Parametric Cubic Polynomial Curves 和 Cubic Interpolating Curves 進行了深入解釋。

Representation of Curves

$y = f(x) \text{ or } x = g(y)$

• Explicit
  • 用函式來表達 curve 上每個點 (x, y) 的關係
  • 有的垂直線、圓形可能無法表達

$$\begin{aligned} &f(x, y) = 0\\ \text{Line: }&ax+by+c=0\\ \text{Circle: }&x^2+y^2-r^2=0 \end{aligned}$$

• Implicit
  • 用 f(x, y) 來表示，每個 curve 上的點 (x, y) 需滿足 f(x, y) = 0
  • 需要把所有點都帶進 f(x, y) 去看是否等於 0

$$p(u) = \begin{bmatrix} x(u) & y(u) \end{bmatrix}^T$$

• Parametric
  • 用 u 來表示 curve 上的每個點 (x, y)
  • 方便產生、控制 curve
  • 每個點對 u 做偏微分，可以得到該點切線方向 (trace 時每個點的速度)

Parametric Cubic Polynomial Curves

我們可以用 polynomial (degree = n+1) 來表示 parametric curves： $\mathbf{p}(u)=c_{0}+c_{1} u+c_{2} u^{2}+\cdots c_{n} u^{n}$，實作上只需要到 cubic polynomial curve 即可

$$\begin{aligned} \mathbf{p}(u)=c_{0}+c_{1} u+c_{2} u^{2}+c_{3} u^{3}=\mathbf{u}^{T} \mathbf{c} &&(0 \le u \le 1) \end{aligned}$$

我們會用 least square curve fitting 來解出所有的 $c_i$。給定一個點得到 (x, y) 分別兩個方程式，所以會有 8 個未知數，需要至少 4 個點才能解出 (底下聯立式 * 4)

$$\begin{aligned} &x(u)=c_{x 0}+c_{x 1} u+c_{x 2} u^{2}+c_{x 3} u^{3}\\ &y(u)=c_{y 0}+c_{y 1} u+c_{y 2} u^{2}+c_{y 3} u^{3} \end{aligned}$$

Least Square Curve Fitting

給定四個座標點 (control points, weight points)，四個點給定的 u 值平均分布在 curve 上，於是就可以得到以下公式 (從 cubic polynomial curve 推得)

$$\begin{aligned} &\mathbf{p}_{0}=\mathbf{p}(0)=\mathbf{c}_{0} \\ &\mathbf{p}_{1}=\mathbf{p}\left(\frac{1}{3}\right)=\mathbf{c}_{0}+\frac{1}{3} \mathbf{c}_{1}+\left(\frac{1}{3}\right)^{2} \mathbf{c}_{2}+\left(\frac{1}{3}\right)^{3} \mathbf{c}_{3}\\ &\mathbf{p}_{2}=\mathbf{p}\left(\frac{2}{3}\right)=\mathbf{c}_{0}+\frac{2}{3} \mathbf{c}_{1}+\left(\frac{2}{3}\right)^{2} \mathbf{c}_{2}+\left(\frac{2}{3}\right)^{3} \mathbf{c}_{3}\\ &\mathbf{p}_{3}=\mathbf{p}(\mathbf{1})=\mathbf{c}_{0}+\mathbf{c}_{1}+\mathbf{c}_{2}+\mathbf{c}_{3} \end{aligned}$$

可以寫成 $\mathbf{P}=\mathbf{A c}$ 的格式，其中

$$\begin{aligned} \mathbf{P}=\left[\begin{array}{c} \mathbf{p}_{0} \\ \mathbf{p}_{1} \\ \mathbf{p}_{2} \\ \mathbf{p}_{3} \end{array}\right] \quad \mathbf{c}=\left[\begin{array}{c} \mathbf{c}_{0} \\ \mathbf{c}_{1} \\ \mathbf{c}_{2} \\ \mathbf{c}_{3} \end{array}\right]\quad \mathbf{A}=\left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 1 & \frac{1}{3} & \left(\frac{1}{3}\right)^{2} & \left(\frac{1}{3}\right)^{3} \\ 1 & \frac{2}{3} & \left(\frac{2}{3}\right)^{2} & \left(\frac{2}{3}\right)^{3} \\ 1 & 1 & 1 & 1 \end{array}\right] \end{aligned}$$

接著把 $\mathbf{P}=\mathbf{A c}$ 兩邊都乘上 $\mathbf{A}^{-1}$ 就可以得到 $\mathbf{c}$

$$\begin{aligned} &\mathbf{A}^{-1} = \mathbf{M}_{\mathbf{I}}\\ &\mathbf{c}=\mathbf{M}_{\mathbf{I}} \mathbf{P}\\ &\mathbf{p}(u)=\mathbf{u}^{T} \mathbf{c}=\mathbf{u}^{T} \mathbf{M}_{\mathbf{I}} \mathbf{P} \end{aligned}$$

注意，因為要滿足 4 維的矩陣乘法，所以把 x, y 對應的 coefficient 拆成兩半表示

$$\begin{aligned} \mathbf{c}_{k}=\left[\begin{array}{l} c_{k x} \\ c_{k y} \end{array}\right] \end{aligned}$$

Cubic Interpolating Curves

當有很多點的時候，則是四個點一組，依序拼出 curves。但不同區段接起來的 curves 可能不夠平滑，所以要考慮「當前區段第一個點」和「前一個區段最後一個點」的微分連續性。我們可以列出一些限制式，最終就可以根據限制式列出 n * n 的矩陣方程來解出這個 curve (n 為 control points 的數量)：

• 每個 control points 都在 curve 上
• 每個 curve 和前個 curve 的一階、二階微分要連續
• 頭尾端點的 curvature (曲率) 為 0