The Tor Browser / file comparison
comparison: dom/smil/nsSMILKeySpline.cpp
dom/smil/nsSMILKeySpline.cpp
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
equal
deleted
inserted
replaced
| -1:000000000000 | 0:3ca319a8bd70 |
|---|---|
| 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 } |
