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 = 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 
    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     0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
    159 };
    160 
    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 
    182 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 
    214 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
    215     return (a * b + Dot14_HALF) >> 14;
    216 }
    217 
    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 
    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 
    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
    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 
    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