15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "ui/base/gestures/velocity_calculator.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace ui { 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)VelocityCalculator::VelocityCalculator(int buffer_size) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : buffer_(new Point[buffer_size]) , 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_(0), 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_valid_entries_(0), 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_size_(buffer_size), 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x_velocity_(0), 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) y_velocity_(0), 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) velocities_stale_(false) { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)VelocityCalculator::~VelocityCalculator() {} 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)float VelocityCalculator::XVelocity() { 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (velocities_stale_) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UpdateVelocity(); 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return x_velocity_; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)float VelocityCalculator::YVelocity() { 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (velocities_stale_) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UpdateVelocity(); 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return y_velocity_; 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VelocityCalculator::PointSeen(int x, int y, int64 time) { 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_[index_].x = x; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_[index_].y = y; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_[index_].time = time; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_ = (index_ + 1) % buffer_size_; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (num_valid_entries_ < buffer_size_) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++num_valid_entries_; 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) velocities_stale_ = true; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)float VelocityCalculator::VelocitySquared() { 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (velocities_stale_) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UpdateVelocity(); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return x_velocity_ * x_velocity_ + y_velocity_ * y_velocity_; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VelocityCalculator::UpdateVelocity() { 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We don't have enough data to make a good estimate of the velocity. 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (num_valid_entries_ < 2) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Where A_i = A[i] - mean(A) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // x velocity = sum_i(x_i * t_i) / sum_i(t_i * t_i) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is an Ordinary Least Squares Regression. 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) float mean_x = 0; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) float mean_y = 0; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 mean_time = 0; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < num_valid_entries_; ++i) { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mean_x += buffer_[i].x; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mean_y += buffer_[i].y; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mean_time += buffer_[i].time; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Minimize number of divides. 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const float num_valid_entries_i = 1.0f / num_valid_entries_; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) mean_x *= num_valid_entries_i; 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) mean_y *= num_valid_entries_i; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The loss in accuracy due to rounding is insignificant compared to 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the error due to the resolution of the timer. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Use integer division to avoid the cast to double, which would cause 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // VelocityCalculatorTest.IsAccurateWithLargeTimes to fail. 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) mean_time /= num_valid_entries_; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) float xt = 0; // sum_i(x_i * t_i) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) float yt = 0; // sum_i(y_i * t_i) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 tt = 0; // sum_i(t_i * t_i) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 t_i; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < num_valid_entries_; ++i) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t_i = (buffer_[i].time - mean_time); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xt += (buffer_[i].x - mean_x) * t_i; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) yt += (buffer_[i].y - mean_y) * t_i; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tt += t_i * t_i; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (tt > 0) { 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Convert time from microseconds to seconds. 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) x_velocity_ = xt / (tt / 1000000.0f); 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) y_velocity_ = yt / (tt / 1000000.0f); 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) x_velocity_ = 0.0f; 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) y_velocity_ = 0.0f; 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) velocities_stale_ = false; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void VelocityCalculator::ClearHistory() { 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_ = 0; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_valid_entries_ = 0; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x_velocity_ = 0; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) y_velocity_ = 0; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) velocities_stale_ = false; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace ui 115