1 /*
2  * Copyright (C) 2014 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.camera.ui.motion;
18 
19 /**
20  * This represents is a precomputed cubic bezier curve starting at (0,0) and
21  * going to (1,1) with two configurable control points. Once the instance is
22  * created, the control points cannot be modified.
23  *
24  * Generally, this will be used for computing timing curves for with control
25  * points where an x value will be provide from 0.0 - 1.0, and the y value will
26  * be solved for where y is used as the timing value in some linear
27  * interpolation of a value.
28  */
29 public class UnitBezier implements UnitCurve {
30 
31     private static final float EPSILON = 1e-6f;
32 
33     private final DerivableFloatFn mXFn;
34     private final DerivableFloatFn mYFn;
35 
36     /**
37      * Build and pre-compute a unit bezier. This assumes a starting point of
38      * (0, 0) and end point of (1.0, 1.0).
39      *
40      * @param c0x control point x value for p0
41      * @param c0y control point y value for p0
42      * @param c1x control point x value for p1
43      * @param c1y control point y value for p1
44      */
UnitBezier(float c0x, float c0y, float c1x, float c1y)45     public UnitBezier(float c0x, float c0y, float c1x, float c1y) {
46         mXFn = new CubicBezierFn(c0x, c1x);
47         mYFn = new CubicBezierFn(c0y, c1y);
48     }
49 
50     /**
51      * Given a unit bezier curve find the height of the curve at t (which is
52      * internally represented as the xAxis).
53      *
54      * @param t the x position between 0 and 1 to solve for y.
55      * @return the closest approximate height of the curve at x.
56      */
57     @Override
valueAt(float t)58     public float valueAt(float t) {
59         return mYFn.value(solve(t, mXFn));
60     }
61 
62     /**
63      * Given a unit bezier curve find a value along the x axis such that
64      * valueAt(result) produces the input value.
65      *
66      * @param value the y position between 0 and 1 to solve for x
67      * @return the closest approximate input that will produce value when provided
68      * to the valueAt function.
69      */
70     @Override
tAt(float value)71     public float tAt(float value) {
72         return mXFn.value(solve(value, mYFn));
73     }
74 
solve(float target, DerivableFloatFn fn)75     private float solve(float target, DerivableFloatFn fn) {
76         // For a linear fn, t = value. This makes value a good starting guess.
77         float input = target;
78 
79         // Newton's method (Faster than bisection)
80         for (int i = 0; i < 8; i++) {
81             float value = fn.value(input) - target;
82             if (Math.abs(value) < EPSILON) {
83                 return input;
84             }
85             float derivative = fn.derivative(input);
86             if (Math.abs(derivative) < EPSILON) {
87                 break;
88             }
89             input = input - value / derivative;
90         }
91 
92         // Fallback on bi-section
93         float min = 0.0f;
94         float max = 1.0f;
95         input = target;
96 
97         if (input < min) {
98             return min;
99         }
100         if (input > max) {
101             return max;
102         }
103 
104         while (min < max) {
105             float value = fn.value(input);
106             if (Math.abs(value - target) < EPSILON) {
107                 return input;
108             }
109 
110             if (target > value) {
111                 min = input;
112             } else {
113                 max = input;
114             }
115 
116             input = (max - min) * .5f + min;
117         }
118 
119         // Give up, return the closest match we got too.
120         return input;
121     }
122 
123     private interface DerivableFloatFn {
value(float x)124         float value(float x);
derivative(float x)125         float derivative(float x);
126     }
127 
128     /**
129      * Precomputed constants for a given set of control points along a given
130      * cubic bezier axis.
131      */
132     private static class CubicBezierFn implements DerivableFloatFn {
133         private final float c;
134         private final float a;
135         private final float b;
136 
137         /**
138          * Build and pre-compute a single axis for a unit bezier. This assumes p0
139          * is 0 and p1 is 1.
140          *
141          * @param c0 start control point.
142          * @param c1 end control point.
143          */
CubicBezierFn(float c0, float c1)144         public CubicBezierFn(float c0, float c1) {
145             c = 3.0f * c0;
146             b = 3.0f * (c1 - c0) - c;
147             a = 1.0f - c - b;
148         }
149 
value(float x)150         public float value(float x) {
151             return ((a * x + b) * x + c) * x;
152         }
derivative(float x)153         public float derivative(float x) {
154             return (3.0f * a * x + 2.0f * b) * x + c;
155         }
156     }
157 }
158