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
17package 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 */
29public 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     */
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
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
71    public float tAt(float value) {
72        return mXFn.value(solve(value, mYFn));
73    }
74
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 {
124        float value(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         */
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
150        public float value(float x) {
151            return ((a * x + b) * x + c) * x;
152        }
153        public float derivative(float x) {
154            return (3.0f * a * x + 2.0f * b) * x + c;
155        }
156    }
157}
158