1 /* 2 * Copyright (C) 2006-2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "SkInterpolator.h" 18 #include "SkMath.h" 19 #include "SkTSearch.h" 20 21 SkInterpolatorBase::SkInterpolatorBase() { 22 fStorage = NULL; 23 fTimes = NULL; 24 SkDEBUGCODE(fTimesArray = NULL;) 25 } 26 27 SkInterpolatorBase::~SkInterpolatorBase() { 28 if (fStorage) { 29 sk_free(fStorage); 30 } 31 } 32 33 void SkInterpolatorBase::reset(int elemCount, int frameCount) { 34 fFlags = 0; 35 fElemCount = SkToU8(elemCount); 36 fFrameCount = SkToS16(frameCount); 37 fRepeat = SK_Scalar1; 38 if (fStorage) { 39 sk_free(fStorage); 40 fStorage = NULL; 41 fTimes = NULL; 42 SkDEBUGCODE(fTimesArray = NULL); 43 } 44 } 45 46 /* Each value[] run is formated as: 47 <time (in msec)> 48 <blend> 49 <data[fElemCount]> 50 51 Totaling fElemCount+2 entries per keyframe 52 */ 53 54 bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const { 55 if (fFrameCount == 0) { 56 return false; 57 } 58 59 if (startTime) { 60 *startTime = fTimes[0].fTime; 61 } 62 if (endTime) { 63 *endTime = fTimes[fFrameCount - 1].fTime; 64 } 65 return true; 66 } 67 68 SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime, 69 SkMSec nextTime, const SkScalar blend[4]) { 70 SkASSERT(time > prevTime && time < nextTime); 71 72 SkScalar t = SkScalarDiv((SkScalar)(time - prevTime), 73 (SkScalar)(nextTime - prevTime)); 74 return blend ? 75 SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t; 76 } 77 78 SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T, 79 int* indexPtr, SkBool* exactPtr) const { 80 SkASSERT(fFrameCount > 0); 81 Result result = kNormal_Result; 82 if (fRepeat != SK_Scalar1) { 83 SkMSec startTime = 0, endTime = 0; // initialize to avoid warning 84 this->getDuration(&startTime, &endTime); 85 SkMSec totalTime = endTime - startTime; 86 SkMSec offsetTime = time - startTime; 87 endTime = SkScalarMulFloor(fRepeat, totalTime); 88 if (offsetTime >= endTime) { 89 SkScalar fraction = SkScalarFraction(fRepeat); 90 offsetTime = fraction == 0 && fRepeat > 0 ? totalTime : 91 SkScalarMulFloor(fraction, totalTime); 92 result = kFreezeEnd_Result; 93 } else { 94 int mirror = fFlags & kMirror; 95 offsetTime = offsetTime % (totalTime << mirror); 96 if (offsetTime > totalTime) { // can only be true if fMirror is true 97 offsetTime = (totalTime << 1) - offsetTime; 98 } 99 } 100 time = offsetTime + startTime; 101 } 102 103 int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time, 104 sizeof(SkTimeCode)); 105 106 bool exact = true; 107 108 if (index < 0) { 109 index = ~index; 110 if (index == 0) { 111 result = kFreezeStart_Result; 112 } else if (index == fFrameCount) { 113 if (fFlags & kReset) { 114 index = 0; 115 } else { 116 index -= 1; 117 } 118 result = kFreezeEnd_Result; 119 } else { 120 exact = false; 121 } 122 } 123 SkASSERT(index < fFrameCount); 124 const SkTimeCode* nextTime = &fTimes[index]; 125 SkMSec nextT = nextTime[0].fTime; 126 if (exact) { 127 *T = 0; 128 } else { 129 SkMSec prevT = nextTime[-1].fTime; 130 *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend); 131 } 132 *indexPtr = index; 133 *exactPtr = exact; 134 return result; 135 } 136 137 138 SkInterpolator::SkInterpolator() { 139 INHERITED::reset(0, 0); 140 fValues = NULL; 141 SkDEBUGCODE(fScalarsArray = NULL;) 142 } 143 144 SkInterpolator::SkInterpolator(int elemCount, int frameCount) { 145 SkASSERT(elemCount > 0); 146 this->reset(elemCount, frameCount); 147 } 148 149 void SkInterpolator::reset(int elemCount, int frameCount) { 150 INHERITED::reset(elemCount, frameCount); 151 fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount + 152 sizeof(SkTimeCode)) * frameCount); 153 fTimes = (SkTimeCode*) fStorage; 154 fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount); 155 #ifdef SK_DEBUG 156 fTimesArray = (SkTimeCode(*)[10]) fTimes; 157 fScalarsArray = (SkScalar(*)[10]) fValues; 158 #endif 159 } 160 161 #define SK_Fixed1Third (SK_Fixed1/3) 162 #define SK_Fixed2Third (SK_Fixed1*2/3) 163 164 static const SkScalar gIdentityBlend[4] = { 165 #ifdef SK_SCALAR_IS_FLOAT 166 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f 167 #else 168 SK_Fixed1Third, SK_Fixed1Third, SK_Fixed2Third, SK_Fixed2Third 169 #endif 170 }; 171 172 bool SkInterpolator::setKeyFrame(int index, SkMSec time, 173 const SkScalar values[], const SkScalar blend[4]) { 174 SkASSERT(values != NULL); 175 176 if (blend == NULL) { 177 blend = gIdentityBlend; 178 } 179 180 bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time, 181 sizeof(SkTimeCode)); 182 SkASSERT(success); 183 if (success) { 184 SkTimeCode* timeCode = &fTimes[index]; 185 timeCode->fTime = time; 186 memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend)); 187 SkScalar* dst = &fValues[fElemCount * index]; 188 memcpy(dst, values, fElemCount * sizeof(SkScalar)); 189 } 190 return success; 191 } 192 193 SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time, 194 SkScalar values[]) const { 195 SkScalar T; 196 int index; 197 SkBool exact; 198 Result result = timeToT(time, &T, &index, &exact); 199 if (values) { 200 const SkScalar* nextSrc = &fValues[index * fElemCount]; 201 202 if (exact) { 203 memcpy(values, nextSrc, fElemCount * sizeof(SkScalar)); 204 } else { 205 SkASSERT(index > 0); 206 207 const SkScalar* prevSrc = nextSrc - fElemCount; 208 209 for (int i = fElemCount - 1; i >= 0; --i) { 210 values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T); 211 } 212 } 213 } 214 return result; 215 } 216 217 /////////////////////////////////////////////////////////////////////////////// 218 219 typedef int Dot14; 220 #define Dot14_ONE (1 << 14) 221 #define Dot14_HALF (1 << 13) 222 223 #define Dot14ToFloat(x) ((x) / 16384.f) 224 225 static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) { 226 return (a * b + Dot14_HALF) >> 14; 227 } 228 229 static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) { 230 return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t); 231 } 232 233 static inline Dot14 pin_and_convert(SkScalar x) { 234 if (x <= 0) { 235 return 0; 236 } 237 if (x >= SK_Scalar1) { 238 return Dot14_ONE; 239 } 240 return SkScalarToFixed(x) >> 2; 241 } 242 243 SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by, 244 SkScalar cx, SkScalar cy) { 245 // pin to the unit-square, and convert to 2.14 246 Dot14 x = pin_and_convert(value); 247 248 if (x == 0) return 0; 249 if (x == Dot14_ONE) return SK_Scalar1; 250 251 Dot14 b = pin_and_convert(bx); 252 Dot14 c = pin_and_convert(cx); 253 254 // Now compute our coefficients from the control points 255 // t -> 3b 256 // t^2 -> 3c - 6b 257 // t^3 -> 3b - 3c + 1 258 Dot14 A = 3*b; 259 Dot14 B = 3*(c - 2*b); 260 Dot14 C = 3*(b - c) + Dot14_ONE; 261 262 // Now search for a t value given x 263 Dot14 t = Dot14_HALF; 264 Dot14 dt = Dot14_HALF; 265 for (int i = 0; i < 13; i++) { 266 dt >>= 1; 267 Dot14 guess = eval_cubic(t, A, B, C); 268 if (x < guess) { 269 t -= dt; 270 } else { 271 t += dt; 272 } 273 } 274 275 // Now we have t, so compute the coeff for Y and evaluate 276 b = pin_and_convert(by); 277 c = pin_and_convert(cy); 278 A = 3*b; 279 B = 3*(c - 2*b); 280 C = 3*(b - c) + Dot14_ONE; 281 return SkFixedToScalar(eval_cubic(t, A, B, C) << 2); 282 } 283 284 /////////////////////////////////////////////////////////////////////////////// 285 /////////////////////////////////////////////////////////////////////////////// 286 287 #ifdef SK_DEBUG 288 289 #ifdef SK_SUPPORT_UNITTEST 290 static SkScalar* iset(SkScalar array[3], int a, int b, int c) { 291 array[0] = SkIntToScalar(a); 292 array[1] = SkIntToScalar(b); 293 array[2] = SkIntToScalar(c); 294 return array; 295 } 296 #endif 297 298 void SkInterpolator::UnitTest() { 299 #ifdef SK_SUPPORT_UNITTEST 300 SkInterpolator inter(3, 2); 301 SkScalar v1[3], v2[3], v[3], vv[3]; 302 Result result; 303 304 inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0); 305 inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330)); 306 307 result = inter.timeToValues(0, v); 308 SkASSERT(result == kFreezeStart_Result); 309 SkASSERT(memcmp(v, v1, sizeof(v)) == 0); 310 311 result = inter.timeToValues(99, v); 312 SkASSERT(result == kFreezeStart_Result); 313 SkASSERT(memcmp(v, v1, sizeof(v)) == 0); 314 315 result = inter.timeToValues(100, v); 316 SkASSERT(result == kNormal_Result); 317 SkASSERT(memcmp(v, v1, sizeof(v)) == 0); 318 319 result = inter.timeToValues(200, v); 320 SkASSERT(result == kNormal_Result); 321 SkASSERT(memcmp(v, v2, sizeof(v)) == 0); 322 323 result = inter.timeToValues(201, v); 324 SkASSERT(result == kFreezeEnd_Result); 325 SkASSERT(memcmp(v, v2, sizeof(v)) == 0); 326 327 result = inter.timeToValues(150, v); 328 SkASSERT(result == kNormal_Result); 329 SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0); 330 331 result = inter.timeToValues(125, v); 332 SkASSERT(result == kNormal_Result); 333 result = inter.timeToValues(175, v); 334 SkASSERT(result == kNormal_Result); 335 #endif 336 } 337 338 #endif 339 340
