Thursday, April 1, 2010

Nice Curves! - Catmull–Rom spline in C#

Download sample code

Suppose you have a series of points that define a region.

points

When you “join-the-dots” you end up with something that looks quite “pointy”.

lines

What if you want your region to look a little curvier than this?

Splines are a great way of calculating extra points between these key points to allow you to create much more organic and natural looking regions.

In this example I used a Catmull-Rom Spline to create curves from a limited set of points. Catmull-Rom is a good spline algorithm to use if you need the line to pass through the points that you define, but appear as curved as possible. It is quite often used for calculating camera tracks from key frames in the field of computer graphics.

The Catmull-Rom requires 4 points, and it calculates the spline points between the 2nd and 3rd points.

catmullrom_spline

The algorithm uses the 1st and 4th points as targets for the smoothing of the curve.

Here is the code to generate a single spline point from the list of key points.


/// <summary>
/// Calculates interpolated point between two points using Catmull-Rom Spline/// </summary>
/// <remarks>
/// Points calculated exist on the spline between points two and three./// </remarks>
/// <param name="p0">First Point</param>
/// <param name="p1">Second Point</param>
/// <param name="p2">Third Point</param>
/// <param name="p3">Fourth Point</param>
/// <param name="t">
/// Normalised distance between second and third point /// where the spline point will be calculated/// </param>
/// <returns>
/// Calculated Spline Point/// </returns>static public PointF PointOnCurve(PointF p0, PointF p1, PointF p2, PointF p3, float t)
{
    PointF ret = new PointF();

    float t2 = t * t;
    float t3 = t2 * t;

    ret.X = 0.5f * ((2.0f * p1.X) +
    (-p0.X + p2.X) * t +
    (2.0f * p0.X - 5.0f * p1.X + 4 * p2.X - p3.X) * t2 +
    (-p0.X + 3.0f * p1.X - 3.0f * p2.X + p3.X) * t3);

    ret.Y = 0.5f * ((2.0f * p1.Y) +
    (-p0.Y + p2.Y) * t +
    (2.0f * p0.Y - 5.0f * p1.Y + 4 * p2.Y - p3.Y) * t2 +
    (-p0.Y + 3.0f * p1.Y - 3.0f * p2.Y + p3.Y) * t3);

    return ret;
}

In order to use this function you must pass in the four points that describe the spline. The spline point itself is only generated between points 2 and 3. The parameter t is the normalised distance between points 2 and 3 for which we are calculating the spline point. This means that this is the distance on the arc between the 2nd and 3rd point on a scale of 0 to 1 - 0 being point 2 and 1 being point 3. For instance, a value of 0.5 will be half-way between points 2 and 3, 0.25 a quarter of the way, etc.

Therefore, in order to calculate the arc between points 2 and 3 to a resolution of 10 points, we will have to call this method 9 times with values of t of 0.1, 0.2, 0.3, 0.4 etc.

As is discussed in this Stack Overflow article, a better explanation of the maths behind Catmull-Rom splines is available here: http://www.mvps.org/directx/articles/catmull/

I have produced a sample application that allows the user to click within the window to create key points, and then hit the “Calculate” button to generate the spline points, which is then rendered as a continuous curve, intersecting each point.


catmullrom


Here is the example solution on Github.

3 comments:

  1. There are 1D, 2D, 3D, and 4D Hermite and Catmull-Rom splines here, symboliccomputation.com/vectorlibrary.htm. You'll find them in the MathHelper, Vector2, Vector3, and Vector4 classes in the library. Free, open source, C#.

    ReplyDelete
  2. This was an ENORMOUS help to me. I easily adapted this style to a Vector3-style points. I am working on capturing rotation from Vector3 to Vector 3 as well (from the transforms housing the Vectors's). Your work really clarified Catmull-Rom for me, thank you!

    ReplyDelete