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 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 333
