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.utils.ResizableIntArray; 25 import com.android.inputmethod.latin.utils.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 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 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 140 public GestureStroke(final int pointerId, final GestureStrokeParams params) { 141 mPointerId = pointerId; 142 mParams = params; 143 } 144 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 167 public int getLength() { 168 return mEventTimes.getLength(); 169 } 170 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 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 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 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 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 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 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 278 private void updateMajorEvent(final int x, final int y, final int time) { 279 mLastMajorEventTime = time; 280 mLastMajorEventX = x; 281 mLastMajorEventY = y; 282 } 283 284 private final boolean hasDetectedFastMove() { 285 return mDetectFastMoveTime > 0; 286 } 287 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 */ 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 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 360 public final boolean hasRecognitionTimePast( 361 final long currentTime, final long lastRecognitionTime) { 362 return currentTime > lastRecognitionTime + mParams.mRecognitionMinimumTime; 363 } 364 365 public final void appendAllBatchPoints(final InputPointers out) { 366 appendBatchPoints(out, getLength()); 367 } 368 369 public final void appendIncrementalBatchPoints(final InputPointers out) { 370 appendBatchPoints(out, mIncrementalRecognitionSize); 371 } 372 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 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
