HyperSpline.java

/*
 * Copyright (C) 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package androidx.constraintlayout.core.motion.utils;

/**
 * Provides spline interpolation code.
 * Currently not used but it is anticipated that we will be using it in the
 * KeyMotion
 *
 *
 */

public class HyperSpline {
    int mPoints;
    Cubic[][] mCurve;
    int mDimensionality;
    double[] mCurveLength;
    double mTotalLength;
    double[][] mCtl;

    /**
     * Spline in N dimensions
     *
     * @param points [mPoints][dimensionality]
     */
    public HyperSpline(double[][] points) {
        setup(points);
    }

    public HyperSpline() {
    }

    // @TODO: add description
    public void setup(double[][] points) {
        mDimensionality = points[0].length;
        mPoints = points.length;
        mCtl = new double[mDimensionality][mPoints];
        mCurve = new Cubic[mDimensionality][];
        for (int d = 0; d < mDimensionality; d++) {
            for (int p = 0; p < mPoints; p++) {
                mCtl[d][p] = points[p][d];
            }
        }

        for (int d = 0; d < mDimensionality; d++) {
            mCurve[d] = calcNaturalCubic(mCtl[d].length, mCtl[d]);
        }

        mCurveLength = new double[mPoints - 1];
        mTotalLength = 0;
        Cubic[] temp = new Cubic[mDimensionality];
        for (int p = 0; p < mCurveLength.length; p++) {
            for (int d = 0; d < mDimensionality; d++) {

                temp[d] = mCurve[d][p];

            }
            mTotalLength += mCurveLength[p] = approxLength(temp);
        }
    }

    // @TODO: add description
    public void getVelocity(double p, double[] v) {
        double pos = p * mTotalLength;
        int k = 0;
        for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
            pos -= mCurveLength[k];
        }
        for (int i = 0; i < v.length; i++) {
            v[i] = mCurve[i][k].vel(pos / mCurveLength[k]);
        }
    }

    // @TODO: add description
    public void getPos(double p, double[] x) {
        double pos = p * mTotalLength;
        int k = 0;
        for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
            pos -= mCurveLength[k];
        }
        for (int i = 0; i < x.length; i++) {
            x[i] = mCurve[i][k].eval(pos / mCurveLength[k]);
        }
    }

    // @TODO: add description
    public void getPos(double p, float[] x) {
        double pos = p * mTotalLength;
        int k = 0;
        for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
            pos -= mCurveLength[k];
        }
        for (int i = 0; i < x.length; i++) {
            x[i] = (float) mCurve[i][k].eval(pos / mCurveLength[k]);
        }
    }

    // @TODO: add description
    public double getPos(double p, int splineNumber) {
        double pos = p * mTotalLength;
        int k = 0;
        for (; k < mCurveLength.length - 1 && mCurveLength[k] < pos; k++) {
            pos -= mCurveLength[k];
        }
        return mCurve[splineNumber][k].eval(pos / mCurveLength[k]);
    }

    // @TODO: add description
    public double approxLength(Cubic[] curve) {
        double sum = 0;

        int n = curve.length;
        double[] old = new double[n];
        for (double i = 0; i < 1; i += .1) {
            double s = 0;
            for (int j = 0; j < n; j++) {
                double tmp = old[j];
                tmp -= old[j] = curve[j].eval(i);
                s += tmp * tmp;
            }
            if (i > 0) {
                sum += Math.sqrt(s);
            }

        }
        double s = 0;
        for (int j = 0; j < n; j++) {
            double tmp = old[j];
            tmp -= old[j] = curve[j].eval(1);
            s += tmp * tmp;
        }
        sum += Math.sqrt(s);
        return sum;
    }

    static Cubic[] calcNaturalCubic(int n, double[] x) {
        double[] gamma = new double[n];
        double[] delta = new double[n];
        double[] d = new double[n];
        n -= 1;

        gamma[0] = 1.0f / 2.0f;
        for (int i = 1; i < n; i++) {
            gamma[i] = 1 / (4 - gamma[i - 1]);
        }
        gamma[n] = 1 / (2 - gamma[n - 1]);

        delta[0] = 3 * (x[1] - x[0]) * gamma[0];
        for (int i = 1; i < n; i++) {
            delta[i] = (3 * (x[i + 1] - x[i - 1]) - delta[i - 1]) * gamma[i];
        }
        delta[n] = (3 * (x[n] - x[n - 1]) - delta[n - 1]) * gamma[n];

        d[n] = delta[n];
        for (int i = n - 1; i >= 0; i--) {
            d[i] = delta[i] - gamma[i] * d[i + 1];
        }

        Cubic[] c = new Cubic[n];
        for (int i = 0; i < n; i++) {
            c[i] = new Cubic((float) x[i], d[i], 3 * (x[i + 1] - x[i]) - 2
                    * d[i] - d[i + 1], 2 * (x[i] - x[i + 1]) + d[i] + d[i + 1]);
        }
        return c;
    }

    public static class Cubic {
        double mA, mB, mC, mD;

        public Cubic(double a, double b, double c, double d) {
            mA = a;
            mB = b;
            mC = c;
            mD = d;
        }

        // @TODO: add description
        public double eval(double u) {
            return (((mD * u) + mC) * u + mB) * u + mA;
        }

        // @TODO: add description
        public double vel(double v) {
            //  (((mD * u) + mC) * u + mB) * u + mA
            //  =  "mA + u*mB + u*u*mC+u*u*u*mD" a cubic expression
            // diff with respect to u = mB + u*mC/2+ u*u*mD/3
            // made efficient (mD*u/3+mC/2)*u+mB;

            return (mD * 3 * v + mC * 2) * v + mB;
        }
    }
}