Splines and curves part I – Bézier Curves

In this series I want to give an introduction to curves and splines for the programmer. These are typically used in computer graphics, game design scenarios (especially camera motion) and engineering to generate smooth shapes from simple datasets.

Hopefully by the end of this series you will be able to not only generate your own curves in your program, but will understand why they are formed the way they are and have the tools to understand which curve technique to select for your own scenarios.

Splines were originally a tool for engineering draftsman for building smooth curves in disciplines like boat-building to generate smooth curves using control points. The flexibility of the flat metal or wood spline along with the placement and constraint of the control points defined the shape of the curve. Most spline techniques in mathematics and software borrow from these ideas to form the shapes desired by the user.

Wikipedia defines splines in the mathematical context as

In mathematics, a spline is a smooth polynomial function that is piecewise-defined, and possesses a high degree of smoothness at the places where the polynomial pieces connect (which are known as knots).

We’ll get into what exactly is meant by “high degree of smoothness” and the other technical terms as we go. For now you can think of a spline as a series of points which we will generally define parametrically over the unit interval, determined by some spline function. We are free to determine the number of points along the interval depending on the context in which the spline is to be used.

As an aside, did you know that the famous Utah Teapot is defined as a set of control points over which we build splines with an arbitrary number of points over each interval? The number of points drawn over each curve interval determines the number of polygons drawn, which is what is meant by the previous paragraph. Using a single small data set we can build a teapot with an arbitrary number of polygons. Neat, huh?

Approximation versus Interpolation

Before we get started it’s important to note the difference between an approximation technique and an interpolation technique for curve generation. All curves are defined interactively by placing control points. If the algorithm for generating the curve passes through all control points then it is referred to as an interpolation algorithm. Algorithms that build curves that are affected by the control points but don’t necessarily pass through them all are referred to as approximation algorithms. Which one you use will depend on your particular use case. We will explore the differences in more detail further down.

Bézier curves

The first curve we will investigate is the infamous Bezier curve. It should be noted that the Bezier curve is not, in fact, a spline, but it’s still a useful starting point. We will start with an example, and delve into some details of how this curve works and why. Note that the interactive examples in this article use the HTML5 canvas element so may not work correctly on older browsers and some mobile devices. Hover your mouse over the curve to see how it is constructed.


Hover over canvas to see line construction. Click & drag control points to modify line.

This is a quadratic Bezier, which is a fancy way of saying it’s a Bezier curve with 3 control points (the reason for the names quadratic, cubic etc will become clear soon). So what’s going on here? You can see when you hover your mouse over the above image that as we vary t, we take the parametric point t along each of the lines that form our control points (I have drawn these straight lines in light grey for your convenience). We then take these new points and draw a line between them. The point that determines the point t on our curve is the point t along this new line.

We can implement this quadratic Bezier using an algorithm known as de Casteljau’s Algorithm. It is essentially a sequence of tweening steps, in this case to generate a part of a parabola. Think of it like this: if we label the two straight lines defined by our three control points A and B, we linearly interpolate across these lines and then repeat the interpolation to find the point P(t) that resides a fraction t of the way between A(t) and B(t):
A(t) = (1 - t){P_0} + t{P_1}
B(t) = (1 - t){P_1} + t{P_2}
P(t) = (1 - t)A + tB

You can see we’re using the basic linear interpolation formula for parametric lines here. If you’re not familiar with linear interpolation then read up!

Anyway, by direct substitution (try this out on paper if you like) we can get to this formula for P(t):
P(t) = {{(1 - t)}^2}{P_0} + 2t(1 - t){P_1} + {t^2}{P_2}

Here’s the code I have used to implement this in Javascript. Please note that most of the code in this guide is rushed and not optimal. This article is more about the concepts than the code, and you should put some thought into how to write optimal versions before you implement your own. Also, for the supporting code around this check out the bottom of this post, I’ll include the code I used for drawing, mouse events, etc at the end because it’s not directly relevant to this post.

function quadraticBezier(clicks, ctx) {
function bezierFunc(points, t) {
var p0 = points[0];
var p1 = points[1];
var p2 = points[2];
var t2 = t*t;

var dx = dot([p0.x, p1.x, p2.x], [(1-t)*(1-t), 2*t*(1-t), t2]);
var dy = dot([p0.y, p1.y, p2.y], [(1-t)*(1-t), 2*t*(1-t), t2]);

return point(dx,dy);
}

var p = [];
for (var j = 0; j < lineSegments+1; j++) {
p.push(bezierFunc(controlPoints, j/lineSegments));
}
curveSegment(p, ctx);
}

function dot(v1, v2) {
var sum = 0;
for (var i = 0; i < v1.length; i++) {
sum += v1[i]*v2[i];
}
return sum;
}

function lineSegment(p0, p1, ctx) {
ctx.beginPath();
ctx.moveTo(p0.x,p0.y);
ctx.lineTo(p1.x,p1.y);
ctx.stroke();
ctx.closePath();
}

function point(x, y) {
return {
x:x,
y:y
};
}

function curveSegment(points, ctx) {
ctx.lineWidth = 2;
ctx.strokeStyle = '#000';
for (var i = 0; i < points.length-1; i++) {
lineSegment(points[i], points[i+1], ctx);
}
}

In this code I am using a dot product that I defined to make multiplying over points a little cleaner. You don’t have to do it this way but I prefer it. Also some libraries have extremely efficient matrix and vector multiplication algorithms so I tend to gravitate towards these functions.

To explain very briefly what’s happening in this code, given a set of control points we take the first three (we’re only dealing with quadratic Beziers for now) and apply the above formula. We can use a dot product because each control point appears once and only once in the formula, which is thankfully true of Bezier curves of all degree.

We can extend this technique to Bezier curves of higher order. To generate a cubic Bezier curve, we add another control point. We then apply the same interpolation we just did across the first three points, and we apply that interpolation across the last three points. Finally we interpolate across the two points we have just generated with respect to t and this point defines our curve at t. See the demonstration below, where the blue line represents our newly interpolated line:

Hover over canvas to see line construction. Click & drag control points to modify line.

It’s not difficult to find the formula for the cubic Bezier (left as an exercise):
P(t) = {P_0}{{(1-t)}^3} + {P_1}3{{(1-t)}^2}t + {P_2}3(1-t){t^2} + {P_3}{t^3}

For completeness, here is the code to generate this curve, which is very similar to the previous code.

function cubicBezier(controlPoints, ctx) {
function bezierFunc(points, t) {
var p0 = points[0];
var p1 = points[1];
var p2 = points[2];
var p3 = points[3];
var t3 = t*t*t;
var t2 = t*t;

var dx = dot([p0.x, p1.x, p2.x, p3.x], [(1-t)*(1-t)*(1-t), 3*(1-t)*(1-t)*t, 3*(1-t)*t2, t3]);
var dy = dot([p0.y, p1.y, p2.y, p3.y], [(1-t)*(1-t)*(1-t), 3*(1-t)*(1-t)*t, 3*(1-t)*t2, t3]);

return point(dx,dy);
}

var p = [];
for (var j = 0; j < lineSegments+1; j++) {
p.push(bezierFunc(controlPoints, j/lineSegments));
}
curveSegment(p, ctx);
}

In fact, we can extend this to arbitrary degrees. The terms by which we multiply each of our control points turn out to be (for reasons outside the scope of this article) the Bernstein polynomials. You can get these terms by raising the expression a(t) = (1 - t + t) to the nth power (of course this expression is simply a(t) = 1, so all terms always add to 1, an important result that we won’t go into here, but if you’re familiar with affine combinations you’ll surely see why this is pretty nifty).

The Bezier curve extends to any number of control points using this Bernstein polynomial result thusly:
P(t) = sum{k=0}{L}{P_k}{{B_k}^L}(t)
This is pretty cool, but not really used very widely because computing large polynomials is computationaly expensive and there are nicer alternatives for generating curves based on lots of control points. However you should certainly experiment with generating arbitrarily large Bezier curves.

Properties of Bezier curves
Bezier curves have some interesting properties that make them useful for certain purposes but less so for others. Bezier curves are approximation curves in that they don’t pass through all control points, however they will always pass through their endpoints (can you see why, in terms of Bernstein polynomials?). This makes them useful for designers who need to visually generate smooth curves but need well-defined start and finish points.

Bezier curves are also affine invariant (hinted at earlier). This means we can use familiar matrix transformation techniques to shift the control points and the curve will transform as expected – rotating, scaling and skewing the curve is as simple as transforming the control points. This is extremely useful in CAD and graphics design contexts.

Another interesting property of Bezier curves is the convex hull property. All points on a Bezier curve are within a convex hull defined by the control points of the curve. If you don’t know what a convex hull is then you probably don’t need to, but I assume this property is useful for someone.

Problems with Bezier curves
Bezier curves are C^1 smooth functions. This means that the Bezier curve can generally be differentiated once across the unit interval. C^1 smoothness means that, for example, a camera following the curve along the unit interval at a constant speed (with respect to t) will move at a continuous velocity (not a constant velocity, but continuous with no breaks or jumps). With C^1 smoothness acceleration is not guaranteed to be continous.

Typically to get Bezier curves with more than 4 control points we will join multiple Bezier curves together. In this case the complete curve will be C^0 smooth, which means that the curve is continuous but the first derivative is not guaranteed to be, ie there could be jumps in velocity. This can be mitigated with careful placements of the control points. For more information of curve smoothness, read this.

The biggest problem with Bezier curves is the lack of local control over the curve. What I mean by this is that getting precisely the shape of the curve you want is difficult because changing a single control point in a Bezier curve will affect the entire curve. You can see from the formulae that each point on the curve (except for the endpoints) is affected to some degree by the position of the other points. Maybe other curve/spline types will allow us greater local control over our curve…

In the next article I will cover C-Spline and B-Spline curves and the famous Catmull Rom spline. We’ll look at what it takes to work with C^2 smooth splines.

The (very rough) code I wrote for this article can be found on my Github repository.



This entry was posted in Programming and tagged , , . Bookmark the permalink.

8 Responses to "Splines and curves part I – Bézier Curves"

Leave a reply

*