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 "mozilla/StandardInteger.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);
19 nsSMILKeySpline::Init(double aX1
,
29 if (mX1
!= mY1
|| mX2
!= mY2
)
34 nsSMILKeySpline::GetSplineValue(double aX
) const
36 if (mX1
== mY1
&& mX2
== mY2
)
39 return CalcBezier(GetTForX(aX
), mY1
, mY2
);
43 nsSMILKeySpline::GetSplineDerivativeValues(double aX
, double& aDX
, double& aDY
) const
45 double t
= GetTForX(aX
);
46 aDX
= GetSlope(t
, mX1
, mX2
);
47 aDY
= GetSlope(t
, mY1
, mY2
);
51 nsSMILKeySpline::CalcSampleValues()
53 for (uint32_t i
= 0; i
< kSplineTableSize
; ++i
) {
54 mSampleValues
[i
] = CalcBezier(double(i
) * kSampleStepSize
, mX1
, mX2
);
59 nsSMILKeySpline::CalcBezier(double aT
,
63 // use Horner's scheme to evaluate the Bezier polynomial
64 return ((A(aA1
, aA2
)*aT
+ B(aA1
, aA2
))*aT
+ C(aA1
))*aT
;
68 nsSMILKeySpline::GetSlope(double aT
,
72 return 3.0 * A(aA1
, aA2
)*aT
*aT
+ 2.0 * B(aA1
, aA2
) * aT
+ C(aA1
);
76 nsSMILKeySpline::GetTForX(double aX
) const
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
;
84 intervalStart
+= kSampleStepSize
;
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
96 double initialSlope
= GetSlope(guessForT
, mX1
, mX2
);
97 if (initialSlope
>= NEWTON_MIN_SLOPE
) {
98 return NewtonRaphsonIterate(aX
, guessForT
);
99 } else if (initialSlope
== 0.0) {
102 return BinarySubdivide(aX
, intervalStart
, intervalStart
+ kSampleStepSize
);
107 nsSMILKeySpline::NewtonRaphsonIterate(double aX
, double aGuessT
) const
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)
119 aGuessT
-= currentX
/ currentSlope
;
126 nsSMILKeySpline::BinarySubdivide(double aX
, double aA
, double aB
) const
134 currentT
= aA
+ (aB
- aA
) / 2.0;
135 currentX
= CalcBezier(currentT
, mX1
, mX2
) - aX
;
137 if (currentX
> 0.0) {
142 } while (fabs(currentX
) > SUBDIVISION_PRECISION
143 && ++i
< SUBDIVISION_MAX_ITERATIONS
);