Motion paths using cardinal splines

Question

I reformatted some code I found to use cardinal splines and draw a curve given a set of points to work with my Canvas library, which works quite nicely, but then I wanted to also use said technique to move objects along a given set of points -- a path. SO had several questions pertaining to my problem, and I've tried to implement the last answer of this question, but I honestly have no idea what half the variables in his code mean. Here's my library, and the curve object by itself:

Art.prototype.modules.display.Base.extend({
  constructor: function (options) {

    // Declare variables for brevity.

    var extend = Art.prototype.modules.utility.extend,
      defaults = {
        points: [],
        tension: 0.5,
        closed: false
      };

    // Extend the object with the defaults overwritten by the options.

    extend(this, extend(defaults, options));

  },
  id: 'curve',
  draw: function () {

    // Declare variables for brevity.

    var t = this,
      graphics = Art.prototype.modules.display.curve.core.graphics,
      controls = [],
      n = t.points.length,
      getControlPoints = function (a, b, c, d, e, f, tension) {
        var x = {
          x: Math.sqrt(Math.pow(c - a, 2) + Math.pow(d - b, 2)),
          y: Math.sqrt(Math.pow(e - c, 2) + Math.pow(f - d, 2))
        };
        var y = {
          x: tension * x.x / (x.x + x.y)
        };
        y.y = tension - y.x;
        var z = {
          x: c + y.x * (a - e),
          y: d + y.x * (b - f)
        };
        var $z = {
          x: c - y.y * (a - e),
          y: d - y.y * (b - f)
        };
        return [z.x, z.y, $z.x, $z.y];
      };

    graphics.strokeStyle = t.stroke;

    graphics.lineWidth = t.lineWidth;

    if (t.closed) {
      t.points.push(t.points[0], t.points[1], t.points[2], t.points[3]);
      t.points.unshift(t.points[n - 1]);
      t.points.unshift(t.points[n - 1]);
      for (var p = 0; p < n; p += 2) {
        controls = controls.concat(getControlPoints(t.points[p], t.points[p + 1], t.points[p + 2], t.points[p + 3], t.points[p + 4], t.points[p + 5], t.tension));
      }
      controls = controls.concat(controls[0], controls[1]);
      for (var $p = 2; $p < n + 2; $p += 2) {
        graphics.beginPath();
        graphics.moveTo(t.points[$p], t.points[$p + 1]);
        graphics.bezierCurveTo(controls[2 * $p - 2], controls[2 * $p - 1], controls[2 * $p], controls[2 * $p + 1], t.points[$p + 2], t.points[$p + 3]);
        graphics.stroke();
        graphics.closePath();
      }
    } else {
      for (var p = 0; p < n - 4; p += 2) {
        controls = controls.concat(getControlPoints(t.points[p], t.points[p + 1], t.points[p + 2], t.points[p + 3], t.points[p + 4], t.points[p + 5], t.tension));
      }
      for (var $p = 2; $p < t.points.length - 5; $p += 2) {
        graphics.beginPath();
        graphics.moveTo(t.points[$p], t.points[$p + 1]);
        graphics.bezierCurveTo(controls[2 * $p - 2], controls[2 * $p - 1], controls[2 * $p], controls[2 * $p + 1], t.points[$p + 2], t.points[$p + 3]);
        graphics.stroke();
        graphics.closePath();
      }
      graphics.beginPath();
      graphics.moveTo(t.points[0], t.points[1]);
      graphics.quadraticCurveTo(controls[0], controls[1], t.points[2], t.points[3]);
      graphics.stroke();
      graphics.closePath();
      graphics.beginPath();
      graphics.moveTo(t.points[n - 2], t.points[n - 1]);
      graphics.quadraticCurveTo(controls[2 * n - 10], controls[2 * n - 9], t.points[n - 4], t.points[n - 3]);
      graphics.stroke();
      graphics.closePath();
    }

    return this;

  }
});

I don't necessarily want the code handed to me on a silver platter (although... that would be nice) -- rather, I want to learn the math involved, but preferably in psuedocode and in relatively simple terms. An explanation of the SO answer I linked to would be especially helpful, as it works nicely.

Answer 1

Using an alternative implementation (https://gitlab.com/epistemex/cardinal-spline-js disclaimer: I'm the author) will produce all points along the path that you need in a simple way.

• You can now calculate the total length
• Find the corresponding segment in the returned array
• Normalize the remainder to find exact location on the path

Example

After obtaining the points as a spline point array, the main function will iterate over the array to find the segment the two points the desired position is between. Next it will interpolate between those to get a final (x,y) position (there is plenty of room for optimization here):

This allows us to move along the spline with an even speed -

function getXY(points, pos, length) {

  var len = 0,             // total length so far
      lastLen,             // last segment length
      i,                   // iterator
      l = points.length;   // length of point array

  // find segment
  for(i = 2; i < l; i += 2) {

    // calculate length of this segment
    lastLen = dist(points[i], points[i+1], points[i-2], points[i-1]);

    // add to total length for now    
    len += lastLen;

    // are we inside a segment?
    if (pos < len && lastLen) {
      len -= lastLen;     // to back to beginning
      pos -= len;         // adjust position so we can normalize

      return {
        // interpolate  prev X + (next X - prev X) * normalized
        x: points[i-2] + (points[i] - points[i-2])   * (pos / lastLen),
        y: points[i-1] + (points[i+1] - points[i-1]) * (pos / lastLen)
      }
    }
  }
}

Full example

var ctx = document.querySelector("canvas").getContext("2d"),
    points = [
      10,  10,    // x,y pairs
      100, 50,
      500, 100,
      600, 200,
      400, 220,
      200, 90
    ],
    spline = getCurvePoints(points),
    length = getLength(spline),
    t = 0,
    dx = 3;  // number of pixels to move object

// move along path:
(function loop() {

  // make t ping-pong, and clamp t to [0, (length-1)]
  t += dx;
  if (t < 0 || t >= length) dx = -dx;
  t = Math.max(0, Math.min(length - 1, t));

  // find segment in points which t is inside:
  var pos = getXY(spline, t, length);

  // redraw
  ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height);
  render();

  // show marker
  ctx.fillRect(pos.x - 3, pos.y - 3, 6, 6);

  requestAnimationFrame(loop)
})();

function render(points) {
  ctx.beginPath();
  ctx.moveTo(spline[0], spline[1]);
  for(var i = 2; i < spline.length; i+=2)
    ctx.lineTo(spline[i], spline[i+1]);
  ctx.stroke()
}

function getXY(points, pos, length) {

  var len = 0, lastLen, i, l = points.length;

  // find segment
  for(i = 2; i < l; i += 2) {
    lastLen = dist(points[i], points[i+1], points[i-2], points[i-1]);

    len += lastLen;
    if (pos < len && lastLen) {
      len -= lastLen;
      pos -= len;

      return {
        x: points[i-2] + (points[i] - points[i-2]) * (pos / lastLen),
        y: points[i-1] + (points[i+1] - points[i-1]) * (pos / lastLen)
      }
    }
  }

  return null
}

function getLength(points) {
  for(var len = 0, i = 0, dx, dy; i < points.length - 2; i+=2) {
    len += dist(points[i+2], points[i+3], points[i], points[i+1])
  }
  return len
}

function dist(x1, y1, x2, y2) {
  var dx = x2 - x1,
      dy = y2 - y1;
  return Math.sqrt(dx*dx + dy*dy)
}