http://openjdk.java.net/projects/openjfx/javafx-graphics/: OpenJFX JavaFX
  • OpenJFX Mailing List 
/*
 * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package com.sun.scenario.animation;

import javafx.animation.Interpolator;


An implementation of a spline interpolator for temporal interpolation that
tries to follow the specification referenced by:
http://www.w3.org/TR/SMIL/animation.html#animationNS-OverviewSpline .


Basically, a cubic Bezier curve is created with start point (0,0) and
endpoint (1,1). The other two control points (px1, py1) and (px2, py2) are
given by the user, where px1, py1, px1, and px2 are all in the range [0,1]. A
property of this specially constrained Bezier curve is that it is strictly
monotonically increasing in both X and Y with t in range [0,1].


The interpolator works by giving it a value for X. It then finds what
parameter t would generate this X value for the curve. Then this t parameter
is applied to the curve to solve for Y. As X increases from 0 to 1, t also
increases from 0 to 1, and correspondingly Y increases from 0 to 1. The
X-to-Y mapping is not a function of path/curve length.

/**
 * An implementation of a spline interpolator for temporal interpolation that
 * tries to follow the specification referenced by:
 * http://www.w3.org/TR/SMIL/animation.html#animationNS-OverviewSpline .
 * <p>
 * Basically, a cubic Bezier curve is created with start point (0,0) and
 * endpoint (1,1). The other two control points (px1, py1) and (px2, py2) are
 * given by the user, where px1, py1, px1, and px2 are all in the range [0,1]. A
 * property of this specially constrained Bezier curve is that it is strictly
 * monotonically increasing in both X and Y with t in range [0,1].
 * <p>
 * The interpolator works by giving it a value for X. It then finds what
 * parameter t would generate this X value for the curve. Then this t parameter
 * is applied to the curve to solve for Y. As X increases from 0 to 1, t also
 * increases from 0 to 1, and correspondingly Y increases from 0 to 1. The
 * X-to-Y mapping is not a function of path/curve length.
 *
 */
public class SplineInterpolator extends Interpolator {

    
The coordinates of the 2 2D control points for a cubic Bezier curve, with
implicit start point (0,0) and end point (1,1) -- each individual
coordinate value must be in range [0,1].

/**
     * The coordinates of the 2 2D control points for a cubic Bezier curve, with
     * implicit start point (0,0) and end point (1,1) -- each individual
     * coordinate value must be in range [0,1].
     */
    private final double x1, y1, x2, y2;

    
Do the input control points form a line with (0,0) and (1,1), i.e., x1 ==
y1 and x2 == y2 -- if so, then all x(t) == y(t) for the curve.

/**
     * Do the input control points form a line with (0,0) and (1,1), i.e., x1 ==
     * y1 and x2 == y2 -- if so, then all x(t) == y(t) for the curve.
     */
    private final boolean isCurveLinear;

    
Power of 2 sample size for lookup table of x values.

/**
     * Power of 2 sample size for lookup table of x values.
     */
    private static final int SAMPLE_SIZE = 16;

    
Difference in t used to calculate each of the xSamples values -- power of
2 sample size should provide exact representation of this value and its
integer multiples (integer in range of [0..SAMPLE_SIZE].

/**
     * Difference in t used to calculate each of the xSamples values -- power of
     * 2 sample size should provide exact representation of this value and its
     * integer multiples (integer in range of [0..SAMPLE_SIZE].
     */
    private static final double SAMPLE_INCREMENT = 1.0 / SAMPLE_SIZE;

    
X values for the bezier curve, sampled at increments of 1/SAMPLE_SIZE --
this is used to find the good initial guess for parameter t, given an x.

/**
     * X values for the bezier curve, sampled at increments of 1/SAMPLE_SIZE --
     * this is used to find the good initial guess for parameter t, given an x.
     */
    private final double[] xSamples = new double[SAMPLE_SIZE + 1];

    
Creates a new instance with control points (0,0) (px1,py1) (px2,py2)
(1,1) -- px1, py1, px2, py2 all in range [0,1].

Params:
  • px1 – 
           X coordinate of first control point, in range [0,1]
  • py1 – 
           Y coordinate of first control point, in range [0,1]
  • px2 – 
           X coordinate of second control point, in range [0,1]
  • py2 – 
           Y coordinate of second control point, in range [0,1]
/**
     * Creates a new instance with control points (0,0) (px1,py1) (px2,py2)
     * (1,1) -- px1, py1, px2, py2 all in range [0,1].
     *
     * @param px1
     *            X coordinate of first control point, in range [0,1]
     * @param py1
     *            Y coordinate of first control point, in range [0,1]
     * @param px2
     *            X coordinate of second control point, in range [0,1]
     * @param py2
     *            Y coordinate of second control point, in range [0,1]
     */
    public SplineInterpolator(double px1, double py1, double px2, double py2) {
        // check user input for precondition
        if (px1 < 0 || px1 > 1 || py1 < 0 || py1 > 1 || px2 < 0 || px2 > 1
                || py2 < 0 || py2 > 1) {
            throw new IllegalArgumentException(
                    "Control point coordinates must " + "all be in range [0,1]");
        }

        // save control point data
        this.x1 = px1;
        this.y1 = py1;
        this.x2 = px2;
        this.y2 = py2;

        // calc linearity/identity curve
        isCurveLinear = ((x1 == y1) && (x2 == y2));

        // make the array of x value samples
        if (!isCurveLinear) {
            for (int i = 0; i < SAMPLE_SIZE + 1; ++i) {
                xSamples[i] = eval(i * SAMPLE_INCREMENT, x1, x2);
            }
        }
    }

    public double getX1() {
        return x1;
    }

    public double getY1() {
        return y1;
    }

    public double getX2() {
        return x2;
    }

    public double getY2() {
        return y2;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 19 * hash + (int) (Double.doubleToLongBits(this.x1) ^ (Double.doubleToLongBits(this.x1) >>> 32));
        hash = 19 * hash + (int) (Double.doubleToLongBits(this.y1) ^ (Double.doubleToLongBits(this.y1) >>> 32));
        hash = 19 * hash + (int) (Double.doubleToLongBits(this.x2) ^ (Double.doubleToLongBits(this.x2) >>> 32));
        hash = 19 * hash + (int) (Double.doubleToLongBits(this.y2) ^ (Double.doubleToLongBits(this.y2) >>> 32));
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final SplineInterpolator other = (SplineInterpolator) obj;
        if (Double.doubleToLongBits(this.x1) != Double.doubleToLongBits(other.x1)) {
            return false;
        }
        if (Double.doubleToLongBits(this.y1) != Double.doubleToLongBits(other.y1)) {
            return false;
        }
        if (Double.doubleToLongBits(this.x2) != Double.doubleToLongBits(other.x2)) {
            return false;
        }
        if (Double.doubleToLongBits(this.y2) != Double.doubleToLongBits(other.y2)) {
            return false;
        }
        return true;
    }

    
Returns the y-value of the cubic bezier curve that corresponds to the x
input.

Params:
  • x – 
           is x-value of cubic bezier curve, in range [0,1]
Returns:corresponding y-value of cubic bezier curve -- in range [0,1]
/**
     * Returns the y-value of the cubic bezier curve that corresponds to the x
     * input.
     *
     * @param x
     *            is x-value of cubic bezier curve, in range [0,1]
     * @return corresponding y-value of cubic bezier curve -- in range [0,1]
     */
    @Override
    public double curve(double x) {
        // check user input for precondition
        if (x < 0 || x > 1) {
            throw new IllegalArgumentException("x must be in range [0,1]");
        }

        // check quick exit identity cases (linear curve or curve endpoints)
        if (isCurveLinear || x == 0 || x == 1) {
            return x;
        }

        // find the t parameter for a given x value, and use this t to calculate
        // the corresponding y value
        return eval(findTForX(x), y1, y2);
    }

    
Use Bernstein basis to evaluate 1D cubic Bezier curve (quicker and more
numerically stable than power basis) -- 1D control coordinates are (0,
p1, p2, 1), where p1 and p2 are in range [0,1], and there is no ordering
constraint on p1 and p2, i.e., p1 <= p2 does not have to be true.

Params:
  • t – 
           is the paramaterized value in range [0,1]
  • p1 – 
           is 1st control point coordinate in range [0,1]
  • p2 – 
           is 2nd control point coordinate in range [0,1]
Returns:the value of the Bezier curve at parameter t
/**
     * Use Bernstein basis to evaluate 1D cubic Bezier curve (quicker and more
     * numerically stable than power basis) -- 1D control coordinates are (0,
     * p1, p2, 1), where p1 and p2 are in range [0,1], and there is no ordering
     * constraint on p1 and p2, i.e., p1 &lt;= p2 does not have to be true.
     *
     * @param t
     *            is the paramaterized value in range [0,1]
     * @param p1
     *            is 1st control point coordinate in range [0,1]
     * @param p2
     *            is 2nd control point coordinate in range [0,1]
     * @return the value of the Bezier curve at parameter t
     */
    private double eval(double t, double p1, double p2) {
        // Use optimized version of the normal Bernstein basis form of Bezier:
        // (3*(1-t)*(1-t)*t*p1)+(3*(1-t)*t*t*p2)+(t*t*t), since p0=0, p3=1.
        // The above unoptimized version is best using -server, but since we
        // are probably doing client-side animation, this is faster.
        double compT = 1 - t;
        return t * (3 * compT * (compT * p1 + t * p2) + (t * t));
    }

    
Evaluates Bernstein basis derivative of 1D cubic Bezier curve, where 1D
control points are (0, p1, p2, 1), where p1 and p2 are in range [0,1],
and there is no ordering constraint on p1 and p2, i.e., p1 <= p2 does
not have to be true.

Params:
  • t – 
           is the paramaterized value in range [0,1]
  • p1 – 
           is 1st control point coordinate in range [0,1]
  • p2 – 
           is 2nd control point coordinate in range [0,1]
Returns:the value of the Bezier curve at parameter t
/**
     * Evaluates Bernstein basis derivative of 1D cubic Bezier curve, where 1D
     * control points are (0, p1, p2, 1), where p1 and p2 are in range [0,1],
     * and there is no ordering constraint on p1 and p2, i.e., p1 &lt;= p2 does
     * not have to be true.
     *
     * @param t
     *            is the paramaterized value in range [0,1]
     * @param p1
     *            is 1st control point coordinate in range [0,1]
     * @param p2
     *            is 2nd control point coordinate in range [0,1]
     * @return the value of the Bezier curve at parameter t
     */
    private double evalDerivative(double t, double p1, double p2) {
        // use optimized version of Berstein basis Bezier derivative:
        // (3*(1-t)*(1-t)*p1)+(6*(1-t)*t*(p2-p1))+(3*t*t*(1-p2)), since
        // p0=0 and p3=1. The above unoptimized version is best using -server,
        // but since we are probably doing client-side animation, this is
        // faster.
        double compT = 1 - t;
        return 3 * (compT * (compT * p1 + 2 * t * (p2 - p1)) + t * t * (1 - p2));
    }

    
Find an initial good guess for what parameter t might produce the x-value
on the Bezier curve -- uses linear interpolation on the x-value sample
array that was created on construction.

Params:
  • x – 
           is x-value of cubic bezier curve, in range [0,1]
Returns:a good initial guess for parameter t (in range [0,1]) that gives
        x
/**
     * Find an initial good guess for what parameter t might produce the x-value
     * on the Bezier curve -- uses linear interpolation on the x-value sample
     * array that was created on construction.
     *
     * @param x
     *            is x-value of cubic bezier curve, in range [0,1]
     * @return a good initial guess for parameter t (in range [0,1]) that gives
     *         x
     */
    private double getInitialGuessForT(double x) {
        // find which places in the array that x would be sandwiched between,
        // and then linearly interpolate a reasonable value of t -- array values
        // are ascending (or at least never descending) -- binary search is
        // probably more trouble than it is worth here
        for (int i = 1; i < SAMPLE_SIZE + 1; ++i) {
            if (xSamples[i] >= x) {
                double xRange = xSamples[i] - xSamples[i - 1];
                if (xRange == 0) {
                    // no change in value between samples, so use earlier time
                    return (i - 1) * SAMPLE_INCREMENT;
                } else {
                    // linearly interpolate the time value
                    return ((i - 1) + ((x - xSamples[i - 1]) / xRange))
                            * SAMPLE_INCREMENT;
                }
            }
        }

        // shouldn't get here since 0 <= x <= 1, and xSamples[0] == 0 and
        // xSamples[SAMPLE_SIZE] == 1 (using power of 2 SAMPLE_SIZE for more
        // exact increment arithmetic)
        return 1;
    }

    
Finds the parameter t that produces the given x-value for the curve --
uses Newton-Raphson to refine the value as opposed to subdividing until
we are within some tolerance.

Params:
  • x – 
           is x-value of cubic bezier curve, in range [0,1]
Returns:the parameter t (in range [0,1]) that produces x
/**
     * Finds the parameter t that produces the given x-value for the curve --
     * uses Newton-Raphson to refine the value as opposed to subdividing until
     * we are within some tolerance.
     *
     * @param x
     *            is x-value of cubic bezier curve, in range [0,1]
     * @return the parameter t (in range [0,1]) that produces x
     */
    private double findTForX(double x) {
        // get an initial good guess for t
        double t = getInitialGuessForT(x);

        // use Newton-Raphson to refine the value for t -- for this constrained
        // Bezier with float accuracy (7 digits), any value not converged by 4
        // iterations is cycling between values, which can minutely affect the
        // accuracy of the last digit
        final int numIterations = 4;
        for (int i = 0; i < numIterations; ++i) {
            // stop if this value of t gives us exactly x
            double xT = (eval(t, x1, x2) - x);
            if (xT == 0) {
                break;
            }

            // stop if derivative is 0
            double dXdT = evalDerivative(t, x1, x2);
            if (dXdT == 0) {
                break;
            }

            // refine t
            t -= xT / dXdT;
        }

        return t;
    }

    @Override
    public String toString() {
        return "SplineInterpolator [x1=" + x1 + ", y1=" + y1 + ", x2=" + x2
                + ", y2=" + y2 + "]";
    }

}