am 16330e24: am 94e838f6: Merge "Improve VelocityTracker numerical stability. (DO NOT MERGE)" into honeycomb-mr2

* commit '16330e249663fed890df0e95fce4016c2971120a':
  Improve VelocityTracker numerical stability. (DO NOT MERGE)

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 dda5a81..fb65743 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 97cba23..0840cf8 100644
--- a/core/jni/android_view_MotionEvent.cpp
+++ b/core/jni/android_view_MotionEvent.cpp
@@ -59,7 +59,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));
 }
@@ -70,10 +73,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();
@@ -90,18 +93,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()) {
@@ -502,13 +493,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 55f73ac..1ef36d0 100644
--- a/include/ui/Input.h
+++ b/include/ui/Input.h
@@ -313,6 +313,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; }
@@ -460,6 +467,8 @@ public:
                 AMOTION_EVENT_AXIS_ORIENTATION, pointerIndex, historicalIndex);
     }
 
+    ssize_t findPointerIndex(int32_t pointerId) const;
+
     void initialize(
             int32_t deviceId,
             int32_t source,
@@ -553,8 +562,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:
@@ -567,6 +575,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.
@@ -574,11 +587,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;
@@ -587,7 +609,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;
@@ -597,6 +619,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 0f13879..0a53d69 100644
--- a/libs/ui/Input.cpp
+++ b/libs/ui/Input.cpp
@@ -483,6 +483,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;
@@ -667,12 +677,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;
@@ -681,8 +706,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);
@@ -690,7 +720,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);
@@ -701,6 +731,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)) {
@@ -718,36 +812,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.
+        // 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.
         //
-        // 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.
-        //
-        // 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;
@@ -755,19 +830,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 80dddc2..a86b5bd 100644
--- a/services/jni/com_android_server_InputManager.cpp
+++ b/services/jni/com_android_server_InputManager.cpp
@@ -1024,15 +1024,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()