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 = (SkScalar)(time - prevTime) / (SkScalar)(nextTime - prevTime);
     66     return blend ?
     67             SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
     68 }
     69 
     70 SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
     71                                         int* indexPtr, SkBool* exactPtr) const {
     72     SkASSERT(fFrameCount > 0);
     73     Result  result = kNormal_Result;
     74     if (fRepeat != SK_Scalar1) {
     75         SkMSec startTime = 0, endTime = 0;  // initialize to avoid warning
     76         this->getDuration(&startTime, &endTime);
     77         SkMSec totalTime = endTime - startTime;
     78         SkMSec offsetTime = time - startTime;
     79         endTime = SkScalarFloorToInt(fRepeat * totalTime);
     80         if (offsetTime >= endTime) {
     81             SkScalar fraction = SkScalarFraction(fRepeat);
     82             offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
     83                 (SkMSec) SkScalarFloorToInt(fraction * totalTime);
     84             result = kFreezeEnd_Result;
     85         } else {
     86             int mirror = fFlags & kMirror;
     87             offsetTime = offsetTime % (totalTime << mirror);
     88             if (offsetTime > totalTime) { // can only be true if fMirror is true
     89                 offsetTime = (totalTime << 1) - offsetTime;
     90             }
     91         }
     92         time = offsetTime + startTime;
     93     }
     94 
     95     int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
     96                                   sizeof(SkTimeCode));
     97 
     98     bool    exact = true;
     99 
    100     if (index < 0) {
    101         index = ~index;
    102         if (index == 0) {
    103             result = kFreezeStart_Result;
    104         } else if (index == fFrameCount) {
    105             if (fFlags & kReset) {
    106                 index = 0;
    107             } else {
    108                 index -= 1;
    109             }
    110             result = kFreezeEnd_Result;
    111         } else {
    112             exact = false;
    113         }
    114     }
    115     SkASSERT(index < fFrameCount);
    116     const SkTimeCode* nextTime = &fTimes[index];
    117     SkMSec   nextT = nextTime[0].fTime;
    118     if (exact) {
    119         *T = 0;
    120     } else {
    121         SkMSec prevT = nextTime[-1].fTime;
    122         *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
    123     }
    124     *indexPtr = index;
    125     *exactPtr = exact;
    126     return result;
    127 }
    128 
    129 
    130 SkInterpolator::SkInterpolator() {
    131     INHERITED::reset(0, 0);
    132     fValues = NULL;
    133     SkDEBUGCODE(fScalarsArray = NULL;)
    134 }
    135 
    136 SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
    137     SkASSERT(elemCount > 0);
    138     this->reset(elemCount, frameCount);
    139 }
    140 
    141 void SkInterpolator::reset(int elemCount, int frameCount) {
    142     INHERITED::reset(elemCount, frameCount);
    143     fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
    144                                 sizeof(SkTimeCode)) * frameCount);
    145     fTimes = (SkTimeCode*) fStorage;
    146     fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
    147 #ifdef SK_DEBUG
    148     fTimesArray = (SkTimeCode(*)[10]) fTimes;
    149     fScalarsArray = (SkScalar(*)[10]) fValues;
    150 #endif
    151 }
    152 
    153 #define SK_Fixed1Third      (SK_Fixed1/3)
    154 #define SK_Fixed2Third      (SK_Fixed1*2/3)
    155 
    156 static const SkScalar gIdentityBlend[4] = {
    157     0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
    158 };
    159 
    160 bool SkInterpolator::setKeyFrame(int index, SkMSec time,
    161                             const SkScalar values[], const SkScalar blend[4]) {
    162     SkASSERT(values != NULL);
    163 
    164     if (blend == NULL) {
    165         blend = gIdentityBlend;
    166     }
    167 
    168     bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
    169                                                sizeof(SkTimeCode));
    170     SkASSERT(success);
    171     if (success) {
    172         SkTimeCode* timeCode = &fTimes[index];
    173         timeCode->fTime = time;
    174         memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
    175         SkScalar* dst = &fValues[fElemCount * index];
    176         memcpy(dst, values, fElemCount * sizeof(SkScalar));
    177     }
    178     return success;
    179 }
    180 
    181 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
    182                                                     SkScalar values[]) const {
    183     SkScalar T;
    184     int index;
    185     SkBool exact;
    186     Result result = timeToT(time, &T, &index, &exact);
    187     if (values) {
    188         const SkScalar* nextSrc = &fValues[index * fElemCount];
    189 
    190         if (exact) {
    191             memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
    192         } else {
    193             SkASSERT(index > 0);
    194 
    195             const SkScalar* prevSrc = nextSrc - fElemCount;
    196 
    197             for (int i = fElemCount - 1; i >= 0; --i) {
    198                 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
    199             }
    200         }
    201     }
    202     return result;
    203 }
    204 
    205 ///////////////////////////////////////////////////////////////////////////////
    206 
    207 typedef int Dot14;
    208 #define Dot14_ONE       (1 << 14)
    209 #define Dot14_HALF      (1 << 13)
    210 
    211 #define Dot14ToFloat(x) ((x) / 16384.f)
    212 
    213 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
    214     return (a * b + Dot14_HALF) >> 14;
    215 }
    216 
    217 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
    218     return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
    219 }
    220 
    221 static inline Dot14 pin_and_convert(SkScalar x) {
    222     if (x <= 0) {
    223         return 0;
    224     }
    225     if (x >= SK_Scalar1) {
    226         return Dot14_ONE;
    227     }
    228     return SkScalarToFixed(x) >> 2;
    229 }
    230 
    231 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
    232                            SkScalar cx, SkScalar cy) {
    233     // pin to the unit-square, and convert to 2.14
    234     Dot14 x = pin_and_convert(value);
    235 
    236     if (x == 0) return 0;
    237     if (x == Dot14_ONE) return SK_Scalar1;
    238 
    239     Dot14 b = pin_and_convert(bx);
    240     Dot14 c = pin_and_convert(cx);
    241 
    242     // Now compute our coefficients from the control points
    243     //  t   -> 3b
    244     //  t^2 -> 3c - 6b
    245     //  t^3 -> 3b - 3c + 1
    246     Dot14 A = 3*b;
    247     Dot14 B = 3*(c - 2*b);
    248     Dot14 C = 3*(b - c) + Dot14_ONE;
    249 
    250     // Now search for a t value given x
    251     Dot14   t = Dot14_HALF;
    252     Dot14   dt = Dot14_HALF;
    253     for (int i = 0; i < 13; i++) {
    254         dt >>= 1;
    255         Dot14 guess = eval_cubic(t, A, B, C);
    256         if (x < guess) {
    257             t -= dt;
    258         } else {
    259             t += dt;
    260         }
    261     }
    262 
    263     // Now we have t, so compute the coeff for Y and evaluate
    264     b = pin_and_convert(by);
    265     c = pin_and_convert(cy);
    266     A = 3*b;
    267     B = 3*(c - 2*b);
    268     C = 3*(b - c) + Dot14_ONE;
    269     return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
    270 }
    271