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 = NULL;
16 fTimes = NULL;
17 SkDEBUGCODE(fTimesArray = NULL;)
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 = NULL;
34 fTimes = NULL;
35 SkDEBUGCODE(fTimesArray = NULL);
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 = SkScalarDiv((SkScalar)(time - prevTime),
66 (SkScalar)(nextTime - prevTime));
67 return blend ?
68 SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
69 }
70
timeToT(SkMSec time,SkScalar * T,int * indexPtr,SkBool * exactPtr) const71 SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
72 int* indexPtr, SkBool* exactPtr) const {
73 SkASSERT(fFrameCount > 0);
74 Result result = kNormal_Result;
75 if (fRepeat != SK_Scalar1) {
76 SkMSec startTime = 0, endTime = 0; // initialize to avoid warning
77 this->getDuration(&startTime, &endTime);
78 SkMSec totalTime = endTime - startTime;
79 SkMSec offsetTime = time - startTime;
80 endTime = SkScalarMulFloor(fRepeat, totalTime);
81 if (offsetTime >= endTime) {
82 SkScalar fraction = SkScalarFraction(fRepeat);
83 offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
84 (SkMSec) SkScalarMulFloor(fraction, totalTime);
85 result = kFreezeEnd_Result;
86 } else {
87 int mirror = fFlags & kMirror;
88 offsetTime = offsetTime % (totalTime << mirror);
89 if (offsetTime > totalTime) { // can only be true if fMirror is true
90 offsetTime = (totalTime << 1) - offsetTime;
91 }
92 }
93 time = offsetTime + startTime;
94 }
95
96 int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
97 sizeof(SkTimeCode));
98
99 bool exact = true;
100
101 if (index < 0) {
102 index = ~index;
103 if (index == 0) {
104 result = kFreezeStart_Result;
105 } else if (index == fFrameCount) {
106 if (fFlags & kReset) {
107 index = 0;
108 } else {
109 index -= 1;
110 }
111 result = kFreezeEnd_Result;
112 } else {
113 exact = false;
114 }
115 }
116 SkASSERT(index < fFrameCount);
117 const SkTimeCode* nextTime = &fTimes[index];
118 SkMSec nextT = nextTime[0].fTime;
119 if (exact) {
120 *T = 0;
121 } else {
122 SkMSec prevT = nextTime[-1].fTime;
123 *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
124 }
125 *indexPtr = index;
126 *exactPtr = exact;
127 return result;
128 }
129
130
SkInterpolator()131 SkInterpolator::SkInterpolator() {
132 INHERITED::reset(0, 0);
133 fValues = NULL;
134 SkDEBUGCODE(fScalarsArray = NULL;)
135 }
136
SkInterpolator(int elemCount,int frameCount)137 SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
138 SkASSERT(elemCount > 0);
139 this->reset(elemCount, frameCount);
140 }
141
reset(int elemCount,int frameCount)142 void SkInterpolator::reset(int elemCount, int frameCount) {
143 INHERITED::reset(elemCount, frameCount);
144 fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
145 sizeof(SkTimeCode)) * frameCount);
146 fTimes = (SkTimeCode*) fStorage;
147 fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
148 #ifdef SK_DEBUG
149 fTimesArray = (SkTimeCode(*)[10]) fTimes;
150 fScalarsArray = (SkScalar(*)[10]) fValues;
151 #endif
152 }
153
154 #define SK_Fixed1Third (SK_Fixed1/3)
155 #define SK_Fixed2Third (SK_Fixed1*2/3)
156
157 static const SkScalar gIdentityBlend[4] = {
158 #ifdef SK_SCALAR_IS_FLOAT
159 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
160 #else
161 SK_Fixed1Third, SK_Fixed1Third, SK_Fixed2Third, SK_Fixed2Third
162 #endif
163 };
164
setKeyFrame(int index,SkMSec time,const SkScalar values[],const SkScalar blend[4])165 bool SkInterpolator::setKeyFrame(int index, SkMSec time,
166 const SkScalar values[], const SkScalar blend[4]) {
167 SkASSERT(values != NULL);
168
169 if (blend == NULL) {
170 blend = gIdentityBlend;
171 }
172
173 bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
174 sizeof(SkTimeCode));
175 SkASSERT(success);
176 if (success) {
177 SkTimeCode* timeCode = &fTimes[index];
178 timeCode->fTime = time;
179 memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
180 SkScalar* dst = &fValues[fElemCount * index];
181 memcpy(dst, values, fElemCount * sizeof(SkScalar));
182 }
183 return success;
184 }
185
timeToValues(SkMSec time,SkScalar values[]) const186 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
187 SkScalar values[]) const {
188 SkScalar T;
189 int index;
190 SkBool exact;
191 Result result = timeToT(time, &T, &index, &exact);
192 if (values) {
193 const SkScalar* nextSrc = &fValues[index * fElemCount];
194
195 if (exact) {
196 memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
197 } else {
198 SkASSERT(index > 0);
199
200 const SkScalar* prevSrc = nextSrc - fElemCount;
201
202 for (int i = fElemCount - 1; i >= 0; --i) {
203 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
204 }
205 }
206 }
207 return result;
208 }
209
210 ///////////////////////////////////////////////////////////////////////////////
211
212 typedef int Dot14;
213 #define Dot14_ONE (1 << 14)
214 #define Dot14_HALF (1 << 13)
215
216 #define Dot14ToFloat(x) ((x) / 16384.f)
217
Dot14Mul(Dot14 a,Dot14 b)218 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
219 return (a * b + Dot14_HALF) >> 14;
220 }
221
eval_cubic(Dot14 t,Dot14 A,Dot14 B,Dot14 C)222 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
223 return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
224 }
225
pin_and_convert(SkScalar x)226 static inline Dot14 pin_and_convert(SkScalar x) {
227 if (x <= 0) {
228 return 0;
229 }
230 if (x >= SK_Scalar1) {
231 return Dot14_ONE;
232 }
233 return SkScalarToFixed(x) >> 2;
234 }
235
SkUnitCubicInterp(SkScalar value,SkScalar bx,SkScalar by,SkScalar cx,SkScalar cy)236 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
237 SkScalar cx, SkScalar cy) {
238 // pin to the unit-square, and convert to 2.14
239 Dot14 x = pin_and_convert(value);
240
241 if (x == 0) return 0;
242 if (x == Dot14_ONE) return SK_Scalar1;
243
244 Dot14 b = pin_and_convert(bx);
245 Dot14 c = pin_and_convert(cx);
246
247 // Now compute our coefficients from the control points
248 // t -> 3b
249 // t^2 -> 3c - 6b
250 // t^3 -> 3b - 3c + 1
251 Dot14 A = 3*b;
252 Dot14 B = 3*(c - 2*b);
253 Dot14 C = 3*(b - c) + Dot14_ONE;
254
255 // Now search for a t value given x
256 Dot14 t = Dot14_HALF;
257 Dot14 dt = Dot14_HALF;
258 for (int i = 0; i < 13; i++) {
259 dt >>= 1;
260 Dot14 guess = eval_cubic(t, A, B, C);
261 if (x < guess) {
262 t -= dt;
263 } else {
264 t += dt;
265 }
266 }
267
268 // Now we have t, so compute the coeff for Y and evaluate
269 b = pin_and_convert(by);
270 c = pin_and_convert(cy);
271 A = 3*b;
272 B = 3*(c - 2*b);
273 C = 3*(b - c) + Dot14_ONE;
274 return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
275 }
276
277 ///////////////////////////////////////////////////////////////////////////////
278 ///////////////////////////////////////////////////////////////////////////////
279
280 #ifdef SK_DEBUG
281
282 #ifdef SK_SUPPORT_UNITTEST
iset(SkScalar array[3],int a,int b,int c)283 static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
284 array[0] = SkIntToScalar(a);
285 array[1] = SkIntToScalar(b);
286 array[2] = SkIntToScalar(c);
287 return array;
288 }
289 #endif
290
UnitTest()291 void SkInterpolator::UnitTest() {
292 #ifdef SK_SUPPORT_UNITTEST
293 SkInterpolator inter(3, 2);
294 SkScalar v1[3], v2[3], v[3], vv[3];
295 Result result;
296
297 inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
298 inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
299
300 result = inter.timeToValues(0, v);
301 SkASSERT(result == kFreezeStart_Result);
302 SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
303
304 result = inter.timeToValues(99, v);
305 SkASSERT(result == kFreezeStart_Result);
306 SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
307
308 result = inter.timeToValues(100, v);
309 SkASSERT(result == kNormal_Result);
310 SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
311
312 result = inter.timeToValues(200, v);
313 SkASSERT(result == kNormal_Result);
314 SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
315
316 result = inter.timeToValues(201, v);
317 SkASSERT(result == kFreezeEnd_Result);
318 SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
319
320 result = inter.timeToValues(150, v);
321 SkASSERT(result == kNormal_Result);
322 SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
323
324 result = inter.timeToValues(125, v);
325 SkASSERT(result == kNormal_Result);
326 result = inter.timeToValues(175, v);
327 SkASSERT(result == kNormal_Result);
328 #endif
329 }
330
331 #endif
332