1 /*
2  * Copyright (C) 2024 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 com.android.systemui.car.displayarea;
18 
19 import android.view.animation.Interpolator;
20 
21 /**
22  * Animation interpolator which can do time based interpolation over cubic bezier curves as defined
23  * by 2 x,y control points.
24  *
25  * To be clear, this is not just interpolating over the parametric form of B(t) = {x,y}, but over
26  * f(x) = y, where x is linear time {0...1} and y is adjusted time {0...1}. We essentially want to
27  * do the following:
28  * - given that we have a a 2d bezier form of B(t) = {x, y} with 1d forms of bx(t) = x and by(t) = y
29  * - compute y in f(x) = y such that at a given xn we have B(tn) = {xn, yn}
30  * - where f(x) = by(bx'(x)) where bx'(x) = t is the inverse of bx(t) = x
31  *
32  * There is no closed form solution to the equation in solving f(x) = y. Presently it uses Newton's
33  * method to find t for which B(t) = x, then compute y based on that t.
34  *
35  * We pregenerate a number of high precision approximations of x-to-t lookup buckets, which we use
36  * as the starting guesess for a lower precision look up at runtime. In combination this gives about
37  * a 0.1% error margin, which is more than sufficient for the animation interpolations. If we need
38  * more precision or more perf we can expand the look up buckets, or use a binary search to drill
39  * into it more, or a few other methods.
40  *
41  * This class is largely a copy of GMM's CubicBezierInterpolator, but has modified constructors and
42  * static fields in order to make it easier to input animation specifications from our UX team.
43  * See go/cubicbezierinterpolator for the code that was copied.
44  */
45 public final class CarCubicBezierInterpolator implements Interpolator {
46 
47     private static final int BUCKET_COUNT = 25;
48     private static final int PRECOMPUTE_ITERATIONS = 10;
49     private static final int INTERPOLATE_ITERATIONS = 3;
50     private static final float EPSILON = 0.0001f;
51 
52     private final CarBezierFunction mXFunction;
53     private final CarBezierFunction mYfunction;
54 
55     // Quick bucketing of X-to-t
56     public final float[] mXt = new float[BUCKET_COUNT];
57 
58     /**
59      * A cubic bezier 2D interpolator, with the bezier curve defined by {P1/C1, P2/C2}.
60      */
CarCubicBezierInterpolator(float x1, float y1, float x2, float y2)61     public CarCubicBezierInterpolator(float x1, float y1, float x2, float y2) {
62         mXFunction = new CarBezierFunction(0, x1, x2, 1);
63         mYfunction = new CarBezierFunction(0, y1, y2, 1);
64 
65         for (int i = 0; i < mXt.length; i++) {
66             float x = (float) i / (float) (mXt.length - 1);
67             float t = inverseBezierValue(x, PRECOMPUTE_ITERATIONS, false);
68             mXt[i] = t;
69         }
70     }
71 
inverseBezierValue( CarCubicBezierInterpolator this, float x, int maxIterations, boolean useLookup)72     private float inverseBezierValue(
73             CarCubicBezierInterpolator this,
74             float x,
75             int maxIterations,
76             boolean useLookup) {
77         // Use Newton Raphson Iteration to approximate the T at which Bezier(T) = x.
78         int index = (int) (x * (mXt.length - 1));
79         float t = useLookup ? mXt[index] : x;
80         float tmax = useLookup && (index < mXt.length - 1) ? mXt[index + 1] : 1;
81 
82         for (int i = 0; i < maxIterations; ++i) {
83             float error = (float) mXFunction.getValue(t) - x;
84             if (Math.abs(error) <= EPSILON) {
85                 return t;
86             }
87             float slope = (float) mXFunction.getDerivative(t);
88             if (slope != 0) {
89                 t -= error / slope;
90             } else {
91                 // If we landed on a zero-slope we need shift the t in some direction. Shift a
92                 // bit towards
93                 // the max.
94                 t += ((tmax - t) / 2);
95             }
96         }
97 
98         return t;
99     }
100 
101     @Override
getInterpolation(float time)102     public float getInterpolation(float time) {
103         // The x-axis is linear time. To get the adjusted time we need to find at which T B(T) =
104         // time,
105         // then compute the y value at T, which represents our adjusted time.
106         return (float) mYfunction.getValue(inverseBezierValue(time, INTERPOLATE_ITERATIONS, true));
107     }
108 }
109