1 /* 2 * Copyright (C) 2020 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 package androidx.constraintlayout.core.motion.utils; 18 19 import java.util.Arrays; 20 21 /** 22 * This performs a spline interpolation in multiple dimensions 23 * 24 * 25 */ 26 public class MonotonicCurveFit extends CurveFit { 27 private static final String TAG = "MonotonicCurveFit"; 28 private double[] mT; 29 private double[][] mY; 30 private double[][] mTangent; 31 private boolean mExtrapolate = true; 32 double[] mSlopeTemp; 33 MonotonicCurveFit(double[] time, double[][] y)34 public MonotonicCurveFit(double[] time, double[][] y) { 35 final int n = time.length; 36 final int dim = y[0].length; 37 mSlopeTemp = new double[dim]; 38 double[][] slope = new double[n - 1][dim]; // could optimize this out 39 double[][] tangent = new double[n][dim]; 40 for (int j = 0; j < dim; j++) { 41 for (int i = 0; i < n - 1; i++) { 42 double dt = time[i + 1] - time[i]; 43 slope[i][j] = (y[i + 1][j] - y[i][j]) / dt; 44 if (i == 0) { 45 tangent[i][j] = slope[i][j]; 46 } else { 47 tangent[i][j] = (slope[i - 1][j] + slope[i][j]) * 0.5f; 48 } 49 } 50 tangent[n - 1][j] = slope[n - 2][j]; 51 } 52 53 for (int i = 0; i < n - 1; i++) { 54 for (int j = 0; j < dim; j++) { 55 if (slope[i][j] == 0.) { 56 tangent[i][j] = 0.; 57 tangent[i + 1][j] = 0.; 58 } else { 59 double a = tangent[i][j] / slope[i][j]; 60 double b = tangent[i + 1][j] / slope[i][j]; 61 double h = Math.hypot(a, b); 62 if (h > 9.0) { 63 double t = 3. / h; 64 tangent[i][j] = t * a * slope[i][j]; 65 tangent[i + 1][j] = t * b * slope[i][j]; 66 } 67 } 68 } 69 } 70 mT = time; 71 mY = y; 72 mTangent = tangent; 73 } 74 75 @Override getPos(double t, double[] v)76 public void getPos(double t, double[] v) { 77 final int n = mT.length; 78 final int dim = mY[0].length; 79 if (mExtrapolate) { 80 if (t <= mT[0]) { 81 getSlope(mT[0], mSlopeTemp); 82 for (int j = 0; j < dim; j++) { 83 v[j] = mY[0][j] + (t - mT[0]) * mSlopeTemp[j]; 84 } 85 return; 86 } 87 if (t >= mT[n - 1]) { 88 getSlope(mT[n - 1], mSlopeTemp); 89 for (int j = 0; j < dim; j++) { 90 v[j] = mY[n - 1][j] + (t - mT[n - 1]) * mSlopeTemp[j]; 91 } 92 return; 93 } 94 } else { 95 if (t <= mT[0]) { 96 for (int j = 0; j < dim; j++) { 97 v[j] = mY[0][j]; 98 } 99 return; 100 } 101 if (t >= mT[n - 1]) { 102 for (int j = 0; j < dim; j++) { 103 v[j] = mY[n - 1][j]; 104 } 105 return; 106 } 107 } 108 109 for (int i = 0; i < n - 1; i++) { 110 if (t == mT[i]) { 111 for (int j = 0; j < dim; j++) { 112 v[j] = mY[i][j]; 113 } 114 } 115 if (t < mT[i + 1]) { 116 double h = mT[i + 1] - mT[i]; 117 double x = (t - mT[i]) / h; 118 for (int j = 0; j < dim; j++) { 119 double y1 = mY[i][j]; 120 double y2 = mY[i + 1][j]; 121 double t1 = mTangent[i][j]; 122 double t2 = mTangent[i + 1][j]; 123 v[j] = interpolate(h, x, y1, y2, t1, t2); 124 } 125 return; 126 } 127 } 128 } 129 130 @Override getPos(double t, float[] v)131 public void getPos(double t, float[] v) { 132 final int n = mT.length; 133 final int dim = mY[0].length; 134 if (mExtrapolate) { 135 if (t <= mT[0]) { 136 getSlope(mT[0], mSlopeTemp); 137 for (int j = 0; j < dim; j++) { 138 v[j] = (float) (mY[0][j] + (t - mT[0]) * mSlopeTemp[j]); 139 } 140 return; 141 } 142 if (t >= mT[n - 1]) { 143 getSlope(mT[n - 1], mSlopeTemp); 144 for (int j = 0; j < dim; j++) { 145 v[j] = (float) (mY[n - 1][j] + (t - mT[n - 1]) * mSlopeTemp[j]); 146 } 147 return; 148 } 149 } else { 150 if (t <= mT[0]) { 151 for (int j = 0; j < dim; j++) { 152 v[j] = (float) mY[0][j]; 153 } 154 return; 155 } 156 if (t >= mT[n - 1]) { 157 for (int j = 0; j < dim; j++) { 158 v[j] = (float) mY[n - 1][j]; 159 } 160 return; 161 } 162 } 163 164 for (int i = 0; i < n - 1; i++) { 165 if (t == mT[i]) { 166 for (int j = 0; j < dim; j++) { 167 v[j] = (float) mY[i][j]; 168 } 169 } 170 if (t < mT[i + 1]) { 171 double h = mT[i + 1] - mT[i]; 172 double x = (t - mT[i]) / h; 173 for (int j = 0; j < dim; j++) { 174 double y1 = mY[i][j]; 175 double y2 = mY[i + 1][j]; 176 double t1 = mTangent[i][j]; 177 double t2 = mTangent[i + 1][j]; 178 v[j] = (float) interpolate(h, x, y1, y2, t1, t2); 179 } 180 return; 181 } 182 } 183 } 184 185 @Override getPos(double t, int j)186 public double getPos(double t, int j) { 187 final int n = mT.length; 188 if (mExtrapolate) { 189 if (t <= mT[0]) { 190 return mY[0][j] + (t - mT[0]) * getSlope(mT[0], j); 191 } 192 if (t >= mT[n - 1]) { 193 return mY[n - 1][j] + (t - mT[n - 1]) * getSlope(mT[n - 1], j); 194 } 195 } else { 196 if (t <= mT[0]) { 197 return mY[0][j]; 198 } 199 if (t >= mT[n - 1]) { 200 return mY[n - 1][j]; 201 } 202 } 203 204 for (int i = 0; i < n - 1; i++) { 205 if (t == mT[i]) { 206 return mY[i][j]; 207 } 208 if (t < mT[i + 1]) { 209 double h = mT[i + 1] - mT[i]; 210 double x = (t - mT[i]) / h; 211 double y1 = mY[i][j]; 212 double y2 = mY[i + 1][j]; 213 double t1 = mTangent[i][j]; 214 double t2 = mTangent[i + 1][j]; 215 return interpolate(h, x, y1, y2, t1, t2); 216 217 } 218 } 219 return 0; // should never reach here 220 } 221 222 @Override getSlope(double t, double[] v)223 public void getSlope(double t, double[] v) { 224 final int n = mT.length; 225 int dim = mY[0].length; 226 if (t <= mT[0]) { 227 t = mT[0]; 228 } else if (t >= mT[n - 1]) { 229 t = mT[n - 1]; 230 } 231 232 for (int i = 0; i < n - 1; i++) { 233 if (t <= mT[i + 1]) { 234 double h = mT[i + 1] - mT[i]; 235 double x = (t - mT[i]) / h; 236 for (int j = 0; j < dim; j++) { 237 double y1 = mY[i][j]; 238 double y2 = mY[i + 1][j]; 239 double t1 = mTangent[i][j]; 240 double t2 = mTangent[i + 1][j]; 241 v[j] = diff(h, x, y1, y2, t1, t2) / h; 242 } 243 break; 244 } 245 } 246 } 247 248 @Override getSlope(double t, int j)249 public double getSlope(double t, int j) { 250 final int n = mT.length; 251 252 if (t < mT[0]) { 253 t = mT[0]; 254 } else if (t >= mT[n - 1]) { 255 t = mT[n - 1]; 256 } 257 for (int i = 0; i < n - 1; i++) { 258 if (t <= mT[i + 1]) { 259 double h = mT[i + 1] - mT[i]; 260 double x = (t - mT[i]) / h; 261 double y1 = mY[i][j]; 262 double y2 = mY[i + 1][j]; 263 double t1 = mTangent[i][j]; 264 double t2 = mTangent[i + 1][j]; 265 return diff(h, x, y1, y2, t1, t2) / h; 266 } 267 } 268 return 0; // should never reach here 269 } 270 271 @Override getTimePoints()272 public double[] getTimePoints() { 273 return mT; 274 } 275 276 /** 277 * Cubic Hermite spline 278 */ interpolate(double h, double x, double y1, double y2, double t1, double t2)279 private static double interpolate(double h, 280 double x, 281 double y1, 282 double y2, 283 double t1, 284 double t2) { 285 double x2 = x * x; 286 double x3 = x2 * x; 287 return -2 * x3 * y2 + 3 * x2 * y2 + 2 * x3 * y1 - 3 * x2 * y1 + y1 288 + h * t2 * x3 + h * t1 * x3 - h * t2 * x2 - 2 * h * t1 * x2 289 + h * t1 * x; 290 } 291 292 /** 293 * Cubic Hermite spline slope differentiated 294 */ diff(double h, double x, double y1, double y2, double t1, double t2)295 private static double diff(double h, double x, double y1, double y2, double t1, double t2) { 296 double x2 = x * x; 297 return -6 * x2 * y2 + 6 * x * y2 + 6 * x2 * y1 - 6 * x * y1 + 3 * h * t2 * x2 298 + 3 * h * t1 * x2 - 2 * h * t2 * x - 4 * h * t1 * x + h * t1; 299 } 300 301 /** 302 * This builds a monotonic spline to be used as a wave function 303 */ buildWave(String configString)304 public static MonotonicCurveFit buildWave(String configString) { 305 // done this way for efficiency 306 String str = configString; 307 double[] values = new double[str.length() / 2]; 308 int start = configString.indexOf('(') + 1; 309 int off1 = configString.indexOf(',', start); 310 int count = 0; 311 while (off1 != -1) { 312 String tmp = configString.substring(start, off1).trim(); 313 values[count++] = Double.parseDouble(tmp); 314 off1 = configString.indexOf(',', start = off1 + 1); 315 } 316 off1 = configString.indexOf(')', start); 317 String tmp = configString.substring(start, off1).trim(); 318 values[count++] = Double.parseDouble(tmp); 319 320 return buildWave(Arrays.copyOf(values, count)); 321 } 322 buildWave(double[] values)323 private static MonotonicCurveFit buildWave(double[] values) { 324 int length = values.length * 3 - 2; 325 int len = values.length - 1; 326 double gap = 1.0 / len; 327 double[][] points = new double[length][1]; 328 double[] time = new double[length]; 329 for (int i = 0; i < values.length; i++) { 330 double v = values[i]; 331 points[i + len][0] = v; 332 time[i + len] = i * gap; 333 if (i > 0) { 334 points[i + len * 2][0] = v + 1; 335 time[i + len * 2] = i * gap + 1; 336 337 points[i - 1][0] = v - 1 - gap; 338 time[i - 1] = i * gap + -1 - gap; 339 } 340 } 341 342 return new MonotonicCurveFit(time, points); 343 } 344 } 345