dom/smil/nsSMILKeySpline.cpp

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