Smooth Bézier Spline Through Prescribed Points

In this article we show you how to generate a smooth spline through a set of prescribed points. The article also contains an interactive SVG demo that allows you to try this in real time. This demo may not work if you are reading this post through email or on a mobile device. In that case, please visit the article from your computer browser.

Introduction

In scientific computing, we often need to construct a line that passes through a set of prescribed controlled points, or knots. A common example is mesh generation. Even if we utilize a mesh-free method, we need to somehow prescribe the outer extent for the problem. This is typically accomplished by specifying boundary splines (the counterpart in 3D are patches).

Bézier Splines

Spline is a collection of polygonal segments. The segments can be linear, quadratic, cubic, or even higher order polynomials. In this article we derive the equations needed to draw a smooth curve through a set of control points using the cubic Bézier polynomial. Wikipedia has a very nice article on Bézier curves that includes animations that show how these polynomials work.

The cubic Bézier curve is given by

this can be rewritten as

In this definition, the points 0 and 3 correspond to the end points (the knots). The other two points are control points that determine the shape of the curve. The curve does not in general pass through these points. Following the steps outlined on codeproject.com, we want the first and second derivatives to be continuous across the spline boundary. This will give us two equations (one for each derivative) at each spline interface which we use to find the control points.

The first derivative is given by

At the left boundary of an “i-th” segment we can write

or

Now, since the curve is continuous, , the “i-th” knot point, and we can simplify this expression as (1)

We also want the second derivative to be continuous. The second derivative is given by

at the boundary we have

Simplifying and taking into account the shared knot point, we get equation (2),

The equations (1) and (2) are defined only at the internal knots – places where two segments come together. Mathematically, this means that we have equations for unknowns. In order to close the system, we prescribe two more natural boundary conditions, and . In other words, the spline becomes linear at the end points. These two remaining equations (3) and (4) are

and

We can further simplify this system by substituting (1) into (2) to obtain
.
On the boundary nodes we have from (3) and (4)

and

This is a tri-diagonal system for which we can solve using the Thomas algorithm. Once we determine , we obtain from equations (1) and (4),

and

Interactive Demo

Below you will find an interactive demo that implements this algorithm. If everything loaded fine, you should see four yellow circles connected by a smooth line composed of three differently colored segments. You can move any of the circles with the mouse. If you don’t see the circles, cannot move them, or the spline is not smooth, first try reloading the page. If that still fails, try a different browser. The demo worked for me with Chrome, Firefox, and Internet Explorer 9 under Windows. I couldn’t get it working on my Android phone (no graphics rendered) and a friend reported it didn’t work on iPad either. If you know how to get the demo working on these mobile devices, please let me know by leaving a comment below.

This demo uses SVG and Javascript (You can find a TON of SVG examples on Prof. Dailey’s website. Another good resource is the SVG tutorial on “Peter’s Website”). SVG (Scalable Vector Graphics) is one of two ways you can get interactive graphics in your website (the other being HTML5′s <canvas> element). Of these two, SVG seems to be much more versatile. There are even free vector graphics programs out there, such as Inkscape, which save the images in the SVG format. The three lines connecting the circles are defined using SVG’s Bézier cubic path syntax. Whenever you drag a circle, the code recomputes the control points and updates the path definition. Your browser then automatically repaints the view. Pretty nifty! You will find the complete code below.

Source Code

You can download the source code here: circles.svg. The image is embedded using the <embed> tag. You can also see just the Javascript: bezier-spline.js (this code is embedded inside the SVG).

As a side note, it took me way too long to get the code running. Javascript is different from Java in that, among other things, it does not define variable types. Initially, the code was using

for (i=0;i<4;i++)
{
    x[i]=V[i].getAttributeNS(null,"cx")
    y[i]=V[i].getAttributeNS(null,"cy")
}

to obtain the coordinates of the four control points. These were then passed to another function which performed the actual computation. The problem was, this actually resulted in x[i] being a string and not an integer. Javascript did not complain about this. Instead, where required it automatically converted the string to an int. However, the plus operator resulted in string concatenation instead of addition of two numbers. For example, for x[i]="50", x[i]+30 resulted in 5030 instead of the expected value of 80. For the longest time I was getting really funky results and could not figure out why despite rechecking my math multiple times. I finally found the bug by stepping through the code with the Javascript debugger that comes with Chrome. The simple fix was to force the conversion to integer,

for (i=0;i<4;i++)
{
    /*use parseInt to convert string to int*/
    x[i]=parseInt(V[i].getAttributeNS(null,"cx"))
    y[i]=parseInt(V[i].getAttributeNS(null,"cy"))
}

Also make sure to checkout the interactive online mesh generator follow up article.

Did you find this article useful? If so, please share the link with your friends, coworkers, and colleagues. And don't forget to subscribe to the newsletter and follow us on Google+ and Twitter. To find out more about how we can assist you on your project, please see the request for proposal page.