Bezier timed animation path

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

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);

The control points of a bezier curve are in fact exactly what you get by adding the desired velocity vector at each end point to the end point. For example, if you want velocity vx0,vy0 at point x0,y0 and then to proceed to point x1,y1 arriving there with velocity vx1,vy1, then use the following four points to define your bezier curve: (x0,y0); (x0+vx0,y0+vy0); (x1-vx1,y1-vy1); (x1,y1). (the middle two are your control points.)