1
2 /*
3 * Copyright 2008 The Android Open Source Project
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10 #include "SkInterpolator.h"
11 #include "SkMath.h"
12 #include "SkTSearch.h"
13
SkInterpolatorBase()14 SkInterpolatorBase::SkInterpolatorBase() {
15 fStorage = nullptr;
16 fTimes = nullptr;
17 SkDEBUGCODE(fTimesArray = nullptr;)
18 }
19
~SkInterpolatorBase()20 SkInterpolatorBase::~SkInterpolatorBase() {
21 if (fStorage) {
22 sk_free(fStorage);
23 }
24 }
25
reset(int elemCount,int frameCount)26 void SkInterpolatorBase::reset(int elemCount, int frameCount) {
27 fFlags = 0;
28 fElemCount = SkToU8(elemCount);
29 fFrameCount = SkToS16(frameCount);
30 fRepeat = SK_Scalar1;
31 if (fStorage) {
32 sk_free(fStorage);
33 fStorage = nullptr;
34 fTimes = nullptr;
35 SkDEBUGCODE(fTimesArray = nullptr);
36 }
37 }
38
39 /* Each value[] run is formated as:
40 <time (in msec)>
41 <blend>
42 <data[fElemCount]>
43
44 Totaling fElemCount+2 entries per keyframe
45 */
46
getDuration(SkMSec * startTime,SkMSec * endTime) const47 bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
48 if (fFrameCount == 0) {
49 return false;
50 }
51
52 if (startTime) {
53 *startTime = fTimes[0].fTime;
54 }
55 if (endTime) {
56 *endTime = fTimes[fFrameCount - 1].fTime;
57 }
58 return true;
59 }
60
ComputeRelativeT(SkMSec time,SkMSec prevTime,SkMSec nextTime,const SkScalar blend[4])61 SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime,
62 SkMSec nextTime, const SkScalar blend[4]) {
63 SkASSERT(time > prevTime && time < nextTime);
64
65 SkScalar t = (SkScalar)(time - prevTime) / (SkScalar)(nextTime - prevTime);
66 return blend ?
67 SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
68 }
69
timeToT(SkMSec time,SkScalar * T,int * indexPtr,bool * exactPtr) const70 SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
71 int* indexPtr, bool* exactPtr) const {
72 SkASSERT(fFrameCount > 0);
73 Result result = kNormal_Result;
74 if (fRepeat != SK_Scalar1) {
75 SkMSec startTime = 0, endTime = 0; // initialize to avoid warning
76 this->getDuration(&startTime, &endTime);
77 SkMSec totalTime = endTime - startTime;
78 SkMSec offsetTime = time - startTime;
79 endTime = SkScalarFloorToInt(fRepeat * totalTime);
80 if (offsetTime >= endTime) {
81 SkScalar fraction = SkScalarFraction(fRepeat);
82 offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
83 (SkMSec) SkScalarFloorToInt(fraction * totalTime);
84 result = kFreezeEnd_Result;
85 } else {
86 int mirror = fFlags & kMirror;
87 offsetTime = offsetTime % (totalTime << mirror);
88 if (offsetTime > totalTime) { // can only be true if fMirror is true
89 offsetTime = (totalTime << 1) - offsetTime;
90 }
91 }
92 time = offsetTime + startTime;
93 }
94
95 int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
96 sizeof(SkTimeCode));
97
98 bool exact = true;
99
100 if (index < 0) {
101 index = ~index;
102 if (index == 0) {
103 result = kFreezeStart_Result;
104 } else if (index == fFrameCount) {
105 if (fFlags & kReset) {
106 index = 0;
107 } else {
108 index -= 1;
109 }
110 result = kFreezeEnd_Result;
111 } else {
112 exact = false;
113 }
114 }
115 SkASSERT(index < fFrameCount);
116 const SkTimeCode* nextTime = &fTimes[index];
117 SkMSec nextT = nextTime[0].fTime;
118 if (exact) {
119 *T = 0;
120 } else {
121 SkMSec prevT = nextTime[-1].fTime;
122 *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
123 }
124 *indexPtr = index;
125 *exactPtr = exact;
126 return result;
127 }
128
129
SkInterpolator()130 SkInterpolator::SkInterpolator() {
131 INHERITED::reset(0, 0);
132 fValues = nullptr;
133 SkDEBUGCODE(fScalarsArray = nullptr;)
134 }
135
SkInterpolator(int elemCount,int frameCount)136 SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
137 SkASSERT(elemCount > 0);
138 this->reset(elemCount, frameCount);
139 }
140
reset(int elemCount,int frameCount)141 void SkInterpolator::reset(int elemCount, int frameCount) {
142 INHERITED::reset(elemCount, frameCount);
143 fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
144 sizeof(SkTimeCode)) * frameCount);
145 fTimes = (SkTimeCode*) fStorage;
146 fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
147 #ifdef SK_DEBUG
148 fTimesArray = (SkTimeCode(*)[10]) fTimes;
149 fScalarsArray = (SkScalar(*)[10]) fValues;
150 #endif
151 }
152
153 #define SK_Fixed1Third (SK_Fixed1/3)
154 #define SK_Fixed2Third (SK_Fixed1*2/3)
155
156 static const SkScalar gIdentityBlend[4] = {
157 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
158 };
159
setKeyFrame(int index,SkMSec time,const SkScalar values[],const SkScalar blend[4])160 bool SkInterpolator::setKeyFrame(int index, SkMSec time,
161 const SkScalar values[], const SkScalar blend[4]) {
162 SkASSERT(values != nullptr);
163
164 if (blend == nullptr) {
165 blend = gIdentityBlend;
166 }
167
168 bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
169 sizeof(SkTimeCode));
170 SkASSERT(success);
171 if (success) {
172 SkTimeCode* timeCode = &fTimes[index];
173 timeCode->fTime = time;
174 memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
175 SkScalar* dst = &fValues[fElemCount * index];
176 memcpy(dst, values, fElemCount * sizeof(SkScalar));
177 }
178 return success;
179 }
180
timeToValues(SkMSec time,SkScalar values[]) const181 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
182 SkScalar values[]) const {
183 SkScalar T;
184 int index;
185 bool exact;
186 Result result = timeToT(time, &T, &index, &exact);
187 if (values) {
188 const SkScalar* nextSrc = &fValues[index * fElemCount];
189
190 if (exact) {
191 memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
192 } else {
193 SkASSERT(index > 0);
194
195 const SkScalar* prevSrc = nextSrc - fElemCount;
196
197 for (int i = fElemCount - 1; i >= 0; --i) {
198 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
199 }
200 }
201 }
202 return result;
203 }
204
205 ///////////////////////////////////////////////////////////////////////////////
206
207 typedef int Dot14;
208 #define Dot14_ONE (1 << 14)
209 #define Dot14_HALF (1 << 13)
210
211 #define Dot14ToFloat(x) ((x) / 16384.f)
212
Dot14Mul(Dot14 a,Dot14 b)213 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
214 return (a * b + Dot14_HALF) >> 14;
215 }
216
eval_cubic(Dot14 t,Dot14 A,Dot14 B,Dot14 C)217 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
218 return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
219 }
220
pin_and_convert(SkScalar x)221 static inline Dot14 pin_and_convert(SkScalar x) {
222 if (x <= 0) {
223 return 0;
224 }
225 if (x >= SK_Scalar1) {
226 return Dot14_ONE;
227 }
228 return SkScalarToFixed(x) >> 2;
229 }
230
SkUnitCubicInterp(SkScalar value,SkScalar bx,SkScalar by,SkScalar cx,SkScalar cy)231 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
232 SkScalar cx, SkScalar cy) {
233 // pin to the unit-square, and convert to 2.14
234 Dot14 x = pin_and_convert(value);
235
236 if (x == 0) return 0;
237 if (x == Dot14_ONE) return SK_Scalar1;
238
239 Dot14 b = pin_and_convert(bx);
240 Dot14 c = pin_and_convert(cx);
241
242 // Now compute our coefficients from the control points
243 // t -> 3b
244 // t^2 -> 3c - 6b
245 // t^3 -> 3b - 3c + 1
246 Dot14 A = 3*b;
247 Dot14 B = 3*(c - 2*b);
248 Dot14 C = 3*(b - c) + Dot14_ONE;
249
250 // Now search for a t value given x
251 Dot14 t = Dot14_HALF;
252 Dot14 dt = Dot14_HALF;
253 for (int i = 0; i < 13; i++) {
254 dt >>= 1;
255 Dot14 guess = eval_cubic(t, A, B, C);
256 if (x < guess) {
257 t -= dt;
258 } else {
259 t += dt;
260 }
261 }
262
263 // Now we have t, so compute the coeff for Y and evaluate
264 b = pin_and_convert(by);
265 c = pin_and_convert(cy);
266 A = 3*b;
267 B = 3*(c - 2*b);
268 C = 3*(b - c) + Dot14_ONE;
269 return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
270 }
271