Bezier timed animation path

Question

Hi,

I'm trying to define a path of points. Each point has an x, y, and time. I then want to query this path and get the current position at that point in time. Let me share some pseudo code.

point {x, y, time}


function initialisePath(point[] path) {
    ... // Create Bezier Path
}

function getXYAtTime(time) {
    return ... // Get interpolated point along the bezier path at the specified time
}

I'm trying to implement this in javascript using the canvas tag. However a sample in any language will do. Does anyone know any open source library (in any language) that creates this kind of queriable path??

Note: I've been trying to get my head around this sample and code from the DynApi project but moving from this sample to a time aware path is a stretch for my poor animational skills.

Thanks

Guido

Answer 1

A Bézier curve has not only a start and end point but also control points that guide the shape of the curve. In the DynApi demo you linked, the end points are marked in yellow, and the control points are marked in red.

Your path will be a sequence of Bézier curves, connected end-to-end.

So let's take your pseudocode, but we'll treat all points that do not have a .time property to be control points.

function Path(points) {
    this.points = points;

    // Sanity check.
    if (points[0].time == undefined || points[points.length - 1].time == undefined)
        throw new Error("all control points must be between two real points");
}

Path.prototype.getXYAtTime = function (t) {
    var points = this.points;

    // First, see if t is out of range.
    if (t < points[0].time)
        return points[0];
    if (t > points[points.length - 1].time)
        return points[points.length - 1];

    // OK, t is in range. Find out which Bezier curve we're in.
    //
    // Specifically we want 'start' and 'stop' to be the indexes of two points
    // that each have a .time property, bracketing the current time t; and
    // all the points in between 'start' and 'stop' should be control points.
    //
    var start = 0, stop = points.length - 1;
    for (var i = 1; i < points.length; i++) {
        var p = points[i];
        if (t < p.time) {
            stop = i;
            break;
        }
        if (p.time != undefined)
            start = i;
    }
    var n = stop - start;

    // Adjust t to be in the range [0, 1).
    var t0 = points[start].time, t1 = points[stop].time;
    t = (t - t0) / (t1 - t0);
    var tInv = 1 - t;

    // Now calculate the current position in the curve.
    // Wikipedia says this is:
    //   sum for i = 0 to n of (n C i * (1 - t) ^ (n - i) * t ^ i * P[i])
    // 
    var x = 0, y = 0;
    for (var i = 0; i <= n; i++) {
        var p = points[start + i];
        var c = nCr(n, i) * Math.pow(1 - t, n - i) * Math.pow(t, i);
        x += c * p.x;
        y += c * p.y;
    }
    return {x: x, y: y};
}

// The number of k-combinations of a set of size n.
function nCr(n, k) {
    var z = 1;
    for (var i = 1; i <= k; i++)
        z *= (n + 1 - i) / i;
    return z;
}

So that's the math part done. It's up to you to hook it up to canvas and make it go.

Here's how you call that method:

// Here's a Path consisting of a single Bezier curve.
var path = new Path([
    {x: 200, y: 150, time: 0},  // start point
    {x: 200, y: 500},           // 2 control points
    {x: 250, y: 100},
    {x: 500, y: 300, time: 50}  // end point
  ]);

var p = path.getXYAtTime(2.718);
alert(p.x + ", " + p.y);