BezierEasing.hx

BezierEasing.hx

package;

import haxe.ds.Vector;

/**
 * BezierEasing - use 2d bezier curve to describe easing function. Follows specification of CSS3 `cubic-bezier`
 * You can easily get desired values in the cubic-bezier editor: http://cubic-bezier.com/
 * Implementation article - http://greweb.me/2012/02/bezier-curve-based-easing-functions-from-concept-to-implementation/
 * The algorithm uses combination of newton and bisection methods (http://en.wikipedia.org/wiki/Brent%27s_method#Dekker.27s_method) 
 * to approximate bezier function. Please note that this method is much more slower than direct easing functions.
 *
 * Credits: 
 * This code is a JS->Haxe port of https://github.com/gre/bezier-easing by Gaëtan Renaudeau 2014 – MIT License
 * Algorithm is based on Firefox's nsSMILKeySpline.cpp
 * Usage:
 * var spline = BezierEasing.makeBezierEasing(0.25, 0.1, 0.25, 1.0)
 * spline(x) => returns the easing value | x must be in [0, 1] range
 *
 */
class BezierEasing
{
	// These values are established by empiricism with tests (tradeoff: performance VS precision)
	static inline var NEWTON_ITERATIONS:Int = 4;
	static inline var NEWTON_MIN_SLOPE:Float = 0.001;
	static inline var SUBDIVISION_PRECISION:Float = 0.0000001;
	static inline var SUBDIVISION_MAX_ITERATIONS:Int = 10;

	static inline var K_SPLINE_TABLE_SIZE:Int = 11;
	static inline var K_SAMPLE_STEP_SIZE:Float = 1.0 / (K_SPLINE_TABLE_SIZE - 1.0);

	static function A(aA1:Float, aA2:Float):Float { return 1.0 - 3.0 * aA2 + 3.0 * aA1; }
	static function B(aA1:Float, aA2:Float):Float { return 3.0 * aA2 - 6.0 * aA1; }
	static function C(aA1:Float):Float { return 3.0 * aA1; }

	// Returns x(t) given t, x1, and x2, or y(t) given t, y1, and y2.
	static function calcBezier(aT:Float, aA1:Float, aA2:Float):Float
	{
		return ((A(aA1, aA2) * aT + B(aA1, aA2)) * aT + C(aA1)) * aT;
	}

	// Returns dx/dt given t, x1, and x2, or dy/dt given t, y1, and y2.
	static function getSlope(aT:Float, aA1:Float, aA2:Float):Float
	{
		return 3.0 * A(aA1, aA2) * aT * aT + 2.0 * B(aA1, aA2) * aT + C(aA1);
	}

	static function binarySubdivide(aX:Float, aA:Float, aB:Float, mX1:Float, mX2:Float)
	{
		var currentX:Float;
		var currentT:Float;
		var i:Int = 0;
		do {
			currentT = aA + (aB - aA) / 2.0;
			currentX = calcBezier(currentT, mX1, mX2) - aX;
			if (currentX > 0.0) {
				aB = currentT;
			} else {
				aA = currentT;
			}
		} while (Math.abs(currentX) > SUBDIVISION_PRECISION && ++i < SUBDIVISION_MAX_ITERATIONS);
		return currentT;
	}

	public static function makeBezierEasing(mX1:Float, mY1:Float, mX2:Float, mY2:Float, lazy:Bool = true):Float->Float
	{
		// Validate arguments
		if (mX1 < 0 || mX1 > 1 || mX2 < 0 || mX2 > 1) {
			throw "x values must be in [0, 1] range.";
		}
		var mSampleValues = new Vector(K_SPLINE_TABLE_SIZE);

		function newtonRaphsonIterate(aX:Float, aGuessT:Float):Float
		{
			for (i in 0...NEWTON_ITERATIONS) {
				var currentSlope = getSlope(aGuessT, mX1, mX2);
				if (currentSlope == 0.0) return aGuessT;
				var currentX = calcBezier(aGuessT, mX1, mX2) - aX;
				aGuessT -= currentX / currentSlope;
			}
			return aGuessT;
		}

		function calcSampleValues():Void
		{
			for (i in 0...K_SPLINE_TABLE_SIZE) {
				mSampleValues[i] = calcBezier(i * K_SAMPLE_STEP_SIZE, mX1, mX2);
			}
		}

		function getTForX(aX):Float
		{
			var intervalStart:Float = 0.0;
			var currentSample:Int = 1;
			var lastSample:Int = K_SPLINE_TABLE_SIZE - 1;
			while (currentSample != lastSample && mSampleValues[currentSample] <= aX) {
				++currentSample;
				intervalStart += K_SAMPLE_STEP_SIZE;
			}
			--currentSample;

			// Interpolate to provide an initial guess for t
			var dist = (aX - mSampleValues[currentSample]) / (mSampleValues[currentSample + 1] - mSampleValues[currentSample]);
			var guessForT = intervalStart + dist * K_SAMPLE_STEP_SIZE;

			var initialSlope = getSlope(guessForT, mX1, mX2);
			if (initialSlope >= NEWTON_MIN_SLOPE) {
				return newtonRaphsonIterate(aX, guessForT);
			} else if (initialSlope == 0.0) {
				return guessForT;
			} else {
				return binarySubdivide(aX, intervalStart, intervalStart + K_SAMPLE_STEP_SIZE, mX1, mX2);
			}
		}

		var _precomputed:Bool = false;
		function precompute():Void
		{
			_precomputed = true;
			if (mX1 != mY1 || mX2 != mY2) {
				calcSampleValues();
			}
		}
		
		if (!lazy) precompute();
		return function(aX:Float):Float
		{
			if (!_precomputed) precompute();
			if (mX1 == mY1 && mX2 == mY2) return aX; // linear
			// Because floats are imprecise, we should guarantee the extremes are right.
			if (aX == 0) return 0;
			if (aX == 1) return 1;
			return calcBezier(getTForX(aX), mY1, mY2);
		};
	}
}