• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 = SkScalarFloorToInt(fRepeat * totalTime);
81         if (offsetTime >= endTime) {
82             SkScalar fraction = SkScalarFraction(fRepeat);
83             offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
84                 (SkMSec) SkScalarFloorToInt(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     0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
159 };
160 
setKeyFrame(int index,SkMSec time,const SkScalar values[],const SkScalar blend[4])161 bool SkInterpolator::setKeyFrame(int index, SkMSec time,
162                             const SkScalar values[], const SkScalar blend[4]) {
163     SkASSERT(values != NULL);
164 
165     if (blend == NULL) {
166         blend = gIdentityBlend;
167     }
168 
169     bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
170                                                sizeof(SkTimeCode));
171     SkASSERT(success);
172     if (success) {
173         SkTimeCode* timeCode = &fTimes[index];
174         timeCode->fTime = time;
175         memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
176         SkScalar* dst = &fValues[fElemCount * index];
177         memcpy(dst, values, fElemCount * sizeof(SkScalar));
178     }
179     return success;
180 }
181 
timeToValues(SkMSec time,SkScalar values[]) const182 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
183                                                     SkScalar values[]) const {
184     SkScalar T;
185     int index;
186     SkBool exact;
187     Result result = timeToT(time, &T, &index, &exact);
188     if (values) {
189         const SkScalar* nextSrc = &fValues[index * fElemCount];
190 
191         if (exact) {
192             memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
193         } else {
194             SkASSERT(index > 0);
195 
196             const SkScalar* prevSrc = nextSrc - fElemCount;
197 
198             for (int i = fElemCount - 1; i >= 0; --i) {
199                 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
200             }
201         }
202     }
203     return result;
204 }
205 
206 ///////////////////////////////////////////////////////////////////////////////
207 
208 typedef int Dot14;
209 #define Dot14_ONE       (1 << 14)
210 #define Dot14_HALF      (1 << 13)
211 
212 #define Dot14ToFloat(x) ((x) / 16384.f)
213 
Dot14Mul(Dot14 a,Dot14 b)214 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
215     return (a * b + Dot14_HALF) >> 14;
216 }
217 
eval_cubic(Dot14 t,Dot14 A,Dot14 B,Dot14 C)218 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
219     return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
220 }
221 
pin_and_convert(SkScalar x)222 static inline Dot14 pin_and_convert(SkScalar x) {
223     if (x <= 0) {
224         return 0;
225     }
226     if (x >= SK_Scalar1) {
227         return Dot14_ONE;
228     }
229     return SkScalarToFixed(x) >> 2;
230 }
231 
SkUnitCubicInterp(SkScalar value,SkScalar bx,SkScalar by,SkScalar cx,SkScalar cy)232 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
233                            SkScalar cx, SkScalar cy) {
234     // pin to the unit-square, and convert to 2.14
235     Dot14 x = pin_and_convert(value);
236 
237     if (x == 0) return 0;
238     if (x == Dot14_ONE) return SK_Scalar1;
239 
240     Dot14 b = pin_and_convert(bx);
241     Dot14 c = pin_and_convert(cx);
242 
243     // Now compute our coefficients from the control points
244     //  t   -> 3b
245     //  t^2 -> 3c - 6b
246     //  t^3 -> 3b - 3c + 1
247     Dot14 A = 3*b;
248     Dot14 B = 3*(c - 2*b);
249     Dot14 C = 3*(b - c) + Dot14_ONE;
250 
251     // Now search for a t value given x
252     Dot14   t = Dot14_HALF;
253     Dot14   dt = Dot14_HALF;
254     for (int i = 0; i < 13; i++) {
255         dt >>= 1;
256         Dot14 guess = eval_cubic(t, A, B, C);
257         if (x < guess) {
258             t -= dt;
259         } else {
260             t += dt;
261         }
262     }
263 
264     // Now we have t, so compute the coeff for Y and evaluate
265     b = pin_and_convert(by);
266     c = pin_and_convert(cy);
267     A = 3*b;
268     B = 3*(c - 2*b);
269     C = 3*(b - c) + Dot14_ONE;
270     return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
271 }
272 
273 ///////////////////////////////////////////////////////////////////////////////
274 ///////////////////////////////////////////////////////////////////////////////
275 
276 #ifdef SK_DEBUG
277 
278 #ifdef SK_SUPPORT_UNITTEST
iset(SkScalar array[3],int a,int b,int c)279     static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
280         array[0] = SkIntToScalar(a);
281         array[1] = SkIntToScalar(b);
282         array[2] = SkIntToScalar(c);
283         return array;
284     }
285 #endif
286 
UnitTest()287 void SkInterpolator::UnitTest() {
288 #ifdef SK_SUPPORT_UNITTEST
289     SkInterpolator  inter(3, 2);
290     SkScalar        v1[3], v2[3], v[3], vv[3];
291     Result          result;
292 
293     inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
294     inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
295 
296     result = inter.timeToValues(0, v);
297     SkASSERT(result == kFreezeStart_Result);
298     SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
299 
300     result = inter.timeToValues(99, v);
301     SkASSERT(result == kFreezeStart_Result);
302     SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
303 
304     result = inter.timeToValues(100, v);
305     SkASSERT(result == kNormal_Result);
306     SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
307 
308     result = inter.timeToValues(200, v);
309     SkASSERT(result == kNormal_Result);
310     SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
311 
312     result = inter.timeToValues(201, v);
313     SkASSERT(result == kFreezeEnd_Result);
314     SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
315 
316     result = inter.timeToValues(150, v);
317     SkASSERT(result == kNormal_Result);
318     SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
319 
320     result = inter.timeToValues(125, v);
321     SkASSERT(result == kNormal_Result);
322     result = inter.timeToValues(175, v);
323     SkASSERT(result == kNormal_Result);
324 #endif
325 }
326 
327 #endif
328