ui/events/gesture_detection/velocity_tracker.cc

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