Catmull-Rom Splines in Game Development

Splines are incredibly useful in game development. Anytime you want to generate a smooth curve that goes through (or “interpolates”) any arbitrary number of points, you can easily do so by using splines. Maybe you want to procedurally generate a wacky Sonic the Hedgehog-style level, complete with crazy loops and turns. Or maybe you want an enemy AI in your game to smoothly move through some waypoints. Or maybe you just want to understand how that weird pen tool in Photoshop works. The secret to all of these things is – you guessed it – splines.

Quick warning: this article assumes some degree of mathematical fluency and it’s not at all necessary to understand all of the math behind splines to be able to make use of them. If you’re on this page because you’re just looking for a simple way to generate a curve that interpolates a list of points, then scroll down to the bottom of this article for a code sample that you can plug right into your project (well, as long as it’s a C#/Unity project).

Before we dive into the math, we’ll go over some practical examples of what you can do with splines. Both of these examples are from games I worked on in the past.

Procedural Mesh Generation

This is a video from a game I worked on at a jam last year.

The tail motion is implemented via a chain of sprites connected with springs. One way to make the tail smooth would be to increase the number of joints, but this would get expensive fairly quickly. Instead, I created a curve that smoothly interpolates all of the joints and procedurally generated a mesh that conforms to that curve. Here’s the source code for the spline generation and for the tail mesh generation.

Movement Along a Curve

My friend Ed Lu also utilized splines in a game that we worked on together for Global Game Jam 2018 called Dog Walk. In Dog Walk, the player travels between neurons along axons of varying degrees of curvature. Using splines, Ed was able to ensure that the character moved smoothly along the path.

DogWalkScreenshotDogWalkScreenshot131616816683808552.png.png

The player gliding along a curved axon in Dog Walk.

Spline Internals

So… what exactly is a spline, anyway? According to Wikipedia, it’s a “numeric function that is piecewise-defined by polynomial functions, and which possesses a high degree of smoothness at the places where the polynomial pieces connect.” I’ll elaborate since it might not make sense without some context. For our purposes, you can think of a spline as a bunch of curves that are stitched together at the endpoints in a way that allows the transitions between the individual curves to be smooth. The end result is that all of these stitched-together curves actually look like one big continuous curve. That’s where the “piecewise” part of the wikipedia definition comes in – a spline is a bunch of “pieces”, each of which is an individual curve. The “functions” that are mentioned in the definition are just the curves, each of which is defined by a function.

Hermite Curves

Before diving into how splines themselves work, it’s important to understand the individual curves that make up the splines. These curves are “third-degree polynomials specified in Hermite form”, which is kind of a mouthful, so I’m going to call them “Hermite curves”. Anyway, here’s what your typical third degree (aka cubic) polynomial looks like:

p(t) = c_0 + c_1t + c_2t^2 + c_3t^3

We use p to emphasize that we are calculating position – that’s what we care about when drawing our curve, since we’re plotting points with x, y, and possibly z coordinates. You’ll also notice that this formula is a function of t. Hermite curves (and other related curves, such as Bézier curves) are defined by parametric equations – both x and y are a function of some independent variable t, rather than depending on each other. To demonstrate this concept using the cubic polynomial equation from above, we define x in terms of t:

x(t) = c_0 + c_1t + c_2t^2 + c_3t^3

y(t) will look identical but most likely with different values for the coefficients. t is basically a value that represents how far along the curve you are, normalized between 0 and 1. is 0 at the beginning of the curve and is 1 at the end of the curve. If you’ve ever used the lerp function of Unity/GLSL/etc, then you’ve used  t.

So what does it mean to express a cubic curve in Hermite form?  In a nutshell, it just means to provide the four Hermite values, which I will explain in more depth shortly. These four values tell you everything you need to know to generate a curve. They also give you enough information to get the coefficients of t in the standard cubic polynomial equation, and with these coefficients we have the entire formula for a polynomial curve. The reason we prefer Hermite form is because these values are more intuitive to reason about than the coefficients. You can kind of predict how a cubic curve will look if you know the Hermite values. The Hermite values are:

p_0 = p(0) – the position of the starting point of the curve.
p_1 = p(1) – the position of the end point of the curve
v_0 = v(0) – the rate of change at p0
v_1 = v(1) – the rate of change at p1

To get a bit of intuition around how this works, think of it this way – p0 and p1 give you the endpoints of the curve. v0 and v1, which represent the rate of change around p0 and p1, tell you how the curve changes as it goes away from p0 and p1. See the following diagram to get a sense for how the  Hermite values affect the final resulting curve:

hermitecurves

A key thing to understand is that a Hermite curve is a cubic polynomial curve. Any Hermite curve can be described by the formula p(t) = c_0 + c_1t + c_2t^2 + c_3t^3 . It’s just a different way of expressing the same thing – you’re supplying Hermite values instead of coefficients of the powers of t. Bézier curves are also just another form of cubic curves, except instead of using Hermite values they use “control points”. All three of these forms are capable of generating the exact same set of curves. To make this more clear – cubic curves can only generate a certain type of curve. For example it’s impossible to trace the outline of Abraham Lincoln’s face with a cubic curve, since a cubic curve has a degree of three and can therefore only have two “wiggles” (just like how a parabola, which is of degree 2, can only have one “wiggle” or “turn”). Any curve that can be described by a third degree polynomial can also be described by the Hermite or Bézier form.

Moving on. Now that we know what the Hermite values are, we can actually solve for them by plugging them into the standard equation for a cubic curve. p(0) and p(1) are pretty straightforward:

p(0) = c_0 + c_1(0) + c_2(0)^2 + c_3(0)^3 = c_0
p(1) = c_0 + c_1(1) + c_2(1)^2 + c_3(1)^3 = c_0 + c_1 + c_2 + c_3

To find v0 and v1, recall that the velocity is just the derivative of the position. So the velocity of a cubic curve at any value of t is:

v(t) = p\prime(t) = c_1 + 2c_2t + 3c_3t^2

To solve for v(0) and v(1), we just plug in 0 and 1. Easy peasy:

v(0) = c_1 + 2c_2(0) + 3c_3(0)^2 = c_1
v(1) = c_1 + 2c_2(1) + 3c_3(1)^2 = c_1 + 2c_2 + 3c_3

Now that we have the Hermite values, let’s try to actually get a formula for the curve that we can plug numbers into and get position values out of. The first thing we’ll do is solve for the coefficients of t. We already have enough information to do this. We have all four Hermite values and there are exactly four unknowns. We can find these coefficients by solving a system of equations, which I won’t go over here since the details are pretty mundane and straightforward. Anyway, you end up with these coefficients for your cubic polynomial:

c_0 = p_0
c_1 = v_0
c_2 = -3p_0 - 2v_0 - v_1 + 3p_1
c_3 = 2p_0 + v_0 + v_1 - 2p_1

Since these are the coefficients for the various powers of t, we can actually rewrite this as a matrix product (multiply it out and you’ll see that we end up with a polynomial where each of the above coefficients is multiplied by the corresponding t):

p(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -3 & 3 & -2 & -1 \\ 2 & -2 & 1 & 1\end{bmatrix}\begin{bmatrix}p_0 \\ p_1 \\ v_0 \\ v_1\end{bmatrix}

A quick side note on this – you don’t actually have to use matrix form. I’m using matrices because that’s what most of the literature on this topic uses and one of my goals is for you to be able to easily and intuitively digest that sort of material after reading this article. But if you don’t like dealing with matrices, you can just keep the coefficients in their present form and just replace p0, p1, v0, and v1 with the new values that we come up with in the next section.

Anyway, this formula is already starting to become pretty useful. It’s a formula for a Hermite curve – we can supply any two endpoints (p0 and p1) and the tangents v0 and v1 and this formula will give us points along that curve as we plug in values of t. But this isn’t what we set out to do. We don’t want to supply tangents. That’s a pain in the ass. We just want to supply a bunch of points and magically generate a curve that goes through them. So how do we do that?

Creating our Spline

Let’s start with a small example. Let’s say we have four points and we want to generate a spline that goes through all of these points:

splinepoints

We’re going to do this by making a bunch of Hermite curves and sticking them together. Yup, that’s right. A Catmull-Rom spline is nothing more than a bunch of cubic curves joined together at their endpoints. The first curve will go from p0 to p1. The second one will go from p1 to p2. The final one will go from p2 to p3. So you’ll apply that formula we derived above for p(t), but in three different variants, each variant with a different pair of endpoints. The formula for the first curve will have endpoint p0 and p1, the second one will have p1 and p2, and the third will have p2 and p3:

splinepoints2

But wait, don’t we also need the tangents v0 and v1? How do we decide what those should be?

Generally, two curves joined together at some point will be smooth if the tangent at the end of the first curve (which is analogous to v1 in our formula) is equal to the tangent at the beginning of the second curve (which is analogous to v0 in our formula). So all we need to do is make sure those are equal and we’re golden. But what should those tangents actually be? A long time ago, two computer scientists named Edwin Catmull and Raphael Rom discovered that a good way to pick tangents is to just subtract the previous point from the next point. So if you’re calculating the tangent for point p2, you’d take the result of (p3 – p1) since p3 is the next point and p1 is the previous point.  It’s also common to divide these tangents by 2, not for any mathematically rigorous reason but just because doing so tends to give curves that are aesthetically pleasing. The key insight to gain from this is that the only information that you need in order to calculate tangents is the adjacent points. So you can actually rewrite the above equation in terms of four points p0 through p3, instead of in terms of p0 p1 v0 and v1. We’ll do this shortly.

splinepoints3

Another tricky thing that comes up is that if you need to use the previous and next point to calculate the tangent, it raises the question of what the previous point of the first point will be and what the next point of the last point will be. One solution to this is to add a “ghost” start point and another ghost end point, which aren’t actually part of the curve but are used to calculate the tangent:

splines

The ghost points are used to calculate the tangents at p0 and p3. The yellow lines are there to indicate that the tangents at the endpoints are calculated by finding the vector difference of the adjacent points (one of which is a ghost vector in both cases) and then dividing by 2.

Another common technique is to just assume some pre-determined default value for the tangent at the start and endpoints instead of using ghost endpoints. This is less flexible but slightly simpler. For the rest of this tutorial, we’ll be using the ghost endpoint technique.

Anyway, let’s modify our formula from above to reflect this previously mentioned method of calculating the tangents. Keep in mind that p0 and p1 below are not the same p0 and p1 from the previous matrix. We are simply rewriting the above matrix as a function of four arbitrary control points:

p(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -3 & 3 & -2 & -1 \\ 2 & -2 & 1 & 1\end{bmatrix}\begin{bmatrix}p_1 \\ p_2 \\ \frac{p_2-p_0}{2*\tau} \\ \frac{p_3-p_1}{2*\tau} \end{bmatrix}

In this form, p1 is analogous to p0 in the previous matrix (it’s the first interpolated point). p2 is the same as p1 in the previous matrix (it’s the last interpolated point). The next two elements of the column matrix are the tangents, which are calculated using the adjacent points as we just discussed. We introduced two other points p0 and p3 to use for tangent calculation. The \tau symbol is tension, which you can tweak to change how sharply your spline changes direction at the knots between curves. This is commonly set to 1. You can play around with tension values to change the appearance of your curve. Just to give you an idea of how this looks, here’s a picture of a spline with the tension bumped up from 1 to 10:

wildspline

Anyway, the equation we derived above technically gives us everything we need in order to draw a curve from four points, but the equation is a bit ugly. You can actually do a bit of matrix manipulation (not shown, since it’s not really relevant) to get it into the form below, which is the form you’d probably actually want to use:

p(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix}\cdot\frac{1}{2}\cdot\begin{bmatrix} 0 & 2 & 0 & 0 \\ -\tau & 0 & \tau & 0 \\ 2\tau & \tau-6 & -2(\tau-3) & -\tau \\ -\tau & 4-\tau & \tau-4 & \tau\end{bmatrix}\begin{bmatrix}p_0 \\ p_1 \\ p_2 \\ p_3\end{bmatrix}

At this point, you’re basically done. Believe it or not, the formula above gives you everything you need to create a spline that goes through any arbitrarily-sized list of points (minus the first and last points in the list, which will be the ghost points). p0 and p3 are used for tangent calculation, and p1 and p2 are actually passed through by the curve.

From here, you can create a list of points that you want your spline to go through. For each piece of the spline, you can get the formula for that piece by plugging in values to the formula and getting a Hermite curve equation. For the first curve you’d plug in the first, second, third, and fourth points. This curve will go through the second and third points, using the first and fourth points just for tangent calculation. For the second curve you’d plug in the second, third, fourth, and fifth points. This curve will go through the third and fourth points, using the second and fifth points just for tangent calculation. And so on and so forth. Note that all of the points used for tangent calculation will eventually become an actual interpolated endpoint of another curve, except for the very first and last points in the list (which is why I call them “ghost” endpoints).

You can evaluate these functions at various values of t, spaced out however you like (depending on how many points you want to evaluate on that curve). As I mentioned previously, the spline won’t go through the first and last points of your list, since they’re being used just for calculating tangents, but it will go through every single other point.

Also don’t forget that since these curves are parametric, you’re actually solving for x(t) and y(t) separately. This doesn’t really complicate things though – after solving individually for x(t) and y(t), you have the coordinates you need to plot an (x, y) point in 2D space. Similarly, if you’re doing a 3D game, you could just do it again for z and get a 3D point. No biggie.

So there you go. Create a big list of as many control points as you want. Use the above template to get the actual formulas for each of the curves that make up your spline. Plug in a bunch of values of t spaced out however you like. And you’re done.

Example Code

In practice, you generally won’t want to actually put the matrices in your code. If you multiply out the matrices that we derived above, you get a very simple equation that you can then plug into a function:

public static List GenerateSpline(List points, int stepsPerCurve = 3, float tension = 1)
    {
        List result = new List();

        for (int i = 0; i < points.Count - 1; i++)
        {
            Vector3 prev = i == 0 ? points[i] : points[i - 1];
            Vector3 currStart = points[i];
            Vector3 currEnd = points[i + 1];
            Vector3 next = i == points.Count - 2 ? points[i + 1] : points[i + 2];

            for (int step = 0; step <= stepsPerCurve; step++)
            {
                float t = (float)step / stepsPerCurve;
                float tSquared = t * t;
                float tCubed = tSquared * t;

                Vector3 interpolatedPoint =
                    (-.5f * tension * tCubed + tension * tSquared - .5f * tension * t) * prev +
                    (1 + .5f * tSquared * (tension - 6) + .5f * tCubed * (4 - tension)) * currStart +
                    (.5f * tCubed * (tension - 4) + .5f * tension * t - (tension - 3) * tSquared) * currEnd +
                    (-.5f * tension * tSquared + .5f * tension * tCubed) * next;

                result.Add(interpolatedPoint);
            }
        }

        return result;
    }

Basically all this is doing is taking a list of points and returning a list of points along a spline that smoothly interpolates all of the provided points. The stepsPerCurve parameter specifies the number of points to generate between each of the original points. The greater the value, the smoother the spline. The tension parameter should remain at the default value in most cases.

References

I came across quite a few online resources while I was learning this material but these two were by far the best:

  • Bézier Curves from the Ground Up – Jamie Wong – A very clear and intuitive explanation of Bézier curves with great animations. Doesn’t go into too much detail on the math, but it’ll give you a very solid intuition of how Bézier curves work and how to construct them.
  • A Primer on Bézier Curves – This is an amazing resource and will give you a really solid mathematical foundation for understanding all sorts of splines and curves. I used this resource heavily during my own learning. I haven’t finished the whole book yet and I’m pretty eager to see what other cool knowledge awaits me in there.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s