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
