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