1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/utils/SkInterpolator.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,327 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2008 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkInterpolator.h"
1.14 +#include "SkMath.h"
1.15 +#include "SkTSearch.h"
1.16 +
1.17 +SkInterpolatorBase::SkInterpolatorBase() {
1.18 + fStorage = NULL;
1.19 + fTimes = NULL;
1.20 + SkDEBUGCODE(fTimesArray = NULL;)
1.21 +}
1.22 +
1.23 +SkInterpolatorBase::~SkInterpolatorBase() {
1.24 + if (fStorage) {
1.25 + sk_free(fStorage);
1.26 + }
1.27 +}
1.28 +
1.29 +void SkInterpolatorBase::reset(int elemCount, int frameCount) {
1.30 + fFlags = 0;
1.31 + fElemCount = SkToU8(elemCount);
1.32 + fFrameCount = SkToS16(frameCount);
1.33 + fRepeat = SK_Scalar1;
1.34 + if (fStorage) {
1.35 + sk_free(fStorage);
1.36 + fStorage = NULL;
1.37 + fTimes = NULL;
1.38 + SkDEBUGCODE(fTimesArray = NULL);
1.39 + }
1.40 +}
1.41 +
1.42 +/* Each value[] run is formated as:
1.43 + <time (in msec)>
1.44 + <blend>
1.45 + <data[fElemCount]>
1.46 +
1.47 + Totaling fElemCount+2 entries per keyframe
1.48 +*/
1.49 +
1.50 +bool SkInterpolatorBase::getDuration(SkMSec* startTime, SkMSec* endTime) const {
1.51 + if (fFrameCount == 0) {
1.52 + return false;
1.53 + }
1.54 +
1.55 + if (startTime) {
1.56 + *startTime = fTimes[0].fTime;
1.57 + }
1.58 + if (endTime) {
1.59 + *endTime = fTimes[fFrameCount - 1].fTime;
1.60 + }
1.61 + return true;
1.62 +}
1.63 +
1.64 +SkScalar SkInterpolatorBase::ComputeRelativeT(SkMSec time, SkMSec prevTime,
1.65 + SkMSec nextTime, const SkScalar blend[4]) {
1.66 + SkASSERT(time > prevTime && time < nextTime);
1.67 +
1.68 + SkScalar t = SkScalarDiv((SkScalar)(time - prevTime),
1.69 + (SkScalar)(nextTime - prevTime));
1.70 + return blend ?
1.71 + SkUnitCubicInterp(t, blend[0], blend[1], blend[2], blend[3]) : t;
1.72 +}
1.73 +
1.74 +SkInterpolatorBase::Result SkInterpolatorBase::timeToT(SkMSec time, SkScalar* T,
1.75 + int* indexPtr, SkBool* exactPtr) const {
1.76 + SkASSERT(fFrameCount > 0);
1.77 + Result result = kNormal_Result;
1.78 + if (fRepeat != SK_Scalar1) {
1.79 + SkMSec startTime = 0, endTime = 0; // initialize to avoid warning
1.80 + this->getDuration(&startTime, &endTime);
1.81 + SkMSec totalTime = endTime - startTime;
1.82 + SkMSec offsetTime = time - startTime;
1.83 + endTime = SkScalarFloorToInt(fRepeat * totalTime);
1.84 + if (offsetTime >= endTime) {
1.85 + SkScalar fraction = SkScalarFraction(fRepeat);
1.86 + offsetTime = fraction == 0 && fRepeat > 0 ? totalTime :
1.87 + (SkMSec) SkScalarFloorToInt(fraction * totalTime);
1.88 + result = kFreezeEnd_Result;
1.89 + } else {
1.90 + int mirror = fFlags & kMirror;
1.91 + offsetTime = offsetTime % (totalTime << mirror);
1.92 + if (offsetTime > totalTime) { // can only be true if fMirror is true
1.93 + offsetTime = (totalTime << 1) - offsetTime;
1.94 + }
1.95 + }
1.96 + time = offsetTime + startTime;
1.97 + }
1.98 +
1.99 + int index = SkTSearch<SkMSec>(&fTimes[0].fTime, fFrameCount, time,
1.100 + sizeof(SkTimeCode));
1.101 +
1.102 + bool exact = true;
1.103 +
1.104 + if (index < 0) {
1.105 + index = ~index;
1.106 + if (index == 0) {
1.107 + result = kFreezeStart_Result;
1.108 + } else if (index == fFrameCount) {
1.109 + if (fFlags & kReset) {
1.110 + index = 0;
1.111 + } else {
1.112 + index -= 1;
1.113 + }
1.114 + result = kFreezeEnd_Result;
1.115 + } else {
1.116 + exact = false;
1.117 + }
1.118 + }
1.119 + SkASSERT(index < fFrameCount);
1.120 + const SkTimeCode* nextTime = &fTimes[index];
1.121 + SkMSec nextT = nextTime[0].fTime;
1.122 + if (exact) {
1.123 + *T = 0;
1.124 + } else {
1.125 + SkMSec prevT = nextTime[-1].fTime;
1.126 + *T = ComputeRelativeT(time, prevT, nextT, nextTime[-1].fBlend);
1.127 + }
1.128 + *indexPtr = index;
1.129 + *exactPtr = exact;
1.130 + return result;
1.131 +}
1.132 +
1.133 +
1.134 +SkInterpolator::SkInterpolator() {
1.135 + INHERITED::reset(0, 0);
1.136 + fValues = NULL;
1.137 + SkDEBUGCODE(fScalarsArray = NULL;)
1.138 +}
1.139 +
1.140 +SkInterpolator::SkInterpolator(int elemCount, int frameCount) {
1.141 + SkASSERT(elemCount > 0);
1.142 + this->reset(elemCount, frameCount);
1.143 +}
1.144 +
1.145 +void SkInterpolator::reset(int elemCount, int frameCount) {
1.146 + INHERITED::reset(elemCount, frameCount);
1.147 + fStorage = sk_malloc_throw((sizeof(SkScalar) * elemCount +
1.148 + sizeof(SkTimeCode)) * frameCount);
1.149 + fTimes = (SkTimeCode*) fStorage;
1.150 + fValues = (SkScalar*) ((char*) fStorage + sizeof(SkTimeCode) * frameCount);
1.151 +#ifdef SK_DEBUG
1.152 + fTimesArray = (SkTimeCode(*)[10]) fTimes;
1.153 + fScalarsArray = (SkScalar(*)[10]) fValues;
1.154 +#endif
1.155 +}
1.156 +
1.157 +#define SK_Fixed1Third (SK_Fixed1/3)
1.158 +#define SK_Fixed2Third (SK_Fixed1*2/3)
1.159 +
1.160 +static const SkScalar gIdentityBlend[4] = {
1.161 + 0.33333333f, 0.33333333f, 0.66666667f, 0.66666667f
1.162 +};
1.163 +
1.164 +bool SkInterpolator::setKeyFrame(int index, SkMSec time,
1.165 + const SkScalar values[], const SkScalar blend[4]) {
1.166 + SkASSERT(values != NULL);
1.167 +
1.168 + if (blend == NULL) {
1.169 + blend = gIdentityBlend;
1.170 + }
1.171 +
1.172 + bool success = ~index == SkTSearch<SkMSec>(&fTimes->fTime, index, time,
1.173 + sizeof(SkTimeCode));
1.174 + SkASSERT(success);
1.175 + if (success) {
1.176 + SkTimeCode* timeCode = &fTimes[index];
1.177 + timeCode->fTime = time;
1.178 + memcpy(timeCode->fBlend, blend, sizeof(timeCode->fBlend));
1.179 + SkScalar* dst = &fValues[fElemCount * index];
1.180 + memcpy(dst, values, fElemCount * sizeof(SkScalar));
1.181 + }
1.182 + return success;
1.183 +}
1.184 +
1.185 +SkInterpolator::Result SkInterpolator::timeToValues(SkMSec time,
1.186 + SkScalar values[]) const {
1.187 + SkScalar T;
1.188 + int index;
1.189 + SkBool exact;
1.190 + Result result = timeToT(time, &T, &index, &exact);
1.191 + if (values) {
1.192 + const SkScalar* nextSrc = &fValues[index * fElemCount];
1.193 +
1.194 + if (exact) {
1.195 + memcpy(values, nextSrc, fElemCount * sizeof(SkScalar));
1.196 + } else {
1.197 + SkASSERT(index > 0);
1.198 +
1.199 + const SkScalar* prevSrc = nextSrc - fElemCount;
1.200 +
1.201 + for (int i = fElemCount - 1; i >= 0; --i) {
1.202 + values[i] = SkScalarInterp(prevSrc[i], nextSrc[i], T);
1.203 + }
1.204 + }
1.205 + }
1.206 + return result;
1.207 +}
1.208 +
1.209 +///////////////////////////////////////////////////////////////////////////////
1.210 +
1.211 +typedef int Dot14;
1.212 +#define Dot14_ONE (1 << 14)
1.213 +#define Dot14_HALF (1 << 13)
1.214 +
1.215 +#define Dot14ToFloat(x) ((x) / 16384.f)
1.216 +
1.217 +static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
1.218 + return (a * b + Dot14_HALF) >> 14;
1.219 +}
1.220 +
1.221 +static inline Dot14 eval_cubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
1.222 + return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
1.223 +}
1.224 +
1.225 +static inline Dot14 pin_and_convert(SkScalar x) {
1.226 + if (x <= 0) {
1.227 + return 0;
1.228 + }
1.229 + if (x >= SK_Scalar1) {
1.230 + return Dot14_ONE;
1.231 + }
1.232 + return SkScalarToFixed(x) >> 2;
1.233 +}
1.234 +
1.235 +SkScalar SkUnitCubicInterp(SkScalar value, SkScalar bx, SkScalar by,
1.236 + SkScalar cx, SkScalar cy) {
1.237 + // pin to the unit-square, and convert to 2.14
1.238 + Dot14 x = pin_and_convert(value);
1.239 +
1.240 + if (x == 0) return 0;
1.241 + if (x == Dot14_ONE) return SK_Scalar1;
1.242 +
1.243 + Dot14 b = pin_and_convert(bx);
1.244 + Dot14 c = pin_and_convert(cx);
1.245 +
1.246 + // Now compute our coefficients from the control points
1.247 + // t -> 3b
1.248 + // t^2 -> 3c - 6b
1.249 + // t^3 -> 3b - 3c + 1
1.250 + Dot14 A = 3*b;
1.251 + Dot14 B = 3*(c - 2*b);
1.252 + Dot14 C = 3*(b - c) + Dot14_ONE;
1.253 +
1.254 + // Now search for a t value given x
1.255 + Dot14 t = Dot14_HALF;
1.256 + Dot14 dt = Dot14_HALF;
1.257 + for (int i = 0; i < 13; i++) {
1.258 + dt >>= 1;
1.259 + Dot14 guess = eval_cubic(t, A, B, C);
1.260 + if (x < guess) {
1.261 + t -= dt;
1.262 + } else {
1.263 + t += dt;
1.264 + }
1.265 + }
1.266 +
1.267 + // Now we have t, so compute the coeff for Y and evaluate
1.268 + b = pin_and_convert(by);
1.269 + c = pin_and_convert(cy);
1.270 + A = 3*b;
1.271 + B = 3*(c - 2*b);
1.272 + C = 3*(b - c) + Dot14_ONE;
1.273 + return SkFixedToScalar(eval_cubic(t, A, B, C) << 2);
1.274 +}
1.275 +
1.276 +///////////////////////////////////////////////////////////////////////////////
1.277 +///////////////////////////////////////////////////////////////////////////////
1.278 +
1.279 +#ifdef SK_DEBUG
1.280 +
1.281 +#ifdef SK_SUPPORT_UNITTEST
1.282 + static SkScalar* iset(SkScalar array[3], int a, int b, int c) {
1.283 + array[0] = SkIntToScalar(a);
1.284 + array[1] = SkIntToScalar(b);
1.285 + array[2] = SkIntToScalar(c);
1.286 + return array;
1.287 + }
1.288 +#endif
1.289 +
1.290 +void SkInterpolator::UnitTest() {
1.291 +#ifdef SK_SUPPORT_UNITTEST
1.292 + SkInterpolator inter(3, 2);
1.293 + SkScalar v1[3], v2[3], v[3], vv[3];
1.294 + Result result;
1.295 +
1.296 + inter.setKeyFrame(0, 100, iset(v1, 10, 20, 30), 0);
1.297 + inter.setKeyFrame(1, 200, iset(v2, 110, 220, 330));
1.298 +
1.299 + result = inter.timeToValues(0, v);
1.300 + SkASSERT(result == kFreezeStart_Result);
1.301 + SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
1.302 +
1.303 + result = inter.timeToValues(99, v);
1.304 + SkASSERT(result == kFreezeStart_Result);
1.305 + SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
1.306 +
1.307 + result = inter.timeToValues(100, v);
1.308 + SkASSERT(result == kNormal_Result);
1.309 + SkASSERT(memcmp(v, v1, sizeof(v)) == 0);
1.310 +
1.311 + result = inter.timeToValues(200, v);
1.312 + SkASSERT(result == kNormal_Result);
1.313 + SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
1.314 +
1.315 + result = inter.timeToValues(201, v);
1.316 + SkASSERT(result == kFreezeEnd_Result);
1.317 + SkASSERT(memcmp(v, v2, sizeof(v)) == 0);
1.318 +
1.319 + result = inter.timeToValues(150, v);
1.320 + SkASSERT(result == kNormal_Result);
1.321 + SkASSERT(memcmp(v, iset(vv, 60, 120, 180), sizeof(v)) == 0);
1.322 +
1.323 + result = inter.timeToValues(125, v);
1.324 + SkASSERT(result == kNormal_Result);
1.325 + result = inter.timeToValues(175, v);
1.326 + SkASSERT(result == kNormal_Result);
1.327 +#endif
1.328 +}
1.329 +
1.330 +#endif
