Velocity Tracker II: The Revenge of Velocity Tracker

Bug: 5265529

Rewrote the velocity tracker to fit a polynomial curve
to pointer movements using least squares linear regression.
The velocity is simply the first derivative of this polynomial.

Clients can also obtain an Estimator that describes the
complete terms of the estimating polynomial including
the coefficient of determination which provides a measure
of the quality of the fit (confidence).

Enhanced PointerLocation to display the movement curve predicted
by the estimator in addition to the velocity vector.

By default, the algorithm computes a 2nd degree (quadratic)
polynomial based on a 100ms recent history horizon.

Change-Id: Id377bef44117fce68fee2c41f90134ce3224d3a1

2 files changed, 114 insertions, 2 deletions

diff --git a/core/java/android/view/VelocityTracker.java b/core/java/android/view/VelocityTracker.java
index 5a91d31..dfb2c32 100644
--- a/core/java/android/view/VelocityTracker.java
+++ b/core/java/android/view/VelocityTracker.java
@@ -59,6 +59,8 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     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);
 
     /**
      * Retrieve a new VelocityTracker object to watch the velocity of a
@@ -215,4 +217,94 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     public float getYVelocity(int id) {
         return nativeGetYVelocity(mPtr, id);
     }
+
+    /**
+     * Get an estimator for the movements of a pointer using past movements of the
+     * pointer to predict future movements.
+     *
+     * It is not necessary to call {@link #computeCurrentVelocity(int)} before calling
+     * 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) {
+        if (outEstimator == null) {
+            throw new IllegalArgumentException("outEstimator must not be null");
+        }
+        return nativeGetEstimator(mPtr, id, degree, horizonMillis, outEstimator);
+    }
+
+    /**
+     * An estimator for the movements of a pointer based on a polynomial model.
+     *
+     * The last recorded position of the pointer is at time zero seconds.
+     * Past estimated positions are at negative times and future estimated positions
+     * are at positive times.
+     *
+     * First coefficient is position (in pixels), second is velocity (in pixels per second),
+     * third is acceleration (in pixels per second squared).
+     *
+     * @hide For internal use only.  Not a final API.
+     */
+    public static final class Estimator {
+        // Must match VelocityTracker::Estimator::MAX_DEGREE
+        private static final int MAX_DEGREE = 2;
+
+        /**
+         * Polynomial coefficients describing motion in X.
+         */
+        public final float[] xCoeff = new float[MAX_DEGREE + 1];
+
+        /**
+         * Polynomial coefficients describing motion in Y.
+         */
+        public final float[] yCoeff = new float[MAX_DEGREE + 1];
+
+        /**
+         * Polynomial degree, or zero if only position information is available.
+         */
+        public int degree;
+
+        /**
+         * Confidence (coefficient of determination), between 0 (no fit) and 1 (perfect fit).
+         */
+        public float confidence;
+
+        /**
+         * Gets an estimate of the X position of the pointer at the specified time point.
+         * @param time The time point in seconds, 0 is the last recorded time.
+         * @return The estimated X coordinate.
+         */
+        public float estimateX(float time) {
+            return estimate(time, xCoeff);
+        }
+
+        /**
+         * Gets an estimate of the Y position of the pointer at the specified time point.
+         * @param time The time point in seconds, 0 is the last recorded time.
+         * @return The estimated Y coordinate.
+         */
+        public float estimateY(float time) {
+            return estimate(time, yCoeff);
+        }
+
+        private float estimate(float time, float[] c) {
+            float a = 0;
+            float scale = 1;
+            for (int i = 0; i <= degree; i++) {
+                a += c[i] * scale;
+                scale *= time;
+            }
+            return a;
+        }
+    }
 }
diff --git a/core/java/com/android/internal/widget/PointerLocationView.java b/core/java/com/android/internal/widget/PointerLocationView.java
index 158291b..9a0ce3a 100644
--- a/core/java/com/android/internal/widget/PointerLocationView.java
+++ b/core/java/com/android/internal/widget/PointerLocationView.java
@@ -51,7 +51,10 @@ public class PointerLocationView extends View {
         // Most recent velocity.
         private float mXVelocity;
         private float mYVelocity;
-        
+
+        // Position estimator.
+        private VelocityTracker.Estimator mEstimator = new VelocityTracker.Estimator();
+
         public void clearTrace() {
             mTraceCount = 0;
         }
@@ -75,6 +78,10 @@ public class PointerLocationView extends View {
         }
     }
 
+    private final int ESTIMATE_PAST_POINTS = 4;
+    private final int ESTIMATE_FUTURE_POINTS = 2;
+    private final float ESTIMATE_INTERVAL = 0.02f;
+
     private final ViewConfiguration mVC;
     private final Paint mTextPaint;
     private final Paint mTextBackgroundPaint;
@@ -278,8 +285,20 @@ public class PointerLocationView extends View {
                     haveLast = true;
                 }
                 
-                // Draw velocity vector.
                 if (drawn) {
+                    // Draw movement estimate curve.
+                    mPaint.setARGB(128, 128, 0, 128);
+                    float lx = ps.mEstimator.estimateX(-ESTIMATE_PAST_POINTS * ESTIMATE_INTERVAL);
+                    float ly = ps.mEstimator.estimateY(-ESTIMATE_PAST_POINTS * ESTIMATE_INTERVAL);
+                    for (int i = -ESTIMATE_PAST_POINTS + 1; i <= ESTIMATE_FUTURE_POINTS; i++) {
+                        float x = ps.mEstimator.estimateX(i * ESTIMATE_INTERVAL);
+                        float y = ps.mEstimator.estimateY(i * ESTIMATE_INTERVAL);
+                        canvas.drawLine(lx, ly, x, y, mPaint);
+                        lx = x;
+                        ly = y;
+                    }
+
+                    // Draw velocity vector.
                     mPaint.setARGB(255, 255, 64, 128);
                     float xVel = ps.mXVelocity * (1000 / 60);
                     float yVel = ps.mYVelocity * (1000 / 60);
@@ -517,6 +536,7 @@ public class PointerLocationView extends View {
                     ps.addTrace(coords.x, coords.y);
                     ps.mXVelocity = mVelocity.getXVelocity(id);
                     ps.mYVelocity = mVelocity.getYVelocity(id);
+                    mVelocity.getEstimator(id, -1, -1, ps.mEstimator);
                     ps.mToolType = event.getToolType(i);
                 }
             }