May 17, 2020

Roger Ngo

If we have 2 endpoints $P_0$, and $P_1$, we can interpolate the line in a parametric manner for every $t$ by using the equation:

$P(t) = (1 - t)P_0 + tP_1$

For each coordinate $(x, y)$ at a $t$, we can solve for the interpolated coordinate by:

This parametric line equation is very powerful, and the concept can be extended towards higher-order polynomials where we must interpolate points in order to obtain the graphical curve.

It is rather straightforward to graph a straight line through the parametric line equation presented above, but what if we want to graph a cubic polynomial?

Cubic polynomials have a degree $d = 3$, and so can cross the x-axis 3 times by Bezout's Theorem. So it is no longer as straightforward as connecting the dots. The main problem is that we do not know when the curve changes direction.

Fortunately, a mathematician in the past has helped us with that. Charles Hermite invented Hermite Curves to help us interpolate cubic polynomials.

Given positions $P_0$, and $P_1$, and the directional vectors for the corresponding points $P'_0$, and $P'_1$, we can find a function $\gamma : [0, 1] \rightarrow R^2$ such that:

Extending it to a third-dimension is easy here. We just introduce a $P_2$ in this case, and parametrically solve. So not a big deal here.

We can also interpolate an Hermite curve, by turning the $\gamma(t)$ polynomial into a matrix multiplication expression.

If we simplify and represent each coefficient of $\gamma(t)$ as some variant of $a$, we get:

If we let $\bold{T}$ be the vector $\begin{bmatrix} 1 \\ t \\ t^2 \\ t^3 \end{bmatrix}$ , $\bold{M}$ be the matrix of coefficients for each $t$ term $\begin{bmatrix} 1 & 0 & -3 & 2 \\ 0 & 0 & 3 & -2 \\ 0 & 1 & -2 & 1 \\ 0 & 0 & -1 & 1\end{bmatrix}$, and $\bold{G}$ be the vector consisting of known points, $\begin{bmatrix} P_0 & P_1 & P'_0 & P'_1 \end{bmatrix}$, we can express a value $t$ of the Hermite curve with:

Let's work out an example. Suppose we have the following defined:

We can write our matrix multiplication expression of our Hermite curve at $t$ as:

We then solve for the $x$, and $y$ components independently.

Using the points I have given, if we interpolate through $t$ using various fixed $\Delta{t}$, we can see we can obtain different versions of the plotted curve.

Finer increments will allow for a better approximated curve. Here are graphical examples of using $\Delta{t} = 1.0$, $\Delta{t} = 0.5$, $\Delta{t} = 0.25$, $\Delta{t} = 0.1$, and $\Delta{t} = 0.01$.

$\Delta{t} = 1.0$

$\Delta{t} = 0.5$

$\Delta{t} = 0.25$

$\Delta{t} = 0.1$

$\Delta{t} = 0.01$

As you can see, we best approximate the curve when $\Delta{t} = 0.01$. Although this generates a nice looking curve, there are more data points to interpolate, and as a result, more computationally expensive.

Choosing an appropriate step for interpolation should be kept in mind if performance is a concern.

Implementation

We use glMatrix library to compute the matrices to interpolate a point given a $t$ in the Hermite curve.

for(let t = 0; t <= 1.0; t += 0.01) {
	const coord = hermite(p0, p1, pp0, pp1, t);

    console.log(coord);
}

function hermite(p0, p1, pp0, pp1, t) {
    const g_x = glMatrix.mat4.fromValues(
        p0.x, 0, 0, 0,
        p1.x, 0, 0, 0,
        pp0.x, 0, 0, 0,
        pp1.x, 0, 0, 0
    );
    const g_y = glMatrix.mat4.fromValues(
        p0.y, 0, 0, 0,
        p1.y, 0, 0, 0,
        pp0.y, 0, 0, 0,
        pp1.y, 0, 0, 0
    );

    const M = glMatrix.mat4.fromValues(
        1, 0, 0, 0, 
        0, 0, 1, 0, 
        -3, 3, -2, -1, 
        2, -2, 1, 1
    );
    const T = glMatrix.mat4.fromValues(
        1, t, Math.pow(t, 2), Math.pow(t, 3),
        0, 0, 0, 0,
        0, 0, 0, 0,
        0, 0, 0, 0
    );

    const r_x = glMatrix.mat4.create();
    glMatrix.mat4.multiply(r_x, g_x, M);
    glMatrix.mat4.multiply(r_x, r_x, T);

    const r_y = glMatrix.mat4.create();
    glMatrix.mat4.multiply(r_y, g_y, M);
    glMatrix.mat4.multiply(r_y, r_y, T);

    return {
        x: r_x[0] / 10,
        y: r_y[0] / 10
    };
}

Demo