From 85bd0d62830a098c1bdc720dfdcf4fe1b18b657c Mon Sep 17 00:00:00 2001 From: Jeff Brown Date: Sun, 13 May 2012 15:30:42 -0700 Subject: [PATCH] More VelocityTracker refactoring. Bug: 6413587 Change-Id: Ida1152e7a34d5fe5caab5e6b5e1bc79f6c7a25e6 --- core/java/android/view/VelocityTracker.java | 11 +- .../internal/widget/PointerLocationView.java | 2 +- core/jni/android_view_VelocityTracker.cpp | 18 +-- include/androidfw/VelocityTracker.h | 71 ++++++++--- libs/androidfw/VelocityTracker.cpp | 138 +++++++++++++-------- 5 files changed, 155 insertions(+), 85 deletions(-) diff --git a/core/java/android/view/VelocityTracker.java b/core/java/android/view/VelocityTracker.java index f703e34e93ad..f5870e1ba902 100644 --- a/core/java/android/view/VelocityTracker.java +++ b/core/java/android/view/VelocityTracker.java @@ -60,8 +60,7 @@ public final class VelocityTracker implements Poolable { private static native void nativeComputeCurrentVelocity(int ptr, int units, float maxVelocity); private static native float nativeGetXVelocity(int ptr, int id); private static native float nativeGetYVelocity(int ptr, int id); - private static native boolean nativeGetEstimator(int ptr, int id, - int degree, int horizonMillis, Estimator outEstimator); + private static native boolean nativeGetEstimator(int ptr, int id, Estimator outEstimator); /** * Retrieve a new VelocityTracker object to watch the velocity of a @@ -227,21 +226,17 @@ public final class VelocityTracker implements Poolable { * this method. * * @param id Which pointer's velocity to return. - * @param degree The desired polynomial degree. The actual estimator may have - * a lower degree than what is requested here. If -1, uses the default degree. - * @param horizonMillis The maximum age of the oldest sample to consider, in milliseconds. - * If -1, uses the default horizon. * @param outEstimator The estimator to populate. * @return True if an estimator was obtained, false if there is no information * available about the pointer. * * @hide For internal use only. Not a final API. */ - public boolean getEstimator(int id, int degree, int horizonMillis, Estimator outEstimator) { + public boolean getEstimator(int id, Estimator outEstimator) { if (outEstimator == null) { throw new IllegalArgumentException("outEstimator must not be null"); } - return nativeGetEstimator(mPtr, id, degree, horizonMillis, outEstimator); + return nativeGetEstimator(mPtr, id, outEstimator); } /** diff --git a/core/java/com/android/internal/widget/PointerLocationView.java b/core/java/com/android/internal/widget/PointerLocationView.java index 1d6af905a89b..85e6c162a482 100644 --- a/core/java/com/android/internal/widget/PointerLocationView.java +++ b/core/java/com/android/internal/widget/PointerLocationView.java @@ -527,7 +527,7 @@ public class PointerLocationView extends View implements InputDeviceListener { ps.addTrace(coords.x, coords.y); ps.mXVelocity = mVelocity.getXVelocity(id); ps.mYVelocity = mVelocity.getYVelocity(id); - mVelocity.getEstimator(id, -1, -1, ps.mEstimator); + mVelocity.getEstimator(id, ps.mEstimator); ps.mToolType = event.getToolType(i); } } diff --git a/core/jni/android_view_VelocityTracker.cpp b/core/jni/android_view_VelocityTracker.cpp index 04d1056103de..0180e0a682a0 100644 --- a/core/jni/android_view_VelocityTracker.cpp +++ b/core/jni/android_view_VelocityTracker.cpp @@ -48,8 +48,7 @@ public: void addMovement(const MotionEvent* event); void computeCurrentVelocity(int32_t units, float maxVelocity); void getVelocity(int32_t id, float* outVx, float* outVy); - bool getEstimator(int32_t id, uint32_t degree, nsecs_t horizon, - VelocityTracker::Estimator* outEstimator); + bool getEstimator(int32_t id, VelocityTracker::Estimator* outEstimator); private: struct Velocity { @@ -129,9 +128,8 @@ void VelocityTrackerState::getVelocity(int32_t id, float* outVx, float* outVy) { } } -bool VelocityTrackerState::getEstimator(int32_t id, uint32_t degree, nsecs_t horizon, - VelocityTracker::Estimator* outEstimator) { - return mVelocityTracker.getEstimator(id, degree, horizon, outEstimator); +bool VelocityTrackerState::getEstimator(int32_t id, VelocityTracker::Estimator* outEstimator) { + return mVelocityTracker.getEstimator(id, outEstimator); } @@ -186,14 +184,10 @@ static jfloat android_view_VelocityTracker_nativeGetYVelocity(JNIEnv* env, jclas } static jboolean android_view_VelocityTracker_nativeGetEstimator(JNIEnv* env, jclass clazz, - jint ptr, jint id, jint degree, jint horizonMillis, jobject outEstimatorObj) { + jint ptr, jint id, jobject outEstimatorObj) { VelocityTrackerState* state = reinterpret_cast(ptr); VelocityTracker::Estimator estimator; - bool result = state->getEstimator(id, - degree < 0 ? VelocityTracker::DEFAULT_DEGREE : uint32_t(degree), - horizonMillis < 0 ? VelocityTracker::DEFAULT_HORIZON : - nsecs_t(horizonMillis) * 1000000L, - &estimator); + bool result = state->getEstimator(id, &estimator); jfloatArray xCoeffObj = jfloatArray(env->GetObjectField(outEstimatorObj, gEstimatorClassInfo.xCoeff)); @@ -236,7 +230,7 @@ static JNINativeMethod gVelocityTrackerMethods[] = { "(II)F", (void*)android_view_VelocityTracker_nativeGetYVelocity }, { "nativeGetEstimator", - "(IIIILandroid/view/VelocityTracker$Estimator;)Z", + "(IILandroid/view/VelocityTracker$Estimator;)Z", (void*)android_view_VelocityTracker_nativeGetEstimator }, }; diff --git a/include/androidfw/VelocityTracker.h b/include/androidfw/VelocityTracker.h index 6d17e1f32c2d..69645889dc92 100644 --- a/include/androidfw/VelocityTracker.h +++ b/include/androidfw/VelocityTracker.h @@ -23,19 +23,13 @@ namespace android { +class VelocityTrackerStrategy; + /* * Calculates the velocity of pointer movements over time. */ class VelocityTracker { public: - // Default polynomial degree. (used by getVelocity) - static const uint32_t DEFAULT_DEGREE = 2; - - // Default sample horizon. (used by getVelocity) - // We don't use too much history by default since we want to react to quick - // changes in direction. - static const nsecs_t DEFAULT_HORIZON = 100 * 1000000; // 100 ms - struct Position { float x, y; }; @@ -64,6 +58,8 @@ public: }; VelocityTracker(); + VelocityTracker(VelocityTrackerStrategy* strategy); + ~VelocityTracker(); // Resets the velocity tracker state. void clear(); @@ -88,35 +84,80 @@ public: // insufficient movement information for the pointer. bool getVelocity(uint32_t id, float* outVx, float* outVy) const; - // Gets a quadratic estimator for the movements of the specified pointer id. + // Gets an estimator for the recent movements of the specified pointer id. // Returns false and clears the estimator if there is no information available // about the pointer. - bool getEstimator(uint32_t id, uint32_t degree, nsecs_t horizon, - Estimator* outEstimator) const; + bool getEstimator(uint32_t id, Estimator* outEstimator) const; // Gets the active pointer id, or -1 if none. inline int32_t getActivePointerId() const { return mActivePointerId; } // Gets a bitset containing all pointer ids from the most recent movement. - inline BitSet32 getCurrentPointerIdBits() const { return mMovements[mIndex].idBits; } + inline BitSet32 getCurrentPointerIdBits() const { return mCurrentPointerIdBits; } + +private: + BitSet32 mCurrentPointerIdBits; + int32_t mActivePointerId; + VelocityTrackerStrategy* mStrategy; +}; + + +/* + * Implements a particular velocity tracker algorithm. + */ +class VelocityTrackerStrategy { +protected: + VelocityTrackerStrategy() { } + +public: + virtual ~VelocityTrackerStrategy() { } + + virtual void clear() = 0; + virtual void clearPointers(BitSet32 idBits) = 0; + virtual void addMovement(nsecs_t eventTime, BitSet32 idBits, + const VelocityTracker::Position* positions) = 0; + virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const = 0; +}; + + +/* + * Velocity tracker algorithm based on least-squares linear regression. + */ +class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy { +public: + LeastSquaresVelocityTrackerStrategy(); + virtual ~LeastSquaresVelocityTrackerStrategy(); + + virtual void clear(); + virtual void clearPointers(BitSet32 idBits); + virtual void addMovement(nsecs_t eventTime, BitSet32 idBits, + const VelocityTracker::Position* positions); + virtual bool getEstimator(uint32_t id, VelocityTracker::Estimator* outEstimator) const; private: + // Polynomial degree. Must be less than or equal to Estimator::MAX_DEGREE. + static const uint32_t DEGREE = 2; + + // Sample horizon. + // We don't use too much history by default since we want to react to quick + // changes in direction. + static const nsecs_t HORIZON = 100 * 1000000; // 100 ms + // Number of samples to keep. static const uint32_t HISTORY_SIZE = 20; struct Movement { nsecs_t eventTime; BitSet32 idBits; - Position positions[MAX_POINTERS]; + VelocityTracker::Position positions[MAX_POINTERS]; - inline const Position& getPosition(uint32_t id) const { + inline const VelocityTracker::Position& getPosition(uint32_t id) const { return positions[idBits.getIndexOfBit(id)]; } }; uint32_t mIndex; Movement mMovements[HISTORY_SIZE]; - int32_t mActivePointerId; }; } // namespace android diff --git a/libs/androidfw/VelocityTracker.cpp b/libs/androidfw/VelocityTracker.cpp index 2fb094ee6687..de214f8fc799 100644 --- a/libs/androidfw/VelocityTracker.cpp +++ b/libs/androidfw/VelocityTracker.cpp @@ -33,13 +33,7 @@ namespace android { -// --- VelocityTracker --- - -const uint32_t VelocityTracker::DEFAULT_DEGREE; -const nsecs_t VelocityTracker::DEFAULT_HORIZON; -const uint32_t VelocityTracker::HISTORY_SIZE; - -static inline float vectorDot(const float* a, const float* b, uint32_t m) { +static float vectorDot(const float* a, const float* b, uint32_t m) { float r = 0; while (m--) { r += *(a++) * *(b++); @@ -47,7 +41,7 @@ static inline float vectorDot(const float* a, const float* b, uint32_t m) { return r; } -static inline float vectorNorm(const float* a, uint32_t m) { +static float vectorNorm(const float* a, uint32_t m) { float r = 0; while (m--) { float t = *(a++); @@ -91,46 +85,53 @@ static String8 matrixToString(const float* a, uint32_t m, uint32_t n, bool rowMa } #endif -VelocityTracker::VelocityTracker() { - clear(); + +// --- VelocityTracker --- + +VelocityTracker::VelocityTracker() : + mCurrentPointerIdBits(0), mActivePointerId(-1), + mStrategy(new LeastSquaresVelocityTrackerStrategy()) { +} + +VelocityTracker::VelocityTracker(VelocityTrackerStrategy* strategy) : + mCurrentPointerIdBits(0), mActivePointerId(-1), + mStrategy(strategy) { +} + +VelocityTracker::~VelocityTracker() { + delete mStrategy; } void VelocityTracker::clear() { - mIndex = 0; - mMovements[0].idBits.clear(); + mCurrentPointerIdBits.clear(); mActivePointerId = -1; + + mStrategy->clear(); } void VelocityTracker::clearPointers(BitSet32 idBits) { - BitSet32 remainingIdBits(mMovements[mIndex].idBits.value & ~idBits.value); - mMovements[mIndex].idBits = remainingIdBits; + BitSet32 remainingIdBits(mCurrentPointerIdBits.value & ~idBits.value); + mCurrentPointerIdBits = remainingIdBits; if (mActivePointerId >= 0 && idBits.hasBit(mActivePointerId)) { mActivePointerId = !remainingIdBits.isEmpty() ? remainingIdBits.firstMarkedBit() : -1; } + + mStrategy->clearPointers(idBits); } void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions) { - if (++mIndex == HISTORY_SIZE) { - mIndex = 0; - } - while (idBits.count() > MAX_POINTERS) { idBits.clearLastMarkedBit(); } - Movement& movement = mMovements[mIndex]; - movement.eventTime = eventTime; - movement.idBits = idBits; - uint32_t count = idBits.count(); - for (uint32_t i = 0; i < count; i++) { - movement.positions[i] = positions[i]; - } - + mCurrentPointerIdBits = idBits; if (mActivePointerId < 0 || !idBits.hasBit(mActivePointerId)) { - mActivePointerId = count != 0 ? idBits.firstMarkedBit() : -1; + mActivePointerId = idBits.isEmpty() ? -1 : idBits.firstMarkedBit(); } + mStrategy->addMovement(eventTime, idBits, positions); + #if DEBUG_VELOCITY ALOGD("VelocityTracker: addMovement eventTime=%lld, idBits=0x%08x, activePointerId=%d", eventTime, idBits.value, mActivePointerId); @@ -139,7 +140,7 @@ void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Posi uint32_t index = idBits.getIndexOfBit(id); iterBits.clearBit(id); Estimator estimator; - getEstimator(id, DEFAULT_DEGREE, DEFAULT_HORIZON, &estimator); + getEstimator(id, &estimator); ALOGD(" %d: position (%0.3f, %0.3f), " "estimator (degree=%d, xCoeff=%s, yCoeff=%s, confidence=%f)", id, positions[index].x, positions[index].y, @@ -215,6 +216,61 @@ void VelocityTracker::addMovement(const MotionEvent* event) { addMovement(eventTime, idBits, positions); } +bool VelocityTracker::getVelocity(uint32_t id, float* outVx, float* outVy) const { + Estimator estimator; + if (getEstimator(id, &estimator) && estimator.degree >= 1) { + *outVx = estimator.xCoeff[1]; + *outVy = estimator.yCoeff[1]; + return true; + } + *outVx = 0; + *outVy = 0; + return false; +} + +bool VelocityTracker::getEstimator(uint32_t id, Estimator* outEstimator) const { + return mStrategy->getEstimator(id, outEstimator); +} + + +// --- LeastSquaresVelocityTrackerStrategy --- + +const uint32_t LeastSquaresVelocityTrackerStrategy::DEGREE; +const nsecs_t LeastSquaresVelocityTrackerStrategy::HORIZON; +const uint32_t LeastSquaresVelocityTrackerStrategy::HISTORY_SIZE; + +LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy() { + clear(); +} + +LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() { +} + +void LeastSquaresVelocityTrackerStrategy::clear() { + mIndex = 0; + mMovements[0].idBits.clear(); +} + +void LeastSquaresVelocityTrackerStrategy::clearPointers(BitSet32 idBits) { + BitSet32 remainingIdBits(mMovements[mIndex].idBits.value & ~idBits.value); + mMovements[mIndex].idBits = remainingIdBits; +} + +void LeastSquaresVelocityTrackerStrategy::addMovement(nsecs_t eventTime, BitSet32 idBits, + const VelocityTracker::Position* positions) { + if (++mIndex == HISTORY_SIZE) { + mIndex = 0; + } + + Movement& movement = mMovements[mIndex]; + movement.eventTime = eventTime; + movement.idBits = idBits; + uint32_t count = idBits.count(); + for (uint32_t i = 0; i < count; i++) { + movement.positions[i] = positions[i]; + } +} + /** * Solves a linear least squares problem to obtain a N degree polynomial that fits * the specified input data as nearly as possible. @@ -361,22 +417,8 @@ static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32 return true; } -bool VelocityTracker::getVelocity(uint32_t id, float* outVx, float* outVy) const { - Estimator estimator; - if (getEstimator(id, DEFAULT_DEGREE, DEFAULT_HORIZON, &estimator)) { - if (estimator.degree >= 1) { - *outVx = estimator.xCoeff[1]; - *outVy = estimator.yCoeff[1]; - return true; - } - } - *outVx = 0; - *outVy = 0; - return false; -} - -bool VelocityTracker::getEstimator(uint32_t id, uint32_t degree, nsecs_t horizon, - Estimator* outEstimator) const { +bool LeastSquaresVelocityTrackerStrategy::getEstimator(uint32_t id, + VelocityTracker::Estimator* outEstimator) const { outEstimator->clear(); // Iterate over movement samples in reverse time order and collect samples. @@ -393,11 +435,11 @@ bool VelocityTracker::getEstimator(uint32_t id, uint32_t degree, nsecs_t horizon } nsecs_t age = newestMovement.eventTime - movement.eventTime; - if (age > horizon) { + if (age > HORIZON) { break; } - const Position& position = movement.getPosition(id); + const VelocityTracker::Position& position = movement.getPosition(id); x[m] = position.x; y[m] = position.y; time[m] = -age * 0.000000001f; @@ -409,9 +451,7 @@ bool VelocityTracker::getEstimator(uint32_t id, uint32_t degree, nsecs_t horizon } // Calculate a least squares polynomial fit. - if (degree > Estimator::MAX_DEGREE) { - degree = Estimator::MAX_DEGREE; - } + uint32_t degree = DEGREE; if (degree > m - 1) { degree = m - 1; } -- 2.11.0