1 /*
2 * Copyright (c) 2023 - 2024 the ThorVG project. All rights reserved.
3
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10
11 * The above copyright notice and this permission notice shall be included in all
12 * copies or substantial portions of the Software.
13
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 * SOFTWARE.
21 */
22
23 #include "../../lv_conf_internal.h"
24 #if LV_USE_THORVG_INTERNAL
25
26 /* This Source Code Form is subject to the terms of the Mozilla Public
27 * License, v. 2.0. If a copy of the MPL was not distributed with this
28 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
29
30 #include <string.h>
31 #include "tvgCommon.h"
32 #include "tvgMath.h"
33 #include "tvgLottieInterpolator.h"
34
35
36 /************************************************************************/
37 /* Internal Class Implementation */
38 /************************************************************************/
39
40 #define NEWTON_MIN_SLOPE 0.02f
41 #define NEWTON_ITERATIONS 4
42 #define SUBDIVISION_PRECISION 0.0000001f
43 #define SUBDIVISION_MAX_ITERATIONS 10
44
45
_constA(float aA1,float aA2)46 static inline float _constA(float aA1, float aA2) { return 1.0f - 3.0f * aA2 + 3.0f * aA1; }
_constB(float aA1,float aA2)47 static inline float _constB(float aA1, float aA2) { return 3.0f * aA2 - 6.0f * aA1; }
_constC(float aA1)48 static inline float _constC(float aA1) { return 3.0f * aA1; }
49
50
_getSlope(float t,float aA1,float aA2)51 static inline float _getSlope(float t, float aA1, float aA2)
52 {
53 return 3.0f * _constA(aA1, aA2) * t * t + 2.0f * _constB(aA1, aA2) * t + _constC(aA1);
54 }
55
56
_calcBezier(float t,float aA1,float aA2)57 static inline float _calcBezier(float t, float aA1, float aA2)
58 {
59 return ((_constA(aA1, aA2) * t + _constB(aA1, aA2)) * t + _constC(aA1)) * t;
60 }
61
62
getTForX(float aX)63 float LottieInterpolator::getTForX(float aX)
64 {
65 //Find interval where t lies
66 auto intervalStart = 0.0f;
67 auto currentSample = &samples[1];
68 auto lastSample = &samples[SPLINE_TABLE_SIZE - 1];
69
70 for (; currentSample != lastSample && *currentSample <= aX; ++currentSample) {
71 intervalStart += SAMPLE_STEP_SIZE;
72 }
73
74 --currentSample; // t now lies between *currentSample and *currentSample+1
75
76 // Interpolate to provide an initial guess for t
77 auto dist = (aX - *currentSample) / (*(currentSample + 1) - *currentSample);
78 auto guessForT = intervalStart + dist * SAMPLE_STEP_SIZE;
79
80 // Check the slope to see what strategy to use. If the slope is too small
81 // Newton-Raphson iteration won't converge on a root so we use bisection
82 // instead.
83 auto initialSlope = _getSlope(guessForT, outTangent.x, inTangent.x);
84 if (initialSlope >= NEWTON_MIN_SLOPE) return NewtonRaphsonIterate(aX, guessForT);
85 else if (initialSlope == 0.0) return guessForT;
86 else return binarySubdivide(aX, intervalStart, intervalStart + SAMPLE_STEP_SIZE);
87 }
88
89
binarySubdivide(float aX,float aA,float aB)90 float LottieInterpolator::binarySubdivide(float aX, float aA, float aB)
91 {
92 float x, t;
93 int i = 0;
94
95 do {
96 t = aA + (aB - aA) / 2.0f;
97 x = _calcBezier(t, outTangent.x, inTangent.x) - aX;
98 if (x > 0.0f) aB = t;
99 else aA = t;
100 } while (fabsf(x) > SUBDIVISION_PRECISION && ++i < SUBDIVISION_MAX_ITERATIONS);
101 return t;
102 }
103
104
NewtonRaphsonIterate(float aX,float aGuessT)105 float LottieInterpolator::NewtonRaphsonIterate(float aX, float aGuessT)
106 {
107 // Refine guess with Newton-Raphson iteration
108 for (int i = 0; i < NEWTON_ITERATIONS; ++i) {
109 // We're trying to find where f(t) = aX,
110 // so we're actually looking for a root for: CalcBezier(t) - aX
111 auto currentX = _calcBezier(aGuessT, outTangent.x, inTangent.x) - aX;
112 auto currentSlope = _getSlope(aGuessT, outTangent.x, inTangent.x);
113 if (currentSlope == 0.0f) return aGuessT;
114 aGuessT -= currentX / currentSlope;
115 }
116 return aGuessT;
117 }
118
119
120 /************************************************************************/
121 /* External Class Implementation */
122 /************************************************************************/
123
progress(float t)124 float LottieInterpolator::progress(float t)
125 {
126 if (outTangent.x == outTangent.y && inTangent.x == inTangent.y) return t;
127 return _calcBezier(getTForX(t), outTangent.y, inTangent.y);
128 }
129
130
set(const char * key,Point & inTangent,Point & outTangent)131 void LottieInterpolator::set(const char* key, Point& inTangent, Point& outTangent)
132 {
133 this->key = strdup(key);
134 this->inTangent = inTangent;
135 this->outTangent = outTangent;
136
137 if (outTangent.x == outTangent.y && inTangent.x == inTangent.y) return;
138
139 //calculates sample values
140 for (int i = 0; i < SPLINE_TABLE_SIZE; ++i) {
141 samples[i] = _calcBezier(float(i) * SAMPLE_STEP_SIZE, outTangent.x, inTangent.x);
142 }
143 }
144
145 #endif /* LV_USE_THORVG_INTERNAL */
146
147
