Event smoothing in CrOS gesture recognizer.

ui/aura/gestures/velocity_calculator.cc

Index: ui/aura/gestures/velocity_calculator.cc
diff --git a/ui/aura/gestures/velocity_calculator.cc b/ui/aura/gestures/velocity_calculator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..5d5720f60fac05b5d4ef39c6937725af7e889d30
--- /dev/null
+++ b/ui/aura/gestures/velocity_calculator.cc
@@ -0,0 +1,74 @@
+// 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)
+    : index_(0)
+    , num_valid_entries_(0)
+    , buffer_size_(buffer_size) {
+  buffer_.reserve(buffer_size);
+}
+
+VelocityCalculator::~VelocityCalculator() {
+}
+
+void VelocityCalculator::PointSeen(float x, float y, double 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_;
+}
+
+void VelocityCalculator::Velocity(float* x, float* y) {
+  // We don't have enough data to make a good estimate of the velocity.
+  if (num_valid_entries_ < buffer_size_) {
+    *x = 0;
+    *y = 0;
+    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;
+  float 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;
+  }
+
+  mean_x /= buffer_size_;
+  mean_y /= buffer_size_;
+  mean_time /= buffer_size_;
+
+  float xt = 0;  // sum_i(x_i * t_i)
+  float yt = 0;  // sum_i(y_i * t_i)
+  float tt = 0;  // sum_i(t_i * t_i)

[rjkroege, 2012/02/02 15:58:37]

you are using doubles somewhere else. and here, you use a float. either you need
all the bits... or you don't. :-)

+
+  for (size_t i = 0; i < buffer_size_; ++i) {
+    xt += (buffer_[i].x - mean_x) * (buffer_[i].time - mean_time);
+    yt += (buffer_[i].y - mean_y) * (buffer_[i].time - mean_time);
+    tt += (buffer_[i].time - mean_time) * (buffer_[i].time - mean_time);

[rjkroege, 2012/02/02 15:58:37]

this algorithm can be numerically unstable. See:
http://www.jstor.org/pss/2156903  -- is your matrix always well conditioned?

+  }
+
+  *x = xt / tt;
+  *y = yt / tt;
+}
+
+void VelocityCalculator::ClearHistory() {
+  index_ = 0;
+  num_valid_entries_ = 0;
+}
+
+}  // namespace aura