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 /**
20  * Provides spline interpolation code.
21  * Currently not used but it is anticipated that we will be using it in the
22  * KeyMotion
23  *
24  *
25  */
26 
27 public class HyperSpline {
28     int mPoints;
29     Cubic[][] mCurve;
30     int mDimensionality;
31     double[] mCurveLength;
32     double mTotalLength;
33     double[][] mCtl;
34 
35     /**
36      * Spline in N dimensions
37      *
38      * @param points [mPoints][dimensionality]
39      */
HyperSpline(double[][] points)40     public HyperSpline(double[][] points) {
41         setup(points);
42     }
43 
HyperSpline()44     public HyperSpline() {
45     }
46 
47     // @TODO: add description
setup(double[][] points)48     public void setup(double[][] points) {
49         mDimensionality = points[0].length;
50         mPoints = points.length;
51         mCtl = new double[mDimensionality][mPoints];
52         mCurve = new Cubic[mDimensionality][];
53         for (int d = 0; d < mDimensionality; d++) {
54             for (int p = 0; p < mPoints; p++) {
55                 mCtl[d][p] = points[p][d];
56             }
57         }
58 
59         for (int d = 0; d < mDimensionality; d++) {
60             mCurve[d] = calcNaturalCubic(mCtl[d].length, mCtl[d]);
61         }
62 
63         mCurveLength = new double[mPoints - 1];
64         mTotalLength = 0;
65         Cubic[] temp = new Cubic[mDimensionality];
66         for (int p = 0; p < mCurveLength.length; p++) {
67             for (int d = 0; d < mDimensionality; d++) {
68 
69                 temp[d] = mCurve[d][p];
70 
71             }
72             mTotalLength += mCurveLength[p] = approxLength(temp);
73         }
74     }
75 
76     // @TODO: add description
getVelocity(double p, double[] v)77     public void getVelocity(double p, double[] v) {
78         double pos = p * mTotalLength;
79         int k = 0;
80         for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
81             pos -= mCurveLength[k];
82         }
83         for (int i = 0; i < v.length; i++) {
84             v[i] = mCurve[i][k].vel(pos / mCurveLength[k]);
85         }
86     }
87 
88     // @TODO: add description
getPos(double p, double[] x)89     public void getPos(double p, double[] x) {
90         double pos = p * mTotalLength;
91         int k = 0;
92         for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
93             pos -= mCurveLength[k];
94         }
95         for (int i = 0; i < x.length; i++) {
96             x[i] = mCurve[i][k].eval(pos / mCurveLength[k]);
97         }
98     }
99 
100     // @TODO: add description
getPos(double p, float[] x)101     public void getPos(double p, float[] x) {
102         double pos = p * mTotalLength;
103         int k = 0;
104         for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
105             pos -= mCurveLength[k];
106         }
107         for (int i = 0; i < x.length; i++) {
108             x[i] = (float) mCurve[i][k].eval(pos / mCurveLength[k]);
109         }
110     }
111 
112     // @TODO: add description
getPos(double p, int splineNumber)113     public double getPos(double p, int splineNumber) {
114         double pos = p * mTotalLength;
115         int k = 0;
116         for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
117             pos -= mCurveLength[k];
118         }
119         return mCurve[splineNumber][k].eval(pos / mCurveLength[k]);
120     }
121 
122     // @TODO: add description
approxLength(Cubic[] curve)123     public double approxLength(Cubic[] curve) {
124         double sum = 0;
125 
126         int n = curve.length;
127         double[] old = new double[n];
128         for (double i = 0; i < 1; i += .1) {
129             double s = 0;
130             for (int j = 0; j < n; j++) {
131                 double tmp = old[j];
132                 tmp -= old[j] = curve[j].eval(i);
133                 s += tmp * tmp;
134             }
135             if (i > 0) {
136                 sum += Math.sqrt(s);
137             }
138 
139         }
140         double s = 0;
141         for (int j = 0; j < n; j++) {
142             double tmp = old[j];
143             tmp -= old[j] = curve[j].eval(1);
144             s += tmp * tmp;
145         }
146         sum += Math.sqrt(s);
147         return sum;
148     }
149 
calcNaturalCubic(int n, double[] x)150     static Cubic[] calcNaturalCubic(int n, double[] x) {
151         double[] gamma = new double[n];
152         double[] delta = new double[n];
153         double[] d = new double[n];
154         n -= 1;
155 
156         gamma[0] = 1.0f / 2.0f;
157         for (int i = 1; i < n; i++) {
158             gamma[i] = 1 / (4 - gamma[i - 1]);
159         }
160         gamma[n] = 1 / (2 - gamma[n - 1]);
161 
162         delta[0] = 3 * (x[1] - x[0]) * gamma[0];
163         for (int i = 1; i < n; i++) {
164             delta[i] = (3 * (x[i + 1] - x[i - 1]) - delta[i - 1]) * gamma[i];
165         }
166         delta[n] = (3 * (x[n] - x[n - 1]) - delta[n - 1]) * gamma[n];
167 
168         d[n] = delta[n];
169         for (int i = n - 1; i >= 0; i--) {
170             d[i] = delta[i] - gamma[i] * d[i + 1];
171         }
172 
173         Cubic[] c = new Cubic[n];
174         for (int i = 0; i < n; i++) {
175             c[i] = new Cubic((float) x[i], d[i], 3 * (x[i + 1] - x[i]) - 2
176                     * d[i] - d[i + 1], 2 * (x[i] - x[i + 1]) + d[i] + d[i + 1]);
177         }
178         return c;
179     }
180 
181     public static class Cubic {
182         double mA, mB, mC, mD;
183 
Cubic(double a, double b, double c, double d)184         public Cubic(double a, double b, double c, double d) {
185             mA = a;
186             mB = b;
187             mC = c;
188             mD = d;
189         }
190 
191         // @TODO: add description
eval(double u)192         public double eval(double u) {
193             return (((mD * u) + mC) * u + mB) * u + mA;
194         }
195 
196         // @TODO: add description
vel(double v)197         public double vel(double v) {
198             //  (((mD * u) + mC) * u + mB) * u + mA
199             //  =  "mA + u*mB + u*u*mC+u*u*u*mD" a cubic expression
200             // diff with respect to u = mB + u*mC/2+ u*u*mD/3
201             // made efficient (mD*u/3+mC/2)*u+mB;
202 
203             return (mD * 3 * v + mC * 2) * v + mB;
204         }
205     }
206 }
207