1 /*
2  * Copyright (C) 2013 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.inputmethod.keyboard.internal;
18 
19 /**
20  * Interpolates XY-coordinates using Cubic Hermite Curve.
21  */
22 public final class HermiteInterpolator {
23     private int[] mXCoords;
24     private int[] mYCoords;
25     private int mMinPos;
26     private int mMaxPos;
27 
28     // Working variable to calculate interpolated value.
29     /** The coordinates of the start point of the interval. */
30     public int mP1X, mP1Y;
31     /** The coordinates of the end point of the interval. */
32     public int mP2X, mP2Y;
33     /** The slope of the tangent at the start point. */
34     public float mSlope1X, mSlope1Y;
35     /** The slope of the tangent at the end point. */
36     public float mSlope2X, mSlope2Y;
37     /** The interpolated coordinates.
38      * The return variables of {@link #interpolate(float)} to avoid instantiations.
39      */
40     public float mInterpolatedX, mInterpolatedY;
41 
HermiteInterpolator()42     public HermiteInterpolator() {
43         // Nothing to do with here.
44     }
45 
46     /**
47      * Reset this interpolator to point XY-coordinates data.
48      * @param xCoords the array of x-coordinates. Valid data are in left-open interval
49      *                <code>[minPos, maxPos)</code>.
50      * @param yCoords the array of y-coordinates. Valid data are in left-open interval
51      *                <code>[minPos, maxPos)</code>.
52      * @param minPos the minimum index of left-open interval of valid data.
53      * @param maxPos the maximum index of left-open interval of valid data.
54      */
reset(final int[] xCoords, final int[] yCoords, final int minPos, final int maxPos)55     public void reset(final int[] xCoords, final int[] yCoords, final int minPos,
56             final int maxPos) {
57         mXCoords = xCoords;
58         mYCoords = yCoords;
59         mMinPos = minPos;
60         mMaxPos = maxPos;
61     }
62 
63     /**
64      * Set interpolation interval.
65      * <p>
66      * The start and end coordinates of the interval will be set in {@link #mP1X}, {@link #mP1Y},
67      * {@link #mP2X}, and {@link #mP2Y}. The slope of the tangents at start and end points will be
68      * set in {@link #mSlope1X}, {@link #mSlope1Y}, {@link #mSlope2X}, and {@link #mSlope2Y}.
69      *
70      * @param p0 the index just before interpolation interval. If <code>p1</code> points the start
71      *           of valid points, <code>p0</code> must be less than <code>minPos</code> of
72      *           {@link #reset(int[],int[],int,int)}.
73      * @param p1 the start index of interpolation interval.
74      * @param p2 the end index of interpolation interval.
75      * @param p3 the index just after interpolation interval. If <code>p2</code> points the end of
76      *           valid points, <code>p3</code> must be equal or greater than <code>maxPos</code> of
77      *           {@link #reset(int[],int[],int,int)}.
78      */
setInterval(final int p0, final int p1, final int p2, final int p3)79     public void setInterval(final int p0, final int p1, final int p2, final int p3) {
80         mP1X = mXCoords[p1];
81         mP1Y = mYCoords[p1];
82         mP2X = mXCoords[p2];
83         mP2Y = mYCoords[p2];
84         // A(ax,ay) is the vector p1->p2.
85         final int ax = mP2X - mP1X;
86         final int ay = mP2Y - mP1Y;
87 
88         // Calculate the slope of the tangent at p1.
89         if (p0 >= mMinPos) {
90             // p1 has previous valid point p0.
91             // The slope of the tangent is half of the vector p0->p2.
92             mSlope1X = (mP2X - mXCoords[p0]) / 2.0f;
93             mSlope1Y = (mP2Y - mYCoords[p0]) / 2.0f;
94         } else if (p3 < mMaxPos) {
95             // p1 has no previous valid point, but p2 has next valid point p3.
96             // B(bx,by) is the slope vector of the tangent at p2.
97             final float bx = (mXCoords[p3] - mP1X) / 2.0f;
98             final float by = (mYCoords[p3] - mP1Y) / 2.0f;
99             final float crossProdAB = ax * by - ay * bx;
100             final float dotProdAB = ax * bx + ay * by;
101             final float normASquare = ax * ax + ay * ay;
102             final float invHalfNormASquare = 1.0f / normASquare / 2.0f;
103             // The slope of the tangent is the mirror image of vector B to vector A.
104             mSlope1X = invHalfNormASquare * (dotProdAB * ax + crossProdAB * ay);
105             mSlope1Y = invHalfNormASquare * (dotProdAB * ay - crossProdAB * ax);
106         } else {
107             // p1 and p2 have no previous valid point. (Interval has only point p1 and p2)
108             mSlope1X = ax;
109             mSlope1Y = ay;
110         }
111 
112         // Calculate the slope of the tangent at p2.
113         if (p3 < mMaxPos) {
114             // p2 has next valid point p3.
115             // The slope of the tangent is half of the vector p1->p3.
116             mSlope2X = (mXCoords[p3] - mP1X) / 2.0f;
117             mSlope2Y = (mYCoords[p3] - mP1Y) / 2.0f;
118         } else if (p0 >= mMinPos) {
119             // p2 has no next valid point, but p1 has previous valid point p0.
120             // B(bx,by) is the slope vector of the tangent at p1.
121             final float bx = (mP2X - mXCoords[p0]) / 2.0f;
122             final float by = (mP2Y - mYCoords[p0]) / 2.0f;
123             final float crossProdAB = ax * by - ay * bx;
124             final float dotProdAB = ax * bx + ay * by;
125             final float normASquare = ax * ax + ay * ay;
126             final float invHalfNormASquare = 1.0f / normASquare / 2.0f;
127             // The slope of the tangent is the mirror image of vector B to vector A.
128             mSlope2X = invHalfNormASquare * (dotProdAB * ax + crossProdAB * ay);
129             mSlope2Y = invHalfNormASquare * (dotProdAB * ay - crossProdAB * ax);
130         } else {
131             // p1 and p2 has no previous valid point. (Interval has only point p1 and p2)
132             mSlope2X = ax;
133             mSlope2Y = ay;
134         }
135     }
136 
137     /**
138      * Calculate interpolation value at <code>t</code> in unit interval <code>[0,1]</code>.
139      * <p>
140      * On the unit interval [0,1], given a starting point p1 at t=0 and an ending point p2 at t=1
141      * with the slope of the tangent m1 at p1 and m2 at p2, the polynomial of cubic Hermite curve
142      * can be defined by
143      *   p(t) = (1+2t)(1-t)(1-t)*p1 + t(1-t)(1-t)*m1 + (3-2t)t^2*p2 + (t-1)t^2*m2
144      * where t is an element of [0,1].
145      * <p>
146      * The interpolated XY-coordinates will be set in {@link #mInterpolatedX} and
147      * {@link #mInterpolatedY}.
148      *
149      * @param t the interpolation parameter. The value must be in close interval <code>[0,1]</code>.
150      */
interpolate(final float t)151     public void interpolate(final float t) {
152         final float omt = 1.0f - t;
153         final float tm2 = 2.0f * t;
154         final float k1 = 1.0f + tm2;
155         final float k2 = 3.0f - tm2;
156         final float omt2 = omt * omt;
157         final float t2 = t * t;
158         mInterpolatedX = (k1 * mP1X + t * mSlope1X) * omt2 + (k2 * mP2X - omt * mSlope2X) * t2;
159         mInterpolatedY = (k1 * mP1Y + t * mSlope1Y) * omt2 + (k2 * mP2Y - omt * mSlope2Y) * t2;
160     }
161 }
162