1 /*
2 * Copyright (C) 2006-2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "SkInterpolator.h"
18 #include "SkMath.h"
19 #include "SkTSearch.h"
20
SkInterpolatorBase()21 SkInterpolatorBase::SkInterpolatorBase() {
22 fStorage = NULL;
23 fTimes = NULL;
24 SkDEBUGCODE(fTimesArray = NULL;)
25 }
26
~SkInterpolatorBase()27 SkInterpolatorBase::~SkInterpolatorBase() {
28 if (fStorage) {
29 sk_free(fStorage);
30 }
31 }
32
reset(int elemCount,int frameCount)33 void SkInterpolatorBase::reset(int elemCount, int frameCount) {
34 fFlags = 0;
35 fElemCount = SkToU8(elemCount);
36 fFrameCount = SkToS16(frameCount);
37 fRepeat = SK_Scalar1;
38 if (fStorage) {
39 sk_free(fStorage);
40 fStorage = NULL;
41 fTimes = NULL;
42 SkDEBUGCODE(fTimesArray = NULL);
43 }
44 }
45
46 /* Each value[] run is formated as:
47 <time (in msec)>
48 <blend>
49 <data[fElemCount]>
50
51 Totaling fElemCount+2 entries per keyframe
52 */
53
getDuration(SkMSec * startTime,SkMSec * endTime) const54 bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
55 if (fFrameCount == 0) {
56 return false;
57 }
58
59 if (startTime) {
60 *startTime = fTimes[0].fTime;
61 }
62 if (endTime) {
63 *endTime = fTimes[fFrameCount - 1].fTime;
64 }
65 return true;
66 }
67
ComputeRelativeT(SkMSec time,SkMSec prevTime,SkMSec nextTime,const SkScalar blend[4])68 SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime,
69 SkMSec nextTime, const SkScalar blend[4]) {
70 SkASSERT(time > prevTime && time < nextTime);
71
72 SkScalar t = SkScalarDiv((SkScalar)(time - prevTime),
73 (SkScalar)(nextTime - prevTime));
74 return blend ?
75 SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
76 }
77
timeToT(SkMSec time,SkScalar * T,int * indexPtr,SkBool * exactPtr) const78 SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
79 int* indexPtr, SkBool* exactPtr) const {
80 SkASSERT(fFrameCount > 0);
81 Result result = kNormal_Result;
82 if (fRepeat != SK_Scalar1) {
83 SkMSec startTime = 0, endTime = 0; // initialize to avoid warning
84 this->getDuration(&startTime, &endTime);
85 SkMSec totalTime = endTime - startTime;
86 SkMSec offsetTime = time - startTime;
87 endTime = SkScalarMulFloor(fRepeat, totalTime);
88 if (offsetTime >= endTime) {
89 SkScalar fraction = SkScalarFraction(fRepeat);
90 offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
91 SkScalarMulFloor(fraction, totalTime);
92 result = kFreezeEnd_Result;
93 } else {
94 int mirror = fFlags & kMirror;
95 offsetTime = offsetTime % (totalTime << mirror);
96 if (offsetTime > totalTime) { // can only be true if fMirror is true
97 offsetTime = (totalTime << 1) - offsetTime;
98 }
99 }
100 time = offsetTime + startTime;
101 }
102
103 int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
104 sizeof(SkTimeCode));
105
106 bool exact = true;
107
108 if (index < 0) {
109 index = ~index;
110 if (index == 0) {
111 result = kFreezeStart_Result;
112 } else if (index == fFrameCount) {
113 if (fFlags & kReset) {
114 index = 0;
115 } else {
116 index -= 1;
117 }
118 result = kFreezeEnd_Result;
119 } else {
120 exact = false;
121 }
122 }
123 SkASSERT(index < fFrameCount);
124 const SkTimeCode* nextTime = &fTimes[index];
125 SkMSec nextT = nextTime[0].fTime;
126 if (exact) {
127 *T = 0;
128 } else {
129 SkMSec prevT = nextTime[-1].fTime;
130 *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
131 }
132 *indexPtr = index;
133 *exactPtr = exact;
134 return result;
135 }
136
137
SkInterpolator()138 SkInterpolator::SkInterpolator() {
139 INHERITED::reset(0, 0);
140 fValues = NULL;
141 SkDEBUGCODE(fScalarsArray = NULL;)
142 }
143
SkInterpolator(int elemCount,int frameCount)144 SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
145 SkASSERT(elemCount > 0);
146 this->reset(elemCount, frameCount);
147 }
148
reset(int elemCount,int frameCount)149 void SkInterpolator::reset(int elemCount, int frameCount) {
150 INHERITED::reset(elemCount, frameCount);
151 fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
152 sizeof(SkTimeCode)) * frameCount);
153 fTimes = (SkTimeCode*) fStorage;
154 fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
155 #ifdef SK_DEBUG
156 fTimesArray = (SkTimeCode(*)[10]) fTimes;
157 fScalarsArray = (SkScalar(*)[10]) fValues;
158 #endif
159 }
160
161 #define SK_Fixed1Third (SK_Fixed1/3)
162 #define SK_Fixed2Third (SK_Fixed1*2/3)
163
164 static const SkScalar gIdentityBlend[4] = {
165 #ifdef SK_SCALAR_IS_FLOAT
166 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
167 #else
168 SK_Fixed1Third, SK_Fixed1Third, SK_Fixed2Third, SK_Fixed2Third
169 #endif
170 };
171
setKeyFrame(int index,SkMSec time,const SkScalar values[],const SkScalar blend[4])172 bool SkInterpolator::setKeyFrame(int index, SkMSec time,
173 const SkScalar values[], const SkScalar blend[4]) {
174 SkASSERT(values != NULL);
175
176 if (blend == NULL) {
177 blend = gIdentityBlend;
178 }
179
180 bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
181 sizeof(SkTimeCode));
182 SkASSERT(success);
183 if (success) {
184 SkTimeCode* timeCode = &fTimes[index];
185 timeCode->fTime = time;
186 memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
187 SkScalar* dst = &fValues[fElemCount * index];
188 memcpy(dst, values, fElemCount * sizeof(SkScalar));
189 }
190 return success;
191 }
192
timeToValues(SkMSec time,SkScalar values[]) const193 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
194 SkScalar values[]) const {
195 SkScalar T;
196 int index;
197 SkBool exact;
198 Result result = timeToT(time, &T, &index, &exact);
199 if (values) {
200 const SkScalar* nextSrc = &fValues[index * fElemCount];
201
202 if (exact) {
203 memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
204 } else {
205 SkASSERT(index > 0);
206
207 const SkScalar* prevSrc = nextSrc - fElemCount;
208
209 for (int i = fElemCount - 1; i >= 0; --i) {
210 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
211 }
212 }
213 }
214 return result;
215 }
216
217 ///////////////////////////////////////////////////////////////////////////////
218
219 typedef int Dot14;
220 #define Dot14_ONE (1 << 14)
221 #define Dot14_HALF (1 << 13)
222
223 #define Dot14ToFloat(x) ((x) / 16384.f)
224
Dot14Mul(Dot14 a,Dot14 b)225 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
226 return (a * b + Dot14_HALF) >> 14;
227 }
228
eval_cubic(Dot14 t,Dot14 A,Dot14 B,Dot14 C)229 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
230 return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
231 }
232
pin_and_convert(SkScalar x)233 static inline Dot14 pin_and_convert(SkScalar x) {
234 if (x <= 0) {
235 return 0;
236 }
237 if (x >= SK_Scalar1) {
238 return Dot14_ONE;
239 }
240 return SkScalarToFixed(x) >> 2;
241 }
242
SkUnitCubicInterp(SkScalar value,SkScalar bx,SkScalar by,SkScalar cx,SkScalar cy)243 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
244 SkScalar cx, SkScalar cy) {
245 // pin to the unit-square, and convert to 2.14
246 Dot14 x = pin_and_convert(value);
247
248 if (x == 0) return 0;
249 if (x == Dot14_ONE) return SK_Scalar1;
250
251 Dot14 b = pin_and_convert(bx);
252 Dot14 c = pin_and_convert(cx);
253
254 // Now compute our coefficients from the control points
255 // t -> 3b
256 // t^2 -> 3c - 6b
257 // t^3 -> 3b - 3c + 1
258 Dot14 A = 3*b;
259 Dot14 B = 3*(c - 2*b);
260 Dot14 C = 3*(b - c) + Dot14_ONE;
261
262 // Now search for a t value given x
263 Dot14 t = Dot14_HALF;
264 Dot14 dt = Dot14_HALF;
265 for (int i = 0; i < 13; i++) {
266 dt >>= 1;
267 Dot14 guess = eval_cubic(t, A, B, C);
268 if (x < guess) {
269 t -= dt;
270 } else {
271 t += dt;
272 }
273 }
274
275 // Now we have t, so compute the coeff for Y and evaluate
276 b = pin_and_convert(by);
277 c = pin_and_convert(cy);
278 A = 3*b;
279 B = 3*(c - 2*b);
280 C = 3*(b - c) + Dot14_ONE;
281 return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
282 }
283
284 ///////////////////////////////////////////////////////////////////////////////
285 ///////////////////////////////////////////////////////////////////////////////
286
287 #ifdef SK_DEBUG
288
289 #ifdef SK_SUPPORT_UNITTEST
iset(SkScalar array[3],int a,int b,int c)290 static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
291 array[0] = SkIntToScalar(a);
292 array[1] = SkIntToScalar(b);
293 array[2] = SkIntToScalar(c);
294 return array;
295 }
296 #endif
297
UnitTest()298 void SkInterpolator::UnitTest() {
299 #ifdef SK_SUPPORT_UNITTEST
300 SkInterpolator inter(3, 2);
301 SkScalar v1[3], v2[3], v[3], vv[3];
302 Result result;
303
304 inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
305 inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
306
307 result = inter.timeToValues(0, v);
308 SkASSERT(result == kFreezeStart_Result);
309 SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
310
311 result = inter.timeToValues(99, v);
312 SkASSERT(result == kFreezeStart_Result);
313 SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
314
315 result = inter.timeToValues(100, v);
316 SkASSERT(result == kNormal_Result);
317 SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
318
319 result = inter.timeToValues(200, v);
320 SkASSERT(result == kNormal_Result);
321 SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
322
323 result = inter.timeToValues(201, v);
324 SkASSERT(result == kFreezeEnd_Result);
325 SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
326
327 result = inter.timeToValues(150, v);
328 SkASSERT(result == kNormal_Result);
329 SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
330
331 result = inter.timeToValues(125, v);
332 SkASSERT(result == kNormal_Result);
333 result = inter.timeToValues(175, v);
334 SkASSERT(result == kNormal_Result);
335 #endif
336 }
337
338 #endif
339
340