1 /* 2 * Copyright (C) 2012 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 android.content.res.TypedArray; 20 import android.util.Log; 21 22 import com.android.inputmethod.latin.InputPointers; 23 import com.android.inputmethod.latin.R; 24 import com.android.inputmethod.latin.ResizableIntArray; 25 import com.android.inputmethod.latin.ResourceUtils; 26 27 public class GestureStroke { 28 private static final String TAG = GestureStroke.class.getSimpleName(); 29 private static final boolean DEBUG = false; 30 private static final boolean DEBUG_SPEED = false; 31 32 // The height of extra area above the keyboard to draw gesture trails. 33 // Proportional to the keyboard height. 34 public static final float EXTRA_GESTURE_TRAIL_AREA_ABOVE_KEYBOARD_RATIO = 0.25f; 35 36 public static final int DEFAULT_CAPACITY = 128; 37 38 private final int mPointerId; 39 private final ResizableIntArray mEventTimes = new ResizableIntArray(DEFAULT_CAPACITY); 40 private final ResizableIntArray mXCoordinates = new ResizableIntArray(DEFAULT_CAPACITY); 41 private final ResizableIntArray mYCoordinates = new ResizableIntArray(DEFAULT_CAPACITY); 42 43 private final GestureStrokeParams mParams; 44 45 private int mKeyWidth; // pixel 46 private int mMinYCoordinate; // pixel 47 private int mMaxYCoordinate; // pixel 48 // Static threshold for starting gesture detection 49 private int mDetectFastMoveSpeedThreshold; // pixel /sec 50 private int mDetectFastMoveTime; 51 private int mDetectFastMoveX; 52 private int mDetectFastMoveY; 53 // Dynamic threshold for gesture after fast typing 54 private boolean mAfterFastTyping; 55 private int mGestureDynamicDistanceThresholdFrom; // pixel 56 private int mGestureDynamicDistanceThresholdTo; // pixel 57 // Variables for gesture sampling 58 private int mGestureSamplingMinimumDistance; // pixel 59 private long mLastMajorEventTime; 60 private int mLastMajorEventX; 61 private int mLastMajorEventY; 62 // Variables for gesture recognition 63 private int mGestureRecognitionSpeedThreshold; // pixel / sec 64 private int mIncrementalRecognitionSize; 65 private int mLastIncrementalBatchSize; 66 67 public static final class GestureStrokeParams { 68 // Static threshold for gesture after fast typing 69 public final int mStaticTimeThresholdAfterFastTyping; // msec 70 // Static threshold for starting gesture detection 71 public final float mDetectFastMoveSpeedThreshold; // keyWidth/sec 72 // Dynamic threshold for gesture after fast typing 73 public final int mDynamicThresholdDecayDuration; // msec 74 // Time based threshold values 75 public final int mDynamicTimeThresholdFrom; // msec 76 public final int mDynamicTimeThresholdTo; // msec 77 // Distance based threshold values 78 public final float mDynamicDistanceThresholdFrom; // keyWidth 79 public final float mDynamicDistanceThresholdTo; // keyWidth 80 // Parameters for gesture sampling 81 public final float mSamplingMinimumDistance; // keyWidth 82 // Parameters for gesture recognition 83 public final int mRecognitionMinimumTime; // msec 84 public final float mRecognitionSpeedThreshold; // keyWidth/sec 85 86 // Default GestureStroke parameters. 87 public static final GestureStrokeParams DEFAULT = new GestureStrokeParams(); 88 GestureStrokeParams()89 private GestureStrokeParams() { 90 // These parameter values are default and intended for testing. 91 mStaticTimeThresholdAfterFastTyping = 350; // msec 92 mDetectFastMoveSpeedThreshold = 1.5f; // keyWidth / sec 93 mDynamicThresholdDecayDuration = 450; // msec 94 mDynamicTimeThresholdFrom = 300; // msec 95 mDynamicTimeThresholdTo = 20; // msec 96 mDynamicDistanceThresholdFrom = 6.0f; // keyWidth 97 mDynamicDistanceThresholdTo = 0.35f; // keyWidth 98 // The following parameters' change will affect the result of regression test. 99 mSamplingMinimumDistance = 1.0f / 6.0f; // keyWidth 100 mRecognitionMinimumTime = 100; // msec 101 mRecognitionSpeedThreshold = 5.5f; // keyWidth / sec 102 } 103 GestureStrokeParams(final TypedArray mainKeyboardViewAttr)104 public GestureStrokeParams(final TypedArray mainKeyboardViewAttr) { 105 mStaticTimeThresholdAfterFastTyping = mainKeyboardViewAttr.getInt( 106 R.styleable.MainKeyboardView_gestureStaticTimeThresholdAfterFastTyping, 107 DEFAULT.mStaticTimeThresholdAfterFastTyping); 108 mDetectFastMoveSpeedThreshold = ResourceUtils.getFraction(mainKeyboardViewAttr, 109 R.styleable.MainKeyboardView_gestureDetectFastMoveSpeedThreshold, 110 DEFAULT.mDetectFastMoveSpeedThreshold); 111 mDynamicThresholdDecayDuration = mainKeyboardViewAttr.getInt( 112 R.styleable.MainKeyboardView_gestureDynamicThresholdDecayDuration, 113 DEFAULT.mDynamicThresholdDecayDuration); 114 mDynamicTimeThresholdFrom = mainKeyboardViewAttr.getInt( 115 R.styleable.MainKeyboardView_gestureDynamicTimeThresholdFrom, 116 DEFAULT.mDynamicTimeThresholdFrom); 117 mDynamicTimeThresholdTo = mainKeyboardViewAttr.getInt( 118 R.styleable.MainKeyboardView_gestureDynamicTimeThresholdTo, 119 DEFAULT.mDynamicTimeThresholdTo); 120 mDynamicDistanceThresholdFrom = ResourceUtils.getFraction(mainKeyboardViewAttr, 121 R.styleable.MainKeyboardView_gestureDynamicDistanceThresholdFrom, 122 DEFAULT.mDynamicDistanceThresholdFrom); 123 mDynamicDistanceThresholdTo = ResourceUtils.getFraction(mainKeyboardViewAttr, 124 R.styleable.MainKeyboardView_gestureDynamicDistanceThresholdTo, 125 DEFAULT.mDynamicDistanceThresholdTo); 126 mSamplingMinimumDistance = ResourceUtils.getFraction(mainKeyboardViewAttr, 127 R.styleable.MainKeyboardView_gestureSamplingMinimumDistance, 128 DEFAULT.mSamplingMinimumDistance); 129 mRecognitionMinimumTime = mainKeyboardViewAttr.getInt( 130 R.styleable.MainKeyboardView_gestureRecognitionMinimumTime, 131 DEFAULT.mRecognitionMinimumTime); 132 mRecognitionSpeedThreshold = ResourceUtils.getFraction(mainKeyboardViewAttr, 133 R.styleable.MainKeyboardView_gestureRecognitionSpeedThreshold, 134 DEFAULT.mRecognitionSpeedThreshold); 135 } 136 } 137 138 private static final int MSEC_PER_SEC = 1000; 139 GestureStroke(final int pointerId, final GestureStrokeParams params)140 public GestureStroke(final int pointerId, final GestureStrokeParams params) { 141 mPointerId = pointerId; 142 mParams = params; 143 } 144 setKeyboardGeometry(final int keyWidth, final int keyboardHeight)145 public void setKeyboardGeometry(final int keyWidth, final int keyboardHeight) { 146 mKeyWidth = keyWidth; 147 mMinYCoordinate = -(int)(keyboardHeight * EXTRA_GESTURE_TRAIL_AREA_ABOVE_KEYBOARD_RATIO); 148 mMaxYCoordinate = keyboardHeight; 149 // TODO: Find an appropriate base metric for these length. Maybe diagonal length of the key? 150 mDetectFastMoveSpeedThreshold = (int)(keyWidth * mParams.mDetectFastMoveSpeedThreshold); 151 mGestureDynamicDistanceThresholdFrom = 152 (int)(keyWidth * mParams.mDynamicDistanceThresholdFrom); 153 mGestureDynamicDistanceThresholdTo = (int)(keyWidth * mParams.mDynamicDistanceThresholdTo); 154 mGestureSamplingMinimumDistance = (int)(keyWidth * mParams.mSamplingMinimumDistance); 155 mGestureRecognitionSpeedThreshold = (int)(keyWidth * mParams.mRecognitionSpeedThreshold); 156 if (DEBUG) { 157 Log.d(TAG, String.format( 158 "[%d] setKeyboardGeometry: keyWidth=%3d tT=%3d >> %3d tD=%3d >> %3d", 159 mPointerId, keyWidth, 160 mParams.mDynamicTimeThresholdFrom, 161 mParams.mDynamicTimeThresholdTo, 162 mGestureDynamicDistanceThresholdFrom, 163 mGestureDynamicDistanceThresholdTo)); 164 } 165 } 166 getLength()167 public int getLength() { 168 return mEventTimes.getLength(); 169 } 170 onDownEvent(final int x, final int y, final long downTime, final long gestureFirstDownTime, final long lastTypingTime)171 public void onDownEvent(final int x, final int y, final long downTime, 172 final long gestureFirstDownTime, final long lastTypingTime) { 173 reset(); 174 final long elapsedTimeAfterTyping = downTime - lastTypingTime; 175 if (elapsedTimeAfterTyping < mParams.mStaticTimeThresholdAfterFastTyping) { 176 mAfterFastTyping = true; 177 } 178 if (DEBUG) { 179 Log.d(TAG, String.format("[%d] onDownEvent: dT=%3d%s", mPointerId, 180 elapsedTimeAfterTyping, mAfterFastTyping ? " afterFastTyping" : "")); 181 } 182 final int elapsedTimeFromFirstDown = (int)(downTime - gestureFirstDownTime); 183 addPointOnKeyboard(x, y, elapsedTimeFromFirstDown, true /* isMajorEvent */); 184 } 185 getGestureDynamicDistanceThreshold(final int deltaTime)186 private int getGestureDynamicDistanceThreshold(final int deltaTime) { 187 if (!mAfterFastTyping || deltaTime >= mParams.mDynamicThresholdDecayDuration) { 188 return mGestureDynamicDistanceThresholdTo; 189 } 190 final int decayedThreshold = 191 (mGestureDynamicDistanceThresholdFrom - mGestureDynamicDistanceThresholdTo) 192 * deltaTime / mParams.mDynamicThresholdDecayDuration; 193 return mGestureDynamicDistanceThresholdFrom - decayedThreshold; 194 } 195 getGestureDynamicTimeThreshold(final int deltaTime)196 private int getGestureDynamicTimeThreshold(final int deltaTime) { 197 if (!mAfterFastTyping || deltaTime >= mParams.mDynamicThresholdDecayDuration) { 198 return mParams.mDynamicTimeThresholdTo; 199 } 200 final int decayedThreshold = 201 (mParams.mDynamicTimeThresholdFrom - mParams.mDynamicTimeThresholdTo) 202 * deltaTime / mParams.mDynamicThresholdDecayDuration; 203 return mParams.mDynamicTimeThresholdFrom - decayedThreshold; 204 } 205 isStartOfAGesture()206 public final boolean isStartOfAGesture() { 207 if (!hasDetectedFastMove()) { 208 return false; 209 } 210 final int size = getLength(); 211 if (size <= 0) { 212 return false; 213 } 214 final int lastIndex = size - 1; 215 final int deltaTime = mEventTimes.get(lastIndex) - mDetectFastMoveTime; 216 if (deltaTime < 0) { 217 return false; 218 } 219 final int deltaDistance = getDistance( 220 mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex), 221 mDetectFastMoveX, mDetectFastMoveY); 222 final int distanceThreshold = getGestureDynamicDistanceThreshold(deltaTime); 223 final int timeThreshold = getGestureDynamicTimeThreshold(deltaTime); 224 final boolean isStartOfAGesture = deltaTime >= timeThreshold 225 && deltaDistance >= distanceThreshold; 226 if (DEBUG) { 227 Log.d(TAG, String.format("[%d] isStartOfAGesture: dT=%3d tT=%3d dD=%3d tD=%3d%s%s", 228 mPointerId, deltaTime, timeThreshold, 229 deltaDistance, distanceThreshold, 230 mAfterFastTyping ? " afterFastTyping" : "", 231 isStartOfAGesture ? " startOfAGesture" : "")); 232 } 233 return isStartOfAGesture; 234 } 235 duplicateLastPointWith(final int time)236 public void duplicateLastPointWith(final int time) { 237 final int lastIndex = getLength() - 1; 238 if (lastIndex >= 0) { 239 final int x = mXCoordinates.get(lastIndex); 240 final int y = mYCoordinates.get(lastIndex); 241 if (DEBUG) { 242 Log.d(TAG, String.format("[%d] duplicateLastPointWith: %d,%d|%d", mPointerId, 243 x, y, time)); 244 } 245 // TODO: Have appendMajorPoint() 246 appendPoint(x, y, time); 247 updateIncrementalRecognitionSize(x, y, time); 248 } 249 } 250 reset()251 protected void reset() { 252 mIncrementalRecognitionSize = 0; 253 mLastIncrementalBatchSize = 0; 254 mEventTimes.setLength(0); 255 mXCoordinates.setLength(0); 256 mYCoordinates.setLength(0); 257 mLastMajorEventTime = 0; 258 mDetectFastMoveTime = 0; 259 mAfterFastTyping = false; 260 } 261 appendPoint(final int x, final int y, final int time)262 private void appendPoint(final int x, final int y, final int time) { 263 final int lastIndex = getLength() - 1; 264 // The point that is created by {@link duplicateLastPointWith(int)} may have later event 265 // time than the next {@link MotionEvent}. To maintain the monotonicity of the event time, 266 // drop the successive point here. 267 if (lastIndex >= 0 && mEventTimes.get(lastIndex) > time) { 268 Log.w(TAG, String.format("[%d] drop stale event: %d,%d|%d last: %d,%d|%d", mPointerId, 269 x, y, time, mXCoordinates.get(lastIndex), mYCoordinates.get(lastIndex), 270 mEventTimes.get(lastIndex))); 271 return; 272 } 273 mEventTimes.add(time); 274 mXCoordinates.add(x); 275 mYCoordinates.add(y); 276 } 277 updateMajorEvent(final int x, final int y, final int time)278 private void updateMajorEvent(final int x, final int y, final int time) { 279 mLastMajorEventTime = time; 280 mLastMajorEventX = x; 281 mLastMajorEventY = y; 282 } 283 hasDetectedFastMove()284 private final boolean hasDetectedFastMove() { 285 return mDetectFastMoveTime > 0; 286 } 287 detectFastMove(final int x, final int y, final int time)288 private int detectFastMove(final int x, final int y, final int time) { 289 final int size = getLength(); 290 final int lastIndex = size - 1; 291 final int lastX = mXCoordinates.get(lastIndex); 292 final int lastY = mYCoordinates.get(lastIndex); 293 final int dist = getDistance(lastX, lastY, x, y); 294 final int msecs = time - mEventTimes.get(lastIndex); 295 if (msecs > 0) { 296 final int pixels = getDistance(lastX, lastY, x, y); 297 final int pixelsPerSec = pixels * MSEC_PER_SEC; 298 if (DEBUG_SPEED) { 299 final float speed = (float)pixelsPerSec / msecs / mKeyWidth; 300 Log.d(TAG, String.format("[%d] detectFastMove: speed=%5.2f", mPointerId, speed)); 301 } 302 // Equivalent to (pixels / msecs < mStartSpeedThreshold / MSEC_PER_SEC) 303 if (!hasDetectedFastMove() && pixelsPerSec > mDetectFastMoveSpeedThreshold * msecs) { 304 if (DEBUG) { 305 final float speed = (float)pixelsPerSec / msecs / mKeyWidth; 306 Log.d(TAG, String.format( 307 "[%d] detectFastMove: speed=%5.2f T=%3d points=%3d fastMove", 308 mPointerId, speed, time, size)); 309 } 310 mDetectFastMoveTime = time; 311 mDetectFastMoveX = x; 312 mDetectFastMoveY = y; 313 } 314 } 315 return dist; 316 } 317 318 /** 319 * Add a touch event as a gesture point. Returns true if the touch event is on the valid 320 * gesture area. 321 * @param x the x-coordinate of the touch event 322 * @param y the y-coordinate of the touch event 323 * @param time the elapsed time in millisecond from the first gesture down 324 * @param isMajorEvent false if this is a historical move event 325 * @return true if the touch event is on the valid gesture area 326 */ addPointOnKeyboard(final int x, final int y, final int time, final boolean isMajorEvent)327 public boolean addPointOnKeyboard(final int x, final int y, final int time, 328 final boolean isMajorEvent) { 329 final int size = getLength(); 330 if (size <= 0) { 331 // Down event 332 appendPoint(x, y, time); 333 updateMajorEvent(x, y, time); 334 } else { 335 final int distance = detectFastMove(x, y, time); 336 if (distance > mGestureSamplingMinimumDistance) { 337 appendPoint(x, y, time); 338 } 339 } 340 if (isMajorEvent) { 341 updateIncrementalRecognitionSize(x, y, time); 342 updateMajorEvent(x, y, time); 343 } 344 return y >= mMinYCoordinate && y < mMaxYCoordinate; 345 } 346 updateIncrementalRecognitionSize(final int x, final int y, final int time)347 private void updateIncrementalRecognitionSize(final int x, final int y, final int time) { 348 final int msecs = (int)(time - mLastMajorEventTime); 349 if (msecs <= 0) { 350 return; 351 } 352 final int pixels = getDistance(mLastMajorEventX, mLastMajorEventY, x, y); 353 final int pixelsPerSec = pixels * MSEC_PER_SEC; 354 // Equivalent to (pixels / msecs < mGestureRecognitionThreshold / MSEC_PER_SEC) 355 if (pixelsPerSec < mGestureRecognitionSpeedThreshold * msecs) { 356 mIncrementalRecognitionSize = getLength(); 357 } 358 } 359 hasRecognitionTimePast( final long currentTime, final long lastRecognitionTime)360 public final boolean hasRecognitionTimePast( 361 final long currentTime, final long lastRecognitionTime) { 362 return currentTime > lastRecognitionTime + mParams.mRecognitionMinimumTime; 363 } 364 appendAllBatchPoints(final InputPointers out)365 public final void appendAllBatchPoints(final InputPointers out) { 366 appendBatchPoints(out, getLength()); 367 } 368 appendIncrementalBatchPoints(final InputPointers out)369 public final void appendIncrementalBatchPoints(final InputPointers out) { 370 appendBatchPoints(out, mIncrementalRecognitionSize); 371 } 372 appendBatchPoints(final InputPointers out, final int size)373 private void appendBatchPoints(final InputPointers out, final int size) { 374 final int length = size - mLastIncrementalBatchSize; 375 if (length <= 0) { 376 return; 377 } 378 out.append(mPointerId, mEventTimes, mXCoordinates, mYCoordinates, 379 mLastIncrementalBatchSize, length); 380 mLastIncrementalBatchSize = size; 381 } 382 getDistance(final int x1, final int y1, final int x2, final int y2)383 private static int getDistance(final int x1, final int y1, final int x2, final int y2) { 384 final int dx = x1 - x2; 385 final int dy = y1 - y2; 386 // Note that, in recent versions of Android, FloatMath is actually slower than 387 // java.lang.Math due to the way the JIT optimizes java.lang.Math. 388 return (int)Math.sqrt(dx * dx + dy * dy); 389 } 390 } 391