dom/smil/SMILKeySpline.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "SMILKeySpline.h"
   8 #include <stdint.h>
   9 #include <math.h>
  10
  11 namespace mozilla {
  12
  13 #define NEWTON_ITERATIONS 4
  14 #define NEWTON_MIN_SLOPE 0.02
  15 #define SUBDIVISION_PRECISION 0.0000001
  16 #define SUBDIVISION_MAX_ITERATIONS 10
  17
  18 const double SMILKeySpline::kSampleStepSize =
  19     1.0 / double(kSplineTableSize - 1);
  20
  21 void SMILKeySpline::Init(double aX1, double aY1, double aX2, double aY2) {
  22   mX1 = aX1;
  23   mY1 = aY1;
  24   mX2 = aX2;
  25   mY2 = aY2;
  26
  27   if (mX1 != mY1 || mX2 != mY2) CalcSampleValues();
  28 }
  29
  30 double SMILKeySpline::GetSplineValue(double aX) const {
  31   if (mX1 == mY1 && mX2 == mY2) return aX;
  32
  33   return CalcBezier(GetTForX(aX), mY1, mY2);
  34 }
  35
  36 void SMILKeySpline::GetSplineDerivativeValues(double aX, double& aDX,
  37                                               double& aDY) const {
  38   double t = GetTForX(aX);
  39   aDX = GetSlope(t, mX1, mX2);
  40   aDY = GetSlope(t, mY1, mY2);
  41 }
  42
  43 void SMILKeySpline::CalcSampleValues() {
  44   for (uint32_t i = 0; i < kSplineTableSize; ++i) {
  45     mSampleValues[i] = CalcBezier(double(i) * kSampleStepSize, mX1, mX2);
  46   }
  47 }
  48
  49 /*static*/
  50 double SMILKeySpline::CalcBezier(double aT, double aA1, double aA2) {
  51   // use Horner's scheme to evaluate the Bezier polynomial
  52   return ((A(aA1, aA2) * aT + B(aA1, aA2)) * aT + C(aA1)) * aT;
  53 }
  54
  55 /*static*/
  56 double SMILKeySpline::GetSlope(double aT, double aA1, double aA2) {
  57   return 3.0 * A(aA1, aA2) * aT * aT + 2.0 * B(aA1, aA2) * aT + C(aA1);
  58 }
  59
  60 double SMILKeySpline::GetTForX(double aX) const {
  61   // Early return when aX == 1.0 to avoid floating-point inaccuracies.
  62   if (aX == 1.0) {
  63     return 1.0;
  64   }
  65   // Find interval where t lies
  66   double intervalStart = 0.0;
  67   const double* currentSample = &mSampleValues[1];
  68   const double* const lastSample = &mSampleValues[kSplineTableSize - 1];
  69   for (; currentSample != lastSample && *currentSample <= aX; ++currentSample) {
  70     intervalStart += kSampleStepSize;
  71   }
  72   --currentSample;  // t now lies between *currentSample and *currentSample+1
  73
  74   // Interpolate to provide an initial guess for t
  75   double dist = (aX - *currentSample) / (*(currentSample + 1) - *currentSample);
  76   double guessForT = intervalStart + dist * kSampleStepSize;
  77
  78   // Check the slope to see what strategy to use. If the slope is too small
  79   // Newton-Raphson iteration won't converge on a root so we use bisection
  80   // instead.
  81   double initialSlope = GetSlope(guessForT, mX1, mX2);
  82   if (initialSlope >= NEWTON_MIN_SLOPE) {
  83     return NewtonRaphsonIterate(aX, guessForT);
  84   }
  85   if (initialSlope == 0.0) {
  86     return guessForT;
  87   }
  88   return BinarySubdivide(aX, intervalStart, intervalStart + kSampleStepSize);
  89 }
  90
  91 double SMILKeySpline::NewtonRaphsonIterate(double aX, double aGuessT) const {
  92   // Refine guess with Newton-Raphson iteration
  93   for (uint32_t i = 0; i < NEWTON_ITERATIONS; ++i) {
  94     // We're trying to find where f(t) = aX,
  95     // so we're actually looking for a root for: CalcBezier(t) - aX
  96     double currentX = CalcBezier(aGuessT, mX1, mX2) - aX;
  97     double currentSlope = GetSlope(aGuessT, mX1, mX2);
  98
  99     if (currentSlope == 0.0) return aGuessT;
 100
 101     aGuessT -= currentX / currentSlope;
 102   }
 103
 104   return aGuessT;
 105 }
 106
 107 double SMILKeySpline::BinarySubdivide(double aX, double aA, double aB) const {
 108   double currentX;
 109   double currentT;
 110   uint32_t i = 0;
 111
 112   do {
 113     currentT = aA + (aB - aA) / 2.0;
 114     currentX = CalcBezier(currentT, mX1, mX2) - aX;
 115
 116     if (currentX > 0.0) {
 117       aB = currentT;
 118     } else {
 119       aA = currentT;
 120     }
 121   } while (fabs(currentX) > SUBDIVISION_PRECISION &&
 122            ++i < SUBDIVISION_MAX_ITERATIONS);
 123
 124   return currentT;
 125 }
 126
 127 }  // namespace mozilla