Improve VelocityTracker numerical stability.

Replaced VelocityTracker with a faster and more accurate
native implementation.  This avoids the duplicate maintenance
overhead of having two implementations.

The new algorithm requires that the sample duration be at least
10ms in order to contribute to the velocity calculation.  This
ensures that the velocity is not severely overestimated when
samples arrive in bursts.

The new algorithm computes the exponentially weighted moving
average using weights based on the relative duration of successive
sample periods.

The new algorithm is also more careful about how it handles
individual pointers going down or up and their effects on the
collected movement traces.  The intent is to preserve the last
known velocity of pointers as they go up while also ensuring
that other motion samples do not count twice in that case.

Bug: 4086785
Change-Id: I2632321232c64d6b8faacdb929e33f60e64dcdd3

12 files changed, 704 insertions, 358 deletions

diff --git a/core/java/android/view/VelocityTracker.java b/core/java/android/view/VelocityTracker.java
index 4ab2881..fccef2b 100644
--- a/core/java/android/view/VelocityTracker.java
+++ b/core/java/android/view/VelocityTracker.java
@@ -16,8 +16,6 @@
 
 package android.view;
 
-import android.util.Config;
-import android.util.Log;
 import android.util.Poolable;
 import android.util.Pool;
 import android.util.Pools;
@@ -25,24 +23,15 @@ import android.util.PoolableManager;
 
 /**
  * Helper for tracking the velocity of touch events, for implementing
- * flinging and other such gestures.  Use {@link #obtain} to retrieve a
- * new instance of the class when you are going to begin tracking, put
- * the motion events you receive into it with {@link #addMovement(MotionEvent)},
- * and when you want to determine the velocity call
- * {@link #computeCurrentVelocity(int)} and then {@link #getXVelocity()}
- * and {@link #getXVelocity()}.
+ * flinging and other such gestures.
+ *
+ * Use {@link #obtain} to retrieve a new instance of the class when you are going
+ * to begin tracking.  Put the motion events you receive into it with
+ * {@link #addMovement(MotionEvent)}.  When you want to determine the velocity call
+ * {@link #computeCurrentVelocity(int)} and then call {@link #getXVelocity(int)}
+ * and {@link #getXVelocity(int)} to retrieve the velocity for each pointer id.
  */
 public final class VelocityTracker implements Poolable<VelocityTracker> {
-    private static final String TAG = "VelocityTracker";
-    private static final boolean DEBUG = false;
-    private static final boolean localLOGV = DEBUG || Config.LOGV;
-
-    private static final int NUM_PAST = 10;
-    private static final int MAX_AGE_MILLISECONDS = 200;
-    
-    private static final int POINTER_POOL_CAPACITY = 20;
-    private static final int INVALID_POINTER = -1;
-
     private static final Pool<VelocityTracker> sPool = Pools.synchronizedPool(
             Pools.finitePool(new PoolableManager<VelocityTracker>() {
                 public VelocityTracker newInstance() {
@@ -56,31 +45,20 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
                     element.clear();
                 }
             }, 2));
-    
-    private static Pointer sRecycledPointerListHead;
-    private static int sRecycledPointerCount;
-    
-    private static final class Pointer {
-        public Pointer next;
-        
-        public int id;
-        public float xVelocity;
-        public float yVelocity;
-        
-        public final float[] pastX = new float[NUM_PAST];
-        public final float[] pastY = new float[NUM_PAST];
-        public final long[] pastTime = new long[NUM_PAST]; // uses Long.MIN_VALUE as a sentinel
-        
-        public int generation;
-    }
-    
-    private Pointer mPointerListHead; // sorted by id in increasing order
-    private int mLastTouchIndex;
-    private int mGeneration;
-    private int mActivePointerId;
 
+    private static final int ACTIVE_POINTER_ID = -1;
+
+    private int mPtr;
     private VelocityTracker mNext;
 
+    private static native int nativeInitialize();
+    private static native void nativeDispose(int ptr);
+    private static native void nativeClear(int ptr);
+    private static native void nativeAddMovement(int ptr, MotionEvent event);
+    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);
+
     /**
      * Retrieve a new VelocityTracker object to watch the velocity of a
      * motion.  Be sure to call {@link #recycle} when done.  You should
@@ -116,18 +94,26 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
     }
 
     private VelocityTracker() {
-        clear();
+        mPtr = nativeInitialize();
     }
-    
+
+    @Override
+    protected void finalize() throws Throwable {
+        try {
+            if (mPtr != 0) {
+                nativeDispose(mPtr);
+                mPtr = 0;
+            }
+        } finally {
+            super.finalize();
+        }
+    }
+
     /**
      * Reset the velocity tracker back to its initial state.
      */
     public void clear() {
-        releasePointerList(mPointerListHead);
-        
-        mPointerListHead = null;
-        mLastTouchIndex = 0;
-        mActivePointerId = INVALID_POINTER;
+        nativeClear(mPtr);
     }
     
     /**
@@ -137,110 +123,13 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * final {@link MotionEvent#ACTION_UP}.  You can, however, call this
      * for whichever events you desire.
      * 
-     * @param ev The MotionEvent you received and would like to track.
+     * @param event The MotionEvent you received and would like to track.
      */
-    public void addMovement(MotionEvent ev) {
-        final int historySize = ev.getHistorySize();
-        final int pointerCount = ev.getPointerCount();
-        final int lastTouchIndex = mLastTouchIndex;
-        final int nextTouchIndex = (lastTouchIndex + 1) % NUM_PAST;
-        final int finalTouchIndex = (nextTouchIndex + historySize) % NUM_PAST;
-        final int generation = mGeneration++;
-        
-        mLastTouchIndex = finalTouchIndex;
-
-        // Update pointer data.
-        Pointer previousPointer = null;
-        for (int i = 0; i < pointerCount; i++){
-            final int pointerId = ev.getPointerId(i);
-            
-            // Find the pointer data for this pointer id.
-            // This loop is optimized for the common case where pointer ids in the event
-            // are in sorted order.  However, we check for this case explicitly and
-            // perform a full linear scan from the start if needed.
-            Pointer nextPointer;
-            if (previousPointer == null || pointerId < previousPointer.id) {
-                previousPointer = null;
-                nextPointer = mPointerListHead;
-            } else {
-                nextPointer = previousPointer.next;
-            }
-            
-            final Pointer pointer;
-            for (;;) {
-                if (nextPointer != null) {
-                    final int nextPointerId = nextPointer.id;
-                    if (nextPointerId == pointerId) {
-                        pointer = nextPointer;
-                        break;
-                    }
-                    if (nextPointerId < pointerId) {
-                        nextPointer = nextPointer.next;
-                        continue;
-                    }
-                }
-                
-                // Pointer went down.  Add it to the list.
-                // Write a sentinel at the end of the pastTime trace so we will be able to
-                // tell when the trace started.
-                if (mActivePointerId == INVALID_POINTER) {
-                    // Congratulations! You're the new active pointer!
-                    mActivePointerId = pointerId;
-                }
-                pointer = obtainPointer();
-                pointer.id = pointerId;
-                pointer.pastTime[lastTouchIndex] = Long.MIN_VALUE;
-                pointer.next = nextPointer;
-                if (previousPointer == null) {
-                    mPointerListHead = pointer;
-                } else {
-                    previousPointer.next = pointer;
-                }
-                break;
-            }
-            
-            pointer.generation = generation;
-            previousPointer = pointer;
-            
-            final float[] pastX = pointer.pastX;
-            final float[] pastY = pointer.pastY;
-            final long[] pastTime = pointer.pastTime;
-            
-            for (int j = 0; j < historySize; j++) {
-                final int touchIndex = (nextTouchIndex + j) % NUM_PAST;
-                pastX[touchIndex] = ev.getHistoricalX(i, j);
-                pastY[touchIndex] = ev.getHistoricalY(i, j);
-                pastTime[touchIndex] = ev.getHistoricalEventTime(j);
-            }
-            pastX[finalTouchIndex] = ev.getX(i);
-            pastY[finalTouchIndex] = ev.getY(i);
-            pastTime[finalTouchIndex] = ev.getEventTime();
-        }
-        
-        // Find removed pointers.
-        previousPointer = null;
-        for (Pointer pointer = mPointerListHead; pointer != null; ) {
-            final Pointer nextPointer = pointer.next;
-            final int pointerId = pointer.id;
-            if (pointer.generation != generation) {
-                // Pointer went up.  Remove it from the list.
-                if (previousPointer == null) {
-                    mPointerListHead = nextPointer;
-                } else {
-                    previousPointer.next = nextPointer;
-                }
-                releasePointer(pointer);
-
-                if (pointerId == mActivePointerId) {
-                    // Pick a new active pointer. How is arbitrary.
-                    mActivePointerId = mPointerListHead != null ?
-                            mPointerListHead.id : INVALID_POINTER;
-                }
-            } else {
-                previousPointer = pointer;
-            }
-            pointer = nextPointer;
+    public void addMovement(MotionEvent event) {
+        if (event == null) {
+            throw new IllegalArgumentException("event must not be null");
         }
+        nativeAddMovement(mPtr, event);
     }
 
     /**
@@ -250,7 +139,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @see #computeCurrentVelocity(int, float) 
      */
     public void computeCurrentVelocity(int units) {
-        computeCurrentVelocity(units, Float.MAX_VALUE);
+        nativeComputeCurrentVelocity(mPtr, units, Float.MAX_VALUE);
     }
 
     /**
@@ -267,78 +156,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * must be positive.
      */
     public void computeCurrentVelocity(int units, float maxVelocity) {
-        final int lastTouchIndex = mLastTouchIndex;
-        
-        for (Pointer pointer = mPointerListHead; pointer != null; pointer = pointer.next) {
-            final long[] pastTime = pointer.pastTime;
-            
-            // Search backwards in time for oldest acceptable time.
-            // Stop at the beginning of the trace as indicated by the sentinel time Long.MIN_VALUE.
-            int oldestTouchIndex = lastTouchIndex;
-            int numTouches = 1;
-            final long minTime = pastTime[lastTouchIndex] - MAX_AGE_MILLISECONDS;
-            while (numTouches < NUM_PAST) {
-                final int nextOldestTouchIndex = (oldestTouchIndex + NUM_PAST - 1) % NUM_PAST;
-                final long nextOldestTime = pastTime[nextOldestTouchIndex];
-                if (nextOldestTime < minTime) { // also handles end of trace sentinel
-                    break;
-                }
-                oldestTouchIndex = nextOldestTouchIndex;
-                numTouches += 1;
-            }
-            
-            // If we have a lot of samples, skip the last received sample since it is
-            // probably pretty noisy compared to the sum of all of the traces already acquired.
-            if (numTouches > 3) {
-                numTouches -= 1;
-            }
-            
-            // Kind-of stupid.
-            final float[] pastX = pointer.pastX;
-            final float[] pastY = pointer.pastY;
-            
-            final float oldestX = pastX[oldestTouchIndex];
-            final float oldestY = pastY[oldestTouchIndex];
-            final long oldestTime = pastTime[oldestTouchIndex];
-            
-            float accumX = 0;
-            float accumY = 0;
-            
-            for (int i = 1; i < numTouches; i++) {
-                final int touchIndex = (oldestTouchIndex + i) % NUM_PAST;
-                final int duration = (int)(pastTime[touchIndex] - oldestTime);
-                
-                if (duration == 0) continue;
-                
-                float delta = pastX[touchIndex] - oldestX;
-                float velocity = (delta / duration) * units; // pixels/frame.
-                accumX = (accumX == 0) ? velocity : (accumX + velocity) * .5f;
-            
-                delta = pastY[touchIndex] - oldestY;
-                velocity = (delta / duration) * units; // pixels/frame.
-                accumY = (accumY == 0) ? velocity : (accumY + velocity) * .5f;
-            }
-            
-            if (accumX < -maxVelocity) {
-                accumX = - maxVelocity;
-            } else if (accumX > maxVelocity) {
-                accumX = maxVelocity;
-            }
-            
-            if (accumY < -maxVelocity) {
-                accumY = - maxVelocity;
-            } else if (accumY > maxVelocity) {
-                accumY = maxVelocity;
-            }
-            
-            pointer.xVelocity = accumX;
-            pointer.yVelocity = accumY;
-            
-            if (localLOGV) {
-                Log.v(TAG, "Pointer " + pointer.id
-                    + ": Y velocity=" + accumX +" X velocity=" + accumY + " N=" + numTouches);
-            }
-        }
+        nativeComputeCurrentVelocity(mPtr, units, maxVelocity);
     }
     
     /**
@@ -348,8 +166,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed X velocity.
      */
     public float getXVelocity() {
-        Pointer pointer = getPointer(mActivePointerId);
-        return pointer != null ? pointer.xVelocity : 0;
+        return nativeGetXVelocity(mPtr, ACTIVE_POINTER_ID);
     }
     
     /**
@@ -359,8 +176,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed Y velocity.
      */
     public float getYVelocity() {
-        Pointer pointer = getPointer(mActivePointerId);
-        return pointer != null ? pointer.yVelocity : 0;
+        return nativeGetYVelocity(mPtr, ACTIVE_POINTER_ID);
     }
     
     /**
@@ -371,8 +187,7 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed X velocity.
      */
     public float getXVelocity(int id) {
-        Pointer pointer = getPointer(id);
-        return pointer != null ? pointer.xVelocity : 0;
+        return nativeGetXVelocity(mPtr, id);
     }
     
     /**
@@ -383,68 +198,6 @@ public final class VelocityTracker implements Poolable<VelocityTracker> {
      * @return The previously computed Y velocity.
      */
     public float getYVelocity(int id) {
-        Pointer pointer = getPointer(id);
-        return pointer != null ? pointer.yVelocity : 0;
-    }
-    
-    private Pointer getPointer(int id) {
-        for (Pointer pointer = mPointerListHead; pointer != null; pointer = pointer.next) {
-            if (pointer.id == id) {
-                return pointer;
-            }
-        }
-        return null;
-    }
-    
-    private static Pointer obtainPointer() {
-        synchronized (sPool) {
-            if (sRecycledPointerCount != 0) {
-                Pointer element = sRecycledPointerListHead;
-                sRecycledPointerCount -= 1;
-                sRecycledPointerListHead = element.next;
-                element.next = null;
-                return element;
-            }
-        }
-        return new Pointer();
-    }
-    
-    private static void releasePointer(Pointer pointer) {
-        synchronized (sPool) {
-            if (sRecycledPointerCount < POINTER_POOL_CAPACITY) {
-                pointer.next = sRecycledPointerListHead;
-                sRecycledPointerCount += 1;
-                sRecycledPointerListHead = pointer;
-            }
-        }
-    }
-    
-    private static void releasePointerList(Pointer pointer) {
-        if (pointer != null) {
-            synchronized (sPool) {
-                int count = sRecycledPointerCount;
-                if (count >= POINTER_POOL_CAPACITY) {
-                    return;
-                }
-                
-                Pointer tail = pointer;
-                for (;;) {
-                    count += 1;
-                    if (count >= POINTER_POOL_CAPACITY) {
-                        break;
-                    }
-                    
-                    Pointer next = tail.next;
-                    if (next == null) {
-                        break;
-                    }
-                    tail = next;
-                }
-
-                tail.next = sRecycledPointerListHead;
-                sRecycledPointerCount = count;
-                sRecycledPointerListHead = pointer;
-            }
-        }
+        return nativeGetYVelocity(mPtr, id);
     }
 }
diff --git a/core/jni/Android.mk b/core/jni/Android.mk
index 52fc930..b4a0e4f 100644
--- a/core/jni/Android.mk
+++ b/core/jni/Android.mk
@@ -54,6 +54,7 @@ LOCAL_SRC_FILES:= \
 	android_view_KeyCharacterMap.cpp \
 	android_view_GLES20Canvas.cpp \
 	android_view_MotionEvent.cpp \
+	android_view_VelocityTracker.cpp \
 	android_text_AndroidCharacter.cpp \
 	android_text_AndroidBidi.cpp \
 	android_os_Debug.cpp \
diff --git a/core/jni/AndroidRuntime.cpp b/core/jni/AndroidRuntime.cpp
index 0e071a4..e4eb692 100644
--- a/core/jni/AndroidRuntime.cpp
+++ b/core/jni/AndroidRuntime.cpp
@@ -170,6 +170,7 @@ extern int register_android_view_InputChannel(JNIEnv* env);
 extern int register_android_view_InputQueue(JNIEnv* env);
 extern int register_android_view_KeyEvent(JNIEnv* env);
 extern int register_android_view_MotionEvent(JNIEnv* env);
+extern int register_android_view_VelocityTracker(JNIEnv* env);
 extern int register_android_content_res_ObbScanner(JNIEnv* env);
 extern int register_android_content_res_Configuration(JNIEnv* env);
 extern int register_android_animation_PropertyValuesHolder(JNIEnv *env);
@@ -1302,6 +1303,7 @@ static const RegJNIRec gRegJNI[] = {
     REG_JNI(register_android_view_InputQueue),
     REG_JNI(register_android_view_KeyEvent),
     REG_JNI(register_android_view_MotionEvent),
+    REG_JNI(register_android_view_VelocityTracker),
 
     REG_JNI(register_android_content_res_ObbScanner),
     REG_JNI(register_android_content_res_Configuration),
diff --git a/core/jni/android_view_InputQueue.cpp b/core/jni/android_view_InputQueue.cpp
index b5a5d2e..80c4871 100644
--- a/core/jni/android_view_InputQueue.cpp
+++ b/core/jni/android_view_InputQueue.cpp
@@ -380,7 +380,7 @@ int NativeInputQueue::handleReceiveCallback(int receiveFd, int events, void* dat
 #if DEBUG_DISPATCH_CYCLE
         LOGD("channel '%s' ~ Received motion event.", connection->getInputChannelName());
 #endif
-        inputEventObj = android_view_MotionEvent_fromNative(env,
+        inputEventObj = android_view_MotionEvent_obtainAsCopy(env,
                 static_cast<MotionEvent*>(inputEvent));
         dispatchMethodId = gInputQueueClassInfo.dispatchMotionEvent;
         break;
diff --git a/core/jni/android_view_MotionEvent.cpp b/core/jni/android_view_MotionEvent.cpp
index 68ebfe7..4ce471e 100644
--- a/core/jni/android_view_MotionEvent.cpp
+++ b/core/jni/android_view_MotionEvent.cpp
@@ -57,7 +57,10 @@ static struct {
 
 // ----------------------------------------------------------------------------
 
-static MotionEvent* android_view_MotionEvent_getNativePtr(JNIEnv* env, jobject eventObj) {
+MotionEvent* android_view_MotionEvent_getNativePtr(JNIEnv* env, jobject eventObj) {
+    if (!eventObj) {
+        return NULL;
+    }
     return reinterpret_cast<MotionEvent*>(
             env->GetIntField(eventObj, gMotionEventClassInfo.mNativePtr));
 }
@@ -68,10 +71,10 @@ static void android_view_MotionEvent_setNativePtr(JNIEnv* env, jobject eventObj,
             reinterpret_cast<int>(event));
 }
 
-jobject android_view_MotionEvent_fromNative(JNIEnv* env, const MotionEvent* event) {
+jobject android_view_MotionEvent_obtainAsCopy(JNIEnv* env, const MotionEvent* event) {
     jobject eventObj = env->CallStaticObjectMethod(gMotionEventClassInfo.clazz,
             gMotionEventClassInfo.obtain);
-    if (env->ExceptionCheck()) {
+    if (env->ExceptionCheck() || !eventObj) {
         LOGE("An exception occurred while obtaining a motion event.");
         LOGE_EX(env);
         env->ExceptionClear();
@@ -88,18 +91,6 @@ jobject android_view_MotionEvent_fromNative(JNIEnv* env, const MotionEvent* even
     return eventObj;
 }
 
-status_t android_view_MotionEvent_toNative(JNIEnv* env, jobject eventObj,
-        MotionEvent* event) {
-    MotionEvent* srcEvent = android_view_MotionEvent_getNativePtr(env, eventObj);
-    if (!srcEvent) {
-        LOGE("MotionEvent was finalized");
-        return BAD_VALUE;
-    }
-
-    event->copyFrom(srcEvent, true);
-    return OK;
-}
-
 status_t android_view_MotionEvent_recycle(JNIEnv* env, jobject eventObj) {
     env->CallVoidMethod(eventObj, gMotionEventClassInfo.recycle);
     if (env->ExceptionCheck()) {
@@ -500,13 +491,7 @@ static jint android_view_MotionEvent_nativeGetPointerId(JNIEnv* env, jclass claz
 static jint android_view_MotionEvent_nativeFindPointerIndex(JNIEnv* env, jclass clazz,
         jint nativePtr, jint pointerId) {
     MotionEvent* event = reinterpret_cast<MotionEvent*>(nativePtr);
-    size_t pointerCount = event->getPointerCount();
-    for (size_t i = 0; i < pointerCount; i++) {
-        if (event->getPointerId(i) == pointerId) {
-            return i;
-        }
-    }
-    return -1;
+    return jint(event->findPointerIndex(pointerId));
 }
 
 static jint android_view_MotionEvent_nativeGetHistorySize(JNIEnv* env, jclass clazz,
diff --git a/core/jni/android_view_MotionEvent.h b/core/jni/android_view_MotionEvent.h
index 80dc861..0cf1fb2 100644
--- a/core/jni/android_view_MotionEvent.h
+++ b/core/jni/android_view_MotionEvent.h
@@ -26,12 +26,11 @@ class MotionEvent;
 
 /* Obtains an instance of a DVM MotionEvent object as a copy of a native MotionEvent instance.
  * Returns NULL on error. */
-extern jobject android_view_MotionEvent_fromNative(JNIEnv* env, const MotionEvent* event);
+extern jobject android_view_MotionEvent_obtainAsCopy(JNIEnv* env, const MotionEvent* event);
 
-/* Copies the contents of a DVM MotionEvent object to a native MotionEvent instance.
- * Returns non-zero on error. */
-extern status_t android_view_MotionEvent_toNative(JNIEnv* env, jobject eventObj,
-        MotionEvent* event);
+/* Gets the underlying native MotionEvent instance within a DVM MotionEvent object.
+ * Returns NULL if the event is NULL or if it is uninitialized. */
+extern MotionEvent* android_view_MotionEvent_getNativePtr(JNIEnv* env, jobject eventObj);
 
 /* Recycles a DVM MotionEvent object.
  * Returns non-zero on error. */
diff --git a/core/jni/android_view_VelocityTracker.cpp b/core/jni/android_view_VelocityTracker.cpp
new file mode 100644
index 0000000..daa0adc
--- /dev/null
+++ b/core/jni/android_view_VelocityTracker.cpp
@@ -0,0 +1,208 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "VelocityTracker-JNI"
+
+#include "JNIHelp.h"
+
+#include <android_runtime/AndroidRuntime.h>
+#include <utils/Log.h>
+#include <ui/Input.h>
+#include "android_view_MotionEvent.h"
+
+
+namespace android {
+
+// Special constant to request the velocity of the active pointer.
+static const int ACTIVE_POINTER_ID = -1;
+
+// --- VelocityTrackerState ---
+
+class VelocityTrackerState {
+public:
+    VelocityTrackerState();
+
+    void clear();
+    void addMovement(const MotionEvent* event);
+    void computeCurrentVelocity(int32_t units, float maxVelocity);
+    void getVelocity(int32_t id, float* outVx, float* outVy);
+
+private:
+    struct Velocity {
+        float vx, vy;
+    };
+
+    VelocityTracker mVelocityTracker;
+    int32_t mActivePointerId;
+    BitSet32 mCalculatedIdBits;
+    Velocity mCalculatedVelocity[MAX_POINTERS];
+};
+
+VelocityTrackerState::VelocityTrackerState() : mActivePointerId(-1) {
+}
+
+void VelocityTrackerState::clear() {
+    mVelocityTracker.clear();
+    mActivePointerId = -1;
+    mCalculatedIdBits.clear();
+}
+
+void VelocityTrackerState::addMovement(const MotionEvent* event) {
+    mVelocityTracker.addMovement(event);
+}
+
+void VelocityTrackerState::computeCurrentVelocity(int32_t units, float maxVelocity) {
+    BitSet32 idBits(mVelocityTracker.getCurrentPointerIdBits());
+    mCalculatedIdBits = idBits;
+
+    for (uint32_t index = 0; !idBits.isEmpty(); index++) {
+        uint32_t id = idBits.firstMarkedBit();
+        idBits.clearBit(id);
+
+        float vx, vy;
+        mVelocityTracker.getVelocity(id, &vx, &vy);
+
+        vx = vx * units / 1000;
+        vy = vy * units / 1000;
+
+        if (vx > maxVelocity) {
+            vx = maxVelocity;
+        } else if (vx < -maxVelocity) {
+            vx = -maxVelocity;
+        }
+        if (vy > maxVelocity) {
+            vy = maxVelocity;
+        } else if (vy < -maxVelocity) {
+            vy = -maxVelocity;
+        }
+
+        Velocity& velocity = mCalculatedVelocity[index];
+        velocity.vx = vx;
+        velocity.vy = vy;
+    }
+}
+
+void VelocityTrackerState::getVelocity(int32_t id, float* outVx, float* outVy) {
+    if (id == ACTIVE_POINTER_ID) {
+        id = mVelocityTracker.getActivePointerId();
+    }
+
+    float vx, vy;
+    if (id >= 0 && id <= MAX_POINTER_ID && mCalculatedIdBits.hasBit(id)) {
+        uint32_t index = mCalculatedIdBits.getIndexOfBit(id);
+        const Velocity& velocity = mCalculatedVelocity[index];
+        vx = velocity.vx;
+        vy = velocity.vy;
+    } else {
+        vx = 0;
+        vy = 0;
+    }
+
+    if (outVx) {
+        *outVx = vx;
+    }
+    if (outVy) {
+        *outVy = vy;
+    }
+}
+
+
+// --- JNI Methods ---
+
+static jint android_view_VelocityTracker_nativeInitialize(JNIEnv* env, jclass clazz) {
+    return reinterpret_cast<jint>(new VelocityTrackerState());
+}
+
+static void android_view_VelocityTracker_nativeDispose(JNIEnv* env, jclass clazz, jint ptr) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    delete state;
+}
+
+static void android_view_VelocityTracker_nativeClear(JNIEnv* env, jclass clazz, jint ptr) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    state->clear();
+}
+
+static void android_view_VelocityTracker_nativeAddMovement(JNIEnv* env, jclass clazz, jint ptr,
+        jobject eventObj) {
+    const MotionEvent* event = android_view_MotionEvent_getNativePtr(env, eventObj);
+    if (!event) {
+        LOGW("nativeAddMovement failed because MotionEvent was finalized.");
+        return;
+    }
+
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    state->addMovement(event);
+}
+
+static void android_view_VelocityTracker_nativeComputeCurrentVelocity(JNIEnv* env, jclass clazz,
+        jint ptr, jint units, jfloat maxVelocity) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    state->computeCurrentVelocity(units, maxVelocity);
+}
+
+static jfloat android_view_VelocityTracker_nativeGetXVelocity(JNIEnv* env, jclass clazz,
+        jint ptr, jint id) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    float vx;
+    state->getVelocity(id, &vx, NULL);
+    return vx;
+}
+
+static jfloat android_view_VelocityTracker_nativeGetYVelocity(JNIEnv* env, jclass clazz,
+        jint ptr, jint id) {
+    VelocityTrackerState* state = reinterpret_cast<VelocityTrackerState*>(ptr);
+    float vy;
+    state->getVelocity(id, NULL, &vy);
+    return vy;
+}
+
+
+// --- JNI Registration ---
+
+static JNINativeMethod gVelocityTrackerMethods[] = {
+    /* name, signature, funcPtr */
+    { "nativeInitialize",
+            "()I",
+            (void*)android_view_VelocityTracker_nativeInitialize },
+    { "nativeDispose",
+            "(I)V",
+            (void*)android_view_VelocityTracker_nativeDispose },
+    { "nativeClear",
+            "(I)V",
+            (void*)android_view_VelocityTracker_nativeClear },
+    { "nativeAddMovement",
+            "(ILandroid/view/MotionEvent;)V",
+            (void*)android_view_VelocityTracker_nativeAddMovement },
+    { "nativeComputeCurrentVelocity",
+            "(IIF)V",
+            (void*)android_view_VelocityTracker_nativeComputeCurrentVelocity },
+    { "nativeGetXVelocity",
+            "(II)F",
+            (void*)android_view_VelocityTracker_nativeGetXVelocity },
+    { "nativeGetYVelocity",
+            "(II)F",
+            (void*)android_view_VelocityTracker_nativeGetYVelocity },
+};
+
+int register_android_view_VelocityTracker(JNIEnv* env) {
+    int res = jniRegisterNativeMethods(env, "android/view/VelocityTracker",
+            gVelocityTrackerMethods, NELEM(gVelocityTrackerMethods));
+    LOG_FATAL_IF(res < 0, "Unable to register native methods.");
+    return 0;
+}
+
+} // namespace android
diff --git a/include/ui/Input.h b/include/ui/Input.h
index e9cacf4..8e8b61b 100644
--- a/include/ui/Input.h
+++ b/include/ui/Input.h
@@ -311,6 +311,13 @@ public:
 
     inline int32_t getAction() const { return mAction; }
 
+    inline int32_t getActionMasked() const { return mAction & AMOTION_EVENT_ACTION_MASK; }
+
+    inline int32_t getActionIndex() const {
+        return (mAction & AMOTION_EVENT_ACTION_POINTER_INDEX_MASK)
+                >> AMOTION_EVENT_ACTION_POINTER_INDEX_SHIFT;
+    }
+
     inline void setAction(int32_t action) { mAction = action; }
 
     inline int32_t getFlags() const { return mFlags; }
@@ -458,6 +465,8 @@ public:
                 AMOTION_EVENT_AXIS_ORIENTATION, pointerIndex, historicalIndex);
     }
 
+    ssize_t findPointerIndex(int32_t pointerId) const;
+
     void initialize(
             int32_t deviceId,
             int32_t source,
@@ -551,8 +560,7 @@ private:
 };
 
 /*
- * Calculates the velocity of pointer motions over time.
- * Uses essentially the same algorithm as android.view.VelocityTracker.
+ * Calculates the velocity of pointer movements over time.
  */
 class VelocityTracker {
 public:
@@ -565,6 +573,11 @@ public:
     // Resets the velocity tracker state.
     void clear();
 
+    // Resets the velocity tracker state for specific pointers.
+    // Call this method when some pointers have changed and may be reusing
+    // an id that was assigned to a different pointer earlier.
+    void clearPointers(BitSet32 idBits);
+
     // Adds movement information for a set of pointers.
     // The idBits bitfield specifies the pointer ids of the pointers whose positions
     // are included in the movement.
@@ -572,11 +585,20 @@ public:
     // increasing id.  Its size should be equal to the number of one bits in idBits.
     void addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions);
 
+    // Adds movement information for all pointers in a MotionEvent, including historical samples.
+    void addMovement(const MotionEvent* event);
+
     // Gets the velocity of the specified pointer id in position units per second.
     // Returns false and sets the velocity components to zero if there is no movement
     // information for the pointer.
     bool getVelocity(uint32_t id, float* outVx, float* outVy) 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; }
+
 private:
     // Number of samples to keep.
     static const uint32_t HISTORY_SIZE = 10;
@@ -585,7 +607,7 @@ private:
     static const nsecs_t MAX_AGE = 200 * 1000000; // 200 ms
 
     // The minimum duration between samples when estimating velocity.
-    static const nsecs_t MIN_DURATION = 5 * 1000000; // 5 ms
+    static const nsecs_t MIN_DURATION = 10 * 1000000; // 10 ms
 
     struct Movement {
         nsecs_t eventTime;
@@ -595,6 +617,7 @@ private:
 
     uint32_t mIndex;
     Movement mMovements[HISTORY_SIZE];
+    int32_t mActivePointerId;
 };
 
 /*
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h
index f03825a..de748b5 100644
--- a/include/utils/BitSet.h
+++ b/include/utils/BitSet.h
@@ -61,6 +61,10 @@ struct BitSet32 {
     // Result is undefined if all bits are marked.
     inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); }
 
+    // Finds the last marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); }
+
     // Gets the index of the specified bit in the set, which is the number of
     // marked bits that appear before the specified bit.
     inline uint32_t getIndexOfBit(uint32_t n) const {
diff --git a/libs/ui/Input.cpp b/libs/ui/Input.cpp
index eaa8926..440ec00 100644
--- a/libs/ui/Input.cpp
+++ b/libs/ui/Input.cpp
@@ -469,6 +469,16 @@ float MotionEvent::getHistoricalAxisValue(int32_t axis, size_t pointerIndex,
     return value;
 }
 
+ssize_t MotionEvent::findPointerIndex(int32_t pointerId) const {
+    size_t pointerCount = mPointerIds.size();
+    for (size_t i = 0; i < pointerCount; i++) {
+        if (mPointerIds.itemAt(i) == pointerId) {
+            return i;
+        }
+    }
+    return -1;
+}
+
 void MotionEvent::offsetLocation(float xOffset, float yOffset) {
     mXOffset += xOffset;
     mYOffset += yOffset;
@@ -668,12 +678,27 @@ VelocityTracker::VelocityTracker() {
 void VelocityTracker::clear() {
     mIndex = 0;
     mMovements[0].idBits.clear();
+    mActivePointerId = -1;
+}
+
+void VelocityTracker::clearPointers(BitSet32 idBits) {
+    BitSet32 remainingIdBits(mMovements[mIndex].idBits.value & ~idBits.value);
+    mMovements[mIndex].idBits = remainingIdBits;
+
+    if (mActivePointerId >= 0 && idBits.hasBit(mActivePointerId)) {
+        mActivePointerId = !remainingIdBits.isEmpty() ? remainingIdBits.firstMarkedBit() : -1;
+    }
 }
 
 void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Position* positions) {
     if (++mIndex == HISTORY_SIZE) {
         mIndex = 0;
     }
+
+    while (idBits.count() > MAX_POINTERS) {
+        idBits.clearBit(idBits.lastMarkedBit());
+    }
+
     Movement& movement = mMovements[mIndex];
     movement.eventTime = eventTime;
     movement.idBits = idBits;
@@ -682,8 +707,13 @@ void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Posi
         movement.positions[i] = positions[i];
     }
 
+    if (mActivePointerId < 0 || !idBits.hasBit(mActivePointerId)) {
+        mActivePointerId = count != 0 ? idBits.firstMarkedBit() : -1;
+    }
+
 #if DEBUG_VELOCITY
-    LOGD("VelocityTracker: addMovement eventTime=%lld, idBits=0x%08x", eventTime, idBits.value);
+    LOGD("VelocityTracker: addMovement eventTime=%lld, idBits=0x%08x, activePointerId=%d",
+            eventTime, idBits.value, mActivePointerId);
     for (BitSet32 iterBits(idBits); !iterBits.isEmpty(); ) {
         uint32_t id = iterBits.firstMarkedBit();
         uint32_t index = idBits.getIndexOfBit(id);
@@ -691,7 +721,7 @@ void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Posi
         float vx, vy;
         bool available = getVelocity(id, &vx, &vy);
         if (available) {
-            LOGD("  %d: position (%0.3f, %0.3f), velocity (%0.3f, %0.3f), speed %0.3f",
+            LOGD("  %d: position (%0.3f, %0.3f), vx=%0.3f, vy=%0.3f, speed=%0.3f",
                     id, positions[index].x, positions[index].y, vx, vy, sqrtf(vx * vx + vy * vy));
         } else {
             assert(vx == 0 && vy == 0);
@@ -702,6 +732,70 @@ void VelocityTracker::addMovement(nsecs_t eventTime, BitSet32 idBits, const Posi
 #endif
 }
 
+void VelocityTracker::addMovement(const MotionEvent* event) {
+    int32_t actionMasked = event->getActionMasked();
+
+    switch (actionMasked) {
+    case AMOTION_EVENT_ACTION_DOWN:
+        // Clear all pointers on down before adding the new movement.
+        clear();
+        break;
+    case AMOTION_EVENT_ACTION_POINTER_DOWN: {
+        // Start a new movement trace for a pointer that just went down.
+        // We do this on down instead of on up because the client may want to query the
+        // final velocity for a pointer that just went up.
+        BitSet32 downIdBits;
+        downIdBits.markBit(event->getActionIndex());
+        clearPointers(downIdBits);
+        break;
+    }
+    case AMOTION_EVENT_ACTION_OUTSIDE:
+    case AMOTION_EVENT_ACTION_CANCEL:
+    case AMOTION_EVENT_ACTION_SCROLL:
+    case AMOTION_EVENT_ACTION_UP:
+    case AMOTION_EVENT_ACTION_POINTER_UP:
+        // Ignore these actions because they do not convey any new information about
+        // pointer movement.  We also want to preserve the last known velocity of the pointers.
+        // Note that ACTION_UP and ACTION_POINTER_UP always report the last known position
+        // of the pointers that went up.  ACTION_POINTER_UP does include the new position of
+        // pointers that remained down but we will also receive an ACTION_MOVE with this
+        // information if any of them actually moved.  Since we don't know how many pointers
+        // will be going up at once it makes sense to just wait for the following ACTION_MOVE
+        // before adding the movement.
+        return;
+    }
+
+    size_t pointerCount = event->getPointerCount();
+    if (pointerCount > MAX_POINTERS) {
+        pointerCount = MAX_POINTERS;
+    }
+
+    BitSet32 idBits;
+    for (size_t i = 0; i < pointerCount; i++) {
+        idBits.markBit(event->getPointerId(i));
+    }
+
+    nsecs_t eventTime;
+    Position positions[pointerCount];
+
+    size_t historySize = event->getHistorySize();
+    for (size_t h = 0; h < historySize; h++) {
+        eventTime = event->getHistoricalEventTime(h);
+        for (size_t i = 0; i < pointerCount; i++) {
+            positions[i].x = event->getHistoricalX(i, h);
+            positions[i].y = event->getHistoricalY(i, h);
+        }
+        addMovement(eventTime, idBits, positions);
+    }
+
+    eventTime = event->getEventTime();
+    for (size_t i = 0; i < pointerCount; i++) {
+        positions[i].x = event->getX(i);
+        positions[i].y = event->getY(i);
+    }
+    addMovement(eventTime, idBits, positions);
+}
+
 bool VelocityTracker::getVelocity(uint32_t id, float* outVx, float* outVy) const {
     const Movement& newestMovement = mMovements[mIndex];
     if (newestMovement.idBits.hasBit(id)) {
@@ -719,36 +813,17 @@ bool VelocityTracker::getVelocity(uint32_t id, float* outVx, float* outVy) const
             oldestIndex = nextOldestIndex;
         } while (++numTouches < HISTORY_SIZE);
 
-        // If we have a lot of samples, skip the last received sample since it is
-        // probably pretty noisy compared to the sum of all of the traces already acquired.
-        //
-        // NOTE: This condition exists in the android.view.VelocityTracker and imposes a
-        // bias against the most recent data.
-        if (numTouches > 3) {
-            numTouches -= 1;
-        }
-
-        // Calculate an exponentially weighted moving average of the velocity at different
-        // points in time measured relative to the oldest samples.  This is essentially
-        // an IIR filter.
+        // Calculate an exponentially weighted moving average of the velocity estimate
+        // at different points in time measured relative to the oldest sample.
+        // This is essentially an IIR filter.  Newer samples are weighted more heavily
+        // than older samples.  Samples at equal time points are weighted more or less
+        // equally.
         //
-        // One problem with this algorithm is that the sample data may be poorly conditioned.
+        // One tricky problem is that the sample data may be poorly conditioned.
         // Sometimes samples arrive very close together in time which can cause us to
         // overestimate the velocity at that time point.  Most samples might be measured
-        // 16ms apart but some consecutive samples could be only 0.5sm apart due to
-        // the way they are reported by the hardware or driver (sometimes in bursts or with
-        // significant jitter).  The instantaneous velocity for those samples 0.5ms apart will
-        // be calculated to be 32 times what it should have been.
-        // To work around this effect, we impose a minimum duration on the samples.
-        //
-        // FIXME: Samples close together in time can have an disproportionately large
-        // impact on the result because all samples are equally weighted.  The average should
-        // instead take the time factor into account.
-        //
-        // FIXME: The minimum duration condition does not exist in
-        // android.view.VelocityTracker yet.  It is less important there because sample times
-        // are truncated to the millisecond so back to back samples will often appear to be
-        // zero milliseconds apart and will be ignored if they are the oldest ones.
+        // 16ms apart but some consecutive samples could be only 0.5sm apart because
+        // the hardware or driver reports them irregularly or in bursts.
         float accumVx = 0;
         float accumVy = 0;
         uint32_t index = oldestIndex;
@@ -756,19 +831,27 @@ bool VelocityTracker::getVelocity(uint32_t id, float* outVx, float* outVy) const
         const Movement& oldestMovement = mMovements[oldestIndex];
         const Position& oldestPosition =
                 oldestMovement.positions[oldestMovement.idBits.getIndexOfBit(id)];
+        nsecs_t lastDuration = 0;
         while (numTouches-- > 1) {
             if (++index == HISTORY_SIZE) {
                 index = 0;
             }
             const Movement& movement = mMovements[index];
             nsecs_t duration = movement.eventTime - oldestMovement.eventTime;
-            if (duration > MIN_DURATION) {
+
+            // If the duration between samples is small, we may significantly overestimate
+            // the velocity.  Consequently, we impose a minimum duration constraint on the
+            // samples that we include in the calculation.
+            if (duration >= MIN_DURATION) {
                 const Position& position = movement.positions[movement.idBits.getIndexOfBit(id)];
                 float scale = 1000000000.0f / duration; // one over time delta in seconds
                 float vx = (position.x - oldestPosition.x) * scale;
                 float vy = (position.y - oldestPosition.y) * scale;
-                accumVx = accumVx == 0 ? vx : (accumVx + vx) * 0.5f;
-                accumVy = accumVy == 0 ? vy : (accumVy + vy) * 0.5f;
+
+                accumVx = (accumVx * lastDuration + vx * duration) / (duration + lastDuration);
+                accumVy = (accumVy * lastDuration + vy * duration) / (duration + lastDuration);
+
+                lastDuration = duration;
                 samplesUsed += 1;
             }
         }
diff --git a/services/jni/com_android_server_InputManager.cpp b/services/jni/com_android_server_InputManager.cpp
index 31d0732..e7e1fa2 100644
--- a/services/jni/com_android_server_InputManager.cpp
+++ b/services/jni/com_android_server_InputManager.cpp
@@ -1018,15 +1018,14 @@ static jint android_server_InputManager_nativeInjectInputEvent(JNIEnv* env, jcla
         return gNativeInputManager->getInputManager()->getDispatcher()->injectInputEvent(
                 & keyEvent, injectorPid, injectorUid, syncMode, timeoutMillis);
     } else if (env->IsInstanceOf(inputEventObj, gMotionEventClassInfo.clazz)) {
-        MotionEvent motionEvent;
-        status_t status = android_view_MotionEvent_toNative(env, inputEventObj, & motionEvent);
-        if (status) {
+        const MotionEvent* motionEvent = android_view_MotionEvent_getNativePtr(env, inputEventObj);
+        if (!motionEvent) {
             jniThrowRuntimeException(env, "Could not read contents of MotionEvent object.");
             return INPUT_EVENT_INJECTION_FAILED;
         }
 
         return gNativeInputManager->getInputManager()->getDispatcher()->injectInputEvent(
-                & motionEvent, injectorPid, injectorUid, syncMode, timeoutMillis);
+                motionEvent, injectorPid, injectorUid, syncMode, timeoutMillis);
     } else {
         jniThrowRuntimeException(env, "Invalid input event type.");
         return INPUT_EVENT_INJECTION_FAILED;
diff --git a/tools/velocityplot/velocityplot.py b/tools/velocityplot/velocityplot.py
new file mode 100755
index 0000000..421bed4
--- /dev/null
+++ b/tools/velocityplot/velocityplot.py
@@ -0,0 +1,289 @@
+#!/usr/bin/env python2.6
+#
+# Copyright (C) 2011 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+#
+# Plots debug log output from VelocityTracker.
+# Enable DEBUG_VELOCITY to print the output.
+#
+# This code supports side-by-side comparison of two algorithms.
+# The old algorithm should be modified to emit debug log messages containing
+# the word "OLD".
+#
+
+import numpy as np
+import matplotlib.pyplot as plot
+import subprocess
+import re
+import fcntl
+import os
+import errno
+import bisect
+from datetime import datetime, timedelta
+
+# Parameters.
+timespan = 15 # seconds total span shown
+scrolljump = 5 # seconds jump when scrolling
+timeticks = 1 # seconds between each time tick
+
+# Non-blocking stream wrapper.
+class NonBlockingStream:
+  def __init__(self, stream):
+    fcntl.fcntl(stream, fcntl.F_SETFL, os.O_NONBLOCK)
+    self.stream = stream
+    self.buffer = ''
+    self.pos = 0
+
+  def readline(self):
+    while True:
+      index = self.buffer.find('\n', self.pos)
+      if index != -1:
+        result = self.buffer[self.pos:index]
+        self.pos = index + 1
+        return result
+
+      self.buffer = self.buffer[self.pos:]
+      self.pos = 0
+      try:
+        chunk = os.read(self.stream.fileno(), 4096)
+      except OSError, e:
+        if e.errno == errno.EAGAIN:
+          return None
+        raise e
+      if len(chunk) == 0:
+        if len(self.buffer) == 0:
+          raise(EOFError)
+        else:
+          result = self.buffer
+          self.buffer = ''
+          self.pos = 0
+          return result
+      self.buffer += chunk
+
+# Plotter
+class Plotter:
+  def __init__(self, adbout):
+    self.adbout = adbout
+
+    self.fig = plot.figure(1)
+    self.fig.suptitle('Velocity Tracker', fontsize=12)
+    self.fig.set_dpi(96)
+    self.fig.set_size_inches(16, 12, forward=True)
+
+    self.velocity_x = self._make_timeseries()
+    self.velocity_y = self._make_timeseries()
+    self.velocity_magnitude = self._make_timeseries()
+    self.velocity_axes = self._add_timeseries_axes(
+        1, 'Velocity', 'px/s', [-5000, 5000],
+        yticks=range(-5000, 5000, 1000))
+    self.velocity_line_x = self._add_timeseries_line(
+        self.velocity_axes, 'vx', 'red')
+    self.velocity_line_y = self._add_timeseries_line(
+        self.velocity_axes, 'vy', 'green')
+    self.velocity_line_magnitude = self._add_timeseries_line(
+        self.velocity_axes, 'magnitude', 'blue')
+    self._add_timeseries_legend(self.velocity_axes)
+
+    shared_axis = self.velocity_axes
+
+    self.old_velocity_x = self._make_timeseries()
+    self.old_velocity_y = self._make_timeseries()
+    self.old_velocity_magnitude = self._make_timeseries()
+    self.old_velocity_axes = self._add_timeseries_axes(
+        2, 'Old Algorithm Velocity', 'px/s', [-5000, 5000],
+        sharex=shared_axis,
+        yticks=range(-5000, 5000, 1000))
+    self.old_velocity_line_x = self._add_timeseries_line(
+        self.old_velocity_axes, 'vx', 'red')
+    self.old_velocity_line_y = self._add_timeseries_line(
+        self.old_velocity_axes, 'vy', 'green')
+    self.old_velocity_line_magnitude = self._add_timeseries_line(
+        self.old_velocity_axes, 'magnitude', 'blue')
+    self._add_timeseries_legend(self.old_velocity_axes)
+
+    self.timer = self.fig.canvas.new_timer(interval=100)
+    self.timer.add_callback(lambda: self.update())
+    self.timer.start()
+
+    self.timebase = None
+    self._reset_parse_state()
+
+  # Initialize a time series.
+  def _make_timeseries(self):
+    return [[], []]
+
+  # Add a subplot to the figure for a time series.
+  def _add_timeseries_axes(self, index, title, ylabel, ylim, yticks, sharex=None):
+    num_graphs = 2
+    height = 0.9 / num_graphs
+    top = 0.95 - height * index
+    axes = self.fig.add_axes([0.1, top, 0.8, height],
+        xscale='linear',
+        xlim=[0, timespan],
+        ylabel=ylabel,
+        yscale='linear',
+        ylim=ylim,
+        sharex=sharex)
+    axes.text(0.02, 0.02, title, transform=axes.transAxes, fontsize=10, fontweight='bold')
+    axes.set_xlabel('time (s)', fontsize=10, fontweight='bold')
+    axes.set_ylabel(ylabel, fontsize=10, fontweight='bold')
+    axes.set_xticks(range(0, timespan + 1, timeticks))
+    axes.set_yticks(yticks)
+    axes.grid(True)
+
+    for label in axes.get_xticklabels():
+      label.set_fontsize(9)
+    for label in axes.get_yticklabels():
+      label.set_fontsize(9)
+
+    return axes
+
+  # Add a line to the axes for a time series.
+  def _add_timeseries_line(self, axes, label, color, linewidth=1):
+    return axes.plot([], label=label, color=color, linewidth=linewidth)[0]
+
+  # Add a legend to a time series.
+  def _add_timeseries_legend(self, axes):
+    axes.legend(
+        loc='upper left',
+        bbox_to_anchor=(1.01, 1),
+        borderpad=0.1,
+        borderaxespad=0.1,
+        prop={'size': 10})
+
+  # Resets the parse state.
+  def _reset_parse_state(self):
+    self.parse_velocity_x = None
+    self.parse_velocity_y = None
+    self.parse_velocity_magnitude = None
+    self.parse_old_velocity_x = None
+    self.parse_old_velocity_y = None
+    self.parse_old_velocity_magnitude = None
+
+  # Update samples.
+  def update(self):
+    timeindex = 0
+    while True:
+      try:
+        line = self.adbout.readline()
+      except EOFError:
+        plot.close()
+        return
+      if line is None:
+        break
+      print line
+
+      try:
+        timestamp = self._parse_timestamp(line)
+      except ValueError, e:
+        continue
+      if self.timebase is None:
+        self.timebase = timestamp
+      delta = timestamp - self.timebase
+      timeindex = delta.seconds + delta.microseconds * 0.000001
+
+      if line.find(': position') != -1:
+        self.parse_velocity_x = self._get_following_number(line, 'vx=')
+        self.parse_velocity_y = self._get_following_number(line, 'vy=')
+        self.parse_velocity_magnitude = self._get_following_number(line, 'speed=')
+        self._append(self.velocity_x, timeindex, self.parse_velocity_x)
+        self._append(self.velocity_y, timeindex, self.parse_velocity_y)
+        self._append(self.velocity_magnitude, timeindex, self.parse_velocity_magnitude)
+
+      if line.find(': OLD') != -1:
+        self.parse_old_velocity_x = self._get_following_number(line, 'vx=')
+        self.parse_old_velocity_y = self._get_following_number(line, 'vy=')
+        self.parse_old_velocity_magnitude = self._get_following_number(line, 'speed=')
+        self._append(self.old_velocity_x, timeindex, self.parse_old_velocity_x)
+        self._append(self.old_velocity_y, timeindex, self.parse_old_velocity_y)
+        self._append(self.old_velocity_magnitude, timeindex, self.parse_old_velocity_magnitude)
+
+    # Scroll the plots.
+    if timeindex > timespan:
+      bottom = int(timeindex) - timespan + scrolljump
+      self.timebase += timedelta(seconds=bottom)
+      self._scroll(self.velocity_x, bottom)
+      self._scroll(self.velocity_y, bottom)
+      self._scroll(self.velocity_magnitude, bottom)
+      self._scroll(self.old_velocity_x, bottom)
+      self._scroll(self.old_velocity_y, bottom)
+      self._scroll(self.old_velocity_magnitude, bottom)
+
+    # Redraw the plots.
+    self.velocity_line_x.set_data(self.velocity_x)
+    self.velocity_line_y.set_data(self.velocity_y)
+    self.velocity_line_magnitude.set_data(self.velocity_magnitude)
+    self.old_velocity_line_x.set_data(self.old_velocity_x)
+    self.old_velocity_line_y.set_data(self.old_velocity_y)
+    self.old_velocity_line_magnitude.set_data(self.old_velocity_magnitude)
+
+    self.fig.canvas.draw_idle()
+
+  # Scroll a time series.
+  def _scroll(self, timeseries, bottom):
+    bottom_index = bisect.bisect_left(timeseries[0], bottom)
+    del timeseries[0][:bottom_index]
+    del timeseries[1][:bottom_index]
+    for i, timeindex in enumerate(timeseries[0]):
+      timeseries[0][i] = timeindex - bottom
+
+  # Extract a word following the specified prefix.
+  def _get_following_word(self, line, prefix):
+    prefix_index = line.find(prefix)
+    if prefix_index == -1:
+      return None
+    start_index = prefix_index + len(prefix)
+    delim_index = line.find(',', start_index)
+    if delim_index == -1:
+      return line[start_index:]
+    else:
+      return line[start_index:delim_index]
+
+  # Extract a number following the specified prefix.
+  def _get_following_number(self, line, prefix):
+    word = self._get_following_word(line, prefix)
+    if word is None:
+      return None
+    return float(word)
+
+  # Add a value to a time series.
+  def _append(self, timeseries, timeindex, number):
+    timeseries[0].append(timeindex)
+    timeseries[1].append(number)
+
+  # Parse the logcat timestamp.
+  # Timestamp has the form '01-21 20:42:42.930'
+  def _parse_timestamp(self, line):
+    return datetime.strptime(line[0:18], '%m-%d %H:%M:%S.%f')
+
+# Notice
+print "Velocity Tracker plotting tool"
+print "-----------------------------------------\n"
+print "Please enable debug logging and recompile the code."
+
+# Start adb.
+print "Starting adb logcat.\n"
+
+adb = subprocess.Popen(['adb', 'logcat', '-s', '-v', 'time', 'Input:*', 'VelocityTracker:*'],
+    stdout=subprocess.PIPE)
+adbout = NonBlockingStream(adb.stdout)
+
+# Prepare plotter.
+plotter = Plotter(adbout)
+plotter.update()
+
+# Main loop.
+plot.show()