The Tor Browser: dom/smil/nsSMILKeySpline.cpp@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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/. */

     6 #include "nsSMILKeySpline.h"

     7 #include <stdint.h>

     8 #include <math.h>

    10 #define NEWTON_ITERATIONS          4

    11 #define NEWTON_MIN_SLOPE           0.02

    12 #define SUBDIVISION_PRECISION      0.0000001

    13 #define SUBDIVISION_MAX_ITERATIONS 10

    15 const double nsSMILKeySpline::kSampleStepSize =

    16                                         1.0 / double(kSplineTableSize - 1);

    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;

    29   if (mX1 != mY1 || mX2 != mY2)

    30     CalcSampleValues();

    31 }

    33 double

    34 nsSMILKeySpline::GetSplineValue(double aX) const

    35 {

    36   if (mX1 == mY1 && mX2 == mY2)

    37     return aX;

    39   return CalcBezier(GetTForX(aX), mY1, mY2);

    40 }

    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 }

    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 }

    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 }

    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 }

    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

    88   // Interpolate to provide an initial guess for t

    89   double dist = (aX - *currentSample) /

    90                 (*(currentSample+1) - *currentSample);

    91   double guessForT = intervalStart + dist * kSampleStepSize;

    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 }

   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);

   116     if (currentSlope == 0.0)

   117       return aGuessT;

   119     aGuessT -= currentX / currentSlope;

   120   }

   122   return aGuessT;

   123 }

   125 double

   126 nsSMILKeySpline::BinarySubdivide(double aX, double aA, double aB) const

   127 {

   128   double currentX;

   129   double currentT;

   130   uint32_t i = 0;

   132   do

   133   {

   134     currentT = aA + (aB - aA) / 2.0;

   135     currentX = CalcBezier(currentT, mX1, mX2) - aX;

   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);

   145   return currentT;

   146 }

The Tor Browser / file revision