Line data    Source code

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