XNA CatmullRom Curves

Question

I'm in need of some clarification over a technique I'm trying. I'm trying to move an entity from point A to point B, but I don't want the entity to travel in a straight line.

For example if the entity is positioned at x: 0, y:0 and I want to get to point x:50, y: 0, I want the entity to travel in a curve to the target, I would imagine the maximum distance it would be away is x:25 y: 25 so it's travelled on the X towards the target but has moved away from the target on the y.

I've investigated a couple of options including splines, curves but what I thought would do the job is the CatmullRom curve. I'm a bit confused how to use it? I want to know where to move my entity each frame rather than what the function returns which is the interpolation. I would appreciate some gudiance as to how to use it.

If there's any alternative methods which might be easier that I've missed, I'd appreciate hearing them as well.

Edit:

To show how I'm getting a curve:

Vector2 blah = Vector2.CatmullRom(
    StartPosition, 
    new Vector2(StartPosition.X + 5, StartPosition.Y + 5), 
    new Vector2(StartPosition.X + 10, StartPosition.Y + 5), 
    /*This is the end position*/ 
    new Vector2(StartPosition.X + 15, StartPosition.Y), 0.25f);

The idea eventually is I generate these points on the fly but I'm just trying to work it out at the moment.

Answer 1

As you've noticed, splines produce line segments of different lengths. The tighter the curve, the shorter the segments. This is fine for display purposes, not so useful for path generation for mobiles.

To get a reasonable approximation of a constant-speed traversal of a spline path, you need to do some interpolation along the segments of the curve. Since you already have a set of line segments (between pairs of points returned by Vector2.CatmullRom()) you need an method of walking those segments in constant speed.

Given a set of points and a total distance to move along the path defined as lines between those points, the following (more-or-less pseudo-)code will find a point that lies a specific distance along the path:

Point2D WalkPath(Point2D[] path, double distance)
{
    Point curr = path[0];
    for (int i = 1; i < path.Length; ++i)
    {
        double dist = Distance(curr, path[i]);
        if (dist < distance)
            return Interpolate(curr, path[i], distance / dist;

        distance -= dist;
        curr = path[i];
    }
    return curr;
}

There are various optimizations you can do to speed this up, such as storing the path distance with each point in the path to make it easier to lookup during a walk operation. This becomes more important as your paths get more complex, but is probable overkill for a path with only a few segments.

Edit: Here's an example that I did with this method in JavaScript a while back. It's a proof-of-concept, so don't look too critically at the code :P

Edit: more information on spline generation
Given a set of 'knot' points - being points that a curve must pass through in sequence - the most obvious fit for a curve algorithm is Catmull-Rom. The downside is that C-R needs two additional control points that can be awkward to generate automatically.

A while back I found a fairly useful article online (which I can't locate anymore to give correct attribution) that calculated a set of control points based on the locations of sets of points within your path. Here's my C# code for the method that calculates the control points:

// Calculate control points for Point 'p1' using neighbour points
public static Point2D[] GetControlsPoints(Point2D p0, Point2D p1, Point2D p2, double tension = 0.5)
{
    // get length of lines [p0-p1] and [p1-p2]
    double d01 = Distance(p0, p1);
    double d12 = Distance(p1, p2);
    // calculate scaling factors as fractions of total
    double sa = tension * d01 / (d01 + d12);
    double sb = tension * d12 / (d01 + d12);
    // left control point
    double c1x = p1.X - sa * (p2.X - p0.X);
    double c1y = p1.Y - sa * (p2.Y - p0.Y);
    // right control point
    double c2x = p1.X + sb * (p2.X - p0.X);
    double c2y = p1.Y + sb * (p2.Y - p0.Y);
    // return control points
    return new Point2D[] { new Point2D(c1x, c1y), new Point2D(c2x, c2y) };
}

The tension parameter adjusts the control point generation to change the tightness of the curve. Higher values result in broader curves, lower values in tighter curves. Play with it and see what value works best for you.

Given a set of 'n' knots (points on the curve), we can generate a set of control points that will be used to generate the curves between pairs of knots:

// Generate all control points for a set of knots
public static List<Point2D> GenerateControlPoints(List<Point2D> knots)
{
    if (knots == null || knots.Count < 3)
        return null;
    List<Point2D> res = new List<Point2D>();
    // First control point is same as first knot
    res.Add(knots.First());
    // generate control point pairs for each non-end knot 
    for (int i = 1; i < knots.Count - 1; ++i)
    {
        Point2D[] cps = GetControlsPoints(knots[i - 1], knots[i], knots[i+1]);
        res.AddRange(cps);
    }
    // Last control points is same as last knot
    res.Add(knots.Last());
    return res;
}

So now you have an array of 2*(n-1) control points, which you can then use to generate the actual curve segments between the knot points.

public static Point2D LinearInterp(Point2D p0, Point2D p1, double fraction)
{
    double ix = p0.X + (p1.X - p0.X) * fraction;
    double iy = p0.Y + (p1.Y - p0.Y) * fraction;
    return new Point2D(ix, iy);
}

public static Point2D BezierInterp(Point2D p0, Point2D p1, Point2D c0, Point2D c1, double fraction)
{
    // calculate first-derivative, lines containing end-points for 2nd derivative
    var t00 = LinearInterp(p0, c0, fraction);
    var t01 = LinearInterp(c0, c1, fraction);
    var t02 = LinearInterp(c1, p1, fraction);
    // calculate second-derivate, line tangent to curve
    var t10 = LinearInterp(t00, t01, fraction);
    var t11 = LinearInterp(t01, t02, fraction);
    // return third-derivate, point on curve
    return LinearInterp(t10, t11, fraction);
}

// generate multiple points per curve segment for entire path
public static List<Point2D> GenerateCurvePoints(List<Point2D> knots, List<Point2D> controls)
{
    List<Point2D> res = new List<Point2D>();
    // start curve at first knot
    res.Add(knots[0]);
    // process each curve segment
    for (int i = 0; i < knots.Count - 1; ++i)
    {
        // get knot points for this curve segment
        Point2D p0 = knots[i];
        Point2D p1 = knots[i + 1];
        // get control points for this curve segment
        Point2D c0 = controls[i * 2];
        Point2D c1 = controls[i * 2 + 1];
        // calculate 20 points along curve segment
        int steps = 20;
        for (int s = 1; s < steps; ++s)
        {
            double fraction = (double)s / steps;
            res.Add(BezierInterp(p0, p1, c0, c1, fraction));
        }
    }
    return res;
}

Once you have run this over your knots you now have a set of interpolated points that are a variable distance apart, distance depending on the curvature of the line. From this you run the original WalkPath method iteratively to generate a set of points that are a constant distance apart, which define your mobile's progression along the curve at constant speed.

The heading of your mobile at any point in the path is (roughly) the angle between the points on either side. For any point n in the path, the angle between p[n-1] and p[n+1] is the heading angle.

// get angle (in Radians) from p0 to p1
public static double AngleBetween(Point2D p0, Point2D p1)
{
    return Math.Atan2(p1.X - p0.X, p1.Y - p0.Y);
}

I've adapted the above from my code, since I use a Point2D class I wrote ages ago that has a lot of the functionality - point arithmetic, interpolation, etc - built in. I might have added some bugs during translation, but hopefully they'll be easy to spot when you're playing with it.

Let me know how it goes. If you run into any particular difficulties I'll see what I can do to help.