CODEWITHSUNDEEP
algorithmluainterpolationcurve-fittingbezier
stack2015
stack2015

Reputation: 11

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

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: 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?

Upvotes: 1

Views: 3140

Answers (2)

Steve Hanov
Steve Hanov

Reputation: 11584

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:

  1. Refine: Place a point in the middle of each edge.
  2. Dual: Place a point in the middle of each edge and remove the old points.
  3. Repeat the Dual step several times.
  4. 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);
}

Upvotes: 1

Niccolo M.
Niccolo M.

Reputation: 3413

You don't need to know math to do this.

Connect each point with the next point with a separate Bezier curve.

Bezier curves have "handles" attached to their end points. These handles are tangent to the curve (at the end points). To make a "smooth" path all you need to do is make the handles of every two adjacent Bezier curves "sit" on one line.

To understand this, experiment with a drawing program like GIMP (but probably almost any other software will do). Such programs even have a special key to make the "handles" of adjacent curves sit on a straight line (and be of the same length).

The only "hard" mathematical decision you'll have to make is to determine the lengths of these handles. Experiment. You might want to make it dependent on how far each 3 consecutive points deviate from being on a straight line, or on the distance between the points.

Lastly, as for moving a point (your "object") along the curve at a seemingly constant speed: You can use an adaptation of a method like this one.

Upvotes: -3

Related Questions