Splines Are Just Obfuscated Beziers

In graphics kindergarten, you’re always taught about Bezier curves. We’re taught that we can use the Decastlejau algorithm to evaluate them, and there’s something-or-other in there about the Bernstein basis polynomials. You’re also taught about Hermite curves, B-spline curves, Catmull-Rohm, Kochanek-Bartels, and other stuffs, but what seems to be lesser known is the fact that these guys are all interchangable. Beziers are to curves as triangles are to everything else. They have some useful properties, and you can always convert to them.

In this educational post, I’m going to go through the recipe for converting from one type of (uniform, non-rational) cubic spline to any of the others. Eventually, you will come to understand why you only ever need one curve-drawing routine (unless you’re especially paranoid about precision).

Let’s Review

A Bezier curve is a curve that magically appears between any four points. We have a start point, and end point, and two other points that control the curve’s shape.

The Bezier curve can be elegantly evaluated by using the Decastlejau algorithm, which boils down to repeatedly interpolating between control points. First, we compute interpolated points on each of the three segments, then we construct two segments between the three result points and lerp on those, and repeat, until we’re down to just one point.

T_{10}(t) = lerp(P_0,P_1,t)\\T_{11}(t) = lerp(P_1,P_2,t)\\T_{12}(t) = lerp(P_2,P_3,t)\\T_{20}(t) = lerp(T_{10},T_{11},t)\\T_{21}(t) = lerp(T_{11},T_{12},t)\\F(t) = lerp(T_{20},T_{21},t)\\

A useful fact about the Bezier curve is that it can be recursively split. We can subdivide a bezier into two smaller Beziers by evaluating it at 0.5 and using some of the intermediate results from Decastlejau as the new control points:

Front = \begin{bmatrix}P_0 & T_{10}(0.5) & T_{20}(0.5) & F(0.5) \end{bmatrix}\\Back = \begin{bmatrix}F(0.5) & T_{21}(0.5) & T_{12}(0.5) & P_3\end{bmatrix}

One final useful fact about Beziers is that the curve is always fully contained within the convex hull of the four control points. This fact is very useful for culling, and it can also be used to do adaptive drawing by subdividing until the size of the convex hull sinks below a suitable threshold.

If you paid attention during graphics kindergarten, you should have learnt that the Bezier curve can be written as a weighted combination of the Bernstein basis polynomials:

P(t) = B_{03}(t)P_0 + B_{13}(t)P_1 + B_{23}(t)P_2 + B_{33}(t)P_3

Where:
B_{03}(t) = (1-t)^3 \\B_{13}(t) = 3t(1-t)^2 \\B_{23}(t) = 3t^2(1-t) \\B_{33}(t) = t^3

In case you were wondering, if you take the lerps I wrote above, expand them all out, and then simplify, you will eventually get the above equation. I’ll leave that as an exercise to the reader. I’m going to start referring to the Bernstein basis as the “just lerp it” basis.

A Hermite spline is defined using a different basis, with the added wrinkle that two of the “control points” are really vectors:

P(t) = B_{03}(t)P_0 + B_{13}(t)T_0 + B_{23}(t)P_1 + B_{33}(t)T_1

Where:
B_{03}(t) = 2t^3-3t^2+1 \\B_{13}(t) = t^3-2t^2+t \\B_{23}(t) = -2t^3 + 3t^2 \\B_{33}(t) = t^3 - t^2

Hermite splines are kindof useless by themselves, but they’re a useful building block. If you string together a series of Hermite splines with consistent tangents at matching endpoints, you have the venerable Catmull-Rohm spline. Kochanek and Bartels took this even further by extra parameters for tension, continuity, and bias. Those extra parameters end up being simple scale factors that get applied to the control points segment by segment.

A (uniform) B-spline is defined using yet another basis:

P(t) = B_{03}(t)P_0 + B_{13}(t)P_1 + B_{23}(t)P_2 + B_{33}(t)P_3

Where:
B_{03}(t) = (-t^3 + 3t^2 -3t + 1)/6 \\B_{13}(t) = (3t^3 - 6t^2 + 4)/6 \\B_{23}(t) = (-3t^3 + 3t^2 + 3t + 1)/6 \\B_{33}(t) = t^3 /6

These little fellas are special in that piecewise B-splines are always C2 continuous.

They’re All The Same. Really…

I just told you that these are all the same thing, so you might be skeptical given how different they look. Here’s the trick: Let’s look at what happens when we expand everything out in the Bezier case:

P(t) = B_{03}(t)P_0 + B_{13}(t)P_1 + B_{23}(t)P_2 + B_{33}(t)P_3

Where:
B_{03}(t) = (1-t)^3 \\B_{13}(t) = 3t(1-t)^2 \\B_{23}(t) = 3t^2(1-t) \\B_{33}(t) = t^3

So:

P(t) = (1-t)^3P_0 + 3t(1-t)^2P_1 + 3t^2(1-t)P_2 + t^3P_3 \\ P(t) = (1-3t+3t^2-t^3)P_0 + (3t-6t^2+3t^3)P_1 + (3t^2-3t^3)P_2 + (t^3)P_3 \\P(t) = P_0 + t(-3P_0+3P_1) + t^2(3P_0-6P_1+3P_2) + t^3(-P_0+3P_1-3P_2+P_3)

At the end of the day, these things are all just cubic polynomials, and they can be contorted back into the form we all learned about in high school algebra. If we liked, we could pre-compute the coefficients of this cubic polynomial and use these instead of the bezier control points. We’d get exactly the same curve, but we’d no longer have the nice properties that Beziers give us, which is why nobody actually does it that way.

Now for the secret sauce…. If we do all of that algebra and then squint a little, we’ll find that we can rewrite each component of the bezier curve as a matrix equation, like so:

x(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix}\begin{bmatrix} 1 &0& 0& 0 \\-3 &3 &0& 0 \\3 &-6 &3& 0 \\-1 &3 &-3& 1 \end{bmatrix}\begin{bmatrix}x_0\\x_1\\x_2\\x_3\end{bmatrix}

We have a control point vector on the right, a parameter vector on the left, and a basis matrix in the middle. We can do the same thing for the curve types too. For Hermite, we’d get:

x(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix}\begin{bmatrix} 1 &0& 0& 0 \\0 & 1 & 0 & 0 \\-3 & -2 & 3 & -1 \\2 & 1 & -2 & 1\end{bmatrix}\begin{bmatrix}x_0\\x_1\\x_2\\x_3\end{bmatrix}

And for B-splines:

x(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix}\frac{1}{6}\begin{bmatrix} 1 &3& -3& 1 \\3 & -6 & 3 & 0 \\-3 & 0 & 3 & 0 \\1 & 4 & 1 & 0\end{bmatrix}\begin{bmatrix}x_0\\x_1\\x_2\\x_3\end{bmatrix}

All of the different cubics all do the same thing. They just use a different basis matrix to convert from control vertices into natural spline coefficients. This means that as long as we can tolerate a little roundoff error, we can always convert a given curve segment to Bezier form.

Suppose we have a set of Hermite control points (endpoints and tangents), and we want to find the corresponding Bezier points. All we have to do is set the curves equal to each other and do some linear algebra:

C_h = \begin{bmatrix} P0_x \\ T0_x \\ P1_x \\ T1_x \end{bmatrix}\\x(t) = \begin{bmatrix}1&t&t^2&t^3\end{bmatrix}M_bC_b \\x(t) = \begin{bmatrix}1&t&t^2&t^3\end{bmatrix}M_hC_h \\M_bC_b = M_hC_h \\M_bC_b = M_hC_h \\C_b = M_b^{-1}M_hC_h

Here we have the recipe for converting from any sort of cubic curve into a Bezier. Take the basis matrix for whatever type of curve it is (Hermite, B-spline, whatever), multiply on the left by the inverse Bezier basis matrix, which is:

M_b^{-1} = \begin{bmatrix}1 & 0 & 0 & 0 \\1 & 1/3 & 0 & 0 \\1 & 2/3 & 1/3 & 0 \\1 & 1 & 1 & 1\end{bmatrix}

This gives a conversion matrix which we then multiply the control points by, one coordinate at a time. So, there you have it. If you can use a Bezier, you can use everything else.

2 Comments

Comments are closed.