About Final Cut Pro Interpolation

Final Cut Pro uses both 1D and 2D Bezier curves to interpolate keyframes. The 2D Bezier algorithm is a simple extension of the 1D algorithm.

The heart of the math Final Cut Pro uses to find a given point on a Bezier curve is described in the article "Quick and Simple Bezier Curve Drawing" by Robert Miller, which appears in Graphic Gems Volume 5, page 206. Final Cut Pro modifies this algorithm to account for acceleration in a curve. As a result, Final Cut Pro users can change the velocity of motion into and out of a keyframe.

In Final Cut Pro, Bezier curves are represented by an approximation of a curve made up of 40 linear segments. The Bezier code itself is divided into two parts. The first part constructs a Bezier structure and calculates the location of all 40 constituent segments of the curve. The second part of the code finds the location of a given time on the curve.

To create the structure that represents a Bezier curve, Final Cut Pro first initializes a number of variables. This first set of variables—the acceleration coefficients— enables the user to ease the effect into the endpoints of the curve. This is done by biasing them either into or out of the endpoints using an exponential scaling factor to create a power curve.

Listing C-1  Acceleration coefficients

    leftScale = curve[i].scale[1];

    leftVal = pow(10, -leftScale)- 1.0;

    rightScale = curve[i+1].scale[0];

    rightVal = pow(10, -rightScale) - 1.0;

The scale values leftScale and rightScale are obtained from a UI widget. The values of this float scale factor range from 1 (biased away from the endpoint) to -1 (biased toward the endpoint).

Next, Final Cut Pro initializes the Cartesian location of the control points of the Bezier curve segment by looking at the values passed in as an array of Bezier points, FloatPt *seg. These values represent the location of the control points of the Bezier curve.

Listing C-2  Control points

MakeBezSegment(Bezier curve, int32 index, FloatPt *seg) {

    FloatPt temp;

    seg[0] = curve[index].location;

    seg[3] = curve[index+1].location;

    if (curve[index].vector[1].length == 0) {

        seg[1].h = seg[0].h + (seg[3].h - seg[0].h) / 2.0 / SCALE_MULT_CONST;

        seg[1].v = seg[0].v + (seg[3].v - seg[0].v) / 2.0 / SCALE_MULT_CONST;

    }

    else {

        PolarToCart(&curve[index].vector[1], &temp);

        seg[1].h = seg[0].h + temp.h * SCALE_MULT_CONST;

        seg[1].v = seg[0].v + temp.v * SCALE_MULT_CONST;

    }

    if (curve[index+1].vector[0].length == 0) {

        seg[2].h = seg[3].h + (seg[0].h - seg[3].h) / 2.0 / SCALE_MULT_CONST;

        seg[2].v = seg[3].v + (seg[0].v - seg[3].v) / 2.0 / SCALE_MULT_CONST;

    }

    else {

        PolarToCart(&curve[index+1].vector[0], &temp);

        seg[2].h = seg[3].h + temp.h * SCALE_MULT_CONST;

        seg[2].v = seg[3].v + temp.v * SCALE_MULT_CONST;

    }

}

With this initialization work complete, Final Cut Pro now employs the algorithm found in the Robert Miller article to quickly and iteratively compute the location of points on the curve. First, Final Cut Pro initializes the values of the vertices of the control polygon of the Bezier curve:

Listing C-3  Locations

BezierForm(FloatPt *p, FloatPt *c, int numCtlPoints) {

    Int32 i, multiplier;

    for (i = 0; i <= numCtlPoints - 1; i++) {

        if (i == 0) multiplier = 1;

        else if (i == 1) multiplier = numCtlPoints - 1;

        else multiplier = multiplier * (numCtlPoints - i) / i;

        c[k].h = p[k].h * multiplier;

        c[k].v = p[k].v * multiplier;

    }

}

Now Final Cut Pro is ready to calculate the final position of each linear segment that represents the Bezier curve. It makes this calculation using the final control points of the curve and the acceleration coefficients calculated earlier.

Final Cut Pro loops over the 40 segments that make up the curve. For each point, it calculates the distance along the curve as a fraction, for example 0, 1/40th, 2/40th, 3/40th, … 39/40th, 40/40th. Then it determines whether the point is on the left or right half of the curve and applies the appropriate acceleration value. It multiples the acceleration constant calculated at the outset by a contribution factor that yields a desired acceleration factor.

Listing C-4  Linear segments

percent = (float)i / 40;

if (percent <= 0.5) {

if (leftScale != 0.0) {

        contribution = (1.0 - (percent * 2));

        contribution *= contribution;           // ^2

        contribution *= contribution;           // ^4

        contribution *= contribution;           // ^8

        scale = 1.0 + leftVal * contribution;

}

else scale = 1.0;

}

else {

    if (rightScale != 0.0) {

        contribution = ((percent * 2) - 1.0);

        contribution *= contribution;           // ^2

        contribution *= contribution;           // ^4

        contribution *= contribution;           // ^8

        scale = 1.0 + rightVal * contribution;

    }

    else scale = 1.0;

}

In effect, these calculations push the segments of the curve in one direction or the other, either "squishing" the curve segments toward an endpoint, or "pulling" them away.

Now Final Cut Pro pulls these values together. First. it fixes the position of each control point which was calculated using Miller's algorithm BezierForm. See Listing C-3 Using the final scaling factor calculated in Listing C-4 the program can stretch or shrink the magnitude of this linear segment of the curve. It can calculate the value of the curve at any point by interpolating between these control points.

Listing C-5  Bezier curve

BezierCurve(FloatPt *c, FloatPt *pt, float t) {

    int32               i, n;

    float               t1, tt, u;

    FloatPt         b[NUM_CONTL_POINTS];

    n = NUM_CONTL_POINTS - 1;

    u = t;

    b[0].h = c[0].h;

    b[0].v = c[0].v;

    for (i =1; i <=n; i++) {

        b[i].h = c[i].h * u;

        b[i].v = c[i].v * u;

        u = u * t;

    }

    (*pt).h = b[n].h;  (*pt).v = b[n].v;

    t1 = 1 - t;

    tt = t1;

    for (k = n - 1; i >= 0; i--) {

        (*pt).h += b[i].h * tt;

        (*pt).v += b[i].v * tt;

        tt = tt * t1;

    }

}

Now that Final Cut Pro has all the information needed about the Cartesian position of the current line segment along the actual curve, it can update the Bezier structure representing the curve with this data. This process involves recording the start and end position of the segment and calculating the line connecting these points, while scaling the line segment by the calculated acceleration factor. Looping around from point to point, the application calculates the position of all 40 points of the curve.

Lastly, before finishing with this segment of the curve, Final Cut Pro calculates the time value for each segment point. Later, it uses these time values to look up and interpolate values between the segment points. This process is a simple matter of calculating the current position on the curve and then using this value to compute the total time along the curve this position represents.