Let’s assume that we have a set of points and we want to draw a path that goes through them. The simplest and easiest way to do this is to connect the points with straight lines as shown in Figure 1.
However, straight lines would cause sharp corners to the path and in many cases a smoother path would be preferred. Figure 2 shows a smoother path that goes through the same points that are in Figure 1.
In this post I’m going to focus on Catmull-Rom splines which are commonly used in computer graphics to create smooth curves. For example, the path in Figure 2 uses them.
Catmull-Rom splines are piecewise-defined polynomial functions. A single spline segment is defined by four control points but the actual curve is drawn only between points and as is illustrated in Figure 3. However, it is easy to chain these segments together.
If we want to draw a curve that goes through points, we need control points because the curve is not drawn through the first and the last ones. These two additional points can be selected arbitrarily, but they affect the shape of the curve. Now a segment between points and is calculated using points , , , and , where . When these segments are combined together, they form a continuous curve, which passes through all points between and . Figure 2 shows an example of this kind of curve.
There are some parameters that can be used to control the shape of the spline. Catmull-Rom splines have three common variants: uniform, centripetal, and chordal. Differences have been studied for example here. Additionally, it is possible to use a tension parameter that defines how “tight” the spline is. When tension is 0, the result looks like the curve in Figure 2, and when tension is 1, the result is straight lines as in Figure 1. The following interactive example demonstrates Catmull-Rom splines and these parameters.
You can add points by clicking the canvas and move existing points by dragging them. The control panel allows you to change the tension of the curve and select the spline variant that is drawn.
Calculating spline segments
Let’s start with following equations that are described in a Wikipedia article about centripetal Catmull-Rom splines:
and , , and .
The actual segment we are interested in is between and i.e. and . If , the resulting curve is a uniform Catmull-Rom spline. When , the curve is a centripetal variant and when , the result is a chordal variant.
Calculating the curve with previous equation can be quite inconvenient. Often it would be better to use precalculated constants , , , and , and represent the curve segment between and as
where , , and . Other way to define this is
We can get a relationship between the tangents of and by differentiating these with respect to as follows:
Now we have
where symbols , and are used to represent tangents at the starting point and at the ending point respectively. By solving , , , and from these four equations we get
Now we have to determine and and for that we need tangents and . Calculating the derivative of is quite cumbersome, but luckily we can use Mathematica to do the work for us. We get
If we want to take tension into account, we must also multiply both and with .
It is now easy to precalculate coefficients , , , and for each segment and use equation to quickly interpolate that segment.
The code is written in C++. It uses GLM library that provides the basic linear algebra functionality. Overall, I’ll try to keep the code syntax in this blog quite simple so that it is easy to understand and to convert to other languages.
In its simplest form, we can define a struct of the spline segment as follows:
Note that we are using two-dimensional splines here. If you want three-dimensional splines, just replace all occurances of
As said in the previous chapter, we need parameters and to calculate the spline. In following code we use variable
alpha for and
tension for . A good value for
alpha is 0.5 which gives us a centripetal Catmull-Rom spline, and for
tension a value 0 is a good choice. These values can range from 0 to 1.
If we now have points
p3 for each segment, we can calculate coefficients for segments with equations from previous chapter:
We can get the same result slightly more efficiently by simplifying the equations and using the following code to calculate
These coefficients can be precaluclated for all spline segments assuming that the parameters do not change afterwards. It is now simple to retrieve a point in a segment
segment by using the precalculated values:
t is of course a value between 0 and 1. With a value 0, the result is the starting point of the spline segment, and with a value 1, the result is the ending point.