Creating cubic and/or quadratic Bezier curves to fit a path

Question

I am working on a 2D game in Lua. I have a path which is made up of a number of points, for example, points A to L:

I want to move an object smoothly along this path. To accomplish this, I wanted to create quadratic or cubic Bezier curves based on the points, and interpolate these curves. However, how do I fit the curves properly, such that the path isn't broken if eg. a curve stops and another starts in point F?

I think most solutions would assume a smooth curve at all points and not try to detect a break as in your point F. You might need to do that out-of-band, but that presents its own problem - what criteria do you use to determine a break? — Mark Ransom
Thanks for the reply. I don't know, and I think that's the root of the problem. Essentially the path needs corners like point F curved. Do I need to find some rotation value to indicate this maybe? — stack2015
No you don't. You want to make a smooth curve through the points, and you might want to ultimately render that using Beziers, but the last thing you want here is actual Bezier curves, which don't go through points. You want Catmull-Rom curves, which are related to Bezier curves but do go through specified points. In addition, can you (in your post) describe what "smoothly" means? If you're thinking fixed speed, for instance, Bezier curves make that quite hard. Lastly: can you also show the path you think should connect these points? Because that determines suitable curve fitting. — Mike 'Pomax' Kamermans
see Interpolation polynomial and Proper implementation of cubic spline interpolation ... use interpolation it goes through the points ... and if needed bezier then convert the control points to Bezier ones no fitting needed equations are in the links — Spektre

Steve Hanov Steve Hanov · Accepted Answer · 2015-11-05T15:07:01

Curve fitting is explained in this question: How can I fit a Bézier curve to a set of data?

However, there is a must easier method to interpolate the points. It goes this way:

Refine: Place a point in the middle of each edge.
Dual: Place a point in the middle of each edge and remove the old points.
Repeat the Dual step several times.
Repeat from step one until the curve is smooth enough.

You can easily see that it works on paper. The resulting curve begins to approximate a series of bezier splines.

It is described more formally in this PDF file (Section 3): http://www.cc.gatech.edu/~jarek/courses/handouts/curves.pdf

Here is some Javascript code to do it:

function bspline_smooth(points, order) {

    // insert a point in the middle of each edge.
    function _refine(points) {
      var i, index, len, point, refined;
      points = [points[0]].concat(points).concat(points[points.length-1]);
      refined = [];
      index = 0;
      for (i = 0, len = points.length; i < len; i++) {
        point = points[i];
        refined[index * 2] = point;
        if (points[index + 1]) {
          refined[index * 2 + 1] = _mid(point, points[index + 1]);
        }
        index += 1;
      }
      return refined;
    }

    // insert point in the middle of each edge and remove the old points.
    function _dual(points) {
      var dualed, i, index, len, point;
      dualed = [];
      index = 0;
      for (i = 0, len = points.length; i < len; i++) {
        point = points[i];
        if (points[index + 1]) {
          dualed[index] = _mid(point, points[index + 1]);
        }
        index += 1;
      }
      return dualed;
    }

    function _mid(a, b) {
      return new Point(
        a.x + ((b.x - a.x) / 2),
        a.y + ((b.y - a.y) / 2) );
    }

    if (!order) {
       return points;
    }
    return bspline_smooth(_dual(_dual(_refine(points))), order - 1);
}

Creating cubic and/or quadratic Bezier curves to fit a path

2 Answers