1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/dom/smil/nsSMILKeySpline.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,146 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "nsSMILKeySpline.h"
1.10 +#include <stdint.h>
1.11 +#include <math.h>
1.12 +
1.13 +#define NEWTON_ITERATIONS 4
1.14 +#define NEWTON_MIN_SLOPE 0.02
1.15 +#define SUBDIVISION_PRECISION 0.0000001
1.16 +#define SUBDIVISION_MAX_ITERATIONS 10
1.17 +
1.18 +const double nsSMILKeySpline::kSampleStepSize =
1.19 + 1.0 / double(kSplineTableSize - 1);
1.20 +
1.21 +void
1.22 +nsSMILKeySpline::Init(double aX1,
1.23 + double aY1,
1.24 + double aX2,
1.25 + double aY2)
1.26 +{
1.27 + mX1 = aX1;
1.28 + mY1 = aY1;
1.29 + mX2 = aX2;
1.30 + mY2 = aY2;
1.31 +
1.32 + if (mX1 != mY1 || mX2 != mY2)
1.33 + CalcSampleValues();
1.34 +}
1.35 +
1.36 +double
1.37 +nsSMILKeySpline::GetSplineValue(double aX) const
1.38 +{
1.39 + if (mX1 == mY1 && mX2 == mY2)
1.40 + return aX;
1.41 +
1.42 + return CalcBezier(GetTForX(aX), mY1, mY2);
1.43 +}
1.44 +
1.45 +void
1.46 +nsSMILKeySpline::GetSplineDerivativeValues(double aX, double& aDX, double& aDY) const
1.47 +{
1.48 + double t = GetTForX(aX);
1.49 + aDX = GetSlope(t, mX1, mX2);
1.50 + aDY = GetSlope(t, mY1, mY2);
1.51 +}
1.52 +
1.53 +void
1.54 +nsSMILKeySpline::CalcSampleValues()
1.55 +{
1.56 + for (uint32_t i = 0; i < kSplineTableSize; ++i) {
1.57 + mSampleValues[i] = CalcBezier(double(i) * kSampleStepSize, mX1, mX2);
1.58 + }
1.59 +}
1.60 +
1.61 +/*static*/ double
1.62 +nsSMILKeySpline::CalcBezier(double aT,
1.63 + double aA1,
1.64 + double aA2)
1.65 +{
1.66 + // use Horner's scheme to evaluate the Bezier polynomial
1.67 + return ((A(aA1, aA2)*aT + B(aA1, aA2))*aT + C(aA1))*aT;
1.68 +}
1.69 +
1.70 +/*static*/ double
1.71 +nsSMILKeySpline::GetSlope(double aT,
1.72 + double aA1,
1.73 + double aA2)
1.74 +{
1.75 + return 3.0 * A(aA1, aA2)*aT*aT + 2.0 * B(aA1, aA2) * aT + C(aA1);
1.76 +}
1.77 +
1.78 +double
1.79 +nsSMILKeySpline::GetTForX(double aX) const
1.80 +{
1.81 + // Find interval where t lies
1.82 + double intervalStart = 0.0;
1.83 + const double* currentSample = &mSampleValues[1];
1.84 + const double* const lastSample = &mSampleValues[kSplineTableSize - 1];
1.85 + for (; currentSample != lastSample && *currentSample <= aX;
1.86 + ++currentSample) {
1.87 + intervalStart += kSampleStepSize;
1.88 + }
1.89 + --currentSample; // t now lies between *currentSample and *currentSample+1
1.90 +
1.91 + // Interpolate to provide an initial guess for t
1.92 + double dist = (aX - *currentSample) /
1.93 + (*(currentSample+1) - *currentSample);
1.94 + double guessForT = intervalStart + dist * kSampleStepSize;
1.95 +
1.96 + // Check the slope to see what strategy to use. If the slope is too small
1.97 + // Newton-Raphson iteration won't converge on a root so we use bisection
1.98 + // instead.
1.99 + double initialSlope = GetSlope(guessForT, mX1, mX2);
1.100 + if (initialSlope >= NEWTON_MIN_SLOPE) {
1.101 + return NewtonRaphsonIterate(aX, guessForT);
1.102 + } else if (initialSlope == 0.0) {
1.103 + return guessForT;
1.104 + } else {
1.105 + return BinarySubdivide(aX, intervalStart, intervalStart + kSampleStepSize);
1.106 + }
1.107 +}
1.108 +
1.109 +double
1.110 +nsSMILKeySpline::NewtonRaphsonIterate(double aX, double aGuessT) const
1.111 +{
1.112 + // Refine guess with Newton-Raphson iteration
1.113 + for (uint32_t i = 0; i < NEWTON_ITERATIONS; ++i) {
1.114 + // We're trying to find where f(t) = aX,
1.115 + // so we're actually looking for a root for: CalcBezier(t) - aX
1.116 + double currentX = CalcBezier(aGuessT, mX1, mX2) - aX;
1.117 + double currentSlope = GetSlope(aGuessT, mX1, mX2);
1.118 +
1.119 + if (currentSlope == 0.0)
1.120 + return aGuessT;
1.121 +
1.122 + aGuessT -= currentX / currentSlope;
1.123 + }
1.124 +
1.125 + return aGuessT;
1.126 +}
1.127 +
1.128 +double
1.129 +nsSMILKeySpline::BinarySubdivide(double aX, double aA, double aB) const
1.130 +{
1.131 + double currentX;
1.132 + double currentT;
1.133 + uint32_t i = 0;
1.134 +
1.135 + do
1.136 + {
1.137 + currentT = aA + (aB - aA) / 2.0;
1.138 + currentX = CalcBezier(currentT, mX1, mX2) - aX;
1.139 +
1.140 + if (currentX > 0.0) {
1.141 + aB = currentT;
1.142 + } else {
1.143 + aA = currentT;
1.144 + }
1.145 + } while (fabs(currentX) > SUBDIVISION_PRECISION
1.146 + && ++i < SUBDIVISION_MAX_ITERATIONS);
1.147 +
1.148 + return currentT;
1.149 +}
