← Back to branch summary

~ubuntu-branches/ubuntu/karmic/gears/karmic

« back to all changes in this revision

Viewing changes to third_party/skia/src/utils/SkInterpolator.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Stefan Lesicnik
  • Date: 2009-04-30 19:15:25 UTC
  • Revision ID: james.westby@ubuntu.com-20090430191525-0790sb5wzg8ou0xb
Tags: upstream-0.5.21.0~svn3334+dfsg
Import upstream version 0.5.21.0~svn3334+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
third_party/skia/src/utils/SkInterpolator.cpp
 
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
 
 
21
SkInterpolatorBase::SkInterpolatorBase() {
 
22
    fStorage    = NULL;
 
23
    fTimes      = NULL;
 
24
    SkDEBUGCODE(fTimesArray = NULL;)
 
25
}
 
26
 
 
27
SkInterpolatorBase::~SkInterpolatorBase() {
 
28
    if (fStorage) {
 
29
        sk_free(fStorage);
 
30
    }
 
31
}
 
32
 
 
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
 
 
54
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
 
 
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
 
 
78
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
 
 
138
SkInterpolator::SkInterpolator() {
 
139
    INHERITED::reset(0, 0);
 
140
    fValues = NULL;
 
141
    SkDEBUGCODE(fScalarsArray = NULL;)
 
142
}
 
143
 
 
144
SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
 
145
    SkASSERT(elemCount > 0);
 
146
    this->reset(elemCount, frameCount);
 
147
}
 
148
 
 
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
 
 
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
 
 
193
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
 
 
225
static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
 
226
    return (a * b + Dot14_HALF) >> 14;
 
227
}
 
228
 
 
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
 
 
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
 
 
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
 
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
 
 
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