Home | History | Annotate | Download | only in utils 
      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 
     14 SkInterpolatorBase::SkInterpolatorBase() {
     15     fStorage    = NULL;
     16     fTimes      = NULL;
     17     SkDEBUGCODE(fTimesArray = NULL;)
     18 }
     19 
     20 SkInterpolatorBase::~SkInterpolatorBase() {
     21     if (fStorage) {
     22         sk_free(fStorage);
     23     }
     24 }
     25 
     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 
     47 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 
     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 
     71 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 
    131 SkInterpolator::SkInterpolator() {
    132     INHERITED::reset(0, 0);
    133     fValues = NULL;
    134     SkDEBUGCODE(fScalarsArray = NULL;)
    135 }
    136 
    137 SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
    138     SkASSERT(elemCount > 0);
    139     this->reset(elemCount, frameCount);
    140 }
    141 
    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 
    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 
    186 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 
    218 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
    219     return (a * b + Dot14_HALF) >> 14;
    220 }
    221 
    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 
    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 
    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
    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 
    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