Event smoothing in CrOS gesture recognizer.

Each GesturePoint owns a VelocityCalculator, which maintains a history
of touch positions and times, and gives the GesturePoint its velocity.

An ordinary least squares regression is used to calculate the velocities.

BUG=110229
TEST=aura_unittests


Review URL: http://codereview.chromium.org/9310031

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@120835 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 334 insertions, 23 deletions

diff --git a/ui/aura/aura.gyp b/ui/aura/aura.gyp
index 8c4bc99..3f7f944 100644
--- a/ui/aura/aura.gyp
+++ b/ui/aura/aura.gyp
@@ -62,6 +62,8 @@
         'gestures/gesture_recognizer_aura.h',
         'gestures/gesture_point.cc',
         'gestures/gesture_point.h',
+        'gestures/velocity_calculator.cc',
+        'gestures/velocity_calculator.h',
         'gestures/gesture_sequence.cc',
         'gestures/gesture_sequence.h',
         'layout_manager.cc',
@@ -160,6 +162,7 @@
       ],
       'sources': [
         'gestures/gesture_recognizer_unittest.cc',
+        'gestures/velocity_calculator_unittest.cc',
         'test/run_all_unittests.cc',
         'test/test_suite.cc',
         'test/test_suite.h',
diff --git a/ui/aura/gestures/gesture_point.cc b/ui/aura/gestures/gesture_point.cc
index 3402e56..4d5b4d6 100644
--- a/ui/aura/gestures/gesture_point.cc
+++ b/ui/aura/gestures/gesture_point.cc
@@ -4,6 +4,7 @@
 
 #include "ui/aura/gestures/gesture_point.h"
 
+#include "base/basictypes.h"
 #include "ui/aura/event.h"
 #include "ui/base/events.h"
 
@@ -16,8 +17,9 @@ const double kMinimumTouchDownDurationInSecondsForClick = 0.01;
 const double kMaximumSecondsBetweenDoubleClick = 0.7;
 const int kMaximumTouchMoveInPixelsForClick = 20;
 const float kMinFlickSpeedSquared = 550.f * 550.f;
+const int kBufferedPoints = 10;
 
-}  // namespace aura
+}  // namespace
 
 namespace aura {
 
@@ -25,20 +27,21 @@ GesturePoint::GesturePoint()
     : first_touch_time_(0.0),
       last_touch_time_(0.0),
       last_tap_time_(0.0),
-      x_velocity_(0.0),
-      y_velocity_(0.0) {
+      velocity_calculator_(kBufferedPoints) {
 }
 
 void GesturePoint::Reset() {
   first_touch_time_ = last_touch_time_ = 0.0;
-  x_velocity_ = y_velocity_ = 0.0;
+  velocity_calculator_.ClearHistory();
 }
 
 void GesturePoint::UpdateValues(const TouchEvent& event, GestureState state) {
+  const int64 event_timestamp_microseconds =
+    event.time_stamp().InMicroseconds();
   if (state != GS_NO_GESTURE && event.type() == ui::ET_TOUCH_MOVED) {
-    double interval(event.time_stamp().InSecondsF() - last_touch_time_);
-    x_velocity_ = (event.x() - last_touch_position_.x()) / interval;
-    y_velocity_ = (event.y() - last_touch_position_.y()) / interval;
+    velocity_calculator_.PointSeen(event.x(),
+                                   event.y(),
+                                   event_timestamp_microseconds);
   }
 
   last_touch_time_ = event.time_stamp().InSecondsF();
@@ -47,8 +50,10 @@ void GesturePoint::UpdateValues(const TouchEvent& event, GestureState state) {
   if (state == GS_NO_GESTURE) {
     first_touch_time_ = last_touch_time_;
     first_touch_position_ = event.location();
-    x_velocity_ = 0.0;
-    y_velocity_ = 0.0;
+    velocity_calculator_.ClearHistory();
+    velocity_calculator_.PointSeen(event.x(),
+                                   event.y(),
+                                   event_timestamp_microseconds);
   }
 }
 
@@ -81,7 +86,7 @@ bool GesturePoint::IsInScrollWindow(const TouchEvent& event) const {
          !IsInsideManhattanSquare(event);
 }
 
-bool GesturePoint::IsInFlickWindow(const TouchEvent& event) const {
+bool GesturePoint::IsInFlickWindow(const TouchEvent& event) {
   return IsOverMinFlickSpeed() && event.type() != ui::ET_TOUCH_CANCELLED;
 }
 
@@ -114,9 +119,8 @@ bool GesturePoint::IsSecondClickInsideManhattanSquare(
   return manhattanDistance < kMaximumTouchMoveInPixelsForClick;
 }
 
-bool GesturePoint::IsOverMinFlickSpeed() const {
-  return (x_velocity_ * x_velocity_ + y_velocity_ * y_velocity_) >
-          kMinFlickSpeedSquared;
+bool GesturePoint::IsOverMinFlickSpeed() {
+  return velocity_calculator_.VelocitySquared() > kMinFlickSpeedSquared;
 }
 
 }  // namespace aura
diff --git a/ui/aura/gestures/gesture_point.h b/ui/aura/gestures/gesture_point.h
index f39d252..ff715ea 100644
--- a/ui/aura/gestures/gesture_point.h
+++ b/ui/aura/gestures/gesture_point.h
@@ -7,6 +7,7 @@
 #pragma once
 
 #include "base/basictypes.h"
+#include "ui/aura/gestures/velocity_calculator.h"
 #include "ui/gfx/point.h"
 
 namespace aura {
@@ -44,7 +45,7 @@ class GesturePoint {
   bool IsInClickWindow(const TouchEvent& event) const;
   bool IsInDoubleClickWindow(const TouchEvent& event) const;
   bool IsInScrollWindow(const TouchEvent& event) const;
-  bool IsInFlickWindow(const TouchEvent& event) const;
+  bool IsInFlickWindow(const TouchEvent& event);
   bool DidScroll(const TouchEvent& event) const;
 
   const gfx::Point& first_touch_position() const {
@@ -62,8 +63,8 @@ class GesturePoint {
     return last_touch_position_.y() - first_touch_position_.y();
   }
 
-  float x_velocity() const { return x_velocity_; }
-  float y_velocity() const { return y_velocity_; }
+  float XVelocity() { return velocity_calculator_.XVelocity(); }
+  float YVelocity() { return velocity_calculator_.YVelocity(); }
 
  private:
   // Various statistical functions to manipulate gestures.
@@ -71,7 +72,7 @@ class GesturePoint {
   bool IsInSecondClickTimeWindow() const;
   bool IsInsideManhattanSquare(const TouchEvent& event) const;
   bool IsSecondClickInsideManhattanSquare(const TouchEvent& event) const;
-  bool IsOverMinFlickSpeed() const;
+  bool IsOverMinFlickSpeed();
 
   gfx::Point first_touch_position_;
   double first_touch_time_;
@@ -81,8 +82,7 @@ class GesturePoint {
   double last_tap_time_;
   gfx::Point last_tap_position_;
 
-  float x_velocity_;
-  float y_velocity_;
+  VelocityCalculator velocity_calculator_;
 
   DISALLOW_COPY_AND_ASSIGN(GesturePoint);
 };
diff --git a/ui/aura/gestures/gesture_sequence.cc b/ui/aura/gestures/gesture_sequence.cc
index 630a9fb..5c4e327 100644
--- a/ui/aura/gestures/gesture_sequence.cc
+++ b/ui/aura/gestures/gesture_sequence.cc
@@ -239,10 +239,10 @@ bool GestureSequence::TouchDown(const TouchEvent& event,
 }
 
 bool GestureSequence::ScrollEnd(const TouchEvent& event,
-    const GesturePoint& point, Gestures* gestures) {
+    GesturePoint& point, Gestures* gestures) {
   if (point.IsInFlickWindow(event))
-    AppendScrollGestureEnd(point, gestures, point.x_velocity(),
-        point.y_velocity());
+    AppendScrollGestureEnd(point, gestures, point.XVelocity(),
+        point.YVelocity());
   else
     AppendScrollGestureEnd(point, gestures, 0.f, 0.f);
   Reset();
diff --git a/ui/aura/gestures/gesture_sequence.h b/ui/aura/gestures/gesture_sequence.h
index 05bba2d..c758def 100644
--- a/ui/aura/gestures/gesture_sequence.h
+++ b/ui/aura/gestures/gesture_sequence.h
@@ -122,7 +122,7 @@ class GestureSequence {
                  const GesturePoint& point,
                  Gestures* gestures);
   bool ScrollEnd(const TouchEvent& event,
-                 const GesturePoint& point,
+                 GesturePoint& point,
                  Gestures* gestures);
 
   // Current state of gesture recognizer.
diff --git a/ui/aura/gestures/velocity_calculator.cc b/ui/aura/gestures/velocity_calculator.cc
new file mode 100644
index 0000000..696c424
--- /dev/null
+++ b/ui/aura/gestures/velocity_calculator.cc
@@ -0,0 +1,107 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "ui/aura/gestures/velocity_calculator.h"
+
+namespace aura {
+
+VelocityCalculator::VelocityCalculator(int buffer_size)
+    : buffer_(new Point[buffer_size]) ,
+      index_(0),
+      num_valid_entries_(0),
+      buffer_size_(buffer_size),
+      x_velocity_(0),
+      y_velocity_(0),
+      velocities_stale_(false) {
+}
+
+float VelocityCalculator::XVelocity() {
+  if (velocities_stale_)
+    UpdateVelocity();
+  return x_velocity_;
+}
+
+float VelocityCalculator::YVelocity() {
+  if (velocities_stale_)
+    UpdateVelocity();
+  return y_velocity_;
+}
+
+void VelocityCalculator::PointSeen(int x, int y, int64 time) {
+  buffer_[index_].x = x;
+  buffer_[index_].y = y;
+  buffer_[index_].time = time;
+
+  index_ = (index_ + 1) % buffer_size_;
+  if (num_valid_entries_ < buffer_size_)
+    ++num_valid_entries_;
+
+  velocities_stale_ = true;
+}
+
+float VelocityCalculator::VelocitySquared() {
+  if (velocities_stale_)
+    UpdateVelocity();
+  return x_velocity_ * x_velocity_ + y_velocity_ * y_velocity_;
+}
+
+void VelocityCalculator::UpdateVelocity() {
+  // We don't have enough data to make a good estimate of the velocity.
+  if (num_valid_entries_ < buffer_size_)
+    return;
+
+  // Where A_i = A[i] - mean(A)
+  // x velocity = sum_i(x_i * t_i) / sum_i(t_i * t_i)
+  // This is an Ordinary Least Squares Regression.
+
+  float mean_x = 0;
+  float mean_y = 0;
+  int64 mean_time = 0;
+
+  for (size_t i = 0; i < buffer_size_; ++i) {
+    mean_x += buffer_[i].x;
+    mean_y += buffer_[i].y;
+    mean_time += buffer_[i].time;
+  }
+
+  // Minimize number of divides.
+  const float buffer_size_i = 1.0f / buffer_size_;
+
+  mean_x *= buffer_size_i;
+  mean_y *= buffer_size_i;
+
+  // The loss in accuracy due to rounding is insignificant compared to
+  // the error due to the resolution of the timer.
+  // Use integer division to avoid the cast to double, which would cause
+  // VelocityCalculatorTest.IsAccurateWithLargeTimes to fail.
+  mean_time /= buffer_size_;
+
+  float xt = 0;  // sum_i(x_i * t_i)
+  float yt = 0;  // sum_i(y_i * t_i)
+  int64 tt = 0;  // sum_i(t_i * t_i)
+
+  int64 t_i;
+
+  for (size_t i = 0; i < buffer_size_; ++i) {
+    t_i = (buffer_[i].time - mean_time);
+    xt += (buffer_[i].x - mean_x) * t_i;
+    yt += (buffer_[i].y - mean_y) * t_i;
+    tt += t_i * t_i;
+  }
+
+  // Convert time from microseconds to seconds.
+  x_velocity_ = xt / (tt / 1000000.0f);
+  y_velocity_ = yt / (tt / 1000000.0f);
+  velocities_stale_ = false;
+}
+
+void VelocityCalculator::ClearHistory() {
+  index_ = 0;
+  num_valid_entries_ = 0;
+  x_velocity_ = 0;
+  y_velocity_ = 0;
+  velocities_stale_ = false;
+}
+
+}  // namespace aura
diff --git a/ui/aura/gestures/velocity_calculator.h b/ui/aura/gestures/velocity_calculator.h
new file mode 100644
index 0000000..80b0c19
--- /dev/null
+++ b/ui/aura/gestures/velocity_calculator.h
@@ -0,0 +1,51 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef UI_AURA_GESTURES_VELOCITY_CALCULATOR_H_
+#define UI_AURA_GESTURES_VELOCITY_CALCULATOR_H_
+#pragma once
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/memory/scoped_ptr.h"
+#include "ui/aura/aura_export.h"
+
+namespace aura {
+
+class AURA_EXPORT VelocityCalculator {
+ public:
+  explicit VelocityCalculator(int bufferSize);
+  ~VelocityCalculator() {}
+  void PointSeen(int x, int y, int64 time);
+  float XVelocity();
+  float YVelocity();
+  float VelocitySquared();
+  void ClearHistory();
+
+ private:
+  struct Point {
+    int x;
+    int y;
+    int64 time;
+  };
+
+  void UpdateVelocity();
+
+  typedef scoped_array<Point> HistoryBuffer;
+  HistoryBuffer buffer_;
+
+  // index_ points directly after the last point added.
+  int index_;
+  size_t num_valid_entries_;
+  const size_t buffer_size_;
+  float x_velocity_;
+  float y_velocity_;
+  bool velocities_stale_;
+  DISALLOW_COPY_AND_ASSIGN(VelocityCalculator);
+};
+
+}  // namespace aura
+
+#endif  // UI_AURA_GESTURES_VELOCITY_CALCULATOR_H_
diff --git a/ui/aura/gestures/velocity_calculator_unittest.cc b/ui/aura/gestures/velocity_calculator_unittest.cc
new file mode 100644
index 0000000..26bad46
--- /dev/null
+++ b/ui/aura/gestures/velocity_calculator_unittest.cc
@@ -0,0 +1,146 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/basictypes.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "ui/aura/gestures/velocity_calculator.h"
+#include "ui/aura/test/aura_test_base.h"
+
+namespace aura {
+namespace test {
+
+namespace {
+
+static void AddPoints(VelocityCalculator* velocity_calculator,
+                      float x_increment,
+                      float y_increment,
+                      float time_increment_seconds,
+                      int num_points) {
+  float x = 0;
+  float y = 0;
+  double time = 0;
+
+  for (int i = 0; i < num_points; ++i) {
+    velocity_calculator->PointSeen(x, y, time);
+    x += x_increment;
+    y += y_increment;
+    time += time_increment_seconds * 1000000;
+  }
+}
+
+}  // namespace
+
+typedef AuraTestBase VelocityCalculatorTest;
+
+// Test that the velocity returned is reasonable
+TEST_F(VelocityCalculatorTest, ReturnsReasonableVelocity) {
+  VelocityCalculator velocity_calculator(5);
+  AddPoints(&velocity_calculator, 10, -10, 1, 7);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 9.9);
+  EXPECT_LT(velocity_calculator.XVelocity(), 10.1);
+  EXPECT_GT(velocity_calculator.YVelocity(), -10.1);
+  EXPECT_LT(velocity_calculator.YVelocity(), -9.9);
+
+  velocity_calculator.PointSeen(9, -11, 5500000);
+  velocity_calculator.PointSeen(21, -19, 6000000);
+  velocity_calculator.PointSeen(30, -32, 6500000);
+  velocity_calculator.PointSeen(38, -40, 7000000);
+  velocity_calculator.PointSeen(50, -51, 7500000);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 19);
+  EXPECT_LT(velocity_calculator.XVelocity(), 21);
+  EXPECT_GT(velocity_calculator.YVelocity(), -21);
+  EXPECT_LT(velocity_calculator.YVelocity(), -19);
+
+  // Significantly larger difference in position
+  velocity_calculator.PointSeen(70, -70, 8000000);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 20);
+  EXPECT_LT(velocity_calculator.XVelocity(), 25);
+  EXPECT_GT(velocity_calculator.YVelocity(), -25);
+  EXPECT_LT(velocity_calculator.YVelocity(), -20);
+}
+
+TEST_F(VelocityCalculatorTest, IsAccurateWithLargeTimes) {
+  VelocityCalculator velocity_calculator(5);
+  int64 start_time = 0;
+  velocity_calculator.PointSeen(9, -11, start_time);
+  velocity_calculator.PointSeen(21, -19, start_time + 8);
+  velocity_calculator.PointSeen(30, -32, start_time + 16);
+  velocity_calculator.PointSeen(38, -40, start_time + 24);
+  velocity_calculator.PointSeen(50, -51, start_time + 32);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 1230000);
+  EXPECT_LT(velocity_calculator.XVelocity(), 1260000);
+  EXPECT_GT(velocity_calculator.YVelocity(), -1270000);
+  EXPECT_LT(velocity_calculator.YVelocity(), -1240000);
+
+  start_time = 1223372036800000000;
+  velocity_calculator.PointSeen(9, -11, start_time);
+  velocity_calculator.PointSeen(21, -19, start_time + 8);
+  velocity_calculator.PointSeen(30, -32, start_time + 16);
+  velocity_calculator.PointSeen(38, -40, start_time + 24);
+  velocity_calculator.PointSeen(50, -51, start_time + 32);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 1230000);
+  EXPECT_LT(velocity_calculator.XVelocity(), 1260000);
+  EXPECT_GT(velocity_calculator.YVelocity(), -1270000);
+  EXPECT_LT(velocity_calculator.YVelocity(), -124000);
+}
+
+// Check that the velocity returned is 0 if the velocity calculator
+// doesn't have enough data
+TEST_F(VelocityCalculatorTest, RequiresEnoughData) {
+  VelocityCalculator velocity_calculator(5);
+  EXPECT_EQ(velocity_calculator.XVelocity(), 0);
+  EXPECT_EQ(velocity_calculator.YVelocity(), 0);
+
+  AddPoints(&velocity_calculator, 10, 10, 1, 4);
+
+  // We've only seen 4 points, the buffer size is 5
+  // Since the buffer isn't full, return 0
+  EXPECT_EQ(velocity_calculator.XVelocity(), 0);
+  EXPECT_EQ(velocity_calculator.YVelocity(), 0);
+
+  AddPoints(&velocity_calculator, 10, 10, 1, 1);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 9.9);
+  EXPECT_GT(velocity_calculator.YVelocity(), 9.9);
+}
+
+// Ensures ClearHistory behaves correctly
+TEST_F(VelocityCalculatorTest, ClearsHistory) {
+  VelocityCalculator velocity_calculator(5);
+  AddPoints(&velocity_calculator, 10, -10, 1, 7);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 9.9);
+  EXPECT_LT(velocity_calculator.XVelocity(), 10.1);
+  EXPECT_GT(velocity_calculator.YVelocity(), -10.1);
+  EXPECT_LT(velocity_calculator.YVelocity(), -9.9);
+
+  velocity_calculator.ClearHistory();
+
+  EXPECT_EQ(velocity_calculator.XVelocity(), 0);
+  EXPECT_EQ(velocity_calculator.YVelocity(), 0);
+}
+
+// Ensure data older than the buffer size is ignored
+TEST_F(VelocityCalculatorTest, IgnoresOldData) {
+  VelocityCalculator velocity_calculator(5);
+  AddPoints(&velocity_calculator, 10, -10, 1, 7);
+
+  EXPECT_GT(velocity_calculator.XVelocity(), 9.9);
+  EXPECT_LT(velocity_calculator.XVelocity(), 10.1);
+  EXPECT_GT(velocity_calculator.YVelocity(), -10.1);
+  EXPECT_LT(velocity_calculator.YVelocity(), -9.9);
+
+  AddPoints(&velocity_calculator, 0, 0, 1, 5);
+
+  EXPECT_EQ(velocity_calculator.XVelocity(), 0);
+  EXPECT_EQ(velocity_calculator.YVelocity(), 0);
+}
+
+}  // namespace test
+}  // namespace aura