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