12,817,318 members (34,241 online)
alternative version

#### Stats

259.1K views
132 bookmarked
Posted 17 Dec 2008

# Draw a Smooth Curve through a Set of 2D Points with Bezier Primitives

, 24 Mar 2009 CPOL
 Rate this:
Calculate piecewise Bezier curve control points to make it a spline

## Introduction

From time to time, I am faced with the question: how to draw a smooth curve through a set of 2D points? It seems strange, but we don't have out of the box primitives to do so. Yes, we can draw a polyline, Bezier polyline, or a piece-wise cardinal spline, but they are all not what is desired: polyline isn't smooth; with Bezier and cardinal spline, we have a headache with additional parameters like Bezier control points or tension. Very often, we don't have any data to evaluate these additional parameters. And, very often, all we need is to draw the curve which passes through the points given and is smooth enough. Let's try to find a solution.

We have interpolation methods at hand. The cubic spline variations, for example, give satisfactory results in most cases. We could use it and draw the result of the interpolation, but there are some nasty drawbacks:

1. Cubic spline is a cubic polynomial, but Win32, .NET Forms, or WPF do not provide methods to draw a piecewise cubic polynomial curve. So, to draw that spline, we have to invent an effective algorithm to approximate a cubic polynomial with polyline, which isn't trivial (word “effective” is a point!).
2. Cubic spline algorithms are usually designed to deal with functions in the Cartesian coordinates, y=f(x). This implies that the function is single valued; it isn't always appropriate.

On the other hand, the platform provides us with a suite of Bezier curve drawing methods. Bezier curve is a special representation of a cubic polynomial expressed in the parametric form (so it isn't the subject of single valued function restriction). Bezier curves start and end with two points often named “knots”; the form of the curve is controlled by two more points known as “control points”.

Bezier spline is a sequence of individual Bezier curves joined to form a whole curve. The trick to making it a spline is to calculate control points in such a way that the whole spline curve has two continuous derivatives.

I spent some time Googling for a code in any C-like language for a Bezier spline, but couldn't found any cool, ready-to-use code.

Here, we'll deal with open-ended curves, but the same approach could be applied to the closed curves.

## Bezier Curve Representation

A Bezier curve on a single interval is expressed as:

`B(t)=(1-t)<sup>3</sup>P<sub>0</sub>+3(1-t)<sup>2</sup>tP<sub>1</sub>+3(1-t)t<sup>2</sup>P<sub>2</sub>+t<sup>3</sup>P<sub>3</sub> (1) `

where `t` is in `[0,1]`, and

1. `P<sub>0</sub>` – first knot point
2. `P<sub>1</sub>` – first control point (close to `P0`)
3. `P<sub>2</sub>` – second control point (close to `P3`)
4. `P<sub>3</sub>` – second knot point

The first derivative of (1) is:

`B’(t)=-3(1-t)<sup>2</sup>P<sub>0</sub>+3(3t<sup>2</sup>–4t+1)P<sub>1</sub>+3(2t–3t<sup>2</sup>)P<sub>2</sub>+3t<sup>2</sup>P<sub>3</sub> `

The second derivative of (1) is:

`B’’(t)=6(1 - t)P<sub>0</sub>+3(6t-4)P<sub>1</sub>+3(2–6t)P<sub>2</sub>+6tP<sub>3</sub> `

## Single Segment

If we have just two knot points, our "smooth" Bezier curve should be a straight line, i.e. in (1) the coefficients in the members with the power 2 and 3 should be zero. It's easy to deduce that its control points should be calculated as:

`3P<sub>1</sub> = 2P<sub>0</sub> + P<sub>3</sub> P<sub>2</sub> = 2P<sub>1</sub> – P<sub>0</sub> `

## Multiple Segments

This is the case where we have more than two points. One more time: to make a sequence of individual Bezier curves to be a spline, we should calculate Bezier control points so that the spline curve has two continuous derivatives at knot points.

Considering a set of piecewise Bezier curves with `n+1` points and `n` subintervals, the `(i-1)`-th curve should connect to the `i`-th one. Now we will denote the points as follows:

1. `P<sub>i</sub>``i`th knot point (`i=1,..,n`)
2. `P1<sub>i</sub>` – first control point close to `P<sub>i</sub>`
3. `P2<sub>i</sub>` – second control point close to `P<sub>i</sub>`

At the `i`th subinterval, the Bezier curve will be:

`B<sub>i</sub>(t)=(1-t)<sup>3</sup>P<sub>i-1</sub>+3(1-t)<sup>2</sup>tP1<sub>i</sub>+3(1-t)t<sup>2</sup>P2<sub>i</sub>+t<sup>3</sup>P<sub>i</sub>; (i=1,..,n) `

The first derivative at the `i`th subinterval is:

`B’<sub>i</sub>(t)=-3(1-t)<sup>2</sup>P<sub>i-1</sub>+3(3t<sup>2</sup>-4t+1)P1<sub>i</sub>+3(2t-3t<sup>2</sup>)P2<sub>i</sub>+3t<sup>2</sup>P<sub>i</sub>; (i=1,..,n) `

The first derivative continuity condition `B’<sub>i-1</sub>(1)=B’<sub>i</sub>(0)` gives:

`P1<sub>i</sub>+P2<sub>i-1</sub> = 2P<sub>i-1</sub>; (i=2,..,n) (2) `

The second derivative at the `i`th subinterval is:

`B’’<sub>i</sub>(t)=6(1-t)P<sub>i-1</sub>+6(3t-2)P1<sub>i</sub>+6(1-3t)P2<sub>i</sub>+6tP<sub>i</sub>; (i=1,..,n) `

The second derivative continuity condition B’’i-1(1)=B’’i(0) gives:

`P1<sub>i-1</sub>+2P1<sub>i</sub>=P2<sub>i</sub>+2P2<sub>i-1</sub>; (i=2,..,n) (3) `

Then, as always with splines, we'll add two more conditions at the ends of the total interval. These will be the “natural conditions” `B’’<sub>1</sub>(0) = 0` and `B’’<sub>n</sub>(1) = 0`.

`2P1<sub>1</sub>-P2<sub>1</sub> = P<sub>0</sub> (4) 2P2<sub>n</sub>-P1<sub>n</sub> = P<sub>n</sub> (5) `

Now, we have `2n` conditions (2-5) for `n` control points `P1 `and `n `control points `P2`. Excluding `P2`, we'll have `n `equations for `n `control points `P1`:

```2P1<sub>1</sub> + P1<sub>2</sub> = P<sub>0</sub> + 2P<sub>1</sub> P1<sub>1</sub> + 4P1<sub>2</sub> + P1<sub>3</sub> = 4P<sub>1</sub> + 2P<sub>2</sub> .... P1<sub>i-1</sub> + 4P1<sub>i</sub> + P1<sub>i+1</sub> =
4P<sub>i-1</sub> + 2P<sub>i</sub> (6) .... P1<sub>n-2</sub> + 4P1<sub>n-1</sub> + P1<sub>n</sub> = 4P<sub>n-2</sub> + 2P<sub>n-1</sub> 2P1<sub>n-1</sub> + 7P1<sub>n</sub> = 8P<sub>n-1</sub> + P<sub>n</sub> ```

System (6) is the tridiagonal one with the diagonal dominance, hence we can solve it by simple variable elimination without any tricks.

When `P1` is found, `P2` could be calculated from (2) and (5).

## The Code

```/// <summary>
/// Bezier Spline methods
/// </summary>
public static class BezierSpline
{
/// <summary>
/// Get open-ended Bezier Spline Control Points.
/// </summary>
/// <param name="knots">Input Knot Bezier spline points.</param>
/// <param name="firstControlPoints">Output First Control points
/// array of knots.Length - 1 length.</param>
/// <param name="secondControlPoints">Output Second Control points
/// array of knots.Length - 1 length.</param>
/// <exception cref="ArgumentNullException"><paramref name="knots"/>
/// parameter must be not null.</exception>
/// <exception cref="ArgumentException"><paramref name="knots"/>
/// array must contain at least two points.</exception>
public static void GetCurveControlPoints(Point[] knots,
out Point[] firstControlPoints, out Point[] secondControlPoints)
{
if (knots == null)
throw new ArgumentNullException("knots");
int n = knots.Length - 1;
if (n < 1)
throw new ArgumentException
("At least two knot points required", "knots");
if (n == 1)
{ // Special case: Bezier curve should be a straight line.
firstControlPoints = new Point[1];
// 3P1 = 2P0 + P3
firstControlPoints[0].X = (2 * knots[0].X + knots[1].X) / 3;
firstControlPoints[0].Y = (2 * knots[0].Y + knots[1].Y) / 3;

secondControlPoints = new Point[1];
// P2 = 2P1 – P0
secondControlPoints[0].X = 2 *
firstControlPoints[0].X - knots[0].X;
secondControlPoints[0].Y = 2 *
firstControlPoints[0].Y - knots[0].Y;
return;
}

// Calculate first Bezier control points
// Right hand side vector
double[] rhs = new double[n];

// Set right hand side X values
for (int i = 1; i < n - 1; ++i)
rhs[i] = 4 * knots[i].X + 2 * knots[i + 1].X;
rhs[0] = knots[0].X + 2 * knots[1].X;
rhs[n - 1] = (8 * knots[n - 1].X + knots[n].X) / 2.0;
// Get first control points X-values
double[] x = GetFirstControlPoints(rhs);

// Set right hand side Y values
for (int i = 1; i < n - 1; ++i)
rhs[i] = 4 * knots[i].Y + 2 * knots[i + 1].Y;
rhs[0] = knots[0].Y + 2 * knots[1].Y;
rhs[n - 1] = (8 * knots[n - 1].Y + knots[n].Y) / 2.0;
// Get first control points Y-values
double[] y = GetFirstControlPoints(rhs);

// Fill output arrays.
firstControlPoints = new Point[n];
secondControlPoints = new Point[n];
for (int i = 0; i < n; ++i)
{
// First control point
firstControlPoints[i] = new Point(x[i], y[i]);
// Second control point
if (i < n - 1)
secondControlPoints[i] = new Point(2 * knots
[i + 1].X - x[i + 1], 2 *
knots[i + 1].Y - y[i + 1]);
else
secondControlPoints[i] = new Point((knots
[n].X + x[n - 1]) / 2,
(knots[n].Y + y[n - 1]) / 2);
}
}

/// <summary>
/// Solves a tridiagonal system for one of coordinates (x or y)
/// of first Bezier control points.
/// </summary>
/// <param name="rhs">Right hand side vector.</param>
/// <returns>Solution vector.</returns>
private static double[] GetFirstControlPoints(double[] rhs)
{
int n = rhs.Length;
double[] x = new double[n]; // Solution vector.
double[] tmp = new double[n]; // Temp workspace.

double b = 2.0;
x[0] = rhs[0] / b;
for (int i = 1; i < n; i++) // Decomposition and forward substitution.
{
tmp[i] = 1 / b;
b = (i < n - 1 ? 4.0 : 3.5) - tmp[i];
x[i] = (rhs[i] - x[i - 1]) / b;
}
for (int i = 1; i < n; i++)
x[n - i - 1] -= tmp[n - i] * x[n - i]; // Backsubstitution.

return x;
}
}```

Although I compiled this code in C# 3.0, I don’t see why it can’t be used without any modification in C# 2.0, and even in C# 1.0 if you remove the keyword “`static`” from the class declaration.

Note that the code uses the `System.Windows.Point` structure, so it is intended for use with Windows Presentation Foundation, and the `using System.Windows;` directive is required. But all you should do to use it with Windows Forms is to replace the `System.Windows.Point` type with `System.Drawing.PointF`. Equally, it is straightforward to convert this code to C/C++, if desired.

## The Sample

The sample supplied with this article is a Visual Studio 2008 solution targeted at .NET 3.5. It contains a WPF Windows Application project designed to demonstrate some curves drawn with the Bezier spline above. You can select one of the curves from the combo box at the top of the window, experiment with the point counts, and set appropriate XY scales. You can even add your own curve, but this requires coding as follows:

1. Add your curve name to the `CurveNames` enum.
3. Add a call to your curve in the `OnRender` override.

In the sample, I use `Path` elements on the custom `Canvas` to render the curve, but in a real application, you would probably use a more effective approach like visual layer rendering.

## History

• 18th December, 2008: Initial post
• 23rd March, 2009: Second article revision with the following corrections and additions:
1. The most important is the bug fix. This bug as well as its correction was found by Peter Lee. A lot of thanks to him! This bug produced visually distinguishable behavior in the case of small knot points count.
2. `GetCurveControlPoints` now throw exceptions if invalid parameter is passed.
3. Added special handling of the case where knots array has just two points

## Share

No Biography provided

 United States
No Biography provided

## You may also be interested in...

 Pro

 First PrevNext
 Great article Member 1216949826-Nov-15 12:52 Member 12169498 26-Nov-15 12:52
 Adding Start and End-Tangent Member 1007739015-Oct-15 0:28 Member 10077390 15-Oct-15 0:28
 A brief clarification a1jrj1-Dec-12 2:09 a1jrj 1-Dec-12 2:09
 I don't know how these formula can become to that codes....? Jeffrey639417-Oct-12 0:27 Jeffrey6394 17-Oct-12 0:27
 Cannot see equation Alexandr.Pi21-Jun-12 4:34 Alexandr.Pi 21-Jun-12 4:34
 Re: Cannot see equation Peter Lee22-Jun-12 22:09 Peter Lee 22-Jun-12 22:09
 Problem with drawing Bezier spline yamelkaya14-Jun-12 23:43 yamelkaya 14-Jun-12 23:43
 how can i generate different number of Points from constant number of knots engkhaledd28-Feb-12 11:49 engkhaledd 28-Feb-12 11:49
 My vote of 5 Member 820478518-Jan-12 4:35 Member 8204785 18-Jan-12 4:35
 Great Job! cdrake19-Dec-11 8:59 cdrake 19-Dec-11 8:59
 My vote of 5 BlazeCell1-Dec-11 17:59 BlazeCell 1-Dec-11 17:59
 Blocks of lines appearing while drawing the curve. deeptigp22-Oct-11 8:16 deeptigp 22-Oct-11 8:16
 My vote of 5 Susan Spencer11-Jun-11 9:34 Susan Spencer 11-Jun-11 9:34
 Smoth curves for signature GauravKP21-Feb-11 2:24 GauravKP 21-Feb-11 2:24
 Use in graph sketching... xian12323-Oct-10 8:21 xian123 23-Oct-10 8:21
 tridiagonal system calonix23-May-10 11:27 calonix 23-May-10 11:27
 More than one control points dineshreddy.cs9-Mar-10 0:35 dineshreddy.cs 9-Mar-10 0:35
 Curl between 2 knots Jean-LucM30-Sep-09 6:09 Jean-LucM 30-Sep-09 6:09
 Re: Curl between 2 knots Oleg V. Polikarpotchkin1-Oct-09 20:41 Oleg V. Polikarpotchkin 1-Oct-09 20:41
 Re: Curl between 2 knots Jean-LucM2-Oct-09 6:43 Jean-LucM 2-Oct-09 6:43
 Re: Curl between 2 knots Oleg V. Polikarpotchkin2-Oct-09 19:40 Oleg V. Polikarpotchkin 2-Oct-09 19:40
 Re: Curl between 2 knots Jean-LucM3-Oct-09 3:34 Jean-LucM 3-Oct-09 3:34
 Re: Curl between 2 knots Oleg V. Polikarpotchkin3-Oct-09 20:10 Oleg V. Polikarpotchkin 3-Oct-09 20:10
 Re: Curl between 2 knots Jean-LucM6-Oct-09 6:59 Jean-LucM 6-Oct-09 6:59
 Re: Curl between 2 knots Oleg V. Polikarpotchkin7-Oct-09 21:06 Oleg V. Polikarpotchkin 7-Oct-09 21:06
 Re: Curl between 2 knots Oleg V. Polikarpotchkin7-Oct-09 21:24 Oleg V. Polikarpotchkin 7-Oct-09 21:24
 Re: Curl between 2 knots Jean-LucM16-Oct-09 4:53 Jean-LucM 16-Oct-09 4:53
 Question about the equation neo30816-Sep-09 13:29 neo308 16-Sep-09 13:29
 Re: Question about the equation Oleg V. Polikarpotchkin16-Sep-09 20:36 Oleg V. Polikarpotchkin 16-Sep-09 20:36
 Re: Question about the equation neo30818-Sep-09 4:34 neo308 18-Sep-09 4:34
 Visual layer rendering. tinatran3022-Jul-09 17:28 tinatran30 22-Jul-09 17:28
 Re: Visual layer rendering. Oleg V. Polikarpotchkin22-Jul-09 18:47 Oleg V. Polikarpotchkin 22-Jul-09 18:47
 I used this algorithm in a project very dear to me. Akatz71221-Jul-09 16:51 Akatz712 21-Jul-09 16:51
 Excellent Luc Pattyn25-Mar-09 1:58 Luc Pattyn 25-Mar-09 1:58
 Re: Excellent Oleg V. Polikarpotchkin25-Mar-09 4:21 Oleg V. Polikarpotchkin 25-Mar-09 4:21
 A mistake in the last equation which causes a strange behavior (corrected) Peter Lee16-Mar-09 5:35 Peter Lee 16-Mar-09 5:35
 Re: A mistake in the last equation which causes a strange behavior (corrected) Peter Lee16-Mar-09 5:47 Peter Lee 16-Mar-09 5:47
 Re: A mistake in the last equation which causes a strange behavior (corrected) Oleg V. Polikarpotchkin19-Mar-09 0:55 Oleg V. Polikarpotchkin 19-Mar-09 0:55
 Re: A mistake in the last equation which causes a strange behavior (corrected) twerd.ster12-Dec-09 8:51 twerd.ster 12-Dec-09 8:51
 algorithm behavior bstrack9-Mar-09 14:45 bstrack 9-Mar-09 14:45
 Re: algorithm behavior Oleg V. Polikarpotchkin9-Mar-09 19:36 Oleg V. Polikarpotchkin 9-Mar-09 19:36
 Need Help on the closed curves wang200226-Feb-09 16:08 wang2002 26-Feb-09 16:08
 Re: Need Help on the closed curves Oleg V. Polikarpotchkin27-Feb-09 18:14 Oleg V. Polikarpotchkin 27-Feb-09 18:14
 Re: Need Help on the closed curves Oleg V. Polikarpotchkin1-Mar-09 5:27 Oleg V. Polikarpotchkin 1-Mar-09 5:27
 Great article Cedric Moonen18-Dec-08 9:12 Cedric Moonen 18-Dec-08 9:12
 Re: Great article Oleg V. Polikarpotchkin18-Dec-08 17:58 Oleg V. Polikarpotchkin 18-Dec-08 17:58
 Variable Names John Simmons / outlaw programmer18-Dec-08 2:11 John Simmons / outlaw programmer 18-Dec-08 2:11
 Re: Variable Names Oleg V. Polikarpotchkin18-Dec-08 17:39 Oleg V. Polikarpotchkin 18-Dec-08 17:39
 Re: Variable Names Herbert Sauro22-Dec-08 12:03 Herbert Sauro 22-Dec-08 12:03
 Last Visit: 31-Dec-99 19:00     Last Update: 24-Mar-17 3:11 Refresh 12 Next »