1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "ui/events/gestures/velocity_calculator.h"
6
7namespace ui {
8
9VelocityCalculator::VelocityCalculator(int buffer_size)
10    : buffer_(new Point[buffer_size]) ,
11      index_(0),
12      num_valid_entries_(0),
13      buffer_size_(buffer_size),
14      x_velocity_(0),
15      y_velocity_(0),
16      velocities_stale_(false) {
17}
18
19VelocityCalculator::~VelocityCalculator() {}
20
21float VelocityCalculator::XVelocity() {
22  if (velocities_stale_)
23    UpdateVelocity();
24  return x_velocity_;
25}
26
27float VelocityCalculator::YVelocity() {
28  if (velocities_stale_)
29    UpdateVelocity();
30  return y_velocity_;
31}
32
33void VelocityCalculator::PointSeen(float x, float y, int64 time) {
34  buffer_[index_].x = x;
35  buffer_[index_].y = y;
36  buffer_[index_].time = time;
37
38  index_ = (index_ + 1) % buffer_size_;
39  if (num_valid_entries_ < buffer_size_)
40    ++num_valid_entries_;
41
42  velocities_stale_ = true;
43}
44
45float VelocityCalculator::VelocitySquared() {
46  if (velocities_stale_)
47    UpdateVelocity();
48  return x_velocity_ * x_velocity_ + y_velocity_ * y_velocity_;
49}
50
51void VelocityCalculator::UpdateVelocity() {
52  // We don't have enough data to make a good estimate of the velocity.
53  if (num_valid_entries_ < 2)
54    return;
55
56  // Where A_i = A[i] - mean(A)
57  // x velocity = sum_i(x_i * t_i) / sum_i(t_i * t_i)
58  // This is an Ordinary Least Squares Regression.
59
60  float mean_x = 0;
61  float mean_y = 0;
62  int64 mean_time = 0;
63
64  for (size_t i = 0; i < num_valid_entries_; ++i) {
65    mean_x += buffer_[i].x;
66    mean_y += buffer_[i].y;
67    mean_time += buffer_[i].time;
68  }
69
70  // Minimize number of divides.
71  const float num_valid_entries_i = 1.0f / num_valid_entries_;
72
73  mean_x *= num_valid_entries_i;
74  mean_y *= num_valid_entries_i;
75
76  // The loss in accuracy due to rounding is insignificant compared to
77  // the error due to the resolution of the timer.
78  // Use integer division to avoid the cast to double, which would cause
79  // VelocityCalculatorTest.IsAccurateWithLargeTimes to fail.
80  mean_time /= num_valid_entries_;
81
82  float xt = 0;  // sum_i(x_i * t_i)
83  float yt = 0;  // sum_i(y_i * t_i)
84  int64 tt = 0;  // sum_i(t_i * t_i)
85
86  int64 t_i;
87
88  for (size_t i = 0; i < num_valid_entries_; ++i) {
89    t_i = (buffer_[i].time - mean_time);
90    xt += (buffer_[i].x - mean_x) * t_i;
91    yt += (buffer_[i].y - mean_y) * t_i;
92    tt += t_i * t_i;
93  }
94
95  if (tt > 0) {
96    // Convert time from microseconds to seconds.
97    x_velocity_ = xt / (tt / 1000000.0f);
98    y_velocity_ = yt / (tt / 1000000.0f);
99  } else {
100    x_velocity_ = 0.0f;
101    y_velocity_ = 0.0f;
102  }
103  velocities_stale_ = false;
104}
105
106void VelocityCalculator::ClearHistory() {
107  index_ = 0;
108  num_valid_entries_ = 0;
109  x_velocity_ = 0;
110  y_velocity_ = 0;
111  velocities_stale_ = false;
112}
113
114}  // namespace ui
115