tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

SMILKeySpline.cpp (3910B)

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