1a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 2a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// found in the LICENSE file. 4a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 5a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "ui/events/gesture_detection/velocity_tracker.h" 6a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 7a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include <cmath> 8a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 9a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "base/logging.h" 10a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "ui/events/gesture_detection/motion_event.h" 11a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 12a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)using base::TimeDelta; 13a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)using base::TimeTicks; 14a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 15a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)namespace ui { 16a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 17a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Implements a particular velocity tracker algorithm. 18a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)class VelocityTrackerStrategy { 19a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) public: 20a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual ~VelocityTrackerStrategy() {} 21a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 22a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void Clear() = 0; 23a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void ClearPointers(BitSet32 id_bits) = 0; 24a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void AddMovement(const base::TimeTicks& event_time, 25a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits, 26a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position* positions) = 0; 27a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual bool GetEstimator(uint32_t id, Estimator* out_estimator) const = 0; 28a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 29a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) protected: 30a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) VelocityTrackerStrategy() {} 31a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}; 32a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 33a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)namespace { 34a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 35a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)COMPILE_ASSERT(MotionEvent::MAX_POINTER_ID < 32, max_pointer_id_too_large); 36a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 37116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Threshold between ACTION_MOVE events for determining that a pointer has 38116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// stopped moving. Some input devices do not send ACTION_MOVE events in the case 39116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// where a pointer has stopped. We need to detect this case so that we can 40116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// accurately predict the velocity after the pointer starts moving again. 41116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst int kAssumePointerMoveStoppedTimeMs = 40; 42116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 43116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Threshold between ACTION_MOVE and ACTION_{UP|POINTER_UP} events for 44116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// determining that a pointer has stopped moving. This is a larger threshold 45116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// than |kAssumePointerMoveStoppedTimeMs|, as some devices may delay synthesis 46116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// of ACTION_{UP|POINTER_UP} to reduce risk of noisy release. 47116680a4aac90f2aa7413d9095a592090648e557Ben Murdochconst int kAssumePointerUpStoppedTimeMs = 80; 48a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 49a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)struct Position { 50a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float x, y; 51a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}; 52a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 53a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)struct Estimator { 54a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) enum { MAX_DEGREE = 4 }; 55a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 56a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Estimator time base. 57a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TimeTicks time; 58a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 59a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Polynomial coefficients describing motion in X and Y. 60a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xcoeff[MAX_DEGREE + 1], ycoeff[MAX_DEGREE + 1]; 61a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 62a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Polynomial degree (number of coefficients), or zero if no information is 63a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // available. 64a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t degree; 65a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 66a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Confidence (coefficient of determination), between 0 (no fit) 67a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // and 1 (perfect fit). 68a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float confidence; 69a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 70a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) inline void Clear() { 71a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) time = TimeTicks(); 72a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) degree = 0; 73a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) confidence = 0; 74a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t i = 0; i <= MAX_DEGREE; i++) { 75a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) xcoeff[i] = 0; 76a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) ycoeff[i] = 0; 77a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 78a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 79a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}; 80a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 81a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochfloat VectorDot(const float* a, const float* b, uint32_t m) { 82a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float r = 0; 83a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) while (m--) { 84a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) r += *(a++) * *(b++); 85a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 86a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return r; 87a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 88a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 89a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochfloat VectorNorm(const float* a, uint32_t m) { 90a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float r = 0; 91a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) while (m--) { 92a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float t = *(a++); 93a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) r += t * t; 94a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 95a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return sqrtf(r); 96a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 97a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 98a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Velocity tracker algorithm based on least-squares linear regression. 99a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy { 100a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) public: 101a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) enum Weighting { 102a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // No weights applied. All data points are equally reliable. 103a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) WEIGHTING_NONE, 104a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 105a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Weight by time delta. Data points clustered together are weighted less. 106a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) WEIGHTING_DELTA, 107a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 108a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Weight such that points within a certain horizon are weighed more than 109a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // those outside of that horizon. 110a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) WEIGHTING_CENTRAL, 111a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 112a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Weight such that points older than a certain amount are weighed less. 113a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) WEIGHTING_RECENT, 114a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 115a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 116a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Number of samples to keep. 117a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) enum { HISTORY_SIZE = 20 }; 118a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 119a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Degree must be no greater than Estimator::MAX_DEGREE. 120a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) LeastSquaresVelocityTrackerStrategy(uint32_t degree, 121a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Weighting weighting = WEIGHTING_NONE); 122a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual ~LeastSquaresVelocityTrackerStrategy(); 123a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 124a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void Clear() OVERRIDE; 125a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void ClearPointers(BitSet32 id_bits) OVERRIDE; 126a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void AddMovement(const TimeTicks& event_time, 127a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits, 128a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position* positions) OVERRIDE; 129a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual bool GetEstimator(uint32_t id, 130a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator* out_estimator) const OVERRIDE; 131a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 132a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) private: 133a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Sample horizon. 134a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // We don't use too much history by default since we want to react to quick 135a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // changes in direction. 136a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch enum { HORIZON_MS = 100 }; 137a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 138a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) struct Movement { 139a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TimeTicks event_time; 140a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits; 141a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Position positions[VelocityTracker::MAX_POINTERS]; 142a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 143a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) inline const Position& GetPosition(uint32_t id) const { 144a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return positions[id_bits.get_index_of_bit(id)]; 145a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 146a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 147a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 148a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ChooseWeight(uint32_t index) const; 149a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 150a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const uint32_t degree_; 151a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Weighting weighting_; 152a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t index_; 153a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Movement movements_[HISTORY_SIZE]; 154a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}; 155a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 156a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Velocity tracker algorithm that uses an IIR filter. 157a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy { 158a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) public: 159a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Degree must be 1 or 2. 160a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) explicit IntegratingVelocityTrackerStrategy(uint32_t degree); 161a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual ~IntegratingVelocityTrackerStrategy(); 162a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 163a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void Clear() OVERRIDE; 164a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void ClearPointers(BitSet32 id_bits) OVERRIDE; 165a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual void AddMovement(const TimeTicks& event_time, 166a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits, 167a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position* positions) OVERRIDE; 168a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) virtual bool GetEstimator(uint32_t id, 169a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator* out_estimator) const OVERRIDE; 170a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 171a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) private: 172a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Current state estimate for a particular pointer. 173a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) struct State { 174a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TimeTicks update_time; 175a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t degree; 176a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 177a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xpos, xvel, xaccel; 178a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ypos, yvel, yaccel; 179a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 180a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 181a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const uint32_t degree_; 182a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 pointer_id_bits_; 183a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) State mPointerState[MotionEvent::MAX_POINTER_ID + 1]; 184a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 185a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) void InitState(State& state, 186a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TimeTicks& event_time, 187a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xpos, 188a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ypos) const; 189a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) void UpdateState(State& state, 190a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TimeTicks& event_time, 191a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xpos, 192a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ypos) const; 193a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) void PopulateEstimator(const State& state, Estimator* out_estimator) const; 194a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}; 195a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 196a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)VelocityTrackerStrategy* CreateStrategy(VelocityTracker::Strategy strategy) { 197a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) switch (strategy) { 198a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::LSQ1: 199a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeastSquaresVelocityTrackerStrategy(1); 200a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::LSQ2: 201a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeastSquaresVelocityTrackerStrategy(2); 202a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::LSQ3: 203a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeastSquaresVelocityTrackerStrategy(3); 204a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::WLSQ2_DELTA: 205a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeastSquaresVelocityTrackerStrategy( 206a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_DELTA); 207a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::WLSQ2_CENTRAL: 208a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeastSquaresVelocityTrackerStrategy( 209a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_CENTRAL); 210a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::WLSQ2_RECENT: 211a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeastSquaresVelocityTrackerStrategy( 212a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_RECENT); 213a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::INT1: 214a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new IntegratingVelocityTrackerStrategy(1); 215a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case VelocityTracker::INT2: 216a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new IntegratingVelocityTrackerStrategy(2); 217a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 218a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) NOTREACHED() << "Unrecognized velocity tracker strategy: " << strategy; 219a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return CreateStrategy(VelocityTracker::STRATEGY_DEFAULT); 220a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 221a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 222a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} // namespace 223a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 224a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// --- VelocityTracker --- 225a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 226a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)VelocityTracker::VelocityTracker() 227a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : current_pointer_id_bits_(0), 228a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) active_pointer_id_(-1), 229a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) strategy_(CreateStrategy(STRATEGY_DEFAULT)) {} 230a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 231a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)VelocityTracker::VelocityTracker(Strategy strategy) 232a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : current_pointer_id_bits_(0), 233a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) active_pointer_id_(-1), 234a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) strategy_(CreateStrategy(strategy)) {} 235a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 236a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)VelocityTracker::~VelocityTracker() {} 237a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 238a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void VelocityTracker::Clear() { 239a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) current_pointer_id_bits_.clear(); 240a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) active_pointer_id_ = -1; 241a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) strategy_->Clear(); 242a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 243a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 244a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void VelocityTracker::ClearPointers(BitSet32 id_bits) { 245a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 remaining_id_bits(current_pointer_id_bits_.value & ~id_bits.value); 246a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) current_pointer_id_bits_ = remaining_id_bits; 247a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 248a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (active_pointer_id_ >= 0 && id_bits.has_bit(active_pointer_id_)) { 249a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) active_pointer_id_ = !remaining_id_bits.is_empty() 250a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) ? remaining_id_bits.first_marked_bit() 251a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : -1; 252a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 253a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 254a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) strategy_->ClearPointers(id_bits); 255a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 256a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 257a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void VelocityTracker::AddMovement(const TimeTicks& event_time, 258a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits, 259a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position* positions) { 260a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) while (id_bits.count() > MAX_POINTERS) 261a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) id_bits.clear_last_marked_bit(); 262a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 263a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if ((current_pointer_id_bits_.value & id_bits.value) && 264116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch (event_time - last_event_time_) >= 265116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch base::TimeDelta::FromMilliseconds(kAssumePointerMoveStoppedTimeMs)) { 266116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // We have not received any movements for too long. Assume that all pointers 267a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // have stopped. 268a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) strategy_->Clear(); 269a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 270a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) last_event_time_ = event_time; 271a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 272a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) current_pointer_id_bits_ = id_bits; 273a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (active_pointer_id_ < 0 || !id_bits.has_bit(active_pointer_id_)) 274a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) active_pointer_id_ = id_bits.is_empty() ? -1 : id_bits.first_marked_bit(); 275a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 276a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) strategy_->AddMovement(event_time, id_bits, positions); 277a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 278a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 279a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void VelocityTracker::AddMovement(const MotionEvent& event) { 280a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) int32_t actionMasked = event.GetAction(); 281a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 282a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) switch (actionMasked) { 283a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case MotionEvent::ACTION_DOWN: 284a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // case MotionEvent::HOVER_ENTER: 285a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Clear all pointers on down before adding the new movement. 286a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Clear(); 287a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) break; 288a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case MotionEvent::ACTION_POINTER_DOWN: { 289a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Start a new movement trace for a pointer that just went down. 290a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // We do this on down instead of on up because the client may want to 291a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // query the final velocity for a pointer that just went up. 292a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 downIdBits; 293a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) downIdBits.mark_bit(event.GetPointerId(event.GetActionIndex())); 294a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) ClearPointers(downIdBits); 295a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) break; 296a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 297a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case MotionEvent::ACTION_MOVE: 298a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // case MotionEvent::ACTION_HOVER_MOVE: 299a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) break; 300116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch case MotionEvent::ACTION_UP: 301116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch case MotionEvent::ACTION_POINTER_UP: 302a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Note that ACTION_UP and ACTION_POINTER_UP always report the last known 303a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // position of the pointers that went up. ACTION_POINTER_UP does include 304a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // the new position of pointers that remained down but we will also 305a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // receive an ACTION_MOVE with this information if any of them actually 306a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // moved. Since we don't know how many pointers will be going up at once 307a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // it makes sense to just wait for the following ACTION_MOVE before adding 308116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // the movement. However, if the up event itself is delayed because of 309116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // (difficult albeit possible) prolonged stationary screen contact, assume 310116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // that motion has stopped. 311116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if ((event.GetEventTime() - last_event_time_) >= 312116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch base::TimeDelta::FromMilliseconds(kAssumePointerUpStoppedTimeMs)) 313116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch strategy_->Clear(); 314116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return; 315116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch default: 316116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Ignore all other actions because they do not convey any new information 317116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // about pointer movement. We also want to preserve the last known 318116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // velocity of the pointers. 319a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return; 320a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 321a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 322a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) size_t pointer_count = event.GetPointerCount(); 323a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (pointer_count > MAX_POINTERS) { 324a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) pointer_count = MAX_POINTERS; 325a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 326a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 327a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits; 328a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t i = 0; i < pointer_count; i++) { 329a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) id_bits.mark_bit(event.GetPointerId(i)); 330a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 331a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 332a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t pointer_index[MAX_POINTERS]; 333a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t i = 0; i < pointer_count; i++) { 334a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) pointer_index[i] = id_bits.get_index_of_bit(event.GetPointerId(i)); 335a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 336a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 337a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Position positions[MAX_POINTERS]; 338a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) size_t historySize = event.GetHistorySize(); 339a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t h = 0; h < historySize; h++) { 340a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t i = 0; i < pointer_count; i++) { 341a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t index = pointer_index[i]; 342a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) positions[index].x = event.GetHistoricalX(i, h); 343a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) positions[index].y = event.GetHistoricalY(i, h); 344a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 345a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) AddMovement(event.GetHistoricalEventTime(h), id_bits, positions); 346a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 347a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 348a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (size_t i = 0; i < pointer_count; i++) { 349a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t index = pointer_index[i]; 350a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) positions[index].x = event.GetX(i); 351a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) positions[index].y = event.GetY(i); 352a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 353a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) AddMovement(event.GetEventTime(), id_bits, positions); 354a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 355a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 356a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)bool VelocityTracker::GetVelocity(uint32_t id, 357a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float* out_vx, 358a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float* out_vy) const { 359a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator estimator; 360a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (GetEstimator(id, &estimator) && estimator.degree >= 1) { 361a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) *out_vx = estimator.xcoeff[1]; 362a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) *out_vy = estimator.ycoeff[1]; 363a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return true; 364a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 365a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) *out_vx = 0; 366a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) *out_vy = 0; 367a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return false; 368a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 369a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 370a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void LeastSquaresVelocityTrackerStrategy::AddMovement( 371a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TimeTicks& event_time, 372a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits, 373a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position* positions) { 374a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (++index_ == HISTORY_SIZE) { 375a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) index_ = 0; 376a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 377a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 378a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Movement& movement = movements_[index_]; 379a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movement.event_time = event_time; 380a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movement.id_bits = id_bits; 381a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t count = id_bits.count(); 382a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t i = 0; i < count; i++) { 383a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movement.positions[i] = positions[i]; 384a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 385a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 386a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 387a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)bool VelocityTracker::GetEstimator(uint32_t id, 388a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator* out_estimator) const { 389a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return strategy_->GetEstimator(id, out_estimator); 390a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 391a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 392a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// --- LeastSquaresVelocityTrackerStrategy --- 393a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 394a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy( 395a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t degree, 396a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Weighting weighting) 397a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : degree_(degree), weighting_(weighting) { 398a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::MAX_DEGREE)); 399a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Clear(); 400a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 401a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 402a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() {} 403a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 404a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void LeastSquaresVelocityTrackerStrategy::Clear() { 405a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) index_ = 0; 406a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movements_[0].id_bits.clear(); 407a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 408a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 409a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)/** 410a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Solves a linear least squares problem to obtain a N degree polynomial that 411a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * fits the specified input data as nearly as possible. 412a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 413a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns true if a solution is found, false otherwise. 414a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 415a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The input consists of two vectors of data points X and Y with indices 0..m-1 416a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * along with a weight vector W of the same size. 417a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 418a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The output is a vector B with indices 0..n that describes a polynomial 419a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * that fits the data, such the sum of W[i] * W[i] * abs(Y[i] - (B[0] + B[1] 420a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * X[i] * + B[2] X[i]^2 ... B[n] X[i]^n)) for all i between 0 and m-1 is 421a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * minimized. 422a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 423a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Accordingly, the weight vector W should be initialized by the caller with the 424a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * reciprocal square root of the variance of the error in each input data point. 425a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * In other words, an ideal choice for W would be W[i] = 1 / var(Y[i]) = 1 / 426a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * stddev(Y[i]). 427a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The weights express the relative importance of each data point. If the 428a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * weights are* all 1, then the data points are considered to be of equal 429a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * importance when fitting the polynomial. It is a good idea to choose weights 430a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * that diminish the importance of data points that may have higher than usual 431a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * error margins. 432a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 433a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Errors among data points are assumed to be independent. W is represented 434a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * here as a vector although in the literature it is typically taken to be a 435a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * diagonal matrix. 436a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 437a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * That is to say, the function that generated the input data can be 438a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * approximated by y(x) ~= B[0] + B[1] x + B[2] x^2 + ... + B[n] x^n. 439a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 440a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The coefficient of determination (R^2) is also returned to describe the 441a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * goodness of fit of the model for the given data. It is a value between 0 442a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * and 1, where 1 indicates perfect correspondence. 443a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 444a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * This function first expands the X vector to a m by n matrix A such that 445a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * A[i][0] = 1, A[i][1] = X[i], A[i][2] = X[i]^2, ..., A[i][n] = X[i]^n, then 446a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * multiplies it by w[i]./ 447a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 448a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Then it calculates the QR decomposition of A yielding an m by m orthonormal 449a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * matrix Q and an m by n upper triangular matrix R. Because R is upper 450a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * triangular (lower part is all zeroes), we can simplify the decomposition into 451a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * an m by n matrix Q1 and a n by n matrix R1 such that A = Q1 R1. 452a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 453a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Finally we solve the system of linear equations given by 454a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * R1 B = (Qtranspose W Y) to find B. 455a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 456a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * For efficiency, we lay out A and Q column-wise in memory because we 457a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * frequently operate on the column vectors. Conversely, we lay out R row-wise. 458a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * 459a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares 460a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * http://en.wikipedia.org/wiki/Gram-Schmidt 461a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 462a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)static bool SolveLeastSquares(const float* x, 463a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const float* y, 464a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const float* w, 465a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t m, 466a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t n, 467a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float* out_b, 468a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float* out_det) { 469a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // MSVC does not support variable-length arrays (used by the original Android 470a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // implementation of this function). 471a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#if defined(COMPILER_MSVC) 472a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) enum { 473a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) M_ARRAY_LENGTH = LeastSquaresVelocityTrackerStrategy::HISTORY_SIZE, 474a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) N_ARRAY_LENGTH = Estimator::MAX_DEGREE 475a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 476a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_LE(m, static_cast<uint32_t>(M_ARRAY_LENGTH)); 477a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_LE(n, static_cast<uint32_t>(N_ARRAY_LENGTH)); 478a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#else 479a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const uint32_t M_ARRAY_LENGTH = m; 480a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const uint32_t N_ARRAY_LENGTH = n; 481a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#endif 482a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 483a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Expand the X vector to a matrix A, pre-multiplied by the weights. 484a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float a[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; // column-major order 485a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 486a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) a[0][h] = w[h]; 487a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t i = 1; i < n; i++) { 488a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) a[i][h] = a[i - 1][h] * x[h]; 489a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 490a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 491a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 492a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Apply the Gram-Schmidt process to A to obtain its QR decomposition. 493a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 494a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Orthonormal basis, column-major order. 495a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float q[N_ARRAY_LENGTH][M_ARRAY_LENGTH]; 496a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Upper triangular matrix, row-major order. 497a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float r[N_ARRAY_LENGTH][N_ARRAY_LENGTH]; 498a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t j = 0; j < n; j++) { 499a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 500a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) q[j][h] = a[j][h]; 501a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 502a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t i = 0; i < j; i++) { 503a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float dot = VectorDot(&q[j][0], &q[i][0], m); 504a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 505a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) q[j][h] -= dot * q[i][h]; 506a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 507a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 508a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 509a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float norm = VectorNorm(&q[j][0], m); 510a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (norm < 0.000001f) { 511a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // vectors are linearly dependent or zero so no solution 512a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return false; 513a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 514a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 515a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float invNorm = 1.0f / norm; 516a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 517a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) q[j][h] *= invNorm; 518a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 519a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t i = 0; i < n; i++) { 520a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) r[j][i] = i < j ? 0 : VectorDot(&q[j][0], &a[i][0], m); 521a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 522a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 523a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 524a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Solve R B = Qt W Y to find B. This is easy because R is upper triangular. 525a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // We just work from bottom-right to top-left calculating B's coefficients. 526a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float wy[M_ARRAY_LENGTH]; 527a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 528a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) wy[h] = y[h] * w[h]; 529a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 530a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t i = n; i-- != 0;) { 531a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_b[i] = VectorDot(&q[i][0], wy, m); 532a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t j = n - 1; j > i; j--) { 533a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_b[i] -= r[i][j] * out_b[j]; 534a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 535a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_b[i] /= r[i][i]; 536a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 537a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 538a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Calculate the coefficient of determination as 1 - (SSerr / SStot) where 539a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // SSerr is the residual sum of squares (variance of the error), 540a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // and SStot is the total sum of squares (variance of the data) where each 541a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // has been weighted. 542a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ymean = 0; 543a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 544a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) ymean += y[h]; 545a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 546a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) ymean /= m; 547a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 548a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float sserr = 0; 549a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float sstot = 0; 550a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t h = 0; h < m; h++) { 551a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float err = y[h] - out_b[0]; 552a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float term = 1; 553a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (uint32_t i = 1; i < n; i++) { 554a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) term *= x[h]; 555a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) err -= term * out_b[i]; 556a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 557a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) sserr += w[h] * w[h] * err * err; 558a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float var = y[h] - ymean; 559a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) sstot += w[h] * w[h] * var * var; 560a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 561a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) *out_det = sstot > 0.000001f ? 1.0f - (sserr / sstot) : 1; 562a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return true; 563a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 564a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 565a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void LeastSquaresVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { 566a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 remaining_id_bits(movements_[index_].id_bits.value & ~id_bits.value); 567a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movements_[index_].id_bits = remaining_id_bits; 568a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 569a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 570a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)bool LeastSquaresVelocityTrackerStrategy::GetEstimator( 571a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t id, 572a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator* out_estimator) const { 573a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->Clear(); 574a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 575a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Iterate over movement samples in reverse time order and collect samples. 576a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float x[HISTORY_SIZE]; 577a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float y[HISTORY_SIZE]; 578a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float w[HISTORY_SIZE]; 579a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float time[HISTORY_SIZE]; 580a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t m = 0; 581a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t index = index_; 582a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(HORIZON_MS); 583a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Movement& newest_movement = movements_[index_]; 584a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) do { 585a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Movement& movement = movements_[index]; 586a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (!movement.id_bits.has_bit(id)) 587a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) break; 588a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 589a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TimeDelta age = newest_movement.event_time - movement.event_time; 590a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (age > horizon) 591a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) break; 592a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 593a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position& position = movement.GetPosition(id); 594a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) x[m] = position.x; 595a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) y[m] = position.y; 596a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) w[m] = ChooseWeight(index); 597a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) time[m] = -age.InSecondsF(); 598a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) index = (index == 0 ? HISTORY_SIZE : index) - 1; 599a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } while (++m < HISTORY_SIZE); 600a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 601a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (m == 0) 602a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return false; // no data 603a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 604a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Calculate a least squares polynomial fit. 605a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t degree = degree_; 606a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (degree > m - 1) 607a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) degree = m - 1; 608a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 609a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (degree >= 1) { 610a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xdet, ydet; 611a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t n = degree + 1; 612a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (SolveLeastSquares(time, x, w, m, n, out_estimator->xcoeff, &xdet) && 613a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) SolveLeastSquares(time, y, w, m, n, out_estimator->ycoeff, &ydet)) { 614a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->time = newest_movement.event_time; 615a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->degree = degree; 616a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->confidence = xdet * ydet; 617a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return true; 618a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 619a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 620a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 621a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // No velocity data available for this pointer, but we do have its current 622a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // position. 623a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->xcoeff[0] = x[0]; 624a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->ycoeff[0] = y[0]; 625a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->time = newest_movement.event_time; 626a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->degree = 0; 627a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->confidence = 1; 628a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return true; 629a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 630a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 631a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)float LeastSquaresVelocityTrackerStrategy::ChooseWeight(uint32_t index) const { 632a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) switch (weighting_) { 633a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case WEIGHTING_DELTA: { 634a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Weight points based on how much time elapsed between them and the next 635a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // point so that points that "cover" a shorter time span are weighed less. 636a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // delta 0ms: 0.5 637a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // delta 10ms: 1.0 638a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (index == index_) { 639a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 1.0f; 640a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 641a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t next_index = (index + 1) % HISTORY_SIZE; 642a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float delta_millis = 643a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) static_cast<float>((movements_[next_index].event_time - 644a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movements_[index].event_time).InMillisecondsF()); 645a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (delta_millis < 0) 646a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f; 647a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (delta_millis < 10) 648a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f + delta_millis * 0.05; 649a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 650a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 1.0f; 651a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 652a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 653a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case WEIGHTING_CENTRAL: { 654a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Weight points based on their age, weighing very recent and very old 655a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // points less. 656a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 0ms: 0.5 657a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 10ms: 1.0 658a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 50ms: 1.0 659a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 60ms: 0.5 660a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float age_millis = 661a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) static_cast<float>((movements_[index_].event_time - 662a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movements_[index].event_time).InMillisecondsF()); 663a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (age_millis < 0) 664a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f; 665a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (age_millis < 10) 666a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f + age_millis * 0.05; 667a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (age_millis < 50) 668a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 1.0f; 669a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (age_millis < 60) 670a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f + (60 - age_millis) * 0.05; 671a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 672a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f; 673a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 674a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 675a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case WEIGHTING_RECENT: { 676a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Weight points based on their age, weighing older points less. 677a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 0ms: 1.0 678a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 50ms: 1.0 679a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // age 100ms: 0.5 680a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float age_millis = 681a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) static_cast<float>((movements_[index_].event_time - 682a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) movements_[index].event_time).InMillisecondsF()); 683a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (age_millis < 50) { 684a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 1.0f; 685a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 686a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (age_millis < 100) { 687a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f + (100 - age_millis) * 0.01f; 688a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 689a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 0.5f; 690a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 691a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 692a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) case WEIGHTING_NONE: 693a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) default: 694a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return 1.0f; 695a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 696a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 697a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 698a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// --- IntegratingVelocityTrackerStrategy --- 699a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 700a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)IntegratingVelocityTrackerStrategy::IntegratingVelocityTrackerStrategy( 701a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t degree) 702a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) : degree_(degree) { 703a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::MAX_DEGREE)); 704a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 705a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 706a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)IntegratingVelocityTrackerStrategy::~IntegratingVelocityTrackerStrategy() {} 707a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 708a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void IntegratingVelocityTrackerStrategy::Clear() { pointer_id_bits_.clear(); } 709a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 710a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void IntegratingVelocityTrackerStrategy::ClearPointers(BitSet32 id_bits) { 711a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) pointer_id_bits_.value &= ~id_bits.value; 712a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 713a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 714a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void IntegratingVelocityTrackerStrategy::AddMovement( 715a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TimeTicks& event_time, 716a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) BitSet32 id_bits, 717a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position* positions) { 718a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t index = 0; 719a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (BitSet32 iter_id_bits(id_bits); !iter_id_bits.is_empty();) { 720a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t id = iter_id_bits.clear_first_marked_bit(); 721a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) State& state = mPointerState[id]; 722a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const Position& position = positions[index++]; 723a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (pointer_id_bits_.has_bit(id)) 724a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) UpdateState(state, event_time, position.x, position.y); 725a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) else 726a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) InitState(state, event_time, position.x, position.y); 727a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 728a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 729a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) pointer_id_bits_ = id_bits; 730a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 731a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 732a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)bool IntegratingVelocityTrackerStrategy::GetEstimator( 733a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) uint32_t id, 734a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator* out_estimator) const { 735a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->Clear(); 736a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 737a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (pointer_id_bits_.has_bit(id)) { 738a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const State& state = mPointerState[id]; 739a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) PopulateEstimator(state, out_estimator); 740a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return true; 741a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 742a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 743a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return false; 744a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 745a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 746a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void IntegratingVelocityTrackerStrategy::InitState(State& state, 747a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TimeTicks& event_time, 748a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xpos, 749a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ypos) const { 750a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.update_time = event_time; 751a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.degree = 0; 752a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xpos = xpos; 753a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xvel = 0; 754a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xaccel = 0; 755a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.ypos = ypos; 756a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yvel = 0; 757a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yaccel = 0; 758a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 759a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 760a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void IntegratingVelocityTrackerStrategy::UpdateState( 761a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) State& state, 762a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TimeTicks& event_time, 763a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xpos, 764a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float ypos) const { 765a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const base::TimeDelta MIN_TIME_DELTA = TimeDelta::FromMicroseconds(2); 766a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const float FILTER_TIME_CONSTANT = 0.010f; // 10 milliseconds 767a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 768a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (event_time <= state.update_time + MIN_TIME_DELTA) 769a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return; 770a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 771a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float dt = static_cast<float>((event_time - state.update_time).InSecondsF()); 772a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.update_time = event_time; 773a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 774a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xvel = (xpos - state.xpos) / dt; 775a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float yvel = (ypos - state.ypos) / dt; 776a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (state.degree == 0) { 777a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xvel = xvel; 778a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yvel = yvel; 779a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.degree = 1; 780a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } else { 781a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float alpha = dt / (FILTER_TIME_CONSTANT + dt); 782a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (degree_ == 1) { 783a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xvel += (xvel - state.xvel) * alpha; 784a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yvel += (yvel - state.yvel) * alpha; 785a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } else { 786a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float xaccel = (xvel - state.xvel) / dt; 787a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) float yaccel = (yvel - state.yvel) / dt; 788a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (state.degree == 1) { 789a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xaccel = xaccel; 790a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yaccel = yaccel; 791a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.degree = 2; 792a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } else { 793a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xaccel += (xaccel - state.xaccel) * alpha; 794a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yaccel += (yaccel - state.yaccel) * alpha; 795a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 796a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xvel += (state.xaccel * dt) * alpha; 797a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.yvel += (state.yaccel * dt) * alpha; 798a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 799a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 800a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.xpos = xpos; 801a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) state.ypos = ypos; 802a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 803a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 804a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void IntegratingVelocityTrackerStrategy::PopulateEstimator( 805a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const State& state, 806a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Estimator* out_estimator) const { 807a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->time = state.update_time; 808a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->confidence = 1.0f; 809a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->degree = state.degree; 810a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->xcoeff[0] = state.xpos; 811a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->xcoeff[1] = state.xvel; 812a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->xcoeff[2] = state.xaccel / 2; 813a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->ycoeff[0] = state.ypos; 814a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->ycoeff[1] = state.yvel; 815a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) out_estimator->ycoeff[2] = state.yaccel / 2; 816a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 817a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 818a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} // namespace ui 819