Make velocity tracker strategy configurable.

This change is very useful for testing purposes because it makes it
easy to compare different implementations to see how they behave.

There is no change to the current default strategy.

Bug: 6413587
Change-Id: I4d8567aa4160571ba9fa397ce419882cd9366749

5 files changed, 178 insertions, 36 deletions

diff --git a/core/java/android/view/VelocityTracker.java b/core/java/android/view/VelocityTracker.java
index f5870e1..82b3963 100644
--- a/core/java/android/view/VelocityTracker.java
+++ b/core/java/android/view/VelocityTracker.java
@@ -35,7 +35,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     private static final Pool<VelocityTracker> sPool = Pools.synchronizedPool(
             Pools.finitePool(new PoolableManager<VelocityTracker>() {
                 public VelocityTracker newInstance() {
-                    return new VelocityTracker();
+                    return new VelocityTracker(null);
                 }
 
                 public void onAcquired(VelocityTracker element) {
@@ -50,10 +50,12 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     private static final int ACTIVE_POINTER_ID = -1;
 
     private int mPtr;
+    private final String mStrategy;
+
     private VelocityTracker mNext;
     private boolean mIsPooled;
 
-    private static native int nativeInitialize();
+    private static native int nativeInitialize(String strategy);
     private static native void nativeDispose(int ptr);
     private static native void nativeClear(int ptr);
     private static native void nativeAddMovement(int ptr, MotionEvent event);
@@ -75,11 +77,29 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     }
 
     /**
+     * Obtains a velocity tracker with the specified strategy.
+     * For testing and comparison purposes only.
+     *
+     * @param strategy The strategy, or null to use the default.
+     * @return The velocity tracker.
+     *
+     * @hide
+     */
+    public static VelocityTracker obtain(String strategy) {
+        if (strategy == null) {
+            return obtain();
+        }
+        return new VelocityTracker(strategy);
+    }
+
+    /**
      * Return a VelocityTracker object back to be re-used by others.  You must
      * not touch the object after calling this function.
      */
     public void recycle() {
-        sPool.release(this);
+        if (mStrategy == null) {
+            sPool.release(this);
+        }
     }
 
     /**
@@ -110,8 +130,9 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
         mIsPooled = isPooled;
     }
 
-    private VelocityTracker() {
-        mPtr = nativeInitialize();
+    private VelocityTracker(String strategy) {
+        mPtr = nativeInitialize(strategy);
+        mStrategy = strategy;
     }
 
     @Override
@@ -253,7 +274,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      */
     public static final class Estimator {
         // Must match VelocityTracker::Estimator::MAX_DEGREE
-        private static final int MAX_DEGREE = 2;
+        private static final int MAX_DEGREE = 4;
 
         /**
          * Polynomial coefficients describing motion in X.
diff --git a/core/java/com/android/internal/widget/PointerLocationView.java b/core/java/com/android/internal/widget/PointerLocationView.java
index 85e6c16..34cdd93 100644
--- a/core/java/com/android/internal/widget/PointerLocationView.java
+++ b/core/java/com/android/internal/widget/PointerLocationView.java
@@ -23,6 +23,7 @@ import android.graphics.RectF;
 import android.graphics.Paint.FontMetricsInt;
 import android.hardware.input.InputManager;
 import android.hardware.input.InputManager.InputDeviceListener;
+import android.os.SystemProperties;
 import android.util.Log;
 import android.view.InputDevice;
 import android.view.KeyEvent;
@@ -36,7 +37,11 @@ import java.util.ArrayList;
 
 public class PointerLocationView extends View implements InputDeviceListener {
     private static final String TAG = "Pointer";
-    
+
+    // The system property key used to specify an alternate velocity tracker strategy
+    // to plot alongside the default one.  Useful for testing and comparison purposes.
+    private static final String ALT_STRATEGY_PROPERY_KEY = "debug.velocitytracker.alt";
+
     public static class PointerState {
         // Trace of previous points.
         private float[] mTraceX = new float[32];
@@ -53,9 +58,12 @@ public class PointerLocationView extends View implements InputDeviceListener {
         // Most recent velocity.
         private float mXVelocity;
         private float mYVelocity;
+        private float mAltXVelocity;
+        private float mAltYVelocity;
 
         // Position estimator.
         private VelocityTracker.Estimator mEstimator = new VelocityTracker.Estimator();
+        private VelocityTracker.Estimator mAltEstimator = new VelocityTracker.Estimator();
 
         public void clearTrace() {
             mTraceCount = 0;
@@ -103,7 +111,8 @@ public class PointerLocationView extends View implements InputDeviceListener {
     private final PointerCoords mTempCoords = new PointerCoords();
     
     private final VelocityTracker mVelocity;
-    
+    private final VelocityTracker mAltVelocity;
+
     private final FasterStringBuilder mText = new FasterStringBuilder();
     
     private boolean mPrintCoords = true;
@@ -145,6 +154,14 @@ public class PointerLocationView extends View implements InputDeviceListener {
         mActivePointerId = 0;
         
         mVelocity = VelocityTracker.obtain();
+
+        String altStrategy = SystemProperties.get(ALT_STRATEGY_PROPERY_KEY);
+        if (altStrategy.length() != 0) {
+            Log.d(TAG, "Comparing default velocity tracker strategy with " + altStrategy);
+            mAltVelocity = VelocityTracker.obtain(altStrategy);
+        } else {
+            mAltVelocity = null;
+        }
     }
 
     public void setPrintCoords(boolean state) {
@@ -296,6 +313,25 @@ public class PointerLocationView extends View implements InputDeviceListener {
                 float xVel = ps.mXVelocity * (1000 / 60);
                 float yVel = ps.mYVelocity * (1000 / 60);
                 canvas.drawLine(lastX, lastY, lastX + xVel, lastY + yVel, mPaint);
+
+                // Draw alternate estimate.
+                if (mAltVelocity != null) {
+                    mPaint.setARGB(128, 0, 128, 128);
+                    lx = ps.mAltEstimator.estimateX(-ESTIMATE_PAST_POINTS * ESTIMATE_INTERVAL);
+                    ly = ps.mAltEstimator.estimateY(-ESTIMATE_PAST_POINTS * ESTIMATE_INTERVAL);
+                    for (int i = -ESTIMATE_PAST_POINTS + 1; i <= ESTIMATE_FUTURE_POINTS; i++) {
+                        float x = ps.mAltEstimator.estimateX(i * ESTIMATE_INTERVAL);
+                        float y = ps.mAltEstimator.estimateY(i * ESTIMATE_INTERVAL);
+                        canvas.drawLine(lx, ly, x, y, mPaint);
+                        lx = x;
+                        ly = y;
+                    }
+
+                    mPaint.setARGB(255, 64, 255, 128);
+                    xVel = ps.mAltXVelocity * (1000 / 60);
+                    yVel = ps.mAltYVelocity * (1000 / 60);
+                    canvas.drawLine(lastX, lastY, lastX + xVel, lastY + yVel, mPaint);
+                }
             }
 
             if (mCurDown && ps.mCurDown) {
@@ -470,6 +506,9 @@ public class PointerLocationView extends View implements InputDeviceListener {
                 mCurNumPointers = 0;
                 mMaxNumPointers = 0;
                 mVelocity.clear();
+                if (mAltVelocity != null) {
+                    mAltVelocity.clear();
+                }
             }
 
             mCurNumPointers += 1;
@@ -497,6 +536,10 @@ public class PointerLocationView extends View implements InputDeviceListener {
 
         mVelocity.addMovement(event);
         mVelocity.computeCurrentVelocity(1);
+        if (mAltVelocity != null) {
+            mAltVelocity.addMovement(event);
+            mAltVelocity.computeCurrentVelocity(1);
+        }
 
         final int N = event.getHistorySize();
         for (int historyPos = 0; historyPos < N; historyPos++) {
@@ -528,6 +571,11 @@ public class PointerLocationView extends View implements InputDeviceListener {
                 ps.mXVelocity = mVelocity.getXVelocity(id);
                 ps.mYVelocity = mVelocity.getYVelocity(id);
                 mVelocity.getEstimator(id, ps.mEstimator);
+                if (mAltVelocity != null) {
+                    ps.mAltXVelocity = mAltVelocity.getXVelocity(id);
+                    ps.mAltYVelocity = mAltVelocity.getYVelocity(id);
+                    mAltVelocity.getEstimator(id, ps.mAltEstimator);
+                }
                 ps.mToolType = event.getToolType(i);
             }
         }
diff --git a/core/jni/android_view_VelocityTracker.cpp b/core/jni/android_view_VelocityTracker.cpp
index 0180e0a..c2fa3be 100644
--- a/core/jni/android_view_VelocityTracker.cpp
+++ b/core/jni/android_view_VelocityTracker.cpp
@@ -24,6 +24,8 @@
 #include <androidfw/VelocityTracker.h>
 #include "android_view_MotionEvent.h"
 
+#include <ScopedUtfChars.h>
+
 
 namespace android {
 
@@ -42,7 +44,7 @@ static struct {
 
 class VelocityTrackerState {
 public:
-    VelocityTrackerState();
+    VelocityTrackerState(const char* strategy);
 
     void clear();
     void addMovement(const MotionEvent* event);
@@ -61,7 +63,8 @@ private:
     Velocity mCalculatedVelocity[MAX_POINTERS];
 };
 
-VelocityTrackerState::VelocityTrackerState() : mActivePointerId(-1) {
+VelocityTrackerState::VelocityTrackerState(const char* strategy) :
+        mVelocityTracker(strategy), mActivePointerId(-1) {
 }
 
 void VelocityTrackerState::clear() {
@@ -135,8 +138,13 @@ bool VelocityTrackerState::getEstimator(int32_t id, VelocityTracker::Estimator*
 
 // --- JNI Methods ---
 
-static jint android_view_VelocityTracker_nativeInitialize(JNIEnv* env, jclass clazz) {
-    return reinterpret_cast<jint>(new VelocityTrackerState());
+static jint android_view_VelocityTracker_nativeInitialize(JNIEnv* env, jclass clazz,
+        jstring strategyStr) {
+    if (strategyStr) {
+        ScopedUtfChars strategy(env, strategyStr);
+        return reinterpret_cast<jint>(new VelocityTrackerState(strategy.c_str()));
+    }
+    return reinterpret_cast<jint>(new VelocityTrackerState(NULL));
 }
 
 static void android_view_VelocityTracker_nativeDispose(JNIEnv* env, jclass clazz, jint ptr) {
@@ -209,7 +217,7 @@ static jboolean android_view_VelocityTracker_nativeGetEstimator(JNIEnv* env, jcl
 static JNINativeMethod gVelocityTrackerMethods[] = {
     /* name, signature, funcPtr */
     { "nativeInitialize",
-            "()I",
+            "(Ljava/lang/String;)I",
             (void*)android_view_VelocityTracker_nativeInitialize },
     { "nativeDispose",
             "(I)V",
diff --git a/include/androidfw/VelocityTracker.h b/include/androidfw/VelocityTracker.h
index cbb0782..1d44f13 100644
--- a/include/androidfw/VelocityTracker.h
+++ b/include/androidfw/VelocityTracker.h
@@ -35,7 +35,7 @@ public:
     };
 
     struct Estimator {
-        static const size_t MAX_DEGREE = 2;
+        static const size_t MAX_DEGREE = 4;
 
         // Estimator time base.
         nsecs_t time;
@@ -61,7 +61,10 @@ public:
         }
     };
 
-    VelocityTracker();
+    // Creates a velocity tracker using the specified strategy.
+    // If strategy is NULL, uses the default strategy for the platform.
+    VelocityTracker(const char* strategy = NULL);
+
     ~VelocityTracker();
 
     // Resets the velocity tracker state.
@@ -99,10 +102,16 @@ public:
     inline BitSet32 getCurrentPointerIdBits() const { return mCurrentPointerIdBits; }
 
 private:
+    static const char* DEFAULT_STRATEGY;
+
     nsecs_t mLastEventTime;
     BitSet32 mCurrentPointerIdBits;
     int32_t mActivePointerId;
     VelocityTrackerStrategy* mStrategy;
+
+    bool configureStrategy(const char* strategy);
+
+    static VelocityTrackerStrategy* createStrategy(const char* strategy);
 };
 
 
@@ -129,7 +138,8 @@ public:
  */
 class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
 public:
-    LeastSquaresVelocityTrackerStrategy();
+    // Degree must be no greater than Estimator::MAX_DEGREE.
+    LeastSquaresVelocityTrackerStrategy(uint32_t degree);
     virtual ~LeastSquaresVelocityTrackerStrategy();
 
     virtual void clear();
@@ -139,9 +149,6 @@ public:
     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.
@@ -160,6 +167,7 @@ private:
         }
     };
 
+    const uint32_t mDegree;
     uint32_t mIndex;
     Movement mMovements[HISTORY_SIZE];
 };
diff --git a/libs/androidfw/VelocityTracker.cpp b/libs/androidfw/VelocityTracker.cpp
index 5dbafd8..408b240 100644
--- a/libs/androidfw/VelocityTracker.cpp
+++ b/libs/androidfw/VelocityTracker.cpp
@@ -20,8 +20,8 @@
 // Log debug messages about velocity tracking.
 #define DEBUG_VELOCITY 0
 
-// Log debug messages about least squares fitting.
-#define DEBUG_LEAST_SQUARES 0
+// Log debug messages about the progress of the algorithm itself.
+#define DEBUG_STRATEGY 0
 
 #include <math.h>
 #include <limits.h>
@@ -31,6 +31,8 @@
 #include <utils/String8.h>
 #include <utils/Timers.h>
 
+#include <cutils/properties.h>
+
 namespace android {
 
 // Nanoseconds per milliseconds.
@@ -60,7 +62,7 @@ static float vectorNorm(const float* a, uint32_t m) {
     return sqrtf(r);
 }
 
-#if DEBUG_LEAST_SQUARES || DEBUG_VELOCITY
+#if DEBUG_STRATEGY || DEBUG_VELOCITY
 static String8 vectorToString(const float* a, uint32_t m) {
     String8 str;
     str.append("[");
@@ -98,15 +100,70 @@ static String8 matrixToString(const float* a, uint32_t m, uint32_t n, bool rowMa
 
 // --- VelocityTracker ---
 
-VelocityTracker::VelocityTracker() :
-        mLastEventTime(0), mCurrentPointerIdBits(0), mActivePointerId(-1),
-        mStrategy(new LeastSquaresVelocityTrackerStrategy()) {
+// The default velocity tracker strategy.
+// Although other strategies are available for testing and comparison purposes,
+// this is the strategy that applications will actually use.  Be very careful
+// when adjusting the default strategy because it can dramatically affect
+// (often in a bad way) the user experience.
+const char* VelocityTracker::DEFAULT_STRATEGY = "lsq2";
+
+VelocityTracker::VelocityTracker(const char* strategy) :
+        mLastEventTime(0), mCurrentPointerIdBits(0), mActivePointerId(-1) {
+    char value[PROPERTY_VALUE_MAX];
+
+    // Allow the default strategy to be overridden using a system property for debugging.
+    if (!strategy) {
+        int length = property_get("debug.velocitytracker.strategy", value, NULL);
+        if (length > 0) {
+            strategy = value;
+        } else {
+            strategy = DEFAULT_STRATEGY;
+        }
+    }
+
+    // Configure the strategy.
+    if (!configureStrategy(strategy)) {
+        ALOGD("Unrecognized velocity tracker strategy name '%s'.", strategy);
+        if (!configureStrategy(DEFAULT_STRATEGY)) {
+            LOG_ALWAYS_FATAL("Could not create the default velocity tracker strategy '%s'!",
+                    strategy);
+        }
+    }
 }
 
 VelocityTracker::~VelocityTracker() {
     delete mStrategy;
 }
 
+bool VelocityTracker::configureStrategy(const char* strategy) {
+    mStrategy = createStrategy(strategy);
+    return mStrategy != NULL;
+}
+
+VelocityTrackerStrategy* VelocityTracker::createStrategy(const char* strategy) {
+    if (!strcmp("lsq1", strategy)) {
+        // 1st order least squares.  Quality: POOR.
+        // Frequently underfits the touch data especially when the finger accelerates
+        // or changes direction.  Often underestimates velocity.  The direction
+        // is overly influenced by historical touch points.
+        return new LeastSquaresVelocityTrackerStrategy(1);
+    }
+    if (!strcmp("lsq2", strategy)) {
+        // 2nd order least squares.  Quality: VERY GOOD.
+        // Pretty much ideal, but can be confused by certain kinds of touch data,
+        // particularly if the panel has a tendency to generate delayed,
+        // duplicate or jittery touch coordinates when the finger is released.
+        return new LeastSquaresVelocityTrackerStrategy(2);
+    }
+    if (!strcmp("lsq3", strategy)) {
+        // 3rd order least squares.  Quality: UNUSABLE.
+        // Frequently overfits the touch data yielding wildly divergent estimates
+        // of the velocity when the finger is released.
+        return new LeastSquaresVelocityTrackerStrategy(3);
+    }
+    return NULL;
+}
+
 void VelocityTracker::clear() {
     mCurrentPointerIdBits.clear();
     mActivePointerId = -1;
@@ -259,11 +316,11 @@ bool VelocityTracker::getEstimator(uint32_t id, Estimator* outEstimator) const {
 
 // --- LeastSquaresVelocityTrackerStrategy ---
 
-const uint32_t LeastSquaresVelocityTrackerStrategy::DEGREE;
 const nsecs_t LeastSquaresVelocityTrackerStrategy::HORIZON;
 const uint32_t LeastSquaresVelocityTrackerStrategy::HISTORY_SIZE;
 
-LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy() {
+LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(uint32_t degree) :
+        mDegree(degree) {
     clear();
 }
 
@@ -302,7 +359,7 @@ void LeastSquaresVelocityTrackerStrategy::addMovement(nsecs_t eventTime, BitSet3
  * Returns true if a solution is found, false otherwise.
  *
  * The input consists of two vectors of data points X and Y with indices 0..m-1.
- * The output is a vector B with indices 0..n-1 that describes a polynomial
+ * The output is a vector B with indices 0..n that describes a polynomial
  * that fits the data, such the sum of abs(Y[i] - (B[0] + B[1] X[i] + B[2] X[i]^2 ... B[n] X[i]^n))
  * for all i between 0 and m-1 is minimized.
  *
@@ -332,7 +389,7 @@ void LeastSquaresVelocityTrackerStrategy::addMovement(nsecs_t eventTime, BitSet3
  */
 static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32_t n,
         float* outB, float* outDet) {
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
     ALOGD("solveLeastSquares: m=%d, n=%d, x=%s, y=%s", int(m), int(n),
             vectorToString(x, m).string(), vectorToString(y, m).string());
 #endif
@@ -345,7 +402,7 @@ static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32
             a[i][h] = a[i - 1][h] * x[h];
         }
     }
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
     ALOGD("  - a=%s", matrixToString(&a[0][0], m, n, false /*rowMajor*/).string());
 #endif
 
@@ -366,7 +423,7 @@ static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32
         float norm = vectorNorm(&q[j][0], m);
         if (norm < 0.000001f) {
             // vectors are linearly dependent or zero so no solution
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
             ALOGD("  - no solution, norm=%f", norm);
 #endif
             return false;
@@ -380,7 +437,7 @@ static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32
             r[j][i] = i < j ? 0 : vectorDot(&q[j][0], &a[i][0], m);
         }
     }
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
     ALOGD("  - q=%s", matrixToString(&q[0][0], m, n, false /*rowMajor*/).string());
     ALOGD("  - r=%s", matrixToString(&r[0][0], n, n, true /*rowMajor*/).string());
 
@@ -406,7 +463,7 @@ static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32
         }
         outB[i] /= r[i][i];
     }
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
     ALOGD("  - b=%s", vectorToString(outB, n).string());
 #endif
 
@@ -433,7 +490,7 @@ static bool solveLeastSquares(const float* x, const float* y, uint32_t m, uint32
         sstot += var * var;
     }
     *outDet = sstot > 0.000001f ? 1.0f - (sserr / sstot) : 1;
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
     ALOGD("  - sserr=%f", sserr);
     ALOGD("  - sstot=%f", sstot);
     ALOGD("  - det=%f", *outDet);
@@ -475,7 +532,7 @@ bool LeastSquaresVelocityTrackerStrategy::getEstimator(uint32_t id,
     }
 
     // Calculate a least squares polynomial fit.
-    uint32_t degree = DEGREE;
+    uint32_t degree = mDegree;
     if (degree > m - 1) {
         degree = m - 1;
     }
@@ -487,7 +544,7 @@ bool LeastSquaresVelocityTrackerStrategy::getEstimator(uint32_t id,
             outEstimator->time = newestMovement.eventTime;
             outEstimator->degree = degree;
             outEstimator->confidence = xdet * ydet;
-#if DEBUG_LEAST_SQUARES
+#if DEBUG_STRATEGY
             ALOGD("estimate: degree=%d, xCoeff=%s, yCoeff=%s, confidence=%f",
                     int(outEstimator->degree),
                     vectorToString(outEstimator->xCoeff, n).string(),